Route Optimization API V2

Introduction

Nextbillion.ai's Route Optimization API is a powerful tool that helps businesses and organizations optimize their delivery routes to maximize efficiency, save time, and reduce costs. It is designed to solve the Multi or Single Vehicle Routing Problem (VRP), which is a classic optimization problem in operations research that involves finding the optimal set of routes for a fleet of vehicles to visit a set of locations while satisfying various constraints such as time windows, capacity, and vehicle availability.

The Route Optimization API consists of two main components - the input data and the optimization engine. The input data includes information about the jobs (stops/places to visit), vehicles (delivery trucks, vans, etc.), and shipments (pickup and delivery tasks), while the optimization engine uses this data to find the most efficient set of routes for the vehicles to follow.

Using the Route Optimization API, businesses can streamline their delivery processes, reduce fuel consumption, and improve customer satisfaction by ensuring timely and accurate deliveries. With the ability to handle complex constraints and variables such as capacity, time windows, and vehicle availability, the API can be customized to meet the specific needs of any business or organization.

There are two components to 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.

What changed in V2?

We updated the route optimization service to add the following new features and other changes.

1. The request URL changes to https: //api.nextbillion.io/optimization/v2 instead of https: //api.nextbillion.io/optimise-mvrp.

2. New solutions and unassigned objects in request for re-optimization cases

3. locations object changes:

   1. A new parameter approaches is included

   2. The schema of location parameter is updated to an array of location objects in [latitude,longitude] format. It used to be pipe delimited in V1.

4. options object includes

   1. constraint object for describing soft constraints

   2. objective object to define optimization objective

   3. routing object to define routing considerations relating to truck and traffic

   4. mode parameter, which is moved into the routing object.

5. Each job can have either pickupor a delivery, not both.

6. setup time is not supported for jobs and shipments

7. vehicle.breaks allows only a single break for a vehicle

8. vehicle.start_index is a required parameter

Conventions

1. All the key/parameter does not include capital letters. If there is, please help convert it to small letters.

2. All the timestamps are UNIX in seconds and other time-related parameters units are in seconds.

3. All the distance-related parameter units are in meters.

4. A time_window object is a pair of timestamps in the form [start, end]

Object Overview

Location Object

The Locations object is used to describe the locations that will be used for route optimization. A maximum of 2k locations can be added in this object. It contains two fields- index and location.

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.

Job Object:

The Job object describes a particular job or task that needs to be completed as part of the overall optimization process. It contains various properties such as the job id, the index of the location where the job needs to be performed, the service duration for the job, multidimensional quantities for pickup and delivery, available time windows for the job, mandatory skills required for the job, the priority of the job, and a description of the job.

The Job object is used with the Locations object and the overall optimization process to determine the most efficient route for completing all the jobs in the given set. The properties of the Job object provide important information to the optimization algorithm, such as the time constraints and resource requirements for each job, which helps generate an optimized route plan.

Vehicle Object

The Vehicle object describes the characteristics and constraints of a vehicle that will be used in a multi-vehicle routing problem.

Note:

1. The users can also set a start or end location of their choice as long as it is present in the locations object. These parameters can have locations that are different from job locations.

2. In order to request a round trip, you can specify both the start_index and end_index with the same location index.

3. The Capacity parameter describes the maximum multidimensional quantities the vehicle can carry.

Optimization POST Input

Request Query

Request Body

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

Example

