Optimize multi-delivery 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 emulate a variety of delivery constraints like time windows, priority, skills and many more by leveraging these parameters.

In this example, we will set up a Route Optimization request to fulfill 5 delivery jobs with the help of two vans. The optimization service will then take into account all the variables specified in the input request and return optimal routes and task assignments to meet the configured objective

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{
2 "locations": {
3 "id": 1,
4 "location": [
5 "34.083950,-118.318640",
6 "34.054927,-118.323726",
7 "34.075525,-118.361588",
8 "34.076350,-118.338519",
9 "34.090425,-118.338933",
10 "34.076646,-118.376969",
11 "34.094986,-118.300885",
12 "34.018780,-118.317919",
13 "33.996658,-118.261708",
14 "34.059244,-118.376969",
15 "34.057106,-118.361326"
16 ]
17 }
18}

Jobs & Shipments

We define a bunch of delivery jobs 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
  • “delivery” amounts for all tasks
  • The actual time taken to complete the delivery 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” JSON after the above properties are configured:

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

Depot

Next, we add a “depot” that would act as the starting point for vans. The van’s would load the required packages before starting from the depot’s location. We assign an ID and a “location_index” to the depot:

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

Vehicles

Now we add 2 delivery vans that are responsible for fulfilling the above delivery jobs. To configure the vans and their properties we add: A unique ID for each van Delivery van’s or the driver’s shift timings using the “time_window” parameter “capacity” of the load that the van can take A “depot” from which the vans would start “skills” of the drivers to ensure only the appropriate tasks are assigned to the respective van.

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

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

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 “car”.
  • Objective of optimization is configured to minimize the total travel distance, using the “travel_cost” attribute.
  • 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": "car",
8 "traffic_timestamp": 1693387800
9 }
10 }
11}

Route Optimization POST request

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

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

Route Optimization POST request

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

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

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=ec38ebf24186b6e7880bb4e2c40957be&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 vans.

1{
2 "description": "Optimize Routes",
3 "result": {
4 "code": 0,
5 "summary": {
6 "cost": 33046,
7 "routes": 2,
8 "unassigned": 0,
9 "setup": 0,
10 "service": 600,
11 "duration": 3177,
12 "waiting_time": 7654,
13 "priority": 0,
14 "delivery": [5],
15 "pickup": [0],
16 "distance": 33049
17 },
18 "routes": [

We can see that all the jobs were fulfilled within the specified time windows and by the vehicle with the right skill set only.

Visit Route Optimization Flexible API documentation to know more about the available features.