Search…
Measures
Overview of measures for your custom app.

Overview

Measures determine the cost of connecting two things together. This may mean assigning one item to another, clustering two points together, or routing a vehicle from one location to another. These cost computations are generically referred to as "measures". Nextmv provides several prebuilt measures and functionality for composing and augmenting measures.
Costs determined by measures (e.g., distance or time traveled) are used in Nextmv engines as part of the value function to make decisions. The measure interface is standardized, enabling measures to be used interchangeably within an engine.
Most measures are defined in the package github.com/nextmv-io/code/engines/measure. Measures that rely on external dependencies, are found in the package github.com/nextmv-io/code/extend/measure.
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.

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:
Go
1
points := []measure.Point{...}
2
byPoint := measure.EuclideanByPoint()
3
byIndex := measure.Indexed(byPoint, points)
Copied!

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:
Go
1
Cost(from, to Point) float64
Copied!
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:
Go
1
Cost(from, to int) float64
Copied!
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).

Available measures

The following measures are available with your Nextmv custom app:
  • Euclidean: ByPoint measure that returns the euclidean distance between two points.
  • Google: ByIndex measures to determine the shortest path between points on road networks using Google's Distance Matrix API.
    • google.DistanceDurationMatrices: returns the distance and duration matrices on the road network.
  • Here: ByIndex measures to determine the shortest path between points on road networks using the Here Maps API; it requires a Here client.
    • here.DistanceMatrix: returns the distance matrix on the road network.
    • here.DurationMatrix: returns the duration matrix on the road network.
    • here.DistanceDurationMatrices: returns the distance and duration matrices on the road network.
  • Haversine: ByPoint measure that returns the haversine
  • Matrix: ByIndex measures to look up the cost of going from an origin index to a destination index.
    • Normal matrix: requires a full dataset.
    • Sparse matrix: does not require a full dataset. (great-circle) distance between two points.
  • OSRM: ByIndex measures to determine the shortest path between points on road networks; it requires an OSRM client.
    • osrm.DistanceMatrix: returns the distance matrix on the road network.
    • osrm.DurationMatrix: returns the duration matrix on the road network.
    • osrm.DistanceDurationMatrices: returns the distance and duration matrices on the road network.
  • Routingkit: measures to determine the shortest path between points on road networks; it does not require a client.
    • routingkit.ByPoint: ByPoint measure that returns the distance between points of the road network.
    • routingkit.DurationByPoint: ByPoint measure that returns the duration between points of the road network.
    • routingkit.Matrix: ByIndex measure that returns the distance matrix on the road network.
    • routingkit.DurationMatrix: ByIndex measure that returns the duration matrix on the road network.
  • Taxicab: ByPoint measure that returns the taxicab (Manhattan) distance between two points.

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.
Last modified 1mo ago