1curl -X POST -H "Content-Type: application/json" -d '{
2   "description": "Test",
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   "jobs": [
8       {
9           "id": 8,
10           "location_index": 0,
11           "service": 300,
12           "setup": 200,
13           "pickup": [
14               1
15           ],
16           "time_windows": [
17               [
18                   1656327600,
19                   1656342000
20               ]
21           ]
22       },
23       {
24           "id": 9,
25           "location_index": 1,
26           "service": 300,
27           "pickup": [
28               1
29           ],
30           "time_windows": [
31               [
32                   1656327600,
33                   1656332000
34               ]
35           ]
36       }, {
37           "id": 100,
38           "location_index": 3,
39           "service": 300,
40           "pickup": [
41               1
42           ],
43           "time_windows": [
44               [
45                   1656327600,
46                   1656362000
47               ]
48           ]
49       }
50   ],
51   "vehicles": [
52       {
53           "id": 1,
54           "start_index": 3,
55           "end_index": 3,
56           "capacity": [
57               46
58           ],
59           "time_window": [
60               1656327600,
61               1656372000
62           ],
63           "skills": [2, 3]
64       }, {
65           "id": 2,
66           "start_index": 1,
67           "end_index": 1,
68           "capacity": [
69               46
70           ],
71           "time_window": [
72               1656327600,
73               1656352000
74           ]
75       }
76   ],
77  "shipments": [
78  		{
79  			"pickup": {
80  				"id": 1,
81  				"service": 300,
82  				"location_index": 6,
83  				"time_windows": [[1656329600, 1656342000]]
84  			},
85  			"delivery": {
86  				"id": 1,
87  				"service": 300,
88  				"location_index": 3,
89  				"time_windows": [[1656347400, 1656352800]]
90  			},
91  			"amount": [5],
92  			"skills": [2],
93  			"priority": 100
94  		}
95  ]
96}' "https://api.nextbillion.io/optimization/v2?key=yourapikey"

The above example will return an output similar to this.

The optimization API returns two optimized routes for the routing problem containing 2 vehicles, 3 jobs, and 1 shipment.

The first optimized route involves a single vehicle starting at a location with coordinates "1.31482858,103.84503015" at 18:53 on June 27, 2022. The first job (ID=100) arrives at the same location at the same time and requires 5 minutes of service. The second job (ID=8) arrives at a different location with coordinates "1.29360227,103.80828989" at 19:15 and requires 16 minutes and 27 seconds of service, with an additional 3 minutes and 20 seconds of setup time and a 5-minute waiting time. Next, a pickup task (ID=1) occurs at a different location with coordinates "1.2996042263,103.8112802999" at 19:29, with a 22-minute and 34-second duration, and a 5-minute setup time. Finally, a delivery task (ID=1) occurs back at the initial location at 19:50, with a duration of 37 minutes and 41 seconds and a 5-minute setup time. The solution ends at this location at 19:55 PM.

The second optimized route involves a single vehicle that starts at location "1.29360227,103.8273062", services job 9 at the same location, and then ends at the same location. The vehicle arrives at the starting location at 2022-06-27 16:30, services job 9 for 5 minutes, and then ends at the same location at 2022-06-27 16:35.

Optimization POST Response

Response Schema

Example

1{
2   "id": "07932255b79d1324d11c01d440ebe79e",
3   "message": "Optimization job created",
4   "status": "Ok",
5   "warning": [
6       "location_index[2] and 4 others are unused",
7   ]
8}

Optimization GET Input

Request Query

Example

1curl https://api.nextbillion.io/optimization/v2/result?id=e218c7aad9dc86b66250cc25fca00625&key=yourapikey

Optimization GET Response

Response Schema

Example

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":[
14            3
15         ],
16         "pickup":[
17            3
18         ]
19      },
20      "unassigned":[
21         {
22            "id":1,
23            "location":[
24               1.35369921,
25               103.9554801
26            ]
27         }
28      ],
29      "routes":[
30         {
31            "vehicle":1,
32            "cost":4359,
33            "steps":[
34               {
35                  "arrival":1655693482,
36                  "duration":0,
37                  "setup":0,
38                  "service":0,
39                  "waiting_time":0,
40                  "location":[
41                     1.42495049,
42                     103.79807462
43                  ],
44                  "load":[
45                     3
46                  ]
47               },
48               {
49                  "arrival":1655694739,
50                  "duration":1257,
51                  "setup":0,
52                  "service":0,
53                  "waiting_time":0,
54                  "location":[
55                     1.35369921,
56                     103.9554801
57                  ],
58                  "id":5,
59                  "load":[
60                     0
61                  ]
62               },
63               {
64                  "arrival":1655696519,
65                  "duration":3037,
66                  "setup":0,
67                  "service":0,
68                  "waiting_time":0,
69                  "location":[
70                     1.31943721,
71                     103.74590942
72                  ],
73                  "id":2,
74                  "load":[
75                     3
76                  ]
77               },
78               {
79                  "arrival":1655697841,
80                  "duration":4359,
81                  "setup":0,
82                  "service":0,
83                  "waiting_time":0,
84                  "location":[
85                     1.42495049,
86                     103.79807462
87                  ],
88                  "load":[
89                     3
90                  ]
91               }
92            ],
93            "setup":0,
94            "service":0,
95            "duration":4359,
96            "waiting_time":0,
97            "priority":0,
98            "delivery":[
99               3
100            ],
101            "pickup":[
102               3
103            ]
104         }
105      ]
106   },
107   "status":"Ok",
108   "message":""
109}
110

