Vehicle Routing Problem

The Vehicle Routing Problem (VRP) provides a solution for optimizing vehicle routes and logistics operations. It calculates the most efficient routes for a fleet of vehicles, considering various constraints such as time windows, vehicle capacities, and delivery priorities. This API is ideal for businesses looking to streamline their operations, reduce costs, and improve delivery efficiency by minimizing travel time and distance, all while maintaining high service quality.

Notes:

• the expected order for all coordinates arrays is [lng, lat]
• all timings are in seconds
• all distances are in meters
• a time_window object is a pair of timestamps in the form [start, end]
• deprecated keys are crossed out
• cost values in output are the one used internally in the optimization objective
• a "task" is either a job, a pickup or a delivery

Input

Endpoint

Method: POST

  https://maps.track-asia.com/api/{VERSION}/vrp?key=public_key

The problem description is read from standard input or from a file (using -i) and should be valid json formatted as follow.

Jobs

A job object has the following properties:

An error is reported if two job objects have the same id.

Shipments

A shipment object has the following properties:

A shipment_step is similar to a job object (expect for shared keys already present in shipment):

An error is reported if two delivery (resp. pickup) objects have the same id.

Vehicles

A vehicle object has the following properties:

A cost object has the following properties:

Using a non-default per-hour value means defining travel costs based on travel times with a multiplicative factor. So in particular providing a custom costs matrix for the vehicle is inconsistent and will raise an error.

A break object has the following properties:

An error is reported if two break objects have the same id for the same vehicle.

A vehicle_step object has the following properties:

Notes

Task locations

For job, pickup and delivery objects, if custom matrices are provided:

• location_index is mandatory
• location is optional but can be set to retrieve coordinates in the response

If no custom matrix is provided:

• a table query will be sent to the routing engine
• location is mandatory
• location_index is irrelevant

vehicle locations

• key start and end are optional for a vehicle, as long as at least one of them is present
• if end is omitted, the resulting route will stop at the last visited task, whose choice is determined by the optimization process
• if start is omitted, the resulting route will start at the first visited task, whose choice is determined by the optimization process
• to request a round trip, just specify both start and end with the same coordinates
• depending on if custom matrices are provided, required fields follow the same logic than for job keys location and location_index

Capacity restrictions

Use amounts (capacity for vehicles, delivery and pickup for jobs, amount for shipments) to describe a problem with capacity restrictions. Those arrays can be used to model custom restrictions for several metrics at once, e.g. number of items, weight, volume etc. A vehicle is only allowed to serve a set of tasks if the resulting load at each route step is lower than the matching value incapacity for each metric. When using multiple components for amounts, it is recommended to put the most important/limiting metrics first.

It is assumed that all delivery-related amounts for jobs are loaded at vehicle start, while all pickup-related amounts for jobs are brought back at vehicle end.

Skills

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 to vehicle v iff 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).

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

Task priorities

Useful in situations where not all tasks can be performed, to gain some control on which tasks are unassigned. Setting a high priorityvalue for some tasks will tend as much as possible to have them included in the solution over lower-priority tasks.

Task setup times

Setup times serve as a mean to describe the time it takes to get started for a task at a given location. This models a duration that should not be re-applied for other tasks following at the same place. So the total "action time" for a task is setup + service upon arriving at a new location or service only if performing a new task at the previous vehicle location.

Time windows

It is up to users to decide how to describe time windows:

• relative values, e.g. [0, 14400] for a 4 hours time window starting at the beginning of the planning horizon. In that case all times reported in output with the arrival key are relative to the start of the planning horizon;
• absolute values, "real" timestamps. In that case all times reported in output with the arrival key can be interpreted as timestamps.

The absence of a time window in input means no timing constraint applies. In particular, a vehicle with no time_window key will be able to serve any number of tasks, and a task with no time_windowskey might be included at any time in any route, to the extent permitted by other constraints such as skills, capacity and other vehicles/tasks time windows.

Vehicle steps

In plan mode

The steps array describes exactly the route ordering that will be generated in response. The (optional) service_* keys forvehicle_step objects are used as additional hard timing constraints.

In solving mode

Using steps for vehicles in default VRP solving mode is a way to force starting the search from the matching user-defined solution, if valid. Unlike the default solving behavior of running several concurrent searches, this means in particular that a single search path is followed, starting from the provided solution. Resulting quality is thus obviously expected to be highly dependent on the user-defined starting point.

In that context:

• only steps with type=job, pickup or delivery are used to decide initial routes ordering
• service_* keys are not used

