Route Optimization API

Introduction

Nextbillion.ai’s Route Optimization API solves for the optimization of a Multi(or single) vehicle routing problem. There are two components to the API

1. Optimization Post - Use this method to submit the input for your VRP.
2. Optimization GET - Retrieve the status of a submitted VRP using a unique reference ID.

Route Optimization

Tutorials

To see all tutorials related to the Route Optimization API, use the filter on our Tutorials page

General Notes:

1. The expected order for all coordinates arrays is [lat, lon]
2. All the timestamps are UNIX timestamps in seconds and other time-related parameters’ units are in seconds.
3. All the distance-related parameter’s units are in metres.
4. A time_window object is a pair of Unix epoch timestamps in the form [start, end].
5. Cost values in output are the one used in the optimization objective.
6. A "task" is either a job, a pickup or a delivery
7. Each depot will be assumed to have infinite inventory
8. Each vehicle can be assigned to one depot only

Optimisation POST

Request Parameters

Request Body Schema

You can choose to use either one of Jobs and Shipments or use both of them.

Response Schema

Notes

How to use the location object and using index values

1. The location object contains a list of coordinates in [lat, lon] format. Other properties in the request will refer to coordinates specified in the location object via their index parameter. An example of a location object can be understood via the following table
2. "Location" : "51.388997,-0.119022 | 51.391915,-0.103666 | 51.369777,-0.10438 | 51.365014,-0.105654 | 51.351818,-0.014773"

   Index	Location
   0	51.388997,-0.119022
   1	51.391915,-0.103666
   2	51.369777,-0.10438
   3	51.365014,-0.105654
   4	51.351818,-0.014773

3. So for example, if in the "vehicles" property, the start_index parameter is set to 2, then the starting coordinate for that vehicle is 51.369777,-0.10438 as per the above table.

Vehicles locations

1. The optional parameter start_index can be used to specify the starting location of the vehicle. If this is not used, the resulting route will start at the first visited task, whose choice is determined by the optimization process.
2. The optional parameter end_index in vehicles object, can be used to specify the ending location of the vehicle. If not used, the resulting route will end at the last visited task, whose choice is determined by the optimization process.
3. You can also set a start or end location of your choice as long as it is present in the locations object. Both of these parameters can have locations which are different from job locations.
4. In order to request a round trip, you can specify both start_index and end_index with the same location index.

Capacity restrictions

1. Use amounts (capacity for vehicles, delivery and pickup for jobs, amount for shipments) to describe a problem with capacity restrictions. Those arrays can be used to model custom restrictions for several metrics at once, e.g. number of items, weight, volume etc.
2. A vehicle is only allowed to serve a set of tasks if the resulting load at each route step is lower than the matching value in capacity for each metric. When using multiple components for amounts, it is recommended to put the most important/limiting metrics first.
3. It is assumed that all delivery-related amounts for jobs are loaded at vehicle start, while all pickup-related amounts for jobs are brought back at vehicle end.
4. All capacity values are integers. It is recommended that the user should convert any non-integer values rounded up to the nearest integer. For example, if a shipment has a weight of 14.57 kg, it is recommended to use 15 in the capacity property.

Skills Restrictions

Use skills to describe a problem where not all tasks can be served by all vehicles. Job skills are mandatory, i.e. a job can only be served by a vehicle that has all its required skills. In other words: job j is eligible to vehicle v iff j.skills is included in v.skills.

This definition implies in particular that:

1. a task without skills can be served by any vehicle;
2. a vehicle without skills can only serve tasks with no particular need (i.e. without skills as well).

In order to ease modelling problems with no skills required, not providing a skills key default to providing an empty array.

Task setup & service times

Setup times serve as a means to describe the time it takes to get started for tasks at a given location. This models a duration that should not be re-applied for other tasks following at the same place.

Service times on the other hand are the times needed for performing services. If for example, a location has 3 different tasks to be completed, each tasks might have a different service duration.

So the total "action time" for a task is setup + service upon arriving at a new location or service only if performing a new task at the previous vehicle location.

Depots

Depots are congregation points for vehicles. A Depot can contain multiple vehicles. It has the following key features.

1. Usually if a depot is defined, it will serve as the starting point for the vehicle.
2. There is no restriction on the number of vehicles a depot can contain.
3. One vehicle can only have one depot.
4. If the depot attribute is set for a vehicle, the start_index of a vehicle will need to be set to the location index set by the depot attribute. As an alternative, you can simply not set the start_index and internally, it will be set to the depot location.
5. If the depot attribute is set for a vehicle, and end_index is not set, the end location for the vehicle will be set to the depot’s location_index.

Examples

Post API Request

1https://api.nextbillion.io/optimise-mvrp?key=<NB_API_Key>