Multi-Dimensional Parameters

Capacity

The Capacity parameter in the Vehicle Object is used to describe the multidimensional quantities of capacity. In this context, multi-dimension refers to the fact that a single vehicle can carry loads defined in different units. For example, a vehicle may have a capacity of 10 cubic meters for volume, 1000 kg for weight, and 6 pallets for a number of items. These are three different dimensions of capacity, and each has its own value. By specifying Capacity as an array of integers, we can provide values for each dimension of capacity that the vehicle possesses. This information is then used by the optimization algorithm to ensure that the total capacity required by all shipments assigned to the vehicle does not exceed its capacity in any of the dimensions.

Example: Let's say a construction company has a fleet of trucks that are used to transport multiple things, such as bricks, cement, and even construction workers. Each truck has a different capacity for weight, volume, and number of persons it can carry.

In this case, the capacity parameter can be used to describe the multidimensional quantities for each truck. For example, a truck may have a capacity of 100 kg weight, 10 cubic meters of volume, and can carry 5 construction workers. The capacity parameter can be defined as [100, 10, 5] to represent these values respectively.

By leveraging the capacity in multiple dimensions, the solver can optimize the job/shipment assignment to appropriate vehicles ensuring better customer service and efficient transportation.

Amount

The Amount parameter in the Shipment Object is used to describe multidimensional quantities of a shipment. The term "multi-dimensional" refers to the fact that a single shipment can have amounts defined in different units. Continuing with our example of the construction company above, let’s say a truck needs to pick up 50 kg of bricks, and 2 cubic meters of cement from a construction material supplier’s location. When defining the shipment we define this input as

1“amount”: [50,2,0]

0 for the construction worker dimension. Next, if we have another stop to pick up 3 construction worker, then we can define the amount as

1“amount”: [0,0,3]

If the other parameters, like distance, time_windows, location of other trucks etc. are favorable then these 2 pickups can be assigned to the same vehicle with “capacity”: [100,10,5] like in this example.

Amount parameter is useful for optimizing delivery routes and determining the most efficient way to transport goods based on multiple dimensions of quantity.

Skills

The Skills parameter in the Vehicles Object describes the skills that a driver or vehicle possesses in different units. The term "multi-dimension" refers to the fact that a single driver or vehicle may have different skills or abilities, each of which could be measured in different units or quantities.

For example, let's say we have a fleet of delivery vehicles. One of these vehicles may have the following skills:

1. Skill ID ‘101’: Capacity to carry 10 large boxes

2. Skill ID ‘102’: Ability to transport goods at a temperature of -10 degrees Celsius

3. Skill ID ‘103’: Ability to transport hazardous materials in a specific type of container

In this case, the Skills parameter would be set as an array of integers, with each element corresponding to a particular skill or ability. For instance, the skills parameter for the vehicle described above might be set as follows:

1"skills": [101, 102, 103]

Here, the first element (101) corresponds to the vehicle's capacity to carry 10 large boxes, the second element (102) corresponds to its ability to transport goods at a temperature of -10 degrees Celsius, and the third element (103) corresponds to its ability to transport hazardous materials in a specific type of container.

By including the Skills parameter in the routing API, users can optimize their delivery routes based on the specific skills and abilities of their drivers and vehicles, helping to ensure that each delivery is made safely and efficiently.

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 for vehicle v if 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).

3. a job with multiple skills will be assigned to vehicles matching all the skills. The job will not be assigned to vehicles with partially matching skills.

In order to ease modeling problems with no skills required, not providing the skills key defaults to providing an empty array.

Query Limits

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

2. A maximum of 2000 locations can be added to the locations object

3. Maximum value that can be provided for truck_weight is 100,000 kg.

4. Maximum dimensions for truck_size are 5000 cm for length, 1000 cm for width, 1000 cm for height.

API Error Codes