Route Optimization Flexible API

Introduction

Nextbillion.ai's Route Optimization Flexible API is a powerful tool that helps businesses optimize their delivery routes to maximize efficiency, save time, and reduce costs. It is designed to solve both Single and/or Multi Vehicle Routing Problem (VRP), which is a classic optimization problem in operations research that involves finding the optimal set of routes for a fleet of vehicles to visit a set of locations while satisfying various constraints such as time windows, capacity, and vehicle availability.

The Route Optimization Flexible API consists of two main components - the input data and the optimization engine. The input data includes information about the jobs (stops/places to visit), vehicles (delivery trucks, vans, etc.), and shipments (pickup and delivery tasks), while the optimization engine uses this data to find the most efficient set of routes for the vehicles to follow.

With the ability to handle complex constraints and variables such as capacity, time windows, and vehicle availability, our API can be customized to meet specific needs of your business.

There are two components to API

  1. Optimization Post - Use this method to submit input for your VRP.
  2. Optimization GET - Retrieve the status of a submitted VRP using a unique reference ID.
Route Optimization Flexible API
Tutorials
To see all tutorials related to the Route Optimization Flexible API, click this banner

Optimization POST Method

POST

https://api.nextbillion.io/optimization/v2?key={your_api_key}


Use this method to configure the constraints and properties of the optimization problem that you need to solve. Use the fundamental objects - vehicles, jobs, locations and shipments to emulate the scenario that your business needs to optimize. You can choose to use either one of jobs and shipments or use both of them.

Define the objective of your optimization, soft-constraints and routing preferences in the options object. You can also use advanced features like re-optimization and order sequencing using the solutions and relations object respectively.

Once an Optimization POST request is successfully submitted, the API will return a unique task ID in the acknowledgement response. Use this unique ID to retrieve the actual solution using the Optimization GET Method.

Request Parameter

Loading..

Request Body

Loading..

Response Schema

Loading..

Example

Let us build a basic flexible route optimization request using a sample scenario which has:

  • 2 vehicles with properties like capacity, time_window, start_index, end_index and skills set.
  • 6 jobs and 1 shipments with their id, locations, pickup/delivery amounts, time_windows and service time set.

Request

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

The above problem statement would look like the following when visualized on a map. We can see the locations of the 2 vehicles, 6 jobs and a shipment task. We will cover the solution and how it looks on a map in the next section.

docs-image

Response

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

Optimization GET Method

GET

https://api.nextbillion.io/optimization/v2/result?id={id}&key={your_api_key}


Use this method to retrieve the optimized solution for the optimization tasks created using the Optimization POST Method.

A point worth highlighting here is that the optimizer uses traffic conditions at the time of making the request to prepare a solution. Slight changes in traffic conditions can cause the optimizer to prefer different routes and possibly different sequences in which to fulfill the jobs or shipments. Therefore, different optimization requests made with similar task or constraint configuration are expected to return different optimized solutions.

Request Parameters

Loading..

Response Schema

Loading..

Example

Let’s retrieve the same job that was created in the example above in the Optimization POST Method section.

Request

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

Response

1{
2 "description": "...",
3 "result": {
4 "code": 0,
5 "summary": "{...}",
6 "routes": "[...]"
7 },
8 "status": "Ok",
9 "message": ""
10}

Following is a visual representation of the optimized solution on a map. We can see that the solution suggested by optimizer has 2 routes to cover all the jobs and shipments. Vehicle 1 starts from its start points and covers the location of all jobs within the prescribed time windows for each job. It also takes care of the shipment between completing the jobs as the skills required for shipment are possessed by only this vehicle in the given scenario. Whereas, vehicle 2 is assigned to only 2 jobs which are located near its starting point. We also get the summary of the overall solution as well as for each of the routes. We can see the overall waiting time is around 30 mins for vehicle 1 which was caused when it was waiting for the delivery time_window of the shipment to start. We also get the route-wise as well as overall cost of the optimized solution.

docs-image

Object Overview

Location Object

Locations object - locations - is used to describe locations that will be used for route optimization. A maximum of 2k locations can be added to this object.

IndexLocation
051.388997,-0.119022
151.391915,-0.103666
251.369777,-0.10438
351.365014,-0.105654
451.351818,-0.014773

With respect to the example above, if in the "vehicles" property, the start_index parameter is set to 2, then 51.369777,-0.10438 would be considered as the starting coordinates for that vehicle.

Job Object

jobs object describes a particular job or a task that needs to be completed as part of the overall optimization process. It contains various properties of a job such as the job id, the index of the location where the job needs to be performed, the service duration, multidimensional quantities for pickup and delivery, available time windows, mandatory skills required, the priority of the job, and a description of the job.

Properties of a jobs object provide important information to the optimization algorithm, such as time constraints and resource requirements for each job, which helps generate an optimized route plan. It is important to note here that all delivery-related amounts for jobs are loaded at vehicle start, while all pickup-related amounts for jobs are brought back to the last stop of the vehicle. Therefore, the vehicles should have appropriate capacity to handle job pickup and deliveries accordingly.

