Optimization MVRP API

Introduction

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

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

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 (currently equal to duration)
  6. A "task" is either a job, a pickup or a delivery

MVRP POST

Request Parameters

Loading...

Request Body Schema

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

Loading...

Response Schema

Loading...

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.

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}

GET

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

Request Parameters

Loading...

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.

Loading...

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

Response CodeDescriptionAdditional Notes
200Normal success case.Normal success case.
400Input validation failed.Such as missing parameter or parameter with invalid value type (for example value cannot be parsed into number).
401APIKEY not supplied or invalid.-
403APIKEY is valid but does not have access to requested resources.You might be querying for a geographical region which is not valid for your account, or requesting a service which is not enabled for you.
404Requested host/path not found.This error occurs when there is a malformed host name used.
422Could not process the request.There is an underlying map issue which prevents the processing of the request.
429Too many requests.QPM reached or something like distance matrix size quota reached.
500Internal Service error.There was an internal issue with Nextbillion.ai services. You can reach out to [email protected] for an explanation.
Optimization
Navigation
DIDN'T FIND WHAT YOU LOOKING FOR?