measure

Documentation

Overview

Package measure contains cost measures based on indices or points.

Measures

Engines models frequently need to 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". Engines provides a number of common patterns for constructing and using them inside models.

Point-to-Point Measures

When cost must be computed based on distance between two points, a model can use a measure.ByPoint implementation. These is the case for models where points are determined dynamically within the model logic, such as in k-means clustering. Such measures map two points to a cost.

cost := m.Cost(fromPoint, toPoint)

The following measure.ByPoint implementations are available.

measure.EuclideanByPoint: Euclidean distance between two points
measure.HaversineByPoint: Haversine distance between two points
measure.TaxicabByPoint:   Taxicab distance between two points

Unassigned 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

Models that do not require points operate on indices. These indices may or may not refer to points. An measure.ByIndex implementation provides the same functionality as a measure.ByPoint implementation, except its cost method accepts two indices instead of two points.

cost := m.Cost(fromIndex, toIndex)

Index measures are more common, and a number of them embed and operate on results from other index measures.

The following measure.ByIndex implementations are available.

measure.Bin:      select from a slice of measure by some function
measure.Location: adds fixed location costs to another measure
measure.Constant: always returns the same cost
measure.Matrix:   looks up cost from a row to a column index
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.Sparse:   sparse matrix measure with a backup
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

In addition, Engines provides measure.Indexed, which adapts any measure.ByPoint into a measure.ByIndex. In addition to the measure.ByPoint to be converted, Indexed accepts a fixed slice of points that it will use to look up the positions of indexes passed to Cost.

Index

• func ByClockwise(center Point, points []Point) sort.Interface
• func IsTriangular(m any) bool
• func LessClockwise(center, a, b Point) bool
• type ByIndex
  • func Bin(measures []ByIndex, selector func(from, to int) int) ByIndex
  • func Constant(c float64) ByIndex
  • func DebugOverride(defaultByIndex ByIndex, overrideByIndex ByIndex, ...) ByIndex
  • func DebugSparse(m ByIndex, arcs map[int]map[int]float64) ByIndex
  • func Indexed(m ByPoint, points []Point) ByIndex
  • func Location(m ByIndex, costs []float64, durationGroups DurationGroups) (ByIndex, error)
  • func Matrix(arcs [][]float64) ByIndex
  • func Override(defaultByIndex ByIndex, overrideByIndex ByIndex, ...) ByIndex
  • func Power(m ByIndex, exponent float64) ByIndex
  • func Scale(m ByIndex, constant float64) ByIndex
  • func Sparse(m ByIndex, arcs map[int]map[int]float64) ByIndex
  • func Sum(m ...ByIndex) ByIndex
  • func Truncate(m ByIndex, lower, upper float64) ByIndex
• type ByPoint
  • func ConstantByPoint(c float64) ByPoint
  • func EuclideanByPoint() ByPoint
  • func HaversineByPoint() ByPoint
  • func ScaleByPoint(m ByPoint, constant float64) ByPoint
  • func TaxicabByPoint() ByPoint
• type DependentByIndex
  • func DependentIndexed(timeDependent bool, cost func(from, to int, data *VehicleData) float64) DependentByIndex
• type DurationGroup
• type DurationGroups
  • func (dg DurationGroups) ToIndexGroup() (map[int]DurationGroup, error)
• type Point
• type Times
• type Triangular
• type VehicleData

Functions

func ByClockwise

func ByClockwise(center Point, points []Point) sort.Interface

ByClockwise implements sort.Interface for sorting points clockwise around a central point.

func IsTriangular

func IsTriangular(m any) bool

IsTriangular returns true if the triangle inequality holds for the provided measure.

func LessClockwise

func LessClockwise(center, a, b Point) bool

LessClockwise returns true if a is closer to a central point than b, and false if it is not.

Types

type ByIndex

type ByIndex interface {
	// Cost estimates the cost of going from one index to another.
	Cost(from, to int) float64
}

ByIndex estimates the cost of going from one index to another.

func Bin

func Bin(
	measures []ByIndex,
	selector func(from, to int) int,
) ByIndex

Bin is a measure that selects from a slice of indexed measures. Logic defined in the selector function determines which measure is used in the cost calculation.

func Constant

func Constant(c float64) ByIndex

Constant measure always estimates the same cost.

func DebugOverride

func DebugOverride(
	defaultByIndex ByIndex,
	overrideByIndex ByIndex,
	condition func(from, to int) bool,
) ByIndex

DebugOverride returns an Override that when marshalled will include debugging information describing the number of queries for default and override elements.

func DebugSparse

func DebugSparse(m ByIndex, arcs map[int]map[int]float64) ByIndex

DebugSparse returns a Sparse that when marshalled will include debugging information describing the number of queries for elements included in (and not included in) the matrix.

func Indexed

func Indexed(m ByPoint, points []Point) ByIndex

Indexed creates a ByIndex measure from the given ByPoint measure and wrapping the provided points.

func Location

func Location(
	m ByIndex,
	costs []float64,
	durationGroups DurationGroups,
) (ByIndex, error)

Location measure returns the sum of the cost computed by the passed in measure and the specified cost of the 'to' location. This cost is read from the passed in costs slice.

func Matrix

func Matrix(arcs [][]float64) ByIndex

Matrix measure returns pre-computed cost between two locations. Cost is assumed to be asymmetric.

func Override

func Override(
	defaultByIndex ByIndex,
	overrideByIndex ByIndex,
	condition func(from, to int) bool,
) ByIndex

Override measure uses a default measure for all arcs that are not true for a condition. It uses an override measure for all arcs that are true for the condition.

func Power

func Power(m ByIndex, exponent float64) ByIndex

Power raises the cost of some other measure to an exponent.

func Scale

func Scale(m ByIndex, constant float64) ByIndex

Scale the cost of some other measure by a constant.

func Sparse

func Sparse(m ByIndex, arcs map[int]map[int]float64) ByIndex

Sparse measure returns pre-computed costs between two locations without requiring a full data set. If two locations do not have an associated cost, then a backup measure is used.

func Sum

func Sum(m ...ByIndex) ByIndex

Sum adds other measures together.

func Truncate

func Truncate(m ByIndex, lower, upper float64) ByIndex

Truncate the cost of some other measure.

type ByPoint

type ByPoint interface {
	// Cost estimates the cost of going from one point to another.
	Cost(from, to Point) float64
}

ByPoint estimates the cost of going from one point to another.

func ConstantByPoint

func ConstantByPoint(c float64) ByPoint

ConstantByPoint measure always estimates the same cost.

func EuclideanByPoint

func EuclideanByPoint() ByPoint

EuclideanByPoint computes straight line distance connecting two indices.

func HaversineByPoint

func HaversineByPoint() ByPoint

HaversineByPoint estimates meters connecting two points along the surface of the earth.

func ScaleByPoint

func ScaleByPoint(m ByPoint, constant float64) ByPoint

ScaleByPoint scales an underlying measure by a constant.

func TaxicabByPoint

func TaxicabByPoint() ByPoint

TaxicabByPoint adds absolute distances between two points in all dimensions.

type DependentByIndex

type DependentByIndex interface {
	TimeDependent() bool
	Cost(
		from,
		to int,
		data *VehicleData,
	) float64
}

DependentByIndex estimates the cost of going from one index to another taking a point in time into account.

func DependentIndexed

func DependentIndexed(
	timeDependent bool,
	cost func(
		from,
		to int,
		data *VehicleData,
	) float64,
) DependentByIndex

DependentIndexed is a measure that uses a custom cost function to calculate parameter dependent costs for connecting two points by index. If the measures are time dependent all future stops in the sequence will be fully recalculated. Otherwise there will be a constant shift to achieve better performance.

type DurationGroup

type DurationGroup struct {
	Group    model.Domain
	Duration int
}

DurationGroup groups stops by index which have additional service costs attached to them.

type DurationGroups

type DurationGroups []DurationGroup

DurationGroups represents a slice of duration groups. Each duration group is used to account for additional service costs whenever a stop of a group is approached first.

func (DurationGroups) ToIndexGroup

func (dg DurationGroups) ToIndexGroup() (map[int]DurationGroup, error)

ToIndexGroup maps a location index to duration group to quickly access the corresponding group of a given location.

type Point

type Point []float64

Point represents a point in space. It may have any dimension.

type Times

type Times struct {
	EstimatedArrival      []int `json:"estimated_arrival,omitempty"`
	EstimatedServiceStart []int `json:"estimated_service_start,omitempty"`
	EstimatedDeparture    []int `json:"estimated_departure,omitempty"`
}

Times holds the estimated time of arrival (ETA), estimated time of when service starts (ETS) and estimated time of departure (ETD).

type Triangular

type Triangular interface {
	Triangular() bool
}

Triangular indicates that the triangle inequality holds for every measure that implements it.

type VehicleData

type VehicleData struct {
	VehicleID  string
	Times      Times
	Route      []int
	Index      int
	RouteValue int
}

VehicleData holds vehicle specific data, including times by index (ETA, ETD and ETS), a vehicle id, the vehicle's route and the solution value for that vehicle.