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:
- Sign in to the Platform Manager.
- 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:
- Create a route building task.
- Periodically check the status of the task until the route calculation is complete.
- 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
andtime_windows
parameters are taken into account for these points. Parameters likedelivery_value
,pickup_value
, andservice_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 IDkey
- 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:
- If the total weight of the goods to be delivered is greater than the total capacity of the agents.
- If the total weight of the goods to be loaded 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.
Advanced features
Time windows for visiting a point
Time windows are allowed time intervals for visiting a point. Two types of time windows are available:
- Hard (default): if the courier does not reach the point within the specified time interval, the point is excluded from the route calculation.
- Soft: the point is included in the route calculation even if the courier is late. The route is calculated to minimize the total delay time at the points.
You can set a time window either for a specific point (the time_windows
parameter in the waypoints
array) or for all route points at once (options
).
For soft time windows, you can set the additional time after the closing of the window: the maximum allowed delay time, after which the point is excluded from the route. If the allowed delay time for all points is set (soft_time_windows_max_delay
), the value for a specific point (max_delay
) has a higher priority. If the maximum delay time is not specified, any delay time is allowed when calculating the route.
The time is set in seconds.
If the start time of the courier (start_time
) is not specified, it is taken from the current UTC at the time of the request.
For example, set a hard time window for a point and visit it from 15:07 to 17:54:
{
"waypoints": [
{
"waypoint_id": 0,
"point": {
"lat": 54.994814,
"lon": 82.87837
},
"time_windows": [
{
"start": 54420,
"end": 64440
}
]
}
]
}
For example, set a soft time window for all route points with a maximum allowed delay time of two hours:
{
"agents": [...],
"waypoints": [...],
"options": {
"is_soft_time_windows": true,
"soft_time_windows_max_delay": 7200
}
}
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": [...],
"routing_options": {
"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": [...],
"start_time": "2020-05-15T15:52:01Z", // ...as of 15 May 2020, 15:52:01 UTC
"routing_options": {
"type": "statistics" // car route using statistical traffic data...
}
}
Shortest route in distance
To build the shortest route in distance, even if it is not the fastest one, specify the shortest
route type.
{
"waypoints": [...],
"agents": [...],
"routing_options": {
"type": "shortest"
}
}
Cargo route
To build a cargo route, use the mode
parameter with the truck
value.
{
"points": [...],
"routing_options": {
"mode": "truck" // cargo transport
}
}
Cargo parameters
To build a truck route taking into account road restrictions, you need to specify the characteristics of the cargo as the truck_params
parameter. If any characteristic is not specified, the default value will be used.
{
"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
}
}
}
For a full list of characteristics and their default values, see API Reference.
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, and exclude specific areas using the exclude
parameter. For more information on using these parameters, see the corresponding sections of Directions API.