Vehicle Object

The Vehicle object describes the characteristics and constraints of a vehicle that will be used in a multi-vehicle routing problem. Some points to consider about vehicles object:

  1. The users can also set a start or an end location of their choice as long as it is present in the locations object. The vehicle’s start and end locations can be different from job locations.

  2. In order to request a round trip, you can specify both the start_index and end_index with the same location index.

  3. capacity parameter describes the maximum multidimensional quantities a vehicle can carry.

Relations Object

relations object is used to configure relationships between jobs and shipments that should be honored in the optimized solution. With this object users can customize the algorithm to emulate real-world constraints like control the sequence of certain jobs/shipments in the solution or ensure certain jobs/shipments are covered on the same route. It allows you to specify various types of relations and their corresponding constraints for the steps. However when using the relations object, please be mindful of the following considerations:

  • time_windows constraints in jobs and shipments might be violated for the steps mentioned in the relations object.
  • Soft constraints parameters like max_vehicle_overtime and max_visit_lateness will not be available in input requests when the relations object is used.
  • Hard constraint of max_activity_waiting time is effective only with in_same_route type of relation. It is not effective for other relation types.
  • If certain relations require multiple steps (e.g., jobs) to be on the same route, the vehicle assigned to that route must have enough capacity and the required skills to serve all the jobs on the route. The optimization service would return an error, otherwise.
  • If a relations input requires a delivery step to occur before a pickup step for a shipment, an error message is returned, as it violates the shipment's logical order.
  • For shipments, both the pickup and delivery steps should exist within the same relations. An error message is reported if a relations contains only one shipment step.

Sample Relations Object

1{
2 "relations": [
3 {
4 "type": "in_direct_sequence",
5 "steps": [
6 {
7 "type": "start"
8 },
9 {
10 "type": "pickup",
11 "id": 25
12 },
13 {
14 "type": "job",
15 "id": 3
16 },
17 {
18 "type": "delivery",
19 "id": 25
20 },
21 {
22 "type": "end"
23 }
24 ],
25 "vehicle": 1
26 }
27 ]
28}

Custom Cost Matrix

This feature enables the optimization algorithm to consider a user-defined cost of traveling between different locations. Users can set the travel_cost parameter of objective property to customized to ensure that the algorithm considers the custom cost values for each traveling between locations.

To utilize the "cost_matrix" object, you need to provide a 2D array with 'n' rows and 'n' columns where n represents the total number of locations. Each element of the array represents the cost of traveling from one location to another. The optimization algorithm would prefer the routes with lower relative costs over the routes with higher relative costs. Therefore, the custom cost matrix can be used to influence the optimized route that the algorithm returns. For example, if you have three locations (A, B, C), the cost_matrix would be a 3x3 array:

1`cost_matrix`: [
2 [0, 10, 5],
3 [10, 0, 8],
4 [5, 8, 0]
5 ]

In this example, the first row represents the cost of traveling from location A to location A,A to B & A to C, the second row represents the cost of traveling to different locations starting from point B to A and so on. Subsequently, for the given example, the cost of traveling from location A to B is 10, from A to C is 5, from B to A is 10, from B to C is 8, and so on.

Few points to consider regarding the use of cost_matrix :

  • The cost values should always be non-negative integers.
  • The cost values do not have any unit. Users can consider the cost of traveling from one location to another as abstract but relative weights.
  • Please ensure to match the index between locations and cost_matrix objects. This means that the costs associated with coordinates at index i in locations object should be added in a row at index i in the cost_matrix object as well.
  • Using custom costs for a subset of total locations is not allowed. Either it should be used for all locations or not used at all. To ignore a particular location and prevent it from being included in the optimization, you can assign a very large value to the corresponding row and column in the cost_matrix. This ensures that the optimizer avoids that location in the routing solution.
  • When the travel_cost is set to customized, the optimization algorithm takes the customized cost matrix into account when calculating the overall cost of a route.
  • max_travel_cost feature allows you to set a maximum travel cost for a route. When a customized cost matrix is used in the optimization request, the total cost of a route is calculated based on the values provided in the customized cost matrix. The max_travel_cost feature ensures that the calculated cost of a route does not exceed a specified value. By combining the customization of the cost_matrix and the max_travel_cost feature, you can optimize routes based on your desired cost factors while also ensuring that the routes remain within specific cost constraints.

Sample Cost Matrix Object

1{
2 "cost_matrix":
3 [
4 [0,4,22,9999],
5 [4,0,12,33],
6 [22,12,0,45],
7 [9999,33,45,0]
8 ]
9 }

Multi-Dimensional Parameters

Capacity

The Capacity parameter in Vehicle Object is used to describe multidimensional quantities of capacity. In this context, multi-dimension refers to the fact that a single vehicle can carry loads defined in different units. For example, a vehicle may have a capacity of 10 cubic meters for volume, 1000 kg for weight, and 6 pallets for a number of items. These are three different dimensions of capacity, and each has its own value. By specifying Capacity as an array of integers, we can provide values for each dimension of capacity that a vehicle possesses. This information is then used by the optimization algorithm to ensure that the total capacity required by all shipments assigned to a vehicle does not exceed its capacity in any of the dimensions.