An error is raised if for any of the vehicles the provided stepsdescribe a route that is invalid with regard to any of the constraints.

Matrices

The matrices object allows to input (non-empty) custom matrices for each vehicle profile. Each matrix is an array of arrays of unsigned integers filed under the profile key, then under:

• durations for a custom travel-time matrix that will be used for all checks against timing constraints;
• distances for a custom distance matrix;
• costs for a custom cost matrix that will be used within all route cost evaluations.

If only the durations matrix is provided, internal costs are derived from durations based on vehicles costs properties.

Example of describing different matrices for different vehicle profiles:

"matrices": {
    "car": {
        "durations": [[0, 14], [21, 0]]
    },
    "moto": {
        "durations": [[0, 57], [43, 0]]
    }
}

If custom matrices are provided for all required vehicle profilevalues, the location, start and end properties become optional. Instead of the coordinates, row and column indications provided with the *_index keys are used during optimization.

Output

The computed solution is written as json on standard output or a file (using -o), formatted as follow.

Code

Possible values for the status code are:

Summary

The summary object has the following properties:

*: provided when using the -g flag or passing distance matrices in input.

Routes

A route object has the following properties:

*: provided when using the -g flag. **: provided when using the -g flag or passing distance matrices in input.

Steps

A step object has the following properties:

*: provided when using the -g flag.

Violation

A violation object has the following properties:

Possible violation causes are:

• "delay" if actual service start does not meet a task time window and is late on a time window end
• "lead_time" if actual service start does not meet a task time window and is early on a time window start
• "load" if the vehicle load goes over its capacity
• "max_tasks" if the vehicle has more tasks than its max_tasks value
• "skills" if the vehicle does not hold all required skills for a task
• "precedence" if a shipment precedence constraint is not met (pickup without matching delivery, delivery before/without matching pickup)
• "missing_break" if a vehicle break has been omitted in its custom route
• "max_travel_time" if the vehicle has more travel time than its max_travel_time value
• "max_distance" if the vehicle has a longer travel distance than its max_distance value
• "max_load" if the load during a break exceed its max_load value

Note on violations: reporting only really makes sense when using -cto choose ETA for custom routes described in input using the stepskeys for a vehicle. When using regular optimization, violations are still reported for consistency, but are guaranteed to be "void", i.e. violations arrays are empty.

Examples

See the detail (visualized/interactable) example at Examples > Vehicle Routing Problem solver.

var jobs = [];
var shipments = [
{
"amount": [
1
],
"pickup": {
"id": 1,
"service": 60,
"location": [
106.6984834,
10.72843945
],
"description": "Đ. Số 65, Phường Tân Phong, Quận 7, Thành phố Hồ Chí Minh, Vietnam",
"time_windows": [
[
1725843600,
1725850800
]
]
},
"delivery": {
"id": 1,
"service": 300,
"location": [
106.7185714,
10.72843945
],
"description": "Crescent Mall 101 Tôn Dật Tiên, Tân Phú, Quận 7, Thành phố Hồ Chí Minh 7000, Vietnam",
"time_windows": [
[
1725843600,
1725850800
]
]
}
},
{
"amount": [
1
],
"pickup": {
"id": 2,
"service": 60,
"location": [
106.7185714,
10.72843945
],
"description": "Crescent Mall 101 Tôn Dật Tiên, Tân Phú, Quận 7, Thành phố Hồ Chí Minh 7000, Vietnam",
"time_windows": [
[
1725843600,
1725850800
]
]
},
"delivery": {
"id": 2,
"service": 300,
"location": [
106.723533,
10.73042726
],
"description": "Capri by Fraser, Ho Chi Minh 2 Đường C - Bắc, Tân Phú, Quận 7, Thành phố Hồ Chí Minh, Vietnam",
"time_windows": [
[
1725843600,
1725850800
]
]
}
}
];
var vehicles = [
{
"id": 5,
"start": [
106.6984834,
10.72843945
],
"end": [
106.723533,
10.73042726
],
"time_window": [
1725879600,
1725880800
],
"capacity": [
1
],
"skills": [
1,
14
],
"startDescription": "Start",
"endDescription": "End"
}
];
var options = {
"g": true
};
 
fetch('https://maps.track-asia.com/api/v1/vrp?key=public_key', {
method: "POST",
headers: { "content-type": "application/json" },
body: JSON.stringify({
"jobs": jobs,
"shipments": shipments,
"vehicles": vehicles,
"options": options,
}),
})
.then((response) => response.json())
.then((data) => console.log(data))
.catch((error) => console.error("Error:", error));