TSP API
TSP API позволяет решить задачу коммивояжёра (TSP/VRP) - построить кратчайший по времени или расстоянию маршрут обхода указанных точек. Для обхода точек можно указать как одного курьера, так и нескольких. При использовании нескольких курьеров маршрут будет разбит на несколько частей и каждый курьер получит свой уникальный подмаршрут.
Для маршрута можно указать до 200 точек и до 50 курьеров.
Получение ключа доступа
Чтобы работать с API сервиса, нужно получить ключ доступа:
- Зарегистрируйтесь в личном кабинете Platform Manager.
- Создайте демо-ключ или купите ключ для доступа к API: см. инструкцию Ключи доступа.
Работать с ключами можно в личном кабинете Platform Manager: подробнее см. в разделе Platform Manager.
Использование
Чтобы построить маршрут, нужно:
- Создать задачу на построение маршрута.
- Периодически проверять статус задачи, пока не завершится расчёт маршрута.
- Получить готовый маршрут после завершения задачи.
Создание задачи на построение маршрута
Для создания задачи на построение маршрута нужно отправить 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).
Стартовая и финишная точки не участвуют в оптимизации маршрута курьера и выступают в роли склада:
- Для этих точек учитываются только параметры
waypoint_idиtime_windows. Параметрыdelivery_value,pickup_valueиservice_timeне учитываются. - Маршрут курьера может оказаться пустым, если для курьера не были определены иные
waypoint_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— агенты, для которых отсутствуют заказы.
Проверки перед стартом задачи
Запрос не будет выполнен при следующих условиях:
- Если суммарный вес грузов для доставки больше, чем суммарная вместимость агентов.
- Если суммарный вес грузов для погрузки больше, чем суммарная вместимость агентов.
- Если стартовая или конечная точка агента была исключена.
- Если время выполнения запроса не входит в рабочее время ни одного из агентов.
Расширенные возможности
Временные окна посещения точки
Временны́е окна — это допустимые временные отрезки посещения точки. Доступны два вида временных окон:
- Жёсткое (по умолчанию): если курьер не попал на точку в указанный временной отрезок, точка исключается из расчёта маршрута.
- Мягкое: точка остаётся в расчёте маршрута даже при опоздании курьера. Маршрут рассчитывается так, чтобы суммарное время опозданий в точках было минимальным.
Задать временное окно можно как для отдельной точки (параметр time_windows в массиве waypoints), так и для всех точек маршрута сразу (options).
Для мягких временных окон можно задать дополнительное время после закрытия окна: максимальное допустимое время опоздания, после которого точка исключается из маршрута. Если задано допустимое время опоздания для всех точек (soft_time_windows_max_delay), то значение для отдельной точки (max_delay) приоритетнее. Если максимальное время опоздания не указано, то при расчёте маршрута допускается любое время опоздания.
Время задается в секундах.
Если стартовое время курьера (start_time) не указано, то для этого параметра устанавливается текущее UTC на момент запроса.
Например, задать жёсткое временное окно для точки и посетить её с 15 часов 07 минут до 17 часов 54 минут:
{
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 54.994814,
"lon": 82.87837
},
"time_windows": [
{
"start": 54420,
"end": 64440
}
]
}
]
}
Например, задать мягкое временное окно для всех точек маршрута с максимальным допустимым временем опоздания в 2 часа:
{
"agents": [...],
"waypoints": [...],
"options": {
"is_soft_time_windows": true,
"soft_time_windows_max_delay": 7200
}
}
Продолжительность работ в точке
Отрезок времени, который курьер проведет в точке задается в секундах (опционально).
Например, задержаться в точке на 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": [...],
"routing_options": {
"type": "jam" // автомобильный маршрут по текущим пробкам
}
}
Вместо текущих пробок можно использовать статистическую информацию по пробкам. Для этого нужно указать тип маршрута statistics и нужную дату-время в формате RFC 3339 в поле start_time.
{
"waypoints": [...],
"agents": [...],
"start_time": "2020-05-15T15:52:01Z", // ...на 15 мая 2020 года, 15:52:01 UTC
"routing_options": {
"type": "statistics" // автомобильный маршрут на основе статистических данных по пробкам...
}
}
Кратчайший по расстоянию
Чтобы построить самый короткий маршрут, даже если он не является оптимальным по времени, нужно указать тип shortest.
{
"waypoints": [...],
"agents": [...],
"routing_options": {
"type": "shortest"
}
}
Для грузового транспорта
Чтобы построить маршрут для грузового транспорта, нужно указать параметр transport со значением truck.
{
"waypoints": [...],
"routing_options": {
"transport": "truck" // грузовой транспорт
}
}
Параметры грузового транспорта
Чтобы построить маршрут с учётом грузовых ограничений, нужно указать характеристики груза и транспорта при помощи параметра truck_params. В случае, если какая-либо характеристика не указана, будет использовано значение по умолчанию.
{
"waypoints": [...],
"routing_options": {
"transport": "truck",
"truck_params": {
"max_perm_mass": 10,
"mass": 9,
"axle_load": 4,
"height": 3.2,
"width": 2.5,
"length": 7,
"dangerous_cargo": true,
"explosive_cargo": true
}
}
}
Полный список учитываемых характеристик и значения по умолчанию можно посмотреть в Справочнике API.
Исключение типов дорог
При построении маршрута можно исключить определенные типы дорог, такие как грунтовые или платные, и указать области, которые будут избегаться. Для этого используются параметры filters и exclude. Подробнее про работу с этим параметром можно посмотреть в соответствующем разделе Directions API.