TSP API

TSP API позволяет решить задачу коммивояжёра (TSP/VRP): построить кратчайший по времени или расстоянию маршрут обхода указанных точек. Для обхода точек можно указать как одного курьера, так и нескольких. Если указано несколько курьеров, маршрут будет разделён между ними наиболее оптимальным способом (некоторые курьеры могут быть исключены, если использование меньшего числа курьеров будет более оптимально).

Для маршрута можно указать до 200 точек и до 50 курьеров.

Получение ключа доступа

Чтобы работать с API сервиса, нужно получить ключ доступа:

1. Зарегистрируйтесь в личном кабинете Менеджер Платформы.
2. Создайте демо-ключ или купите ключ для доступа к API: см. инструкцию Ключи доступа.

Работать с ключами можно в Менеджере Платформы: подробнее см. в документации личного кабинета.

Пример задачи

Доставить груз со склада до пяти разных точек со следующими условиями:

• Могут быть использованы два курьера с рабочим временем с 8:00 до 18:00.
• Каждый курьер может перевозить до 150 единиц груза.
• В каждую точку нужно доставить по 50 единиц груза.
• Все курьеры начинают путь из одной точки (склада).
• В каждой точке курьер должен провести 10 минут.
• У двух из пяти точек есть фиксированное время посещения (окно): с 8:00 до 10:00.

Точки для посещения отмечены на карте. Чтобы посмотреть параметры каждой точки, наведите курсор на соответствующий маркер.

TSP API решает задачу коммивояжёра в асинхронном режиме. Чтобы построить маршрут (последовательность прохождения точек), выполните следующие шаги:

1. Отправьте запрос, чтобы создать задачу на построение маршрута.
2. Периодически проверяйте статус задачи, пока не завершится расчёт маршрута.
3. Получите готовый маршрут после завершения задачи.

Подробнее о всех параметрах из запросов ниже см. в Справочнике API.

Примечание

TSP API предлагает наиболее оптимальный порядок прохождения указанных точек с учётом всех особенностей дорожной ситуации. Чтобы получить детальный маршрут проезда или прохода, используйте Routing API после получения решения от TSP API.

1. Создание задачи

Чтобы создать задачу на построение маршрута, отправьте 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 в теле запроса. Например, чтобы задать параметры обхода из примера задачи:

1. Перечислите все точки для посещения в массиве waypoints и укажите параметры:

   • waypoint_id (обязательный параметр): произвольный идентификатор точки.
   • point (обязательный параметр): координаты точки (ширина и долгота).
   • service_time: сколько времени курьер должен провести в точке в секундах. В текущем примере задачи — 10 минут для всех точек, кроме точки 0 (она будет выступать в роли склада, для неё этот параметр не учитывается).
   • time_windows: временное окно, когда точка доступна для посещения, в секундах. В текущем примере только точки 1 и 5 имеют окно с 8:00 до 10:00, остальные точки не ограничивают время посещения.
   • delivery_value: объём груза, который нужно доставить в точку. В текущем примере задачи — 50 единиц для всех точек, кроме точки 0 (склад). Подробнее см. в разделе Перевозка грузов.

   {
       "waypoints": [
           {
               "waypoint_id": 0,
               "point": {
                   "lat": 55.4846963066064,
                   "lon": 37.5767069795753
               }
           },
           {
               "waypoint_id": 1,
               "point": {
                   "lat": 55.7010743761165,
                   "lon": 37.53086589478259
               },
               "time_windows": [
                   {
                       "start": 28800, // 8:00
                       "end": 36000 // 10:00
                   }
               ],
               "service_time": 600, // 10 минут
               "delivery_value": 50
           },
           {
               "waypoint_id": 2,
               "point": {
                   "lat": 55.72523735978362,
                   "lon": 37.55596751554285
               },
               "service_time": 600,
               "delivery_value": 50
           },
           {
               "waypoint_id": 3,
               "point": {
                   "lat": 55.745965069946045,
                   "lon": 37.64224270924294
               },
               "service_time": 600,
               "delivery_value": 50
           },
           {
               "waypoint_id": 4,
               "point": {
                   "lat": 55.75864347204347,
                   "lon": 37.58023157392096
               },
               "service_time": 600,
               "delivery_value": 50
           },
           {
               "waypoint_id": 5,
               "point": {
                   "lat": 55.79427118434125,
                   "lon": 37.749414711518185
               },
               "time_windows": [
                   {
                       "start": 28800,
                       "end": 36000
                   }
               ],
               "service_time": 600,
               "delivery_value": 50
           }
       ]
   }
   

