Навигация | TSP API | Обзор | 2GIS Documentation
TSP API

TSP API

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

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

Для доступа к API нужен специальный ключ. Чтобы его получить:

  1. Зарегистрируйтесь в личном кабинете Platform Manager.
  2. Создайте демо-ключ (если вы еще не пользовались продуктами 2ГИС) или запросите боевой ключ по ссылке для связи с менеджером на вкладке Ключи API.

В личном кабинете вы также можете:

  • Просматривать информацию по своим уже созданным ключам: какие сервисы подключены, какой лимит задан по каждому из них, когда ключ будет деактивирован.
  • Задавать ограничения на ключ по HTTP-заголовкам или по IP и подсетям.
  • Изучать статистику распределения запросов по каждому ключу.

Чтобы построить маршрут, нужно:

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

Для создания задачи на построение маршрута нужно отправить 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 — агенты, для которых отсутствуют заказы.

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

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

Временны́е окна — это допустимые временные отрезки посещения точки. Доступны два вида временных окон:

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

Задать временное окно можно как для отдельной точки (параметр 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"
    }
}

Чтобы построить маршрут для грузового транспорта, нужно указать параметр mode со значением truck.

{
    "points": [...],
    "routing_options": {
        "mode": "truck" // грузовой транспорт
    }
}

Чтобы построить маршрут с учётом грузовых ограничений, нужно указать характеристики груза и транспорта при помощи параметра truck_params. В случае, если какая-либо характеристика не указана, будет использовано значение по умолчанию.

{
    "points": [...],
    "routing_options": {
        "mode": "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.