Navigation | TSP API | Overview | Urbi Documentation
TSP API
Maps
Search
Navigation
Urbi Pro
CityLens
Account
On‑Premise

TSP API

TSP API allows you to solve the traveling salesman problem (TSP/VRP) - building the shortest route in time or distance to pass through the specified points. You can specify one or several couriers to visit the points. If several couriers are used, the route will be divided between them in the most optimal way (some couriers can be excluded if using less couriers is more optimal for the task).

You can specify up to 200 points and up to 50 couriers for a route.

Getting an access key

To work with the API of the service, you need to get an access key:

  1. Sign in to the Platform Manager.
  2. Create a demo key or purchase an access key for using API: see the Access keys instruction.

To work with access keys, you can use the Platform Manager: for details, see the account documentation.

Task example

Deliver goods from a warehouse to five different points with the following conditions:

  • Two couriers with working time from 8:00 to 18:00 can be used.
  • Each courier can carry up to 200 units of cargo.
  • 50 units of cargo must be delivered to each point.
  • All couriers start their route from one point (warehouse).
  • Courier must spend 10 minutes in each point.
  • Two out of five points have a fixed visiting time window: from 8:00 to 10:00.

Points to visit are displayed on the map. To see parameters of each point, hover over a corresponding marker.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <title>TSP API example with multiple points</title>
    <style>
        html, body, #container {
            margin: 0;
            width: 100%;
            height: 100%;
            overflow: hidden;
        }

        #tooltip {
            padding: 10px 20px;
            background: #fff;
            box-shadow: 1px 1px 2px rgba(0, 0, 0, 0.2);
            border-radius: 4px;
            display: none;
            position: fixed;
            pointer-events: none;
        }
    </style>
</head>
<body>
    <div id="container"></div>
    <div id="tooltip"></div>
    <script src="https://mapgl.2gis.com/api/js/v1"></script>
    <script>
        const map = new mapgl.Map('container', {
            center: [55.38682572325283, 25.15852243090923],
            zoom: 10,
            key: 'Your API access key',
        });

        const tooltipEl = document.getElementById('tooltip');

        // URL to a warehouse icon
        const wareHouseIcon = 'https://docs.2gis.com/img/mapgl/point-red.svg';

        // Warehouse point marker
        const startMarker = new mapgl.Marker(map, {
            coordinates: [55.38682572325283, 25.08606896150556],
            icon: wareHouseIcon,
        });

        startMarker.on('mouseover', (event) => {
            const offset = 5;
            tooltipEl.style.top = `${event.point[1] + offset}px`;
            tooltipEl.style.left = `${event.point[0] + offset}px`;
            tooltipEl.innerHTML = '<strong>Warehouse (point 0)</strong><br/>Coordinates: 25.0860, 55.3868';
            tooltipEl.style.display = 'block';
        });

        startMarker.on('mouseout', () => {
            tooltipEl.style.display = 'none';
        });

        const markers = [
        { coordinates: [55.24949662442945, 25.183975127742627], label: '<strong>Point 1</strong><br/>Coordinates: 25.1839, 55.2494<br/>Time window: 8:00-10:00<br/>Service time: 10 mins' },
        { coordinates: [55.2934419364088, 25.241128416877118], label: '<strong>Point 2</strong><br/>Coordinates: 25.2411, 55.2934<br/>Service time: 10 mins' },
        { coordinates: [55.36759965507009, 25.183664438736898], label: '<strong>Point 3</strong><br/>Coordinates: 25.1836, 55.3675<br/>Service time: 10 mins' },
        { coordinates: [55.24983995183286, 25.123064957468117], label: '<strong>Point 4</strong><br/>Coordinates: 25.1230, 55.24983<br/>Service time: 10 mins' },
        { coordinates: [55.09950443685734, 24.990462175213693], label: '<strong>Point 5</strong><br/>Coordinates: 24.9904, 55.0995<br/>Time window: 8:00-10:00<br/>Service time: 10 mins' },
        ];

        markers.forEach((markerData) => {
            const marker = new mapgl.Marker(map, {
                coordinates: markerData.coordinates,
            });

            marker.on('mouseover', (event) => {
                const offset = 5;
                tooltipEl.style.top = `${event.point[1] + offset}px`;
                tooltipEl.style.left = `${event.point[0] + offset}px`;
                tooltipEl.innerHTML = markerData.label;
                tooltipEl.style.display = 'block';
            });

            marker.on('mouseout', () => {
                tooltipEl.style.display = 'none';
            });
        });
    </script>