2. Перечислите курьеров в массиве agents и укажите параметры:

   • agent_id (обязательный параметр): произвольный идентификатор курьера.
   • start_waypoint_id (обязательный параметр): идентификатор начальной точки. В текущем примере задачи — 0 (точка склада).
   • work_time_window: рабочее время курьера в секундах. В текущем примере задачи — с 8:00 до 18:00.
   • capacity: объём груза, который может перевозить курьер. В текущем примере задачи — 150 единиц.

   {
       "agents": [
           {
               "agent_id": 0,
               "start_waypoint_id": 0, // склад
               "work_time_window": {
                   "start": 28800, // 8:00
                   "end": 64800 // 18:00
               },
               "capacity": 150
           },
           {
               "agent_id": 1,
               "start_waypoint_id": 0,
               "work_time_window": {
                   "start": 28800,
                   "end": 64800
               },
               "capacity": 150
           }
       ]
   }
   

Пример запроса

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,
      "work_time_window": {
        "start": 28800,
        "end": 64800
      },
      "capacity": 150
    },
    {
      "agent_id": 1,
      "start_waypoint_id": 0,
      "work_time_window": {
        "start": 28800,
        "end": 64800
      },
      "capacity": 150
    }
  ],
  "waypoints": [
    {
      "waypoint_id": 0,
      "point": {
        "lat": 55.4846963066064,
        "lon": 37.5767069795753
      }
    },
    {
      "waypoint_id": 1,
      "point": {
        "lat": 55.7010743761165,
        "lon": 37.53086589478259
      },
      "time_windows": [
        {
          "start": 28800,
          "end": 36000
        }
      ],
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 2,
      "point": {
        "lat": 55.72523735978362,
        "lon": 37.55596751554285
      },
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 3,
      "point": {
        "lat": 55.745965069946045,
        "lon": 37.64224270924294
      },
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 4,
      "point": {
        "lat": 55.75864347204347,
        "lon": 37.58023157392096
      },
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 5,
      "point": {
        "lat": 55.79427118434125,
        "lon": 37.749414711518185
      },
      "time_windows": [
        {
          "start": 28800,
          "end": 36000
        }
      ],
      "service_time": 600,
      "delivery_value": 50
    }
  ]
}'

Запрос вернёт информацию о созданной задаче, включая её идентификатор (task_id), который нужно будет использовать для проверки статуса:

{
    "task_id": "99af8aeab7ab459553fcfb7f7708dcfc",
    "status": "Run",
    "urls": null,
    "dm_queue": null,
    "dm": null,
    "vrp_queue": null,
    "vrp": null
}

Ограничения

Запрос не будет выполнен при следующих условиях:

• Если суммарный вес грузов для доставки или погрузки больше, чем суммарная вместимость курьеров.
• Если стартовая или конечная точка курьера была исключена из маршрута.
• Если время выполнения запроса не входит в рабочее время ни одного из курьеров.

2. Проверка статуса задачи

Чтобы проверить статус задачи, отправьте 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 — при построении маршрута возникла ошибка.

• url_vrp_solution: ссылка на файл с решением задачи. Доступно только при статусах Done и Partial.

• url_excluded: ссылка на файл со списком исключённых из маршрута точек или курьеров (файл может быть пустым, если все точки и курьеры были задействованы). Подробнее см. в разделе Исключение точек и курьеров.

• dm_queue: время ожидания расчёта матрицы достижимости (расстояний и времени в пути между всеми возможными парами точек из задачи).

• dm: время расчёта матрицы достижимости.

• vrp: время решения задачи коммивояжёра.

• vrp_queue: время ожидания решения задачи коммивояжёра.

{
    "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, 1, 2, 4], // идентификатор точек, которые посетит курьер
            "duration": 7713, // продолжительность маршрута данного курьера (в секундах)
            "distance": 45818, // протяженность маршрута данного курьера (в метрах)
            "waypoints": [
                {
                    "waypoint_id": 1, // идентификатор точки
                    "duration_waypoint": 4321, // время в пути до точки
                    "distance_to_waypoint": 33125 // протяженность пути до точки
                },
                {
                    "waypoint_id": 2,
                    "duration_waypoint": 5732,
                    "distance_to_waypoint": 38983
                },
                {
                    "waypoint_id": 4,
                    "duration_waypoint": 7713,
                    "distance_to_waypoint": 45818
                }
            ]
        },
        {
            "agent_id": 1,
            "points": [0, 3, 5],
            "duration": 6531,
            "distance": 49816,
            "waypoints": [
                {
                    "waypoint_id": 3,
                    "duration_waypoint": 4185,
                    "distance_to_waypoint": 37686
                },
                {
                    "waypoint_id": 5,
                    "duration_waypoint": 6531,
                    "distance_to_waypoint": 49816
                }
            ]
        }
    ],
    "summary_duration": 14244, // общее время в пути всех курьеров (в секундах)
    "summary_distance": 95634 // общая протяженность пути всех курьеров (в метрах)
}

Рассчитанный маршрут движения курьеров отмечен на карте.