POST Request Body Schema

1// Content type: application/json
2{
3  "locations": {
4    "id": 2,
5    "location": "1.29360227,103.80828989|1.29360227,103.8273062|1.30227739,103.84595327|1.31482858,103.84503015|1.31925839,103.86312334|1.3248957169,103.8285176106|1.2996042263,103.8112802999|1.2830643677,103.8343527086|1.2856021297,103.8384649827"
6  },
7  "description": "Test shipments",
8  "jobs": [
9    {
10      "id": 8,
11      "location_index": 0,
12      "service": 300,
13      "delivery": [1],
14      "setup": 200,
15      "pickup": [1],
16      "time_windows": [[1656327600, 1656342000]]
17    },
18    {
19      "id": 9,
20      "location_index": 1,
21      "service": 300,
22      "delivery": [1],
23      "pickup": [1],
24      "time_windows": [[1656327600, 1656332000]]
25    },
26    {
27      "id": 100,
28      "location_index": 3,
29      "service": 300,
30      "delivery": [1],
31      "pickup": [1],
32      "time_windows": [[1656327600, 1656362000]]
33    }
34  ],
35  "vehicles": [
36    {
37      "id": 1,
38      "start_index": 3,
39      "end_index": 3,
40      "capacity": [46],
41      "time_window": [1656327600, 1656372000],
42      "skills": [2, 3]
43    },
44    {
45      "id": 2,
46      "start_index": 1,
47      "end_index": 1,
48      "capacity": [46],
49      "time_window": [1656327600, 1656352000]
50    }
51  ],
52  "shipments": [
53    {
54      "pickup": {
55        "id": 1,
56        "service": 300,
57        "location_index": 6,
58        "time_windows": [[1656329600, 1656342000]]
59      },
60      "delivery": {
61        "id": 1,
62        "service": 300,
63        "location_index": 3,
64        "time_windows": [[1656339600, 1656352000]]
65      },
66      "amount": [5],
67      "skills": [2],
68      "priority": 100
69    }
70  ]
71}

Post API Response

1{
2  "Id": "28e01d91jfroht8g7dfuid2298313582",
3  "message": "Optimisation job created",
4  "status": "Ok"
5}

Optimization GET

The GET request is used to retrieve the status of a previously submitted VRP using a reference identifier.

Request Parameters

Response Schema

Note: Square brackets [] represent a conditional response, i.e. it depends on specific conditions being met. For example, violations object only gets returned IF a violation occurs.

Examples

Example GET Request

1https://api.nextbillion.io/optimise-mvrp/result?key=<NBAI API Key>&id=<uniqueJobId>

Example GET Response

1{
2  "result": {
3    "code": 0,
4    "summary": {
5      "cost": 4359,
6      "routes": 1,
7      "unassigned": 1,
8      "setup": 0,
9      "service": 0,
10      "duration": 4359,
11      "waiting_time": 0,
12      "priority": 0,
13      "delivery": [3],
14      "pickup": [3]
15    },
16    "unassigned": [
17      {
18        "id": 1,
19        "location": [1.35369921, 103.9554801]
20      }
21    ],
22    "routes": [
23      {
24        "vehicle": 1,
25        "cost": 4359,
26        "steps": [
27          {
28            "arrival": 1655693482,
29            "duration": 0,
30            "setup": 0,
31            "service": 0,
32            "waiting_time": 0,
33            "location": [1.42495049, 103.79807462],
34            "load": [3]
35          },
36          {
37            "arrival": 1655694739,
38            "duration": 1257,
39            "setup": 0,
40            "service": 0,
41            "waiting_time": 0,
42            "location": [1.35369921, 103.9554801],
43            "id": 5,
44            "load": [0]
45          },
46          {
47            "arrival": 1655696519,
48            "duration": 3037,
49            "setup": 0,
50            "service": 0,
51            "waiting_time": 0,
52            "location": [1.31943721, 103.74590942],
53            "id": 2,
54            "load": [3]
55          },
56          {
57            "arrival": 1655697841,
58            "duration": 4359,
59            "setup": 0,
60            "service": 0,
61            "waiting_time": 0,
62            "location": [1.42495049, 103.79807462],
63            "load": [3]
64          }
65        ],
66        "setup": 0,
67        "service": 0,
68        "duration": 4359,
69        "waiting_time": 0,
70        "priority": 0,
71        "delivery": [3],
72        "pickup": [3]
73      }
74    ]
75  },
76  "status": "Ok",
77  "message": ""
78}

Query Limits

Nextbillion.ai allows a maximum rate limit of 6000 queries per minute or 100 queries/second for continuous requests.

Note: We can increase the quota if needed on request. Contact [email protected] for more details.

API Error Codes