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
Optimization Post- Use this method to submit input for your VRP.Optimization GET- Retrieve the status of a submitted VRP using a unique reference ID.
Optimization POST Method
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
vehicleswith properties like capacity, time_window, start_index, end_index and skills set. -
6
jobsand 1shipmentswith their id, locations, pickup/delivery amounts, time_windows and service time set.
Request
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.
Response
Optimization GET Method
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
Response
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.
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.
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:
-
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.
-
In order to request a round trip, you can specify both the start_index and end_index with the same location index.
-
capacityparameter 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_windowsconstraints injobsandshipmentsmight be violated for thestepsmentioned in therelationsobject. -
Soft constraints parameters like
max_vehicle_overtimeandmax_visit_latenesswill not be available in input requests when therelationsobject is used. -
Hard constraint of
max_activity_waiting timeis effective only within_same_routetype 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
vehicleassigned 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
relationsinput requires adeliverystep to occur before apickupstep for ashipment, an error message is returned, as it violates the shipment's logical order. -
For
shipments, both thepickupanddeliverysteps should exist within the samerelations. An error message is reported if arelationscontains only oneshipmentstep.
Sample Relations Object
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:
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
locationsandcost_matrixobjects. This means that the costs associated with coordinates at index i inlocationsobject should be added in a row at index i in thecost_matrixobject 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_costis set tocustomized, the optimization algorithm takes the customized cost matrix into account when calculating the overallcostof a route. max_travel_costfeature 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. Themax_travel_costfeature ensures that the calculated cost of a route does not exceed a specified value. By combining the customization of thecost_matrixand themax_travel_costfeature, 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
Metadata Attribute
The metadata property, as the name suggests, can be used to provide any additional details about the entity that it is being attached to. Route Optimization API allows users to add metadata to vehicles, jobs and shipments. The contents of the metadata attribute always need to follow the “key : value” format. The contents of this attribute do not affect the optimization in any way and are passed through to the solution as is.
This metadata can be used to display additional information, say on an application or a dashboard, about the entities involved in a route optimization problem. A good example is the NextBillion.ai’s Route Planner. User’s can add custom metadata details to their vehicles, jobs & shipments when generating route plans using the Route Planner and then dispatch the routes to an external telematics provider with rich custom details about the route plan like - driver name, vehicle license number, contact details of the drivers or instructions for completing a particular task. The telematics provider then displays these details along with the route on a dashboard for operations manager or shares them directly to the driver, as needed, ensuring managers or drivers have all the details for executing the suggested route plans.
Following is a sample metadata attribute that can be attached to a delivery task
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
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
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:
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
locationsobject -
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_weightis 100,000 kg. -
Maximum dimensions for
truck_sizeare 5000 cm for length, 5000 cm for width, 1000 cm for height. -
When using
traffic_timestampor truck related parameters in theroutingproperty ofoptionsattribute, please expect a higher request processing time, especially if the number of locations provided in the request is also high.
