Soft Constraints

The Soft Constraints feature enables users to complete more tasks by treating specific time-related limitations as flexible. NextBillion.ai’s Route Optimization Flexible API currently allows vehicle shift timings and task time windows to be made flexible up to a configurable degree. This functionality is useful in commercial scenarios where job completion ratio is the most crucial measure and time constraints are not strict. Let’s build an example to understand how these constraints work.

Setup

Jobs

We will start by defining 6 jobs. For these tasks we will add:

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.
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 2 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
Start_index to denote the point from where the vehicle would start.
Costs for all vehicles. We have specified only fixed cost for the sake of simplicity, readers can choose any type of cost.

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
}

Options

And lastly, we configure the degree up to which the job time windows and vehicle shift timings can be treated as flexible. For our example, we allow:

Vehicles to extend their shift timings by 30 mins (~1800 seconds)
Tasks to be assigned even if the vehicle is late by 5 minutes (~300 seconds) beyond the given schedule.

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

1
{
2
  "options": {
3
    "constraint": {
4
      "max_visit_lateness": 300,
5
      "max_vehicle_overtime": 1800
6
    }
7
  }
8
}

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>' --header 'Content-Type: application/json' --data '{...}'

Optimization POST Response

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

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

Optimization GET Response

Following is the optimized route plan:

1
{
2
  "description": "Soft Constraints Example",
3
  "result": '{...}'
4
  }

When the above result is plotted on the map we can see how all the tasks were covered.

Analyzing the Solution

Looking at the result we can observe some interesting insights:

The summary section gives details about the total number of routes, total cost of the solution, distance and duration taken to complete all the assigned jobs.
In the routes section:
- We can see that job 3 was fulfilled even though vehicle 1 arrived at the location 5 mins after the scheduled time window had ended. The late_by field indicates the value by which the vehicle was late to arrive at job 3 location.
- For job 2, the optimizer uses the relaxations available for time window constraints and assigns job 2 with 5 minutes of acceptable delay.
- Observe the vehicle_overtime field for vehicle 1 & 2 and we come to know that they operated for around 16 mins and 3 mins beyond their shift to complete all the assigned jobs. This happened as the optimizer was allowed to operate vehicles for 1800 seconds (~30 minutes) beyond their shift end time, if needed.

The above example exhibits how NextBillion.ai’s Route Optimization Flexible API allows and implements the relaxations configured for vehicle shift times and task time windows and suggests the best solution with maximum possible task assignment. We encourage you to go ahead and try out different configurations of soft constraints and explore how the solution changes under different scenarios presented to Route Optimization Flexible API.

Liked the above example? Take a look at a host of advanced use cases that Route Optimization Flexible API can solve for you.