Distance matrix¶
Info
Nextmv provides a hosted map data service based on OSRM if you wish to use a pre-calculated distance matrix. The service is available as a paid add on to any paid plan. The service can be configured via the input file and can be used with either the Nextmv Routing marketplace app or custom apps.
Info
This feature is configurable via .json input, without the need for code
customization and is available for both the Marketplace app and Platform. You
can find a list of all available features.
Warning
When distance_matrix (with speed) and duration_matrix
are both specified, the duration_matrix takes precedence.
| Field name | Required | Data type | SI Unit | Defined on | Example | Configurable via defaults |
|---|---|---|---|---|---|---|
distance_matrix |
No | array of array of float |
meters |
input | {"distance_matrix": [[1.23, 4.56], [7.89, 0.12]]} |
➖ |
By default, the distance between two locations is calculated using the
Haversine formula. To override this behavior, you can specify a
distance matrix in the input that provides the distance of going from location
A to B, using the distance_matrix feature. The travel duration between
locations is obtained by factoring the distance and the speed (specified in
meters/second) of each vehicle.
Warning
When using the distance_matrix feature, the speed of each vehicle must be
specified.
The distance_matrix is useful when you want to use a different distance
function, or when you want to use a pre-calculated distance matrix. For
example, you may have your own mapping service that provides the distance
between locations.
The distance_matrix is an array of arrays of float. The units for the
values are meters. The matrix must be square, and its size is:
Where:
n: the number of stops.m: the number of vehicles.
If you’re using Nextmv Maps, the max size for the distance matrix is 2,000 x
2,000. If you’re using your own matrix there is no size limit other than the 100
MB file size limit for the input file. The size follows that each float value
is the distance in meters of traveling from location at index i to location at
index j. Indices must be given in the following order:
[
stop-1, ..., stop-n,
vehicle-1-start-location, vehicle-1-end-location, ..., vehicle-m-start-location, vehicle-m-end-location
]
The matrix may be asymmetric, meaning that the distance of going from location A to B may be different than the distance of going from location B to A.
Here is an example input defining a complete distance matrix. In this example,
the distance to travel from "Fushimi Inari Taisha" to "Kiyomizu-dera" and
viceversa is 4300 meters. Vehicle locations are omitted, given that the
distance of going to/from them is zero.
A sample output obtained after solving the problem is also shown.
{
"distance_matrix": [
[0, 4300, 6700, 0, 0, 0, 0],
[4300, 0, 4500, 0, 0, 0, 0],
[6700, 4500, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]
],
"stops": [
{
"id": "Fushimi Inari Taisha",
"location": { "lon": 135.772695, "lat": 34.967146 }
},
{
"id": "Kiyomizu-dera",
"location": { "lon": 135.78506, "lat": 34.994857 }
},
{
"id": "Nijō Castle",
"location": { "lon": 135.748134, "lat": 35.014239 }
}
],
"vehicles": [
{
"id": "v1",
"speed": 10
},
{
"id": "v2",
"speed": 20
}
]
}
{
"options": {
"check": {
"duration": 30000000000,
"verbosity": "off"
},
"format": {
"disable": {
"progression": true
}
},
"model": {
"constraints": {
"disable": {
"attributes": false,
"capacities": null,
"capacity": false,
"distance_limit": false,
"groups": false,
"maximum_duration": false,
"maximum_stops": false,
"maximum_wait_stop": false,
"maximum_wait_vehicle": false,
"mixing_items": false,
"precedence": false,
"start_time_windows": false,
"vehicle_end_time": false,
"vehicle_start_time": false
},
"enable": {
"cluster": false
}
},
"objectives": {
"capacities": "",
"cluster": 0,
"distance": 0,
"early_arrival_penalty": 1,
"late_arrival_penalty": 1,
"min_stops": 1,
"stop_balance": 0,
"travel_duration": 0,
"unplanned_penalty": 1,
"vehicle_activation_penalty": 1,
"vehicles_duration": 1
},
"properties": {
"disable": {
"duration_groups": false,
"durations": false,
"initial_solution": false,
"stop_duration_multipliers": false
},
"maximum_time_horizon": 15552000
},
"validate": {
"disable": {
"resources": false,
"start_time": false
},
"enable": {
"matrix": false,
"matrix_asymmetry_tolerance": 20
}
}
},
"solve": {
"duration": 10000000000,
"iterations": 50,
"parallel_runs": 1,
"plateau": {
"absolute_threshold": -1,
"delay": 0,
"duration": 0,
"iterations": 0,
"relative_threshold": 0
},
"run_deterministically": true,
"solver": {
"plan_group_size": {
"delta": 0,
"delta_after_iterations": 1000000000,
"max_value": 2,
"min_value": 2,
"snap_back_after_improvement": true,
"start_value": 2,
"zigzag": true
},
"unplan_units": {
"delta": 2,
"delta_after_iterations": 125,
"max_value": -1,
"min_value": 2,
"snap_back_after_improvement": true,
"start_value": 2,
"zigzag": true
},
"unplan_weights": "Vehicle:3,Island:1,Location:293"
},
"start_solutions": 1
}
},
"solutions": [
{
"objective": {
"name": "1 * vehicles_duration + 1 * unplanned_penalty",
"objectives": [
{
"base": 335,
"factor": 1,
"name": "vehicles_duration",
"value": 335
},
{
"factor": 1,
"name": "unplanned_penalty",
"value": 0
}
],
"value": 335
},
"unplanned": [],
"vehicles": [
{
"id": "v1",
"route": [
{
"cumulative_travel_duration": 0,
"stop": {
"id": "Kiyomizu-dera",
"location": {
"lat": 34.994857,
"lon": 135.78506
}
},
"travel_duration": 0
}
],
"route_duration": 0,
"route_travel_duration": 0
},
{
"id": "v2",
"route": [
{
"cumulative_travel_duration": 0,
"stop": {
"id": "Nijō Castle",
"location": {
"lat": 35.014239,
"lon": 135.748134
}
},
"travel_duration": 0
},
{
"cumulative_travel_distance": 6700,
"cumulative_travel_duration": 335,
"stop": {
"id": "Fushimi Inari Taisha",
"location": {
"lat": 34.967146,
"lon": 135.772695
}
},
"travel_distance": 6700,
"travel_duration": 335
}
],
"route_duration": 335,
"route_travel_distance": 6700,
"route_travel_duration": 335
}
]
}
],
"statistics": {
"result": {
"custom": {
"activated_vehicles": 2,
"max_duration": 0.123,
"max_stops_in_vehicle": 2,
"max_travel_duration": 0.123,
"min_duration": 0.123,
"min_stops_in_vehicle": 1,
"min_travel_duration": 0.123,
"unplanned_stops": 0
},
"duration": 0.123,
"value": 0.123
},
"run": {
"duration": 0.123,
"iterations": 50
},
"schema": "v1"
},
"version": {
"sdk": "VERSION"
}
}