Navigation | TSP API | Overview | Urbi Documentation
TSP API

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.

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.

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.

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
}

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

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]
            }
        ]
    }
}
  • 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.

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.

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

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

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

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

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.

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

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

To build a cargo route, use the mode parameter with the truck value.

{
    "points": [...],
    "routing_options": {
        "mode": "truck" // cargo transport
    }
}

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.

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.