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 Flexible 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, and the solution will not give precedence to tasks time_windows, soft constraint parameters etc. Also, when using relations the vehicle properties like capacity and skills should be matched to what the tasks on those relations need.

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

Get Started

Readers would need a valid NextBillion API key to try this example out. If you don’t have one, please contact us to get your API key now!

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

• Specify the schedule of tasks. This is done by adding time windows within which a task must be completed. We have added a 15 min time window for all tasks.

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    {
4      "id": 1,
5      "location_index": 0,
6      "service": 120,
7      "pickup": [0],
8      "time_windows": [[1693386000, 1693386900]]
9    },
10    {
11      "id": 2,
12      "location_index": 1,
13      "service": 180,
14      "pickup": [0],
15      "time_windows": [[1693387800, 1693388700]]
16    },
17    {
18      "id": 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

• Vehicle shift time or the time window

• 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    {
4      "id": 1,
5      "start_index": 16,
6      "capacity": [20],
7      "costs": {
8        "fixed": 1000
9      },
10      "time_window": [1693382400, 1693418400]
11    },
12    {
13      "id": 2,
14      "start_index": 17,
15      "capacity": [20],
16      "costs": {
17        "fixed": 1000
18      },

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    "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.037925,-118.459842",
11      "34.004364,-118.421170",
12      "34.000215,-118.318803",
13      "33.945884,-118.325628",
14      "34.000895,-118.204929",
15      "34.076646,-118.376969",
16      "34.094986,-118.300885",
17      "34.018780,-118.317919",
18      "33.996658,-118.261708",

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    {
4      "type": "in_sequence",
5      "steps": [
6        {
7          "type": "start"
8        },
9        {
10          "type": "job",
11          "id": 6
12        },
13        {
14          "type": "job",
15          "id": 4
16        },
17        {
18          "type": "job",

Optimization POST Request

Bringing all these attributes together, let’s create the final POST request that we will submit to the optimizer.

1curl --location  'https://api.nextbillion.io/optimization/v2?key=<your_api_key>'  --request POST \
2--header 'Content-Type: application/json' \
3--data-raw  '{
4      "description": "Relations Example",
5        "jobs": [
6          {
7            "id": 1,
8            "location_index": 0,
9            "service": 120,
10            "pickup": [
11              0
12            ],
13            "time_windows": [
14              [
15                1693386000,
16                1693386900
17              ]
18            ]

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:

1curl --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": "Relations Example",
3  "result": {
4    "code": 0,
5    "summary": {
6      "cost": 16139,
7      "routes": 3,
8      "unassigned": 0,
9      "service": 1910,
10      "duration": 13139,
11      "waiting_time": 15191,
12      "priority": 0,
13      "delivery": [6],
14      "pickup": [6],
15      "distance": 195236.8
16    },
17    "routes": [
18      {

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

Analyzing the Solution

Looking at the result we can observe some interesting insights:

• From the summary, we can see that all the jobs were assigned and a total of 3 routes were created.

• The in_sequence relation with jobs 6, 4, 1 gets fulfilled through vehicle 1. Job 4 & 1 could not be fulfilled within their time window.

• The in_direct_sequence relation with shipment 2 and jobs 10 & 5 get fulfilled through vehicle 2. Job 5 could not be fulfilled within its time window.

• The in_same_route relation with shipment 3 and jobs 7, 8, 9 get fulfilled through vehicle 3.

• Rest of all tasks - jobs 2, 3 and shipment 1 - were also taken care of by vehicle 3 on the same route as well.

As we can see, NextBillion.ai’s Route Optimization Flexible 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, wait_time etc.

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