تعریف سرویس TSP
API بهینهسازی مسیردهی TSP مپ برای حل مسئله فروشنده دورهگرد استفاده میشود. در این سرویس، الگوریتم حل مسئله به روش اکتشافی حریصانه (greedy heuristic) است. شرح مسئله فروشنده دورهگرد بدین شکل است که تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را میدانیم. مطلوب است کمهزینهترین مسیری پیدا شود که از یک شهر شروع شود، از تمامی شهرها دقیقاً یکبار عبور کند و به شهر شروع بازگردد.
نکته 🚧
مسیر بازگشتی ممکن است سریعترین مسیر ممکن نباشد.
نکته 🚧
الگوریتم TSP از نوع NP-hard است و همه مسیرهای بازگشتی در آن بهصورت تقریبی محاسبه میشوند.
نکته 🚧
تمامی نقاط باید به یکدیگر متصل باشند؛ به این معنی که راه ارتباطی میان نقاط روی زمین وجود داشته باشد.
اصطلاحات کاربردی
| ردیف | نام اصطلاح | شرح اصطلاح |
|---|---|---|
| ۱ | Geohash | فرمتی برای نگهداری دادههای جغرافیایی بهصورت فشرده |
| ۲ | Leaflet | یک کتابخانه متنباز JavaScript که بهعنوان ابزاری رایج برای ساخت و نمایش نقشه بهصورت تحت وب استفاده میشود. |
| ۳ | Front end | راهکاری برای نمایش اطلاعات از طریق یک رابط گرافیکی جهت مشاهده و تعامل کاربر با استفاده از HTML، CSS یا JavaScript |
| ۴ | Zoom Level | اندازه بزرگنمایی نقشه |
| ۵ | Lat (Latitude) | عرض جغرافیایی |
| ۶ | Lon (Longitude) | طول جغرافیایی |
ساختار استفاده و گزینههای موجود در سرویس
API بهینهسازی مسیردهی مپ بهصورت Restful توسعه داده شده است و انعطافپذیری بالایی برای انواع روشهای پیادهسازی در محیطهای مختلف دارد. برای پیادهسازی این سرویس لازم است پارامترهای زیر بهعنوان مقادیر ورودی در اختیار سرویس TSP قرار گیرند.
| گزینه | مقادیر | توضیحات | نحوه ارسال |
|---|---|---|---|
x-api-key * | API Key معتبر | کلید اختصاصی دسترسی به سرویسهای مپ | Header |
coordinates * | lon,lat;lon,lat | فهرست مختصات نقاط؛ مختصات با علامت ; از هم جدا میشوند. | Path |
roundtrip | true (پیشفرض)، false | مشخص میکند امکان بازگشت به اولین نقطه وجود داشته باشد یا خیر. | Query |
source | any (پیشفرض)، first | اگر مقدار first باشد، اولین نقطه بهعنوان نقطه شروع در نظر گرفته میشود و در غیر این صورت یک نقطه بهطور تصادفی انتخاب میشود. | Query |
destination | any (پیشفرض)، last | اگر مقدار last باشد، آخرین نقطه بهعنوان نقطه پایان در نظر گرفته میشود و در غیر این صورت یک نقطه بهطور تصادفی انتخاب میشود. | Query |
steps | true، false (پیشفرض) | گامهای هر مسیر را برمیگرداند؛ این گزینه بهصورت پیشفرض غیرفعال است. | Query |
annotations | true، false (پیشفرض)، nodes، distance، duration، datasources، weight، speed | دادههای اضافهای که در هر مسیر بازگشتی میتوان دریافت کرد. برای توضیحات بیشتر به سرویس مسیریابی مراجعه کنید. | Query |
geometries | polyline (پیشفرض)، polyline6، geojson | فرمت مسیر بازگشتی در پارامتر geometry | Query |
overview | simplified (پیشفرض)، full، false | جزئیات مسیر بازگشتی در پارامتر geometry | Query |
نکته 🚧
اگر API Key اختصاصی خود را دریافت نکردهاید، با ثبتنام در پنل مپ و ساخت یک پروژه جدید میتوانید API Key دریافت کنید.
مقادیر امکانپذیر برای حل مسئله در TSP
این سرویس برای گزینههای مختلف roundtrip، source و destination مقادیری پیشفرض در نظر گرفته است. برای مثال اگر source=first، destination=last و roundtrip=true باشد، الگوریتم توانایی حل مسئله را دارد. اگر source=any، destination=any و roundtrip=false باشد، حل مسئله امکانپذیر نیست. همه حالتها در جدول زیر آمدهاند:
| roundtrip | source | destination | امکان |
|---|---|---|---|
| true | first | last | دارد |
| true | first | any | دارد |
| true | any | last | دارد |
| true | any | any | دارد |
| false | first | last | دارد |
| false | first | any | ندارد |
| false | any | last | ندارد |
| false | any | any | ندارد |
عملکرد سرویس
این سرویس با بهینهسازی مسیردهی بین نقاط، مسیر بهینه را محاسبه و در اختیار کاربر قرار میدهد.
| سرویس | Endpoint |
|---|---|
| بهینهسازی مسیردهی (TSP) | /vrp/tsp/v1/driving/{coordinates} |
نمونه درخواست
curl --request GET \
--url 'https://map.ir/vrp/tsp/v1/driving/51.3890,35.6892;51.4200,35.7000;51.4500,35.7200?roundtrip=true&source=first&geometries=geojson' \
--header 'x-api-key: YOUR_API_KEY'خروجی سرویس
code: اگر مقدار آنOkباشد، مسیر بهدرستی پیدا شده است؛ در غیر این صورت خطایی رخ داده است.waypoints: آرایهای از قسمتهای مسیر که مقادیر زیر را دارد:trips_index: اندیس هر زیرسفر که با اندیس خود سفر همخوانی دارد.waypoint_index: اندیس هر زیرمسیر در سفر.
trips: آرایهای از مسیرهایی که پیدا شده است.
خطاهای سرویس
| توضیحات | نوع |
|---|---|
| مسیری برای سفر شما پیدا نشد. | NoTrips |
| ورودیهای شما امکانپذیر نیست. | NotImplemented |
Swagger
Postman
فایل Postman این API را با کلیک روی گزینه زیر دریافت کنید.