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

engine offers the following options to interact with custom measures:

`ValueFunctionMeasures`

. Modify the measures that represent the routing cost being optimized (used to obtain the best solution).`TravelTimeMeasures`

. Modify the measures used to calculate the route durations and the estimated time of arrival/departure when using the Windows or Shifts option.`TravelTimeMeasures`

must not account for any service times. Service times have to be added using Services option.

These options require a list of measures per vehicle. 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 - we have customers using Open Source Routing Machine (OSRM), Google Maps Distance Matrix API, GraphHopper and proprietary internal mapping services.

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]`

When creating your own custom

`TravelTimeMeasure`

, please make sure that it does not account for any service times and use the`Services`

option instead.

- If
`ValueFunctionMeasures`

and/or`TravelTimeMeasures`

are not provided, the`router`

engine will default to a Haversine measure for distance calculations and assume a constant speed of 10 m/s for duration. Note, this default speed can be changed using the Velocities option. - 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.

## Example

The introductory router example is used as a base, where routes are created to visit seven landmarks in Kyoto using two vehicles. Both `ValueFunctionMeasures`

and `TravelTimeMeasures`

options are set to a Haversine measure that calculates duration using a constant speed of 6 m/s. Also we are using the `Shifts`

option. The short time windows for the shifts force the solver to find a solution with two routes with the given speed.

Save the following information in an `input.json`

file (see input and output for more information on working with input.

The following program uses the CLI Runner to obtain a solution and requires access to the Nextmv code repository on GitHub. To request access, please contact support@nextmv.io.

To proceed with running the example, create a `main.go`

file and use the code snippet below. To create the measure, points are passed to it. These points are indexed following the hint given above, where all the stops are listed first and the vehicles after. Note that since vehicle locations are not given, corresponding points take on the zero value.

To execute the example, specify the path to the `input.json`

file using command-line flags and use jq to extract the solution state (see runners for more information on building and running programs).

The solution should look similar to this one:

You can see that `v1`

and `v2`

both receive about half of the stops. One of the stops has a hard window of 15 minutes. Given the shift constraint of 1800 seconds (30 minutes), neither vehicle can service all stops within the given time frame.

## 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. For example:

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.

### 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. `ByPoint`

measures implement the following method:

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 and implement the following method:

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:

`measure.Bin`

: select from a slice of measures by some function`measure.Location`

: adds fixed location costs to another measure`measure.Constant`

: always returns the same cost`measure.Override`

: overrides some other measure given a condition`measure.Power`

: takes some other measure to a power`measure.Scale`

: scales some other measure by a constant`measure.Sum`

: adds the costs of other measures together`measure.Truncate`

: truncates cost values provided by another measure`measure.Location`

: adds cost of visiting a location to another measure

See the go package docs for more information on these additional index measures.

## Triangularity

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

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 the `cluster`

, `vehicle`

, `fleet`

and `router`

engines to calculate the distance between two locations.

The haversine measure is simple to construct:

## Euclidean

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.

The euclidean measure is simple to construct:

## Taxicab

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.

The Taxicab measure is simple to construct:

## Matrix

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.

The Matrix measure can be constructed as:

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

In addition to the Matrix measure, Nextmv also provies a Sparse matrix measure. The Sparse matrix measure 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 dataset*. If two locations do not have an associated cost, then a backup measure is used.

The Sparse matrix measure requires a `ByIndex`

measure and arcs as input, and can be constructed as:

## Routingkit

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 `extend/measure/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 and
- matrix measures that pre-compute all costs between pairs of points up-front.

To instanætiate 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).

Here are examples of the ByPoint measures:

These can then be queried like any `ByPoint`

measure:

Matrix measures are instantiated similarly to the ByPoint measures, except their constructors also receive slices of source and destination points.

In each constructor, 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 to each constructor 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, `routingkit.MaxDistance`

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

After that the travel profile must be specified. We included our own profiles that help you setting up your measure. You can choose one of the following standard profiles:

`routingkit.Car()`

`routingkit.Bike()`

`routingkit.Truck()`

`routingkit.Pedestrian()`

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 final argument to each constructor - 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 `routingkit.MaxDistance`

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 `routingkit.MaxDistance`

, for example by throwing an error when this value is encountered.

### Custom vehicle profiles

The following code example shows how to create your own vehicle profile and use it with routingkit. It customizes the vehicle speed and makes it depend on the tags present. In this example the speed is fixed to a single value (defined in `customVehicleSpeedMapper`

). Furthermore, only ways are allowed to be used by the `customVehicle`

which have the highway tag and its value is motorway (defined in `customVehicleTagMapFilter`

). Please refer to the OpenStreetMaps documentation on ways to learn more about tags and their values.

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.

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

Note: 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.

Here is a minimal example of how to create a `client`

and `request`

, assuming the points are in the form `{longitude, latitude}`

:

Distance and duration matrices can be constructed with the functions provided in the package.

Once the measures have been created, you may estimate the distances and durations by calling the Cost function:

If the measure is properly set up, the above code snippets should print a similar result to this one, which is in the format `(from, to) = [distance, duration]`

:

## HERE

Note: 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.

The following example shows how to create a `Client`

, assuming the points are in the form `{longitude, latitude}`

.

Distance and duration matrices can be constructed with the functions provided in the package.

All of these matrix-constructing functions take a context as their first parameter, which can be used to cancel a request cycle while it is in progress. For example, it is a good general practice to use this context to impose a timeout.

These functions will use a synchronous request flow if the number of points requested is below HERE's size limit for synchronous API calls - otherwise, HERE's asynchronous flow will automatically be used.

The matrix functions also take a variadic list of `MatrixOption`

s that configure how HERE will calculate the routes. For example, this code constructs a DistanceMeasure with a specific departure time for a bicycle:

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

.

Once the measures have been created, you may estimate the distances and durations by calling the `Cost`

function:

If the measure is properly set up, the above code snippets should print a similar result to this one, which is in the format `(from, to) = [distance, duration]`

:

## OSRM

Open Source Routing Machine (OSRM) provides a REST service that can be queried to find shortest paths in road networks. We provide a ByIndex type measure located in package `github.com/nextmv-io/code/extend/measure/osrm`

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.

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 (see below), 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 can now use your client to construct a measure. You will need to decide upfront whether to calculate costs using either distances (in meters), durations (in seconds), or both. The third argument (`parallelQueries`

) specifies the number of parallel queries to be made. You can use 0 to calculate a default, based on the number of points given.