Custom Duration & Distance Matrix

Users can leverage the modular nature of NextBillion.ai’s Route Optimization by configuring custom distance values when a vehicle goes from one location to another. These values then override the distances suggested by the optimization engine and are used for all distance related calculations during the process. Custom distance and duration matrices give the users a strong control over the routes that the algorithm prefers eventually in the final solution. Consequently, optimization engine’s modular implementation allows users to modify its algorithm to achieve a fairly customized solution, fulfilling even some niche business objectives. In the following example we will take a set of locations, tasks and a vehicle to bring out the impact of this powerful feature.

Setup

We will take a set of 3 delivery tasks and a single vehicle to fulfill them. We also provide the custom distance and duration matrices and set some We will define the locations, jobs, vehicles, custom distance and duration matrix and options attributes one by one.

Locations

We start by adding all the delivery locations as well as the vehicle’s starting position.

1
{
2
    "locations": [...]
3
}

Jobs

Next we configure each of the 4 delivery tasks. For each task we add:

• A unique identifier
• Location index
• Delivery quantity
• A time window within which the delivery is to be completed
• A service time to carry out the delivery

Following is the jobs JSON used in the example

1
{
2
    "jobs": [...]
3
}

Vehicles

Next, we add the details of the vehicle that will be responsible for fulfilling these deliveries. For the vehicle we specify:

• A unique ID
• start_index to denote the point from which the vehicle starts its trip.
• capacity of the vehicle

Once the vehicle and their properties are defined, the resulting vehicles JSON is:

1
"vehicles": [
2
       {
3
           "id": "Vehicle 1",
4
           "start_index": 3,
5
           "capacity": [10]
6
       }
7
   ]

Custom Distance Matrix

Next we come to the custom distance matrix attribute where we provide the distances, in meters, for traveling from one location to all the others. Consequently, the resultant matrix would always be a N X N two-dimensional matrix where N is the total number of unique location coordinates involved in the problem.

For this example, we are going to provide the following 4 X 4 distance matrix

We use the above matrix represented as a JSON object in our input request:

1
"distance_matrix": [
2
       [0, 12300, 31800, 5800],
3
       [13500, 0, 34800, 7200],
4
       [24900, 33600, 0, 27200],
5
       [5200, 8200, 29100, 0]
6
   ]

Users can provide any values which they believe to be closer to actual driving distances or just about any random values which helps them achieve a given business goal.

Custom Duration Matrix

Next we would configure the duration matrix to go along with the custom distance matrix. It is worth highlighting that the distance matrix is only used for driving distance calculations and determining the solution costs when travel_cost = distance or control the vehicle’s behavior if the “max_distance” constraints are defined. However, the duration matrix is integral as it is used to determine driving time between locations and the consequent “time_windows” implications which is critical in accepting and rejecting the potential solutions.

Like the distance matrix, the duration matrix is also a N X N two-dimensional matrix of time values, in seconds, where N is the number of unique locations involved in the problem.

For this example, we are going to provide the following 4 X 4 duration matrix.

We use the above matrix represented as a JSON object in our input request:

1
"duration_matrix": [
2
       [0, 1450, 2100, 1050],
3
       [1400, 0, 1950, 850],
4
       [2450, 2750, 0, 2400],
5
       [900, 1000, 1750, 0]
6
   ]
7

Like the distance matrix, the values provided to the duration matrix can be anything that users believe to be closer to actual drive times or any other values which help them achieve specific business operation goals.

Options

For this example, we will go for minimizing the distance as the optimization objective. Following is the JSON to configure this objective:

1

2
"options":{
3
       "objective":{
4
           "travel_cost":"distance"
5
           }
6
   }

Optimization POST Request

Now let’s put all these components together and create the final POST request that we will submit to the optimizer.

1
curl --location 'https://api.nextbillion.io/optimization/v2?key=<your_api_key>' 
2
--header 'Content-Type: application/json' 
3
--data '{...}'

Optimization POST Response

Once the request is made, we get a unique ID in the API response:

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

Optimization GET Request

We take the ID and use the Optimization GET request to retrieve the result. Here is the GET request:

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

Optimization GET Response

Following is the optimized route plan:

1
{
2
"description": "Custom Distance & Duration Matrix Example",
3
"result": {
4
"code": 0,
5
"summary": {...},
6
"unassigned": [....],
7
"routes": [....]
8
}
9
}

Analyzing the Solution

Looking at the result we can observe some interesting insights:

• All tasks were assigned using the available vehicle with a total cost of 52300.
• We can also see that the duration values and distance values used for calculating the duration and distance fields is from the respective custom matrices that were provided in the input
• We don’t get the route geometry in the output as user-defined distance values were used

Above solution shows how NextBillion.ai’s Route Optimization Flexible API is highly modular in its approach and can be plugged-in easily into current processes or traditional solutions to improve upon existing optimization techniques. We encourage you to go ahead and try out different values of distance and duration matrices, for different configurations of vehicles and task locations to explore how the solution changes under different scenarios presented to Route Optimization Flexible API.

Learn more about the other powerful features and the related use cases that Route Optimization Flexible API can solve for you.