TSP API
TSP API позволяет решить задачу коммивояжёра (TSP/VRP) - построить кратчайший по времени или расстоянию маршрут обхода указанных точек. Для обхода точек можно указать как одного курьера, так и нескольких. При использовании нескольких курьеров маршрут будет разбит на несколько частей и каждый курьер получит свой уникальный подмаршрут.
Для маршрута можно указать до 200 точек и до 50 курьеров.
Получение ключа
Для доступа к API нужен специальный ключ. Чтобы его получить, заполните форму по адресу dev.2gis.ru/order.
Использование
Чтобы построить маршрут, нужно:
- Создать задачу на построение маршрута.
- Периодически проверять статус задачи, пока не завершится расчёт маршрута.
- Получить готовый маршрут после завершения задачи.
Создание задачи на построение маршрута
Для создания задачи на построение маршрута нужно отправить POST-запрос на endpoint /logistics/vrp/1.1.0/create. В строке запроса укажите ваш ключ API в качестве значения параметра key.
https://routing.api.2gis.com/logistics/vrp/1.1.0/create?key=API_KEY
Координаты точек маршрута, количество курьеров и другие параметры нужно передать в виде JSON в теле запроса.
Например, чтобы создать задачу на обход пяти точек двумя курьерами, отправьте следующий запрос:
curl --location --request POST 'https://routing.api.2gis.com/logistics/vrp/1.1.0/create?key=API_KEY' \
--header 'Content-Type: application/json' \
--data '{
"agents": [
{
"agent_id": 0,
"start_waypoint_id": 0
},
{
"agent_id": 1,
"start_waypoint_id": 1
}
],
"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
}
}
]
}'
Массив waypoints содержит координаты точек, которые нужно обойти. Для каждой точки дополнительно нужно задать произвольный идентификатор в виде числа (waypoint_id), чтобы было удобнее связывать точки в этом массиве с точками получившегося маршрута и теми точками, которые использует курьеры.
Список курьеров нужно указать в параметре agents. Для каждого курьера нужно задать идентификатор в виде числа (agent_id) и указать идентификатор отправной точки (start_waypoint_id). Дополнительно можно указать идентификатор точки, в которой курьер должен завершить движение (finish_waypoint_id).
Запрос вернёт информацию о созданной задаче, включая её идентификатор (task_id), который нужно будет использовать для проверки статуса.
{
"task_id": "99af8aeab7ab459553fcfb7f7708dcfc",
"status": "Run",
"urls": null,
"dm_queue": null,
"dm": null,
"vrp_queue": null,
"vrp": null
}
Проверка статуса задачи
Чтобы проверить статус задачи, нужно отправить GET-запрос на endpoint /logistics/vrp/1.1.0/status. В строке запроса нужно указать два параметра:
task_id— идентификатор задачи;key— ваш ключ API.
curl --location --request GET 'https://routing.api.2gis.com/logistics/vrp/1.1.0/status?task_id=99af8aeab7ab459553fcfb7f7708dcfc&key=API_KEY'
Если задача в процессе обработки, то запрос вернёт тот же ответ, что и при создании задачи (поле status будет содержать значение "Run"):
{
"task_id": "99af8aeab7ab459553fcfb7f7708dcfc",
"status": "Run",
"urls": null,
"dm_queue": null,
"dm": null,
"vrp_queue": null,
"vrp": null
}
Если задача завершена, то поле status будет содержать одно из следующих значений:
Done— маршрут успешно построен;Partial— маршрут построен, но из него были исключены точки или агенты;Fail— при построении маршрута возникла ошибка.
В случае Done и Partial ответ будет содержать ссылку на файл с решением и время, которое было потрачено на поиск решения. Подробную информацию о каждом поле можно найти в Справочнике API.
{
"task_id": "99af8aeab7ab459553fcfb7f7708dcfc",
"status": "Done",
"urls": {
// ссылка на файл с решением
"url_vrp_solution": "https://disk.2gis.com/navi-docs/99af8aeab7ab459553fcfb7f7708dcfc-sln.json",
// ссылка на файл со списком исключенных точек (файл будет пустым, если статус задачи не "Partial")
"url_excluded": "https://disk.2gis.com/navi-docs/99af8aeab7ab459553fcfb7f7708dcfc-excluded.json"
},
// набор полей, содержащих время, потраченное на поиск решения
"dm_queue": 2,
"dm": 3,
"vrp": 1,
"vrp_queue": 1
}
Пример файла с решением
Файл с решением содержит JSON-объект, в котором указан список маршрутов для каждого курьера и общее время в пути.
{
"routes": [
{
// идентификатор курьера
"agent_id": 0,
// идентификаторы точек для обхода курьером
"points": [0, 3],
// продолжительность маршрута данного курьера (в секундах)
"duration": 1606,
// протяженность маршрута данного курьера (в метрах)
"distance": 23678
},
{
"agent_id": 1,
"points": [1, 4, 2],
"duration": 1283,
"distance": 16259
}
],
// общее время в пути всех курьеров (в секундах)
"summary_duration": 2889,
// общая протяженность пути всех курьеров (в метрах)
"summary_distance": 39937
}
Пример файла с исключёнными точками
Файл содержит 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
},
...
],
}
Приоритет точки
Укажите параметр priority, чтобы построить маршрут через точки с наибольшим приоритетом. Точки с низким приоритетом тоже могут попасть в построенный маршрут, если они близко расположены к точкам с высоким приоритетом.
Параметр priority указывается в интервале от 0 (значение по умолчанию, не приоритетная точка) до 100 (максимальный приоритет).
{
...
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 54.994814,
"lon": 82.87837
},
"priority": 100
},
...
],
}
Рабочее время для курьера
Время также задается в секундах.
Например, время работы курьера с 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 точек превышает суммарную вместимость курьеров, то запрос считается невалидным. Если суммарная разгрузка delivery_value точек превышает суммарную вместимость курьеров, то запрос считается также невалидным.
Типы маршрутов
Поддерживаются только автомобильные маршруты.
Кратчайший по времени
По умолчанию прокладывается кратчайший по времени автомобильный маршрут с учётом текущих пробок. Чтобы указать тип маршрута явно, нужно добавить в запрос поле 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" // автомобильный маршрут без учёта пробок
}
Исключение типов дорог
При построении маршрута можно исключить определенные типы дорог, такие как грунтовые или платные. Для этого используется параметр filters. Подробнее про работу с этим параметром можно посмотреть в соответствующем разделе Directions API.