</body>
</html>

TSP API solves the traveling salesman problem asynchronously. To build a route (an order of passing points), do the following:

  1. Send a request to create a route building task.
  2. Periodically check the status of the task until the route calculation is complete.
  3. Get the calculated route when the task is complete.

For more details on all parameters from the requests below, see the API Reference.

Note

TSP API finds the most optimal order of passing the given points considering all road situation features. To get a detailed driving or walking route, use Routing API after getting a solution from TSP API.

1. Creating a task

To create a task, send a POST request to the /logistics/vrp/1.1.0/create endpoint. Specify your API key as the key parameter in the query string:

https://routing.api.2gis.com/logistics/vrp/1.1.0/create?key=API_KEY

Send route point coordinates, number of couriers, and other parameters as a JSON string in the request body. For example, to define conditions from the task example:

  1. List all points to visit in the waypoints array and specify their parameters:
  • waypoint_id (required): a custom point identifier.
  • point (required): point coordinates (latitude and longitude).
  • service_time: how much time a courier must spend in the point in seconds. In the current task example - 10 minutes for all points, except for the point 0 (this point serves as a warehouse, this parameter is not considered for it).
  • time_windows: time window, during which the point is available for visits, in seconds. In the current task example only point 1 and 5 have a window between 8:00 and 10:00, other points do not limit the visiting time.
  • delivery_value: the amount of cargo to be delivered to the point. In the current task example - 50 units for all points, except for the point 0 (warehouse). For details, see the Delivering cargo section.
{
    "waypoints": [
        {
            "waypoint_id": 0,
            "point": {
                "lat": 25.08606896150556,
                "lon": 55.38682572325283
            }
        },
        {
            "waypoint_id": 1,
            "point": {
                "lat": 25.183975127742627,
                "lon": 55.24949662442945
            },
            "time_windows": [
                {
                    "start": 28800, // 8:00
                    "end": 36000 // 10:00
                }
            ],
            "service_time": 600, // 10 minutes
            "delivery_value": 50
        },
        {
            "waypoint_id": 2,
            "point": {
                "lat": 25.241128416877118,
                "lon": 55.2934419364088
            },
            "service_time": 600,
            "delivery_value": 50
        },
        {
            "waypoint_id": 3,
            "point": {
                "lat": 25.183664438736898,
                "lon": 55.36759965507009
            },
            "service_time": 600,
            "delivery_value": 50
        },
        {
            "waypoint_id": 4,
            "point": {
                "lat": 25.123064957468117,
                "lon": 55.24983995183286
            },
            "service_time": 600,
            "delivery_value": 50
        },
        {
            "waypoint_id": 5,
            "point": {
                "lat": 24.990462175213693,
                "lon": 55.09950443685734
            },
            "time_windows": [
                {
                    "start": 28800,
                    "end": 36000
                }
            ],
            "service_time": 600,
            "delivery_value": 50
        }
    ]
}
  1. List the couriers in the agents array and specify their parameters:
  • agent_id (required): a custom courier identifier.
  • start_waypoint_id (required): identifier of a starting point. In the current task example - 0 (warehouse point).
  • work_time_window: working time of the courier. In the current task example - from 8:00 to 18:00.
  • capacity: the amount of cargo the courier can carry. In the current task example - 200 units.
{
    "agents": [
        {
            "agent_id": 0,
            "start_waypoint_id": 0, // warehouse
            "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
        }
    ]
}

