Measures determine the cost of connecting two things together. In routing this means the cost of going from one location to another. This cost can be calculated using a generic measure that simply computes distance or duration, but it can also represent any type of KPI as well, such as monetary value.
Nextmv provides several prebuilt measures and functionality to go with them. The measure interface is standardized, enabling measures to be used interchangeably within the engine. Nextmv can be used with any mapping service, for example:
here: HERE Matrix Routing API.
osrm: An OSRM server.
routingkit: offline Open Street Maps files (no server required).
time-dependent: Select a measure depending on the route for cost calculation.
- Other proprietary or internal mapping service.
When creating your own measure, it is very important to index stops and vehicles in the expected way. For the measure to work correctly, indices should be given following the format:
[stop-1, ..., stop-n, vehicle-1-start, vehicle-1-end, ..., vehicle-m-start, vehicle-m-end]
If you don't want the solver to consider the cost of going from one location to another, set the corresponding cost to be 0. For example, if vehicles don't have ending locations, the cost of going from a vehicle's end to any other location should be 0.
There are two types of measures:
Each type is represented by a Go interface. Some engines may require a
ByPoint measure while others use a
To convert a
ByPoint to a
ByIndex measure use the
Nextmv offers the following pre-built measures, and you can always create your own.
- Haversine: ByPoint measure that returns the haversine (great-circle) distance between two points.
- Euclidean: ByPoint measure that returns the euclidean distance between two points.
- Taxicab: ByPoint measure that returns the taxicab (Manhattan) distance between two points.
- Matrix: ByIndex measures to look up the cost of going from an origin index to a destination index, requiring a full dataset.
- Sparse matrix: the same as Matrix, but does not require a full dataset.
- Routingkit: measures to determine the shortest path between points on road networks; it does not require a client.
- Google: ByIndex measures to determine the shortest path between points on road networks using Google's Distance Matrix API.
- Here: ByIndex measures to determine the shortest path between points on road networks using the Here Maps API.
- OSRM: ByIndex measures to determine the shortest path between points on road networks; it requires an
time-dependent: select a specific indexed measure from a given set of measures by the starting stops estimated time of departure.
When cost must be computed based on distance between two points of any dimension, a model can use a
It returns the cost to travel from one point to another.
Points may be of any dimension. If the points passed in to any of these measures have differing dimensionality, they will project the lower dimension point into the higher dimension by appending 0s.
ByIndex measures refer to an underlying list of points, using indices. It returns the cost to travel from one point at a particular index in the list to another. A
ByIndex implementation provides the same functionality as a ByPoint implementation, except its cost method accepts two indices instead of two points.
Indexed measures are more common, and a number of them embed and operate on results from other indexed measures (see Composing and augmenting measures below).
In addition to the indexed measures detailed above, a number of ByIndex implementations are also available for augmenting or composing measures.
These additional implementations include:
Bin: select from a slice of measures by some function
Constant: always returns the same cost
Location: adds fixed location costs to another measure
Override: overrides some other measure given a condition
Power: takes some other measure to a power
Scale: scales some other measure by a constant
Sum: adds the costs of other measures together
Truncate: truncates cost values provided by another measure
Dependent: selects from a slice of measures by a function that has additional vehicle information such as ETA, ETD and ETS.
To determine the triangularity of a measure, use the
A measure is considered triangular if, for any three points, the cost of an arc between two of the points will always be less than the cost of an arc between those same two points and a third point. The
IsTriangular function reports whether a given
ByIndex measure upholds this property.
Some engines, such as
vehicle, assume the property of triangular inequality holds for the measures they work with in order to prune their search spaces and find better solutions. However, it also means that if the measure is not triangular, some feasible solutions may not be found by the solver. Whereas the euclidean and haversine measures uphold triangular inequality, the routingkit and OSRM measures may theoretically violate this, although this may be uncommon in practice.
To use a haversine measure, call the
The haversine measure provides more accurate distance estimates for points located on the Earth than a euclidean measure, given its curvature. The haversine formula determines the great-circle distance between two points on a sphere given their longitudes and latitudes. Important in navigation, it is a special case of a more general formula in spherical trigonometry, the law of haversines, that relates the sides and angles of spherical triangles.
Haversine is the default measure used by engines to calculate the distance between two locations.
To use a euclidean measure, call the
The euclidean measure finds the euclidean distance between two points, treating the arc between two points as a straight-line segment connecting them as on a grid. The formula for this measures is the square root of the sum of the squared differences of each dimension of the two points.
To use a taxicab measure, call the
Taxicab distance treats the path between two points as right angle straight lines (also referred to as "city block" or "Manhattan" distance). Here, the distance between two points is the sum of the absolute differences of their Cartesian coordinates. In Taxicab geometry (as opposed to Euclidean geometry), the hypotenuse is never traversed when computing distance.
To use a matrix measure, call the
Matrix is a ByIndex type measure that returns the cost from a row to a column index in a matrix of pre-computed costs (distances, durations, or other costs, e.g., distances with bike-ability level factored in) between two locations. Cost is assumed to be asymmetric.
Please note that when constructing a Matrix measure, you should account for all stops and vehicles' start and end locations in the correct order. Assume you have two stops (
s2) and two vehicles (
v2). Here is a sample Matrix measure:
To use a sparse matrix measure, call the
In addition to the Matrix measure, Nextmv also provides a Sparse matrix measure. The Sparse matrix is a ByIndex measure that returns the cost from a row to a column index in a matrix of pre-computed costs (distances, durations, or other costs, e.g., distances with bikeability level factored in) between two locations without requiring a full distance matrix. If two locations do not have an associated cost, then a backup measure is used. Use a sparse matrix measure whenever you have a lot of points that are sparsely connected. This helps to significantly reduce memory requirements of your application.
The Sparse matrix measure requires a
ByIndex measure and arcs as input, and can be constructed as:
To use a routingkit measure, call one of the
While haversine and euclidean measures can quickly estimate the cost of traveling between two points, these measures are limited in their accuracy because they don't take real-world road networks into account. The measures in the
routingkit package use mapping data from the OpenStreetMap (OSM) project to determine the cost of navigating from one point to another along the shortest possible path. Under the hood, the routingkit measure uses a Go wrapper we created for RoutingKit, an open source C++ library.
We provide two sets of measures:
- ByPoint: implementations that calculate the cost at query time.
- Matrix: measures that pre-compute all costs between pairs of points up-front.
Here are some details on the arguments that are passed to the
routingkit functions to create a measure.
To instantiate a routingkit measure, you'll need to have an OSM file that covers the region containing all the points your model may route to. Geofabrik hosts OSM files for broad geographic areas such as countries and U.S. states. If you are targeting a more specific area, the OSM export tool allows you to create OSM files covering a custom bounding box. Using a larger OSM file will increase the memory required by the routingkit measure (and thus, your model).
routingkitfunction, the first argument is the path to an
.osm.pbffile. The first time a routingkit measure is initialized with a particular
osmfilepath, a new file will be created in the same directory as the provided
osmfile. This file contains a data structure called a contraction hierarchy (CH), which contains indices that speed up queries. It will have the same base name as the
osm.pbffile, but will have an extension following the format
.osm.pbf_<car|pedestrian|bike>_<duration|distance>.ch. Building the contraction hierarchy will cause the routingkit measure to take longer to initialize if the
.chfile is not already present, but this step will be skipped in the future if the
.chfile persists between runs.
The next argument for a
routingkitfunction is the maximum snap distance. Because not all geocoordinates fall exactly on a road, such points will be "snapped" to the nearest location on the road network. But if the distance between the nearest road network point and the queried point is greater than the maximum snap distance, the routingkit measure's
Costfunction will return a sentinel value from the go-routingkit package, a maximum distance. This value is also returned in the event no route can be found between two points (for example, if the two points are connected by a restricted road).
ByPointmeasures cache costs between points in order to improve performance. The maximum memory used by this cache is configured by the third argument to these functions.
After that the travel profile must be specified. We included our own profiles that help you set up your measure. All profiles are exported by the
go-routingkitpackage. Using those profiles, routingkit will only use roads and ways that can actually be traversed by the form of transportation. The same way the standard profiles are created, you can create your own profiles and pass them into the constructor to match your specific routing requirements.
goroutingkit.Profileneeds 6 parameters to build a profile:
Name: The name of the profile
TransportationMode: The transportation mode pre-selects valid ways for the type of transportation. The valid options are:
Prevent left turns flag: This flag is used to allow or forbid left turns. It will only be used if the transportation mode is set to
Prevent U-turns flag: This flag is used to allow or forbid U-turns. It will only be used if the transportation mode is set to
TagMapFilter func: This function is used to create a map of allowed OSM way tags. Ways that do not pass the filter will not be used.
SpeedMapper func: This function is used to assign a speed value to every allowed way tag, defined in the
The final argument to each function - a fallback measure - allows you to override this default behavior when no road network path can be found between two points. If for any reason the max distance is returned as the cost for any two points, this fallback measure will be invoked with the points, and this fallback result will be returned from
Costinstead. For example, you may choose to fall back to a scaled Haversine measure or Manhattan measure to estimate distances in the event their exact road network route cannot be found.
If you pass
nilfor the fallback measure, it is up to you to handle costs of the maximum distance, for example by throwing an error when this value is encountered.
Deploying a model that uses the routingkit measure to AWS Lambda offers two challenges: OSM and CH files must be present on the file system when your model starts; and your model will require dynamic runtime linking to a C standard library.
Pre-build CH files (optional but recommended).
We recommend creating the CH file in advance and making it available via the file system using the same mechanism you use to provide the OSM file (discussed more below), so it does not need to be rebuilt on every model invocation, taking up unnecessary CPU time. You can prebuild a CH file for a particular OSM file simply by instantiating a routingkit measure.
Download OSM and CH files before the solver runs.
One simple solution is to store your CH files in S3, then copy them to
/tmp if they are not already present on each Lambda invocation. The
/tmp directory may persist between Lambda runs, so some runs may not need do the extra work of pulling down the OSM files. That said, pulling even large files from S3 into AWS Lambda should be very fast. Here is a code example:
Note that AWS Lambda's temporary directory has a size of 512MB. If your OSM and CH files jointly exceed this size, you will need to take another approach, like mounting an Amazon Elastic File System (EFS) into your Lambda.
Change your Lambda settings to use amazonlinux2.
Your binary will be built using CGO and the underlying RoutingKit C++ library must be able to dynamically link against a C standard library version that is compatible with the version the binary was built with. If glibc is the standard library implementation you use, version 2.26 or higher is required.
While the default AWS Lambda image has an older version of glibc, the amazonlinux 2 image includes glibc version 2.26. You can configure your Lambda to use this image by using the dropdown under Runtime to select "Provide your own bootstrap on Amazon Linux 2" when creating your lambda function. If creating your Lambda function with SAM, enter provided.al2 under the Runtime setting.
Note that your model binary also has to be linked against glibc version 2.26 at build time. An easy way to ensure this happens is to build your model in an amazonlinux:2 container. Alternatively, you could statically link your binary using musl (which would require musl to be linked as the C standard libary implementation at build time).
To use a google measure, call one of the
Pay special attention to the potential cost of using Google’s Distance Matrix API before completing your transaction.
request are required.
client uses an API key for authentication. At a minimum, the
request requires the origins and destinations to provide an estimate of distance and duration. You can also use the
Polylines function to retrieve polylines for a set of points from Google. The function returns a polyline from first to last point as well as a slice of polylines, one for each leg of the given points. All polylines are encoded in Google's polyline format.
We recommend you visit the examples to understand how to build a Google measure.
To use a here measure, call one of the
Pay special attention to the potential cost incurred with HERE Maps before completing your transaction.
here package provides ByIndex type measures for estimating distances and durations using the HERE Maps API. A HERE Maps
Client is required to make requests to the HERE Maps API. The
Client uses an API key for authentication.
Functions also take a variadic list of
MatrixOptions that configure how HERE will calculate the routes. Here are the available options (see the HERE API reference for more details about these options):
WithDepartureTime(t time.Time): this option sets the departure time that will be used for the calculated routes. If this option is not set (or is set to the zero-value), HERE will not consider traffic.
WithTransportMode(mode TransportMode): this configures the measure to use the appropriate transport mode - for example, the pedestrian transport mode allows pedestrian-exclusive paths to be taken when determining route lengths.
WithAvoidFeatures(features Feature): this option sets features such as toll roads that should be avoided in the routes HERE creates.
WithAvoidAreas(areas BoundingBox): takes a list of areas (defined by two latitude and two longitude values, forming a bounding box) that should be avoided by all calculated routes.
MatrixOptionsallow you to configure routes when using specific transport modes, and must be used with a compatible
WithScooterProfile(s Scooter), and
We recommend you visit the examples to understand how to build a HERE measure.
To use an OSRM measure, call one of the
osrm package provides an Open Source Routing Machine (OSRM) REST service that can be queried to find shortest paths in road networks. We include a ByIndex type measure located in the package that requests a matrix of point distances from an OSRM server. This measure is built on top of the matrix measure.
See the OSRM repo for information about setting up your server. You will need to be able to reach the service from the system your model will be deployed to.
Here are some considerations when instantiating and OSRM measure
- Call the
osrm.DefaultClientconstructor, passing it the hostname of your OSRM server.
- The second argument indicates whether a cache should be used. The resulting client has a
SnapRadiusmethod that can be used to configure a snapping radius for all points that aren't directly on the road network of or even outside the hosted area.
- If you are using OSRM to receive durations via the
DurationMatrixfunction, there is also a
ScaleFactormethod on the client which will multiply every duration returned from OSRM by the configured factor.
MaxTableSizemethod lets you set this parameter which will influence how requests will be sliced. If you set this value to the same value as with your OSRM server, the server will always be able to handle the requests coming from the client.
- You can also use the
Polylinefunction to retrieve polylines for a set of points from the OSRM server. The function returns a polyline from first to last point as well as a slice of polylines, one for each leg of the given points. All polylines are encoded in Google's polyline format.
- You will need to decide upfront whether to calculate costs using either distances (in meters), durations (in seconds), or both.
parallelQueriesargument specifies the number of parallel queries to be made. You can use 0 to calculate a default, based on the number of points given.
We recommend you visit the examples to understand how to build OSRM measures.
Time dependent measures is an implementation based on the DependentByIndex interface. By using a time dependent measure client you can create a DependentByIndex measure which implements a function to select the corresponding measure based on time. When querying the cost going from A to B, the time relevant for selecting the measure is given by the estimated time of arrival of the starting stop A.
For an exmaple implementation you can have a look at the
If you need to make your measure dependent on something else than time you can implement your on selection function to use the DependentByIndex interface.