TSP API
TSP API позволяет решить задачу коммивояжёра (TSP/VRP) - построить кратчайший по времени или расстоянию маршрут обхода указанных точек. Для обхода точек можно указать как одного курьера, так и нескольких. При использовании нескольких курьеров маршрут будет разбит на несколько частей и каждый курьер получит свой уникальный подмаршрут.
Для маршрута можно указать до 4000 точек и до 200 курьеров.
Получение ключа
Для доступа к API нужен специальный ключ. Чтобы его получить, заполните форму по адресу dev.2gis.ru/order.
Использование
Чтобы построить маршрут, нужно:
- Создать задачу на построение маршрута.
- Периодически проверять статус задачи, пока не завершится расчёт маршрута.
- Получить готовый маршрут после завершения задачи.
Создание задачи на построение маршрута
Для создания задачи на построение маршрута нужно отправить POST-запрос на endpoint /logistics/vrp/1.0/create. В строке запроса укажите ваш ключ API в качестве значения параметра key.
https://routing.api.2gis.com/logistics/vrp/1.0/create?key=API_KEY
Координаты точек маршрута, количество курьеров и другие параметры нужно передать в виде JSON в теле запроса.
Например, чтобы создать задачу на обход шести точек двумя курьерами, можно отправить следующий запрос:
curl --request POST \
--url "https://routing.api.2gis.com/logistics/vrp/1.0/create?key=API_KEY" \
--header 'Content-Type: application/json' \
--data '{
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 55.72011298880675,
"lon": 37.4449720376539
}
},
{
"waypoint_id": 1,
"point": {
"lat": 55.76851601909724,
"lon": 37.86501600000758
}
},
{
"waypoint_id": 2,
"point": {
"lat": 55.7085452,
"lon": 37.9031455
}
},
{
"waypoint_id": 3,
"point": {
"lat": 55.622219,
"lon": 37.608992
}
},
{
"waypoint_id": 4,
"point": {
"lat": 55.76565171838069,
"lon": 37.83871081320576
}
},
{
"waypoint_id": 5,
"point": {
"lat": 55.73938281238814,
"lon": 37.48333351388388
}
}
],
"agents": [
{
"agent_id": 0,
"start_waypoint_id": 0
},
{
"agent_id": 1,
"start_waypoint_id": 1
}
]
}'
Массив waypoints содержит координаты точек, которые нужно обойти. Для каждой точки дополнительно нужно задать произвольный идентификатор в виде числа (waypoint_id), чтобы было удобнее связывать точки в этом массиве с точками получившегося маршрута и теми точками, которые использует курьеры.
Список курьеров нужно указать в параметре agents. Для каждого курьера нужно задать идентификатор в виде числа (agent_id) и указать идентификатор отправной точки (start_waypoint_id). Дополнительно можно указать идентификатор точки, в которой курьер должен завершить движение (finish_waypoint_id).
Запрос вернёт информацию о созданной задаче, включая её идентификатор (task_id), который нужно будет использовать для проверки статуса.
{
"task_id": "6ed002c93b5a5f6fe76d849fcff792ad",
"status": "Run",
"urls": null,
"dm_queue": null,
"dm": null,
"vrp_queue": null,
"vrp": null
}
Проверка статуса задачи
Чтобы проверить статус задачи, нужно отправить GET-запрос на endpoint /logistics/vrp/1.0/status. В строке запроса нужно указать два параметра:
task_id- идентификатор задачи;key- ваш ключ API.
curl --request GET "http://routing.api.2gis.com/logistics/vrp/1.0/status?key=API_KEY&task_id=6ed002c93b5a5f6fe76d849fcff792ad"
Если задача в процессе обработки, то запрос вернёт тот же ответ, что и при создании задачи (поле status будет содержать значение "Run"):
{
"task_id": "6ed002c93b5a5f6fe76d849fcff792ad",
"status": "Run",
"urls": null,
"dm_queue": null,
"dm": null,
"vrp_queue": null,
"vrp": null
}
Если задача завершена, то поле status будет содержать одно из следующих значений:
Done- маршрут успешно построен;Partial- маршрут построен, но из него были исключены точки или агенты;Fail- при построении маршрута возникла ошибка.
В случае Done и Partial ответ будет содержать ссылку на файл с решением и время, которое было потрачено на поиск решения. Подробную информацию о каждом поле можно найти в Справочнике API.
{
// идентификатор задачи
"task_id": "6ed002c93b5a5f6fe76d849fcff792ad",
// статус задачи
"status": "Done",
"urls": {
// ссылка на файл с решением
"url_vrp_solution": "http://s3.2gis.one/navi-vrp-bucket/6ed002c93b5a5f6fe76d849fcff792ad-sln.json",
// ссылка на файл со списком исключенных точек (файл будет пустым, если статус задачи не "Partial")
"url_excluded": "http://s3.2gis.one/navi-vrp-bucket/6ed002c93b5a5f6fe76d849fcff792ad-excluded.json"
},
// набор полей, содержащих время, потраченное на поиск решения
"dm_queue": 1,
"dm": 4,
"vrp_queue": 1,
"vrp": 1
}
Пример файла с решением
Файл с решением содержит JSON-объект, в котором указан список маршрутов для каждого курьера и общее время в пути.
{
"routes": [
{
// идентификатор курьера
"agent_id": 0,
// идентификаторы точек для обхода курьером
"points": [0, 5, 3],
// продолжительность маршрута данного курьера (в секундах)
"duration": 2720,
// протяженность маршрута данного курьера (в метрах)
"distance": 27252
},
{
"agent_id": 1,
"duration": 1734,
"points": [1, 4, 2],
"distance": 16243
}
],
// общее время в пути всех курьеров (в секундах)
"summary_duration": 4454,
// общая протяженность пути всех курьеров (в метрах)
"summary_distance": 43495
}
Пример файла с исключёнными точками
Файл содержит JSON-объект, в котором указаны исключенные точки и агенты, сгруппированные по причинам.
{
"excluded_waypoints": {
"count_waypoints": 9,
"reasons": [
{
"reason": "route_does_not_exist",
"count": 2,
"waypoints": [16, 18]
},
{
"reason": "failed_time",
"count": 1,
"waypoints": [7]
},
{
"reason": "failed_time_window_for_worktime",
"count": 3,
"waypoints": [5, 10, 12]
},
{
"reason": "failed_pickup_value",
"count": 1,
"waypoints": [8]
},
{
"reason": "failed_delivery_value",
"count": 2,
"waypoints": [2, 13]
}
]
},
"excluded_agents": {
"count_agents": 2,
"reasons": [
{
"reason": "empty_agent",
"count": 2,
"agents": [1, 4]
}
]
}
}
Причины исключения точек и агентов
route_does_not_exist- точки, до которых невозможно построить маршрут;failed_time- точки, которые не успевает посетить агент;failed_time_window_for_worktime- точки, у которых временное окно не совпадает с расписанием любого из агентов;failed_pickup_value- точки, у которых объем груза для погрузки больше вместимости любого из агентов;failed_delivery_value- точки, у которых объем груза для доставки больше вместимости любого из агентов;empty_agent- агенты, для которых отсутствуют заказы.
Проверки перед стартом задачи
Запрос не будет выполнен при следующих условиях:
- Если суммарный вес грузов для доставки больше, чем суммарная вместимость агентов.
- Если суммарный вес грузов для погрузки больше, чем суммарная вместимость агентов.
- Если стартовая или конечная точка агента была исключена.
- Если время выполнения запроса не входит в рабочее время ни одного из агентов.
Расширенные возможности
Допустимые временные отрезки посещения точки
Время задается в секундах, при этом стартовое время курьера, если не указано, берется текущее UTC на момент запроса. Пример (посетить точку с 15 часов 07 минут до 17 часов 54 минут):
{
...
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 54.994814,
"lon": 82.87837
},
"time_windows": [
{
"start": 54420,
"end": 64440
}
]
},
...
],
}
Продолжительность работ в точке
Отрезок времени, который курьер проведет в точке задается в секундах, поле опционально. Пример (задержаться в точке на 10 минут):
{
...
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 54.994814,
"lon": 82.87837
},
"service_time": 600
},
...
],
}
Рабочее время для курьера
Время также задается в секундах. Пример (время работы курьера с 14:00 до 15:00):
{
...
"agents": [
{
"agent_id": 0,
"start_waypoint_id": 1,
"work_time_window": {
"start": 50400,
"end": 54000
}
}
],
}
Вместимость курьера
Если планируется строить маршрут с учетом pickup/delivery задач, то курьеру нужно укзать параметр вместимости/загруженности,
пример (вместимость курьера 100 единиц):
{
...
"agents": [
{
"agent_id": 0,
"start_waypoint_id": 1,
"capacity": 100
}
],
}
При этом необходимо в каждой точке указать загрузку этой точки. Тип загрузки для всех точек должен быть одинаков.
Загрузка может быть либо delivery_value либо pickup_value.
Пример (забрать с точки 50 единиц товара):
{
...
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 54.994814,
"lon": 82.87837
},
"pickup_value": 50
},
...
],
}
Если суммарная загрузка (pickup_value) точек превышает суммарное capacity курьеров, то запрос считается невалидным. Если суммарная разгрузка (delivery_value) точек превышает суммарное capacity курьеров, то запрос считается невалидным.
Типы маршрутов
Кратчайший по времени
По умолчанию прокладывается кратчайший по времени автомобильный маршрут с учётом текущих пробок. Чтобы указать тип маршрута явно, нужно добавить в запрос поле type.
{
"waypoints": [...],
"agents": [...],
"type": "jam" // автомобильный маршрут по текущим пробкам
}
Вместо текущих пробок можно использовать статистическую информацию по пробкам. Для этого нужно указать тип маршрута statistics и нужную дату-время в формате RFC 3339 в поле start_time.
{
"waypoints": [...],
"agents": [...],
"type": "statistics", // автомобильный маршрут на основе статистических данных по пробкам...
"start_time": "2020-05-15T15:52:01Z" // ...на 15 мая 2020 года, 15:52:01 UTC
}
Кратчайший по расстоянию
Чтобы построить самый короткий маршрут, даже если он не является оптимальным по времени из-за пробок, нужно указать тип shortest.
{
"waypoints": [...],
"agents": [...],
"type": "shortest" // автомобильный маршрут без учёта пробок
}
С учётом полос общественного транспорта
Также можно строить маршруты с учётом полос общественного транспорта (удобно для такси и автобусов). Для этого нужно добавить в запрос поле mode со значением taxi.
{
"waypoints": [...],
"agents": [...],
"mode": "taxi", // автомобильный маршрут, включающий полосы общественного транспорта...
"type": "shortest" // ...без учёта пробок
}
Пешеходный
Чтобы проложить пешеходный маршрут, нужно указать параметр mode со значением walking.
{
"waypoints": [...],
"agents": [...],
"mode": "walking" // пешеходный маршрут
}
Велосипедный
Чтобы проложить велосипедный маршрут, нужно указать параметр mode со значением bicycle.
{
"waypoints": [...],
"agents": [...],
"mode": "bicycle" // велосипедный маршрут
}
Исключение типов дорог
При построении маршрута можно исключить определенные типы дорог, такие как грунтовые или платные. Для этого используется параметр filters. Подробнее про работу с этим параметром можно посмотреть в соответствующем разделе Directions API.