Measures (cost)

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:

google: Google Distance Matrix API and polylines from Google Maps Distance API.
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.
GraphHopper.
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.

Types of measures

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 ByIndex measure.

To convert a ByPoint to a ByIndex measure use the Indexed method.

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 OSRM client.
time-dependent: select a specific indexed measure from a given set of measures by the starting stops estimated time of departure.

Point-to-point measures

When cost must be computed based on distance between two points of any dimension, a model can use a ByPoint implementation.

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.

Indexed measures

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).

Composing and augmenting measures

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.

Triangularity

To determine the triangularity of a measure, use the IsTriangular function.

When using measures with Nextmv engines, you may need to consider the property of triangular inequality for ByIndex measures in particular.

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.

Haversine

To use a haversine measure, call the HaversineByPoint function.

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.

Euclidean

To use a euclidean measure, call the EuclideanByPoint function.

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.

Taxicab

To use a taxicab measure, call the TaxicabByPoint function.

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.

Matrix

To use a matrix measure, call the Matrix function.

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 (s1 and s2) and two vehicles (v1 and v2). Here is a sample Matrix measure:

Sparse matrix

To use a sparse matrix measure, call the Sparse function.

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:

Routingkit

To use a routingkit measure, call one of the routingkit functions.

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.

Please see the routingkit functions for more details and examples on how routingkit estimations can be obtained.

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).
In each routingkit function, the first argument is the path to an .osm.pbf file. The first time a routingkit measure is initialized with a particular osm filepath, a new file will be created in the same directory as the provided osm file. 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.pbf file, 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 .ch file is not already present, but this step will be skipped in the future if the .ch file persists between runs.
The next argument for a routingkit function 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 Cost function 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).
ByPoint measures 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-routingkit package. 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.
The goroutingkit.Profile needs 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: goroutingkit.VehicleMode, goroutingkit.BikeMode and goroutingkit.PedestrianMode.
- 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 goroutingkit.VehicleMode.
- 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 goroutingkit.VehicleMode.
- 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 TagMapFilter function.
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 Cost instead. 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 nil for 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.

How to deploy a routingkit-measure-based model to AWS Lambda

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).

Google

To use a google measure, call one of the google functions.

Pay special attention to the potential cost of using Google’s Distance Matrix API before completing your transaction.

The google package provides ByIndex type measures for estimating distances and durations using the Google Distance Matrix API. This measure is built on top of the matrix measure and it uses the Go client for Google Maps Services. A Google Maps client and request are required.

The 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.

HERE

To use a here measure, call one of the here functions.

Pay special attention to the potential cost incurred with HERE Maps before completing your transaction.

The 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.
Three MatrixOptions allow you to configure routes when using specific transport modes, and must be used with a compatible TransportMode option: WithTruckProfile(t Truck), WithScooterProfile(s Scooter), and WithTaxiProfile(t Taxi).

We recommend you visit the examples to understand how to build a HERE measure.

OSRM

To use an OSRM measure, call one of the osrm functions.

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.DefaultClient constructor, passing it the hostname of your OSRM server.
The second argument indicates whether a cache should be used. The resulting client has a SnapRadius method 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 DurationMatrix function, there is also a ScaleFactor method on the client which will multiply every duration returned from OSRM by the configured factor.
The MaxTableSize method 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 Polyline function 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.
The parallelQueries argument 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

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 time-dependent-measure template.

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.

Technical reference for route measures.