Example: Let's say a construction company has a fleet of trucks that are used to transport multiple things, such as bricks, cement, and even construction workers. Each truck has a different capacity for weight, volume, and number of persons it can carry.

In this case, the capacity parameter can be used to describe the multidimensional quantities for each truck. For example, a truck may have a capacity of 100 kg weight, 10 cubic meters of volume, and can carry 5 construction workers. The capacity parameter can be defined as [100, 10, 5] to represent these values respectively.

By leveraging the capacity in multiple dimensions, the solver can optimize job/shipment assignment to appropriate vehicles ensuring better customer service and efficient transportation.

Amount

Amount parameter in Shipment Object is used to describe multidimensional quantities of a shipment. The term "multi-dimensional" refers to the fact that a single shipment can have amounts defined in different units. Continuing with our example of the construction company above, let’s say a truck needs to pick up 50 kg of bricks, and 2 cubic meters of cement from a construction material supplier’s location. When defining the shipment we define this input as

1“amount”: [50,2,0]

0 for the construction worker dimension. Next, if we have another stop to pick up 3 construction worker, then we can define the amount as

1“amount”: [0,0,3]

If the other parameters, like distance, time_windows, location of other trucks etc. are favorable then these 2 pickups can be assigned to the same vehicle with “capacity”: [100,10,5] like in this example.

Amount parameter is useful for optimizing delivery routes and determining the most efficient way to transport goods based on multiple dimensions of quantity.

Skills

Skills parameter in the Vehicles Object describes the skills that a driver or vehicle possesses in different units. The term "multi-dimension" refers to the fact that a single driver or vehicle may have different skills or abilities, each of which could be measured in different units or quantities.

For example, let's say we have a fleet of delivery vehicles. One of these vehicles may have the following skills:

  • Skill ID ‘101’: Capacity to carry 10 large boxes
  • Skill ID ‘102’: Ability to transport goods at a temperature of -10 degrees Celsius
  • Skill ID ‘103’: Ability to transport hazardous materials in a specific type of container

In this case, the Skills parameter would be set as an array of integers, with each element corresponding to a particular skill or ability. For instance, the skills parameter for the vehicle described above might be set as follows:

1"skills": [101, 102, 103]

Here, the first element (101) corresponds to the vehicle's capacity to carry 10 large boxes, the second element (102) corresponds to its ability to transport goods at a temperature of -10 degrees Celsius, and the third element (103) corresponds to its ability to transport hazardous materials in a specific type of container.

By including skills attribute in the optimization API, users can optimize their delivery routes based on specific skills and abilities of their drivers and vehicles, helping to ensure that each delivery is made efficiently and safely.

Skills Restrictions

Use skills to describe a problem where not all tasks can be served by all vehicles. Job skills are mandatory, i.e. a job can only be served by a vehicle that has all its required skills. In other words: job j is eligible for vehicle v if j.skills is included in v.skills. This definition implies in particular that:

  • a task without skills can be served by any vehicle;
  • a vehicle without skills can only serve tasks with no particular need (i.e. without skills as well).
  • a job with multiple skills will be assigned to vehicles matching all the skills. The job will not be assigned to vehicles with partially matching skills.

In order to ease modeling problems with no skills required, not providing the skills key defaults to providing an empty array.

API Query Limits

  • Nextbillion.ai allows a maximum rate limit of 300 queries per minute or 5 queries/second for continuous requests. Note: We can increase the quota if needed on request. Contact [email protected] for more details.

  • At any point the maximum number of pending requests that the queue can hold is 25, for a given API key. New requests for the same key can be submitted once some of the pending requests are resolved.

  • A maximum of 4000 locations can be added to the locations object

  • A maximum of 4000 tasks can be added in an optimization problem. Number of tasks is calculated as number of jobs + 2 * (number of shipments).

  • Maximum value that can be provided for truck_weight is 100,000 kg.

  • Maximum dimensions for truck_size are 5000 cm for length, 5000 cm for width, 1000 cm for height.

  • When using traffic_timestamp or truck related parameters in the routing property of options attribute, please expect a higher request processing time, especially if the number of locations provided in the request is also high.

API Error Codes

Response CodeDescriptionAdditional Notes
200Normal success case.Normal success case.
400Input validation failed.There is a missing or an invalid parameter or a parameter with an invalid value type is added to the request.
401APIKEY not supplied or invalid.This error occurs when the wrong API key is passed in the request or the key is missing altogether.
403APIKEY is valid but does not have access to requested resources.You might be querying for a geographical region which is not valid for your account or requesting a service which is not enabled for you.
404Requested host/path not found.This error occurs when a malformed hostname is used.
422Could not process the request.A feasible solution could not be generated for the given set of locations or parameter configuration.
429Too many requests.QPM reached or API request count quota reached.
500Internal Service error.There was an internal issue with NextBillion.ai services. You can reach out to [[email protected]](mailto:[email protected]) for an explanation.