Route Grouping

Route Grouping is a powerful feature which deals with how a route plan is actually executed and helps users in achieving highly efficient routes. When used, route grouping attributes tune the algorithm to avoid, as much as possible, overlapping of different routes as well as any back and forth movement of vehicles on a road segment. Using this feature aids in streamlining the execution of optimized route plans to achieve highly efficient routes and consequent cost savings. However, a caveat regarding the feature is that it works well with a large number of orders and its impact might not be apparent for a smaller set of tasks and vehicles. In the following example we will take a large set of vehicles and tasks to bring out the impact of this powerful feature.

Setup

We will take a set of 180 tasks scattered across Los Angeles and 4 vehicles to fulfill them. We will define the locations, jobs, vehicles and options attributes one by one.

Locations

We start by adding all the 180 task locations and another 4 locations which are the starting points for the vehicles.

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

A distribution of all jobs and vehicle’s starting point when shown on the maps looks like below

docs-image

Jobs

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

  • A unique identifier
  • Location index
  • Delivery quantity
  • 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 4 vehicles that will be responsible for fulfilling these tasks. For each of the vehicles we add:

  • A unique ID
  • A start_index and end_index to denote the points from where the vehicle starts and ends its trip.
  • A capacity for each vehicle

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

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

Options

And lastly, we configure the parameters for route grouping. For our example, we allow:

  • A straight-line distance of 1500 meters as the diameter to group the routes together so that they don’t cross each other
  • A penalty factor of 100 to be applied for any routes which violate the route grouping zones
  • We use the “distance” as the cost to be minimized

Once the constraint properties are defined, the resulting options JSON is:

1"options": {
2 "objective": {
3 "travel_cost": "distance"
4 },
5 "grouping": {
6 "route_grouping": {
7 "zone_diameter": 1500,
8 "penalty_factor": 100
9 }
10 }
11}

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{
2 "description": "Route Grouping Example",
3 "locations": "{...}",
4 "jobs":"[...]",
5 "vehicles":"[...]",
6 "options": "{...}",
7}

Optimization POST Response

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

1{
2"id": "7d2dd7788e69dc75dc6c22e8055562df",
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:

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

Optimization GET Response

Following is the optimized route plan:

1{
2 "status": "Ok",
3 "message": "",
4 "result": "[...]"
5}

Following image shows a visual representation of the above route plan

docs-image

Analyzing the Solution

Looking at the result we can observe some interesting insights:

  • All tasks were assigned using 4 routes with a total distance traveled of 874 km.
  • We can see in the image above that the solution hardly has the routes crossing each other and avoid going back and forth on the same road segment as much as possible.
  • The task distribution is good and it ensures that there are clear “operating zones” for each vehicle.

To understand the effect of using the Route Grouping feature, take a look at the below image representing a similar route plan suggested when route grouping was not used for the same set of tasks and vehicles.

docs-image

We can observe that the routes cross each other at multiple places. Also, the distribution of tasks in this solution is such that there is no clear “operating zone” for vehicles and it overlaps at multiple places for at least a couple of vehicles.

This comparison shows how NextBillion.ai’s Route Optimization Flexible API uses its route grouping capabilities to execute a route plan using highly efficient routes. We encourage you to go ahead and try out different configurations of tasks, vehicles and zoning parameters 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.