Optimize multi-vehicle routes

Product Used: Route Optimization Flexible API

NextBillion.ai’s Route Optimization API provides users with a high degree of customization by leveraging over 50+ parameters to closely emulate the real-world constraints of route planning. Users can make use of vehicle specific parameters to cater specifically to solving optimization problems for multiple vehicles from a fleet.

In this example, we will set up a Route Optimization request to fulfill 5 pickup jobs and 2 shipments which need to be fulfilled using two trucks. The optimization service will then take into account all the variables specified in the input request and suggests optimal routes and task assignments to best meet the configured objectiveRoute Optimization POST request

To configure a Route Optimization request we will need to set up the locations, vehicles involved and the tasks to be performed. Let’s address them one by one below.

Configure optimization request

Locations

First we define the locations object and add all the locations used in the problem along with a valid id. Following is the locations object with all the coordinates to be used in this example:

1"locations":
2        {
3            "id": 1,
4            "location": ["34.083950,-118.318640","34.054927,-118.323726","34.075525,-118.361588","34.076350,-118.338519","34.090425,-118.338933","34.076646,-118.376969","34.094986,-118.300885","34.018780,-118.317919","33.996658,-118.261708","34.059244,-118.376969","34.057106,-118.361326"]
5        }

Jobs & Shipments

We define a bunch of tasks that need to be performed in this example. Following are the constraints that we set for these tasks:

• A unique “id” for each task
• “location_index” for each task
• Specify the schedule of tasks. This is done by adding “time_windows” within which a task must be completed.
• “skills” needed to perform each task
• “pickup” and “delivery” amounts for all tasks
• The actual time taken to complete the task once the driver/vehicle is at the task’s location i.e. the “service” time for each task.

Let’s take a look at the “jobs” and “shipments” JSONs after the above properties are configured:

1{
2 "jobs": [
3       {
4           "id": 1,
5           "location_index": 0,
6           "service": 120,
7           "pickup":[1],
8           "skills": [1],
9           "time_windows": [
10               [
11                   1693393200,
12                   1693394100
13               ]
14           ]
15       },
16       {
17           "id": 2,
18           "location_index": 1,

Vehicles

Next, we add 2 trucks that are responsible for fulfilling the above tasks which are to be performed at the locations mentioned above. To describe the trucks and their properties we add:

• A unique ID for each truck
• Truck’s or the driver’s shift timings using the “time_window” parameter
• “capacity” of the load that the truck can take
• Truck’s “depot”, if any.
• “start_index” to denote the point from where the trucks would start.
• “skills” of the driver or the vehicle to ensure appropriate tasks are only assigned to the respective truck.

Following is the vehicles JSON with all the above properties configured:

1{
2 "vehicles": [
3       {
4           "id": 1,
5           "start_index": 10,
6           "skills":[1],
7           "capacity":[10],
8           "time_window": [
9               1693382400,
10                   1693411200
11           ]
12           
13       }, {
14           "id": 2,
15           "depot": 0,
16           "skills": [2,3],
17           "capacity":[10],
18           "time_window": [

Depot

Next, we add a “depot” that we want to assign to one of the trucks. The assigned truck would start from the depot’s location. We assign an ID and a “location_index” to the depot:

1"depots": [
2       {
3           "description":"Depot 1",
4           "id":0,
5           "location_index":9
6       }
7   ]

Options

Lastly we set the optimization objective and other routing constraints for the above optimization problem. We will set the following constraints:

• “mode” option set as “truck”.
• Objective of optimization is configured to minimize the total travel distance, using the “travel_cost” attribute.
• Define the truck dimensions using the “truck_size” & “truck_weight” option.
• Configure the typical traffic conditions by providing the departure time for the trucks using “traffic_timestamp”.

Following is the “options” JSON with above properties configured:

1{
2  "options": {
3    "objective": {
4      "travel_cost": "distance"
5    },
6    "routing": {
7      "mode": "truck",
8      "truck_size": "210,210,320",
9      "truck_wieght": 12000,
10      "traffic_timestamp": 1693387800
11    }
12  }
13}

Route Optimization POST request

All the above components are now combined and submitted as a single JSON to the Route Optimization endpoint:

1curl --location 'https://api.nextbillion.io/optimization/v2?key=<your_api_key>' \
2--header 'Content-Type: application/json' \
3--data '    {
4    "description": "Test",
5     "locations":
6        {
7            "id": 1,
8            "location": ["34.083950,-118.318640","34.054927,-118.323726","34.075525,-118.361588","34.076350,-118.338519","34.090425,-118.338933","34.076646,-118.376969","34.094986,-118.300885","34.018780,-118.317919","33.996658,-118.261708","34.059244,-118.376969","34.057106,-118.361326"]
9        },
10     "jobs": [
11       {
12           "id": 1,
13           "location_index": 0,
14           "service": 120,
15           "pickup":[1],
16           "skills": [1],
17           "time_windows": [
18               [

Route Optimization POST request

Once the above POST request is successfully submitted, a response similar to the following is received:

1{
2    "id": "01c9e8ac3d2f0c070acb06ceef8017d3",
3    "message": "Optimization job created",
4    "status": "Ok"
5}

Retrieve optimization solution

Capture the task “id” from the POST response and use it in a subsequent GET request to retrieve the optimized solution asynchronously:

Route Optimization GET request

1curl --location 'https://api.nextbillion.io/optimization/v2/result?id=01c9e8ac3d2f0c070acb06ceef8017d3&key=<your_api_key>'

Route Optimization GET response

You would see the solution with all the suggested routes and the tasks that were assigned to each of the trucks.

1{
2    "description": "Test",
3    "result": {
4        "code": 0,
5        "summary": {
6            "cost": 63239,
7            "routes": 2,
8            "unassigned": 0,
9            "setup": 0,
10            "service": 600,
11            "duration": 6848,
12            "waiting_time": 15570,
13            "priority": 0,
14            "delivery": [
15                5
16            ],
17            "pickup": [
18                10

Visit Route Optimization Flexible API or Route Optimization Fast API documentations to know more about the available optimization features.