Relations & Task Sequencing

Relations are used to specify the association between different tasks that should be performed in a certain order. NextBillion.ai’s Route Optimization API offers three types of relations that the users can enforce:

  • in_same_route: All the steps mentioned in this type of relation will be part of the same route.

  • in_sequence: All the steps mentioned in this relation will follow the specified sequence but other steps might be inserted by the optimizer, if feasible.

  • in_direct_sequence: All the steps mentioned in this relation will follow the specified sequence without any other steps being inserted between them by the solver.

However, a few points might be worthy to note here. Relations are a hard configuration in that the tasks belonging to a relation should all be feasible for it to work. If any of the tasks in the relation can’t be fulfilled due to any reason (skills mismatch, time-window, insufficient capacity etc) the entire relation would be deemed infeasible and all tasks would be unassigned. Hence, it is critical to ensure that all tasks can be accommodated in one of the available vehicles before adding them to a relations.

Relations is a helpful feature to take care of special sequencing cases of task fulfillment within overall optimization problems.

Setup

Once you have a valid API Key, you can start setting up the components to be used in this example. Let’s take a look at them below.

Jobs & Shipments

We start by defining 10 jobs and 3 shipments. Let’s define the properties of these tasks:

  • A unique identifier for each task

  • Location indexes for each task

  • The actual time taken to complete the tasks 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
}

Vehicles

Next, we add 4 vehicles that will be responsible for fulfilling the tasks within the defined constraints. To describe the vehicles and their properties we add:

  • A unique ID for each vehicle

  • Capacity to denote the amount of load that the vehicle can take

  • start_index to denote the point from where the vehicle would start.

  • Costs for all vehicles. We have specified fixed cost for all vehicles

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

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

Locations

Next, we define the locations object and add all the locations used in the problem along with a valid id. The locations object with all the points used in this example:

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

Relations

And, lastly, we define the relations between the tasks of our choice. For this example, we will

  • Keep shipment 3, jobs 7,8,9 in same route

  • Keep shipment 2 and job 10, 5 in direct sequence

  • Keep jobs 6, 4, 1 in sequence.

  • Jobs 2, 3 and shipment 1 are not part of any relations

The relations object once configured according to the above distribution results in :

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

Optimization POST Request

Bringing all these attributes together, let’s 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>'  --request POST --header 'Content-Type: application/json' --data-raw  '{...}'

Optimization POST Response

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

1
{
2
  "id": "b6752a169903fd4cd6f820e4c27ff850",
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=b6752a169903fd4cd6f820e4c27ff850
2
&key=<your_api_key>'

Optimization GET Response

Following is the optimized route plan:

1
{
2
"description": "Re-optimization (new-tasks) Example",
3
"result": "{...}"
4
}

Following is a visual representation of the initial locations of tasks, vehicles and the routes suggested after optimization as per the given constraints.

documentation image

Analyzing the Solution

Looking at the result we can observe some interesting insights:

  • From the summary, we can see that all the tasks were assigned and a total of 3 routes were created.
  • The in_sequence relation with jobs 6, 4, 1 gets fulfilled through Vehicle 1.
  • The in_direct_sequence relation with Shipment 2, Job 10 & Job 5 gets fulfilled through Vehicle 2.
  • The in_same_route relation with Shipment 3, Jobs 7, Jobs 8, and Jobs 9 gets fulfilled through Vehicle 4.
  • The tasks that were not part of any relations - Job 2, Job 3 and Shipment 1 - were also included in the Vehicle 1 route. It allowed the optimizer to not employ Vehicle 3 at all and save its fixed cost.

As we can see, NextBillion.ai’s Route Optimization API honors the relation constraints exactly as configured. To explore more readers can change the contents of different relations, assign different vehicles to relations. Or else they can just remove the relations object and contrast the result with the above and see how adding relations impacts the job distribution, number of routes, costs, etc.

We hope this example was helpful. Check out some more use cases that Route Optimization API can handle for you!