Measures

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.

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.

{
  "stops": [ 
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": ["v1", "v2"],
  "shifts": [
    {
      "start": "2020-10-17T09:00:00-06:00",
      "end": "2020-10-17T09:30:00-06:00"
    },
    {
      "start": "2020-10-17T09:00:00-06:00",
      "end": "2020-10-17T09:30:00-06:00"
    }
  ]
}

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.

package main

import (
    "github.com/nextmv-io/code/engines/measure"
    "github.com/nextmv-io/code/engines/route"
    "github.com/nextmv-io/code/hop/run/cli"
    "github.com/nextmv-io/code/hop/solve"
)

// Struct to read from JSON in.
type input struct {
    Stops    []route.Stop       `json:"stops,omitempty"`
    Vehicles []string           `json:"vehicles,omitempty"`
    Shifts   []route.TimeWindow `json:"shifts,omitempty"`
}

// Use the CLI runner to solve a Vehicle Routing Problem.
func main() {
    f := func(i input, opt solve.Options) (solve.Solver, error) {
        count := len(i.Stops)
        // Note that indices are created as [stop-1, ..., stop-n, 
        // vehicle-1-start, vehicle-1-end, ..., vehicle-m-start, vehicle-m-end]
        points := make([]measure.Point, count+2*len(i.Vehicles))
        for s, stop := range i.Stops {
            point := measure.Point{
                stop.Position.Lon,
                stop.Position.Lat,
            }

            points[s] = point
        }

        measures := make([]measure.ByIndex, len(i.Vehicles))
        timeMeasures := make([]measure.ByIndex, len(i.Vehicles))

        // Haversine measure and override cost of going to/from an empty
        // point.
        m := measure.Indexed(measure.HaversineByPoint(), points)
        m = measure.Override(
            m,
            measure.Constant(0),
            func(from, to int) bool {
                return points[from] == nil || points[to] == nil
            },
        )

        for v := range i.Vehicles {
            measures[v] = m
            // v1 and v2 have a speed of 6.0 m/s
            timeMeasures[v] = measure.Scale(m, 1/6.0)
        }

        router, err := route.NewRouter(
            i.Stops,
            i.Vehicles,
            route.ValueFunctionMeasures(measures),
            route.TravelTimeMeasures(timeMeasures),
            route.Shifts(i.Shifts),
        )
        if err != nil {
            return nil, err
        }

        return router.Solver(opt)
    }

    cli.Run(f)
}

go run main.go -hop.runner.input.path input.json | jq .state

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:

{
  "unassigned": [],
  "vehicles": [
    {
      "id": "v1",
      "route": [
        {
          "id": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          },
          "estimated_arrival": "2020-10-17T09:00:00-06:00",
          "estimated_departure": "2020-10-17T09:00:00-06:00"
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          },
          "estimated_arrival": "2020-10-17T09:09:07-06:00",
          "estimated_departure": "2020-10-17T09:09:07-06:00"
        },
        {
          "id": "Gionmachi",
          "position": {
            "lon": 135.775682,
            "lat": 35.002457
          },
          "estimated_arrival": "2020-10-17T09:12:27-06:00",
          "estimated_departure": "2020-10-17T09:12:27-06:00"
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          },
          "estimated_arrival": "2020-10-17T09:20:19-06:00",
          "estimated_departure": "2020-10-17T09:20:19-06:00"
        },
        {
          "id": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          },
          "estimated_arrival": "2020-10-17T09:25:15-06:00",
          "estimated_departure": "2020-10-17T09:25:15-06:00"
        }
      ],
      "route_duration": 1514
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          },
          "estimated_arrival": "2020-10-17T09:00:00-06:00",
          "estimated_departure": "2020-10-17T09:00:00-06:00"
        },
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          },
          "estimated_arrival": "2020-10-17T09:15:59-06:00",
          "estimated_departure": "2020-10-17T09:15:59-06:00"
        }
      ],
      "route_duration": 958
    }
  ]
}

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:

