Navigation | TSP API | Overview | Urbi Documentation
TSP API
Maps
Search
Navigation
On-Premise
Urbi Pro

TSP API

TSP API allows you to solve the traveling salesman problem (TSP/VRP) - building a shortest route in time or distance to pass through the specified points. You can specify one or several couriers. When using multiple couriers, the route will be divided into several parts, and each courier will receive its own unique sub-route.

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

Getting an access key

Usage of this API requires an API key. To obtain the key:

  1. Sign in to the Platform Manager.
  2. Create a demo key (if you have not used Urbi products before) or request a production key: follow the link to contact a manager on the API Keys tab.

In the Platform Manager, you can also:

  • See information on your current keys: which services are enabled, which limit is set for each, when a key will be deactivated, and more.
  • Set restrictions for a key by HTTP headers or by IP and subnet.
  • Check the statistics of request distribution for each key.

Usage

To build a route, you need to:

  1. 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.

Creating a route building task

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

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

Route point coordinates, number of couriers and other parameters must be sent as a JSON string in the request body.

For example, to create a task of passing through five points with two couriers, send the following request:

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
      }
    }
  ]
}'

The waypoints array contains the coordinates of the points to be traversed. Additionally, you need to set a custom identifier for each point (waypoint_id) to link the points in this array with the points in the calculated route and with the points used by the couriers.

List of couriers should be specified in the agents parameter. For each courier, you need to set a custom identifier (agent_id) and specify the identifier of the starting point (start_waypoint_id). Additionally, you can specify the identifier of the point at which the courier must end their route (finish_waypoint_id).

The start and finish points do not participate in the route optimization process and act as depots:

  • Only waypoint_id and time_windows parameters are taken into account for these points. Parameters like delivery_value, pickup_value, and service_time are not considered.
  • The courier route may end up empty if no other waypoint_ids, besides the start (start_waypoint_id) and finish (finish_waypoint_id) points, were assigned to the courier. The route for this courier may be excluded from the solution file.

Above request will return information about the created task, including the task ID (task_id), which should be used to check the task status.

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

Check task status

To check the status of the task, you need to send a GET request to the /logistics/vrp/1.0/status endpoint. You need to 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 status field will contain 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.

In case of Done and Partial, the response will contain a link to the solution file with the calculated route, and the time it took to build the route. Detailed information about each field can be found in the API Reference.

{
    // task ID
    "task_id": "99af8aeab7ab459553fcfb7f7708dcfc",
    // task status
    "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 file example

Solution file contains a JSON object with a list of routes for each courier and the total travel time.

{
    "routes": [
        {
            // courier ID
            "agent_id": 0,
            // list of IDs of points for the courier to pass through
            "points": [0, 3],
            // courier route duration in seconds
            "duration": 1606,
            // courier route distance in meters
            "distance": 23678
        },
        {
            "agent_id": 1,
            "points": [1, 4, 2],
            "duration": 1283,
            "distance": 16259
        }
    ],
    // total travel time in seconds
    "summary_duration": 2889,
    // total travel distance in meters
    "summary_distance": 39937
}

Excluded points file example

The file contains a JSON object with excluded points and agents grouped by reasons.

{
    "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]
            }
        ]
    }
}

Points and agents exclusion reasons

  • route_does_not_exist — points no routes were built to;
  • failed_time — points that don't fit to agents work time;
  • failed_time_window_for_worktime — points with time windows no agent can fit;
  • failed_pickup_value — points which pickup value is more than capacity of any agent;
  • failed_delivery_value — points which delivery value is more than capacity of any agent;
  • empty_agent — agents without points.

Checks before starting the task

The request will not be executed under the following conditions:

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

Advanced features

Allowed time intervals of visiting a point

The time is set in seconds, while the courier's starting time, if not specified, is taken from the current UTC at the time of the request.

For example, visit a point from 15:07 to 17:54:

{
    "waypoints": [
        {
            "waypoint_id": 0,
            "point": {
                "lat": 54.994814,
                "lon": 82.87837
            },
            "time_windows": [
                {
                    "start": 54420,
                    "end": 64440
                }
            ]
        }
    ]
}

Work duration at the point

The length of time that the courier will spend at the point in seconds (optional).

For example, to stay at a point for 10 minutes:

{
    "waypoints": [
        {
            "waypoint_id": 0,
            "point": {
                "lat": 54.994814,
                "lon": 82.87837
            },
            "service_time": 600
        }
    ]
}

Point priority

Specify the priority parameter to build a route through the points with the highest priority. Points with low priority can also get into the route if they are close to points with high priority.

The priority parameter is specified in the range from 0 (default value, not a priority point) to 100 (maximum priority).

{
    "waypoints": [
        {
            "waypoint_id": 0,
            "point": {
                "lat": 54.994814,
                "lon": 82.87837
            },
            "priority": 100
        }
    ]
}

Working hours for the courier

The time is also set in seconds.

For example, the courier's working hours are from 14:00 to 15:00:

{
    "agents": [
        {
            "agent_id": 0,
            "start_waypoint_id": 1,
            "work_time_window": {
                "start": 50400,
                "end": 54000
            }
        }
    ]
}

Courier capacity

If you plan to build a route taking into account pickup/delivery tasks, then the courier needs to specify the capacity/workload parameter.

For example, the courier capacity is 100 units:

{
    "agents": [
        {
            "agent_id": 0,
            "start_waypoint_id": 1,
            "capacity": 100
        }
    ]
}

At the same time, it is necessary to specify the loading at each point. The loading type for all points should be the same. The loading can be either delivery_value or pickup_value.

For example, to pick up 50 units of goods from the point:

{
    "waypoints": [
        {
            "waypoint_id": 0,
            "point": {
                "lat": 54.994814,
                "lon": 82.87837
            },
            "pickup_value": 50
        }
    ]
}

If the total load of pickup_value points exceeds the total capacity of couriers, then the request is considered invalid. If the total unloading of delivery_value points exceeds the total capacity of couriers, then the request is also considered invalid.

Route types

Shortest route in time

By default, the server returns the shortest car route in time using current traffic data. To build a specific type of route, set the type parameter in the request.

{
    "waypoints": [...],
    "agents": [...],
    "type": "jam" // car route using current traffic data
}

Instead of current traffic data, you can build a route using statistical traffic data. To do this, specify the statistics route type and the required date and time in RFC 3339 format as the start_time parameter.

{
    "waypoints": [...],
    "agents": [...],
    "type": "statistics", // car route using statistical traffic data...
    "start_time": "2020-05-15T15:52:01Z"    // ...as of 15 May 2020, 15:52:01 UTC
}

Shortest route in distance

To build the shortest route in distance, even if it is not optimal due to traffic jams, specify the shortest route type.

{
    "waypoints": [...],
    "agents": [...],
    "type": "shortest" // car route ignoring traffic
}

Avoiding road types

When building a route, you can exclude certain types of roads, such as toll roads or dirt roads, using the filters parameter. For more information on using this parameter, see the corresponding section of Directions API.