Request example

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": 200
    },
    {
      "agent_id": 1,
      "start_waypoint_id": 0,
      "work_time_window": {
        "start": 28800,
        "end": 64800
      },
      "capacity": 200
    }
  ],
  "waypoints": [
    {
      "waypoint_id": 0,
      "point": {
        "lat": 25.08606896150556,
        "lon": 55.38682572325283
      }
    },
    {
      "waypoint_id": 1,
      "point": {
        "lat": 25.183975127742627,
        "lon": 55.24949662442945
      },
      "time_windows": [
        {
          "start": 28800,
          "end": 36000
        }
      ],
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 2,
      "point": {
        "lat": 25.241128416877118,
        "lon": 55.2934419364088
      },
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 3,
      "point": {
        "lat": 25.183664438736898,
        "lon": 55.36759965507009
      },
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 4,
      "point": {
        "lat": 25.123064957468117,
        "lon": 55.24983995183286
      },
      "service_time": 600,
      "delivery_value": 50
    },
    {
      "waypoint_id": 5,
      "point": {
        "lat": 24.990462175213693,
        "lon": 55.09950443685734
      },
      "time_windows": [
        {
          "start": 28800,
          "end": 36000
        }
      ],
      "service_time": 600,
      "delivery_value": 50
    }
  ]
}'

The request returns information about the created task, including the task identifier (task_id), which is used to check the task status:

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

Limitations

The request will not be executed under the following conditions:

  • If the total weight of the goods to be delivered or picked up is greater than the total capacity of the agents.
  • If the agent's start or end point has been excluded.
  • If the requested execution time is not included in the working hours of the agents.

2. Checking task status

To check the status of the task, send a GET request to the /logistics/vrp/1.0/status endpoint. Specify two parameters in the query string:

  • task_id - task ID
  • key - your API key
curl --location --request GET 'https://routing.api.2gis.com/logistics/vrp/1.1.0/status?task_id=99af8aeab7ab459553fcfb7f7708dcfc&key=API_KEY'

If the task is still being processed, the request will return the same response as when the task was initially created (the status field will contain the value "Run"):

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

If the task is completed, the response body will contain the following data:

  • status: one of the following values:

    • Done - the route was successfully built.
    • Partial - the route was built, but points or agents were excluded from it.
    • Fail - an error occurred when building the route.

  • url_vrp_solution: link to a file with the solution. Available only with Done and Partial statuses.

  • url_excluded: link to a file with a list of excluded points or couriers from the route (the file can be empty if all points and couriers are used in the solution). For details, see the Excluding points and couriers section.

  • dm_queue: queue time for calculation of the reachability matrix (distances and travel time between all possible pairs of points from the task) in seconds.

  • dm: duration of reachability matrix calculation.

  • vrp: duration of the traveling salesman task calculation.

  • vrp_queue: queue time for the traveling salesman task calculation.

{
    "task_id": "99af8aeab7ab459553fcfb7f7708dcfc",
    "status": "Done",
    "urls": {
        // link to the solution file
        "url_vrp_solution": "https://disk.2gis.com/navi-docs/99af8aeab7ab459553fcfb7f7708dcfc-sln.json",
        // link to the file with the list of excluded points (this file will be empty if the task status is not "Partial")
        "url_excluded": "https://disk.2gis.com/navi-docs/99af8aeab7ab459553fcfb7f7708dcfc-excluded.json"
    },
    // time taken to build the route (see API Reference for more info)
    "dm_queue": 2,
    "dm": 3,
    "vrp": 1,
    "vrp_queue": 1
}

Solution example

Solution file contains a JSON object with a list of routes for each courier and the total travel time. For details, see the Route duration section. Solution of the current task example:

{
    "routes": [
        {
            "agent_id": 0, // courier ID
            "points": [0, 2, 1, 4, 5], // list of IDs of points for the courier to pass through
            "duration": 7366, // courier route duration in seconds
            "distance": 76781, // courier route distance in meters
            "waypoints": [
                {
                    "waypoint_id": 2, // point ID
                    "duration_waypoint": 2128, // route duration to the point
                    "distance_to_waypoint": 24718 // route distance to the point
                },
                {
                    "waypoint_id": 1,
                    "duration_waypoint": 3720,
                    "distance_to_waypoint": 36620
                },
                {
                    "waypoint_id": 4,
                    "duration_waypoint": 4971,
                    "distance_to_waypoint": 47148
                },
                {
                    "waypoint_id": 5,
                    "duration_waypoint": 7366,
                    "distance_to_waypoint": 76781
                }
            ]
        },
        {
            "agent_id": 1,
            "points": [0, 3],
            "duration": 1564,
            "distance": 15042,
            "waypoints": [
                {
                    "waypoint_id": 3,
                    "duration_waypoint": 1564,
                    "distance_to_waypoint": 15042
                }
            ]
        }
    ],
    "summary_duration": 8930, // total travel time of all couriers in seconds
    "summary_distance": 91823 // total travel distance of all couriers in meters
}

The calculated route for couriers is displayed on the map.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <title>TSP API example with multiple points</title>
    <style>
        html, body, #container {
            margin: 0;
            width: 100%;
            height: 100%;
            overflow: hidden;
        }

        #tooltip {
            padding: 10px 20px;
            background: #fff;
            box-shadow: 1px 1px 2px rgba(0, 0, 0, 0.2);
            border-radius: 4px;
            display: none;
            position: fixed;
            pointer-events: none;
        }
    </style>
</head>
<body>
    <div id="container"></div>
    <div id="tooltip"></div>
    <script src="https://mapgl.2gis.com/api/js/v1"></script>
    <script>
        const map = new mapgl.Map('container', {
            center: [55.38682572325283, 25.15852243090923],
            zoom: 10,
            key: 'Your API access key',
        });

        const tooltipEl = document.getElementById('tooltip');

        // URL to a warehouse icon
        const wareHouseIcon = 'https://docs.2gis.com/img/mapgl/point-red.svg';

        // Warehouse point marker
        const startMarker = new mapgl.Marker(map, {
            coordinates: [55.38682572325283, 25.08606896150556],
            icon: wareHouseIcon,
        });

        startMarker.on('mouseover', (event) => {
            const offset = 5;
            tooltipEl.style.top = `${event.point[1] + offset}px`;
            tooltipEl.style.left = `${event.point[0] + offset}px`;
            tooltipEl.innerHTML = '<strong>Warehouse (point 0)</strong><br/>Coordinates: 25.0860, 55.3868<br/>Agent IDs: 0, 1';
            tooltipEl.style.display = 'block';
        });

        startMarker.on('mouseout', () => {
            tooltipEl.style.display = 'none';
        });

        const markers = [
            { coordinates: [55.24949662442945, 25.183975127742627], label: '<strong>Point 1</strong><br/>Coordinates: 25.1839, 55.2494<br/>Agent ID: 1' },
            { coordinates: [55.2934419364088, 25.241128416877118], label: '<strong>Point 2</strong><br/>Coordinates: 25.2411, 55.2934<br/>Agent ID: 1' },
            { coordinates: [55.36759965507009, 25.183664438736898], label: '<strong>Point 3</strong><br/>Coordinates: 25.1836, 55.3675<br/>Agent ID: 0' },
            { coordinates: [55.24983995183286, 25.123064957468117], label: '<strong>Point 4</strong><br/>Coordinates: 25.1230, 55.24983<br/>Agent ID: 1' },
            { coordinates: [55.09950443685734, 24.990462175213693], label: '<strong>Point 5</strong><br/>Coordinates: 24.9904, 55.0995<br/>Agent ID: 1' },
            ];

        markers.forEach((markerData) => {
            const marker = new mapgl.Marker(map, {
                coordinates: markerData.coordinates,
            });

            marker.on('mouseover', (event) => {
                const offset = 5;
                tooltipEl.style.top = `${event.point[1] + offset}px`;
                tooltipEl.style.left = `${event.point[0] + offset}px`;
                tooltipEl.innerHTML = markerData.label;
                tooltipEl.style.display = 'block';
            });

            marker.on('mouseout', () => {
                tooltipEl.style.display = 'none';
            });
        });

        const polyline1 = new mapgl.Polyline(map, {
            coordinates: [
                [55.38682572325283, 25.08606896150556],
                [55.2934419364088, 25.241128416877118],
                [55.24949662442945, 25.183975127742627],
                [55.24983995183286, 25.123064957468117],
                [55.09950443685734, 24.990462175213693],
            ],
            width: 7,
            color: '#ff8c00',
        });

        const polyline2 = new mapgl.Polyline(map, {
            coordinates: [
                [55.38682572325283, 25.08606896150556],
                [55.36759965507009, 25.183664438736898],
            ],
            width: 7,
            color: '#0037ff',
        });
    </script>
</body>
</html>