• point-to-point measures and
• indexed measures.

Each type is represented by a Go interface. Some engines may require a ByPoint measure while others use a ByIndex measure.

import "github.com/nextmv-io/code/engines/measure"

points := []measure.Point{...}
byPoint := measure.EuclideanByPoint()
byIndex := measure.Indexed(byPoint, points)

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:

Cost(from, to Point) float64

It returns the cost to travel from one point to another.

Indexed measures

ByIndex measures refer to an underlying list of points and implement the following method:

Cost(from, to int) float64

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.

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:

import "github.com/nextmv-io/code/engines/measure"

m := measure.HaversineByPoint()

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:

import "github.com/nextmv-io/code/engines/measure"

m := measure.EuclideanByPoint()

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:

m := measure.TaxicabByPoint()

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:

import "github.com/nextmv-io/code/engines/measure"

arcs := [][]float64{
    {0., 30.},
    {20., 0.},
}
m := measure.Matrix(arcs)

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:

import "github.com/nextmv-io/code/engines/measure"

arcs := [][]float64{
    {
        /*s1->s1*/ 0.,
        /*s1->s2*/ 1.,
        /*s1->v1-start*/ 2.,
        /*s1->v1-end*/ 3.,
        /*s1->v2-start*/ 4.,
        /*s1->v2-end*/ 5.,
    },
    {
        /*s2->s1*/ 1.,
        /*s2->s2*/ 0.,
        /*s2->v1-start*/ 2.,
        /*s2->v1-end*/ 3.,
        /*s2->v2-start*/ 4.,
        /*s2->v2-end*/ 5.,
    },
    {
        /*v1-start->s1*/ 1.,
        /*v1-start->s2*/ 2.,
        /*v1-start->v1-start*/ 0.,
        /*v1-start->v1-end*/ 3.,
        /*v1-start->v2-start*/ 4.,
        /*v1-start->v2-end*/ 5.,
    },
    {
        /*v1-end->s1*/ 1.,
        /*v1-end->s2*/ 2.,
        /*v1-end->v1-start*/ 3.,
        /*v1-end->v1-end*/ 0.,
        /*v1-end->v2-start*/ 4.,
        /*v1-end->v2-end*/ 5.,
    },
    {
        /*v2-start->s1*/ 1.,
        /*v2-start->s2*/ 2.,
        /*v2-start->v1-start*/ 3.,
        /*v2-start->v1-end*/ 4.,
        /*v2-start->v2-start*/ 0.,
        /*v2-start->v2-end*/ 5.,
    },
    {
        /*v2-end->s1*/ 1.,
        /*v2-end->s2*/ 2.,
        /*v2-end->v1-start*/ 3.,
        /*v2-end->v1-end*/ 4.,
        /*v2-end->v2-start*/ 4.,
        /*v2-end->v2-end*/ 0.,
    },
}
m := measure.Matrix(arcs)

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:

import "github.com/nextmv-io/code/engines/measure"

arcs := [][]float64{
    {10., 20.},
    {20., 30.},
}
fallback := measure.Matrix(arcs)
sparse := map[int]map[int]float64{
    0: {1: 30.},
    1: {0: 20.},
}
m := measure.Sparse(fallback, sparse)

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:

import (
    "github.com/nextmv-io/code/engines/measure"
    "github.com/nextmv-io/code/extend/measure/routingkit"
)

snapDistance := 1000
cacheSize := 1<<30
carProfile := routingkit.Car()
pedestrianProfile := routingkit.Pedestrian()
fallbackMeasure := measure.ScaleByPoint(measure.HaversineByPoint(), 1.3)
byPointDistance, err := routingkit.ByPoint(
   osmFile,
   snapDistance,
   cacheSize,
   carProfile,
   fallbackMeasure,
)
byPointDuration, err := routingkit.DurationByPoint(
   osmFile,
   snapDistance,
   cacheSize,
   pedestrianProfile,
   fallbackMeasure,
)

These can then be queried like any ByPoint measure:

import "github.com/nextmv-io/code/engines/measure"

cost := byPointDistance.Cost(
   measure.Point{-123.1041788,43.9965908},
   measure.Point{-123.0774532,44.044393},
)

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

import (
    "github.com/nextmv-io/code/engines/measure"
    "github.com/nextmv-io/code/extend/measure/routingkit"
)

srcs := []measure.Point{{-123.1041788,43.9965908}, {-123.1117056,44.0568198}},
dests := []measure.Point{{-123.0774532,44.044393}, {-123.0399395,44.0276874}},
distanceByIndex, err := routingkit.Matrix(
   osmFile,
   snapDistance,
   srcs,
   dests,
   routingkit.Car(),
   fallbackMeasure,
)
durationByIndex, err := routingkit.DurationMatrix(
   osmFile,
   snapDistance,
   srcs,
   dests,
   routingkit.Car(),
   fallbackMeasure,
)

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.

import (
    "github.com/nextmv-io/code/engines/measure"
    "github.com/nextmv-io/code/extend/measure/routingkit"
    goroutingkit "github.com/nextmv-io/go-routingkit/routingkit"
)

// CustomVehicle defines and returns a goroutingkit profile
func CustomVehicle() goroutingkit.Profile {
    return goroutingkit.NewProfile(
        "customVehicle", // Profile name
        // TransportationMode
        goroutingkit.VehicleMode, // Other values: BikeMode, PedestrianMode
        false, // Prevent left turns, only for TransportationMode "VehicleMode"
        false, // Prevent U-turns, only for TransportationMode "VehicleMode"
        customVehicleTagMapFilter,
        customVehicleSpeedMapper,
    )
}

// customVehicleTagMapFilter restricts ways to defined OSM way tags
func customVehicleTagMapFilter(id int, tags map[string]string) bool {
    highway := tags["highway"]
    return highway == "motorway"
}

// customVehicleSpeedMapper defines a speed per OSM way tag
func customVehicleSpeedMapper(_ int, tags map[string]string) int {
    return 10
}

func buildCustomMeasure() (measure.ByPoint, error) {
    fallbackMeasure := measure.ScaleByPoint(measure.HaversineByPoint(), 1.3)
    m, err := routingkit.DurationByPoint(
        "testdata/maryland.osm.pbf",
        1000,
        1<<30,
        CustomVehicle(),
        fallbackMeasure,
    )
    if err != nil {
        return nil, err
    }
    return m, nil
}

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:

import (
    "os"

    "github.com/aws/aws-sdk-go/aws"
    "github.com/aws/aws-sdk-go/aws/session"
    "github.com/aws/aws-sdk-go/service/s3"
    "github.com/aws/aws-sdk-go/service/s3/s3manager"
)

func download(bucket, key, file string) error {
    s, err := session.NewSession()
    if err != nil {
        return err
    }
    f, err := os.OpenFile(file, os.O_WRONLY|os.O_CREATE, 0655)
    if err != nil {
        return err
    }
    downloader := s3manager.NewDownloader(s)
    s3input := &s3.GetObjectInput{
        Bucket: aws.String(bucket),
        Key:    aws.String(key),
    }

    _, err = downloader.Download(f, s3input)

    return err
}

osmFile := `/tmp/region.osm.pbf`
chFile := `/tmp/region.ch`
if _, err := os.Stat(osmFile); os.IsNotExist(err) {
    download("bucket", "region.osm.pbf", osmFile)
}
if _, err := os.Stat(chFile); os.IsNotExist(err) {
    download("bucket", "region.ch", chFile)
}

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

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}:

import (
    "fmt"

    "googlemaps.github.io/maps"
)

points := [][2]float64{
    {-74.028297, 4.875835},
    {-74.046965, 4.872842},
    {-74.041763, 4.885648},
}
coords := make([]string, len(points))
for p, point := range points {
    coords[p] = fmt.Sprintf("%f,%f", point[1], point[0])
}
r := &maps.DistanceMatrixRequest{
    Origins:      coords,
    Destinations: coords,
}
c, err := maps.NewClient(maps.WithAPIKey("<your-api-key>"))
if err != nil {
    panic(err)
}

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

import "github.com/nextmv-io/code/extend/measure/google"

dist, dur, err := google.DistanceDurationMatrices(c, r)
if err != nil {
    panic(err)
}

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

import "fmt"

for p1 := range points {
    for p2 := range points {
        fmt.Printf(
            "(%d, %d) = [%.2f, %.2f]\n",
            p1, p2, dist.Cost(p1, p2), dur.Cost(p1, p2),
        )
    }
}

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

(0, 0) = [0.00, 0.00]
(0, 1) = [6526.00, 899.00]
(0, 2) = [4889.00, 669.00]
(1, 0) = [5211.00, 861.00]
(1, 1) = [0.00, 0.00]
(1, 2) = [2260.00, 302.00]
(2, 0) = [3799.00, 638.00]
(2, 1) = [2260.00, 311.00]
(2, 2) = [0.00, 0.00]

HERE

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

import (
    "github.com/nextmv-io/code/engines/measure"
    "github.com/nextmv-io/code/extend/measure/here"
)

points := []measure.Point{
    {-74.028297, 4.875835},
    {-74.046965, 4.872842},
    {-74.041763, 4.885648},
}
cli := here.NewClient("<your-api-key>")

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

dist, dur, err := cli.DistanceDurationMatrices(ctx, points)
if err != nil {
    panic(err)
}

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.

import (
    "context"
    "time"
)

ctx, cancel := context.WithTimeout(context.Background(), time.Second * 5)
defer cancel()
dist, dur, err := cli.DistanceDurationMatrices(ctx, points)
if err != nil {
    panic(err)
}

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 MatrixOptions that configure how HERE will calculate the routes. For example, this code constructs a DistanceMeasure with a specific departure time for a bicycle:

import "github.com/nextmv-io/code/extend/measure/here"

dist, err : = cli.DistanceMatrix(
    ctx,
    points,
    here.WithTransportMode(here.Bicycle),
    here.WithDepartureTime(time.Date(2021, 12, 10, 8, 30, 0, 0, loc)),
)

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:

import "fmt"

for p1 := range points {
    for p2 := range points {
        fmt.Printf(
            "(%d, %d) = [%.2f, %.2f]\n",
            p1, p2, dist.Cost(p1, p2), dur.Cost(p1, p2),
        )
    }
}

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

(0, 0) = [0.00, 0.00]
(0, 1) = [6519.00, 791.00]
(0, 2) = [4884.00, 632.00]
(1, 0) = [5242.00, 580.00]
(1, 1) = [0.00, 0.00]
(1, 2) = [2270.00, 248.00]
(2, 0) = [3800.00, 493.00]
(2, 1) = [2270.00, 250.00]
(2, 2) = [0.00, 0.00]

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.

import "github.com/nextmv-io/code/extend/measure/osrm"

cli := osrm.DefaultClient(host, false)

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.

import (
    "github.com/nextmv-io/code/engines/measure"
    "github.com/nextmv-io/code/extend/measure/osrm"
)

distance, err := osrm.DistanceMatrix(
   cli,
   []measure.Point{{-118.397257,34.0258837}, {-118.5040938,33.9975221}},
   0,
)
duration, err := osrm.DurationMatrix(
   cli,
   []measure.Point{{-118.397257,34.0258837}, {-118.5040938,33.9975221}},
   0,
)
distance, duration, err = osrm.DistanceDurationMatrices(
   cli,
   []measure.Point{{-118.397257,34.0258837}, {-118.5040938,33.9975221}},
   0,
)