Documentation ¶
Overview ¶
Package route provides vehicle routing functionalities. Routing models direct vehicles from some start location to an end location, servicing other locations along the way. These locations often represent customer requests, though they may logically correspond to any number of things. Such models attempt to service all locations optimizing a value, such as minimizing cost.
Router ¶
The Router API provides a convenient interface for solving vehicle routing problems. It employs a hybrid solver that relies on decision diagrams and ALNS. To use it, invoke the Router by passing stops and vehicles.
router, err := route.NewRouter(stops, vehicles)
The Router can be configured through options. It is composable, meaning that several options (or none at all) could be used. Every option, unless otherwise noted, can be used independently of others. An example of this is setting vehicle start locations.
router, err := route.NewRouter(stops, vehicles, route.Starts(starts))
For convenience, options can also be configured after the Router is declared through the Options function. An example of this is setting vehicle end locations.
err := router.Options(route.Ends(ends))
The Router is built on top of the `store` package for solving decision automation problems. As such, the Solver function is used to obtain the Solver that searches for a Solution.
solver, err := router.Solver(store.DefaultOptions())
Retrieve the routing plan -made up of the vehicle routes and any unassigned stops- directly by calling the Last Solution on the Solver, for example.
solution := solver.Last(context.Background()) s := solution.Store plan := router.Plan() vehicles := plan.Get(s).Vehicles // On each vehicle call .Route unassigned := plan.Get(s).Unassigned
The Router can be paired with a Runner for convenience, to read data and options and manage the call to the Solver directly. Please see the documentation of the `store` and `run` packages for more information.
package main import ( "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/run" "github.com/nextmv-io/sdk/store" ) type input struct { Stops []route.Stop `json:"stops"` Vehicles []string `json:"vehicles"` Capacities []int `json:"capacities"` Quantities []int `json:"quantities"` Precedences []route.Job `json:"precedences"` } func main() { handler := func(i input, opt store.Options) (store.Solver, error) { router, err := route.NewRouter( i.Stops, i.Vehicles, // Add all options, or none. route.Capacity(i.Quantities, i.Capacities), route.Precedence(i.Precedences), ) if err != nil { return nil, err } return router.Solver(opt) // Options are passed by the runner. } run.Run(handler) }
Given that the Router works with a Store (used for any type of decisions), vehicle routing problems can be embedded into broader decision problems. E.g.: determine the number of vehicles that minimize the cost of routing. The Store defines a Variable x holding the number of vehicles. To estimate the cost of adding an additional vehicle, the Router is used to estimate the total cost. The problem is operationally valid if all stops are assigned.
package main import ( "context" "strconv" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/run" "github.com/nextmv-io/sdk/store" ) type input struct { Stops []route.Stop `json:"stops"` } // Rough pseudo-code that shouldn't be run. func main() { handler := func(i input, opt store.Options) (store.Solver, error) { // Declare a new store of variables. s := store.New() // Outer decision: number of vehicles represented by an integer // variable. x := store.NewVar(s, 0) // Modify the main store. s = s. Value(func(s store.Store) int { // Each vehicle has a cost => the value of the store is the // total cost. return x.Get(s) * 99 }). Generate(func(s store.Store) store.Generator { // Current number of vehicles. vehicles := make([]string, x.Get(s)) for i := 0; i < x.Get(s); i++ { vehicles[i] = strconv.Itoa(i) } // Embedded decision: summon the router and its solver. router, err := route.NewRouter( i.Stops, vehicles, ) if err != nil { return nil } solver, err := router.Solver(opt) if err != nil { return nil } // Get the solution to the routing problem. Estimate the // cost and obtain the unassigned stops. solution := solver.Last(context.Background()) plan := router.Plan() unassigned := plan.Get(solution.Store).Unassigned routingCost := solution.Statistics.Value return store.Lazy( func() bool { // Use some generating condition, such as generating // children stores as long as there are unassigned // stops. return len(unassigned) > 0 }, func() store.Store { return s. // Add another vehicle. Apply(x.Set(x.Get(s) + 1)). // Modify the value of the Store. Value(func(s store.Store) int { return *routingCost }). // Operationally valid if all stops are assigned. Validate(func(s store.Store) bool { return len(unassigned) == 0 }) }, ) }) // Minimize the total cost. return s.Minimizer(opt), nil } run.Run(handler) }
Measures ¶
Routing 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". The package 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 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 ByPoint implementations are available.
EuclideanByPoint: Euclidean distance between two points HaversineByPoint: Haversine distance between two points TaxicabByPoint: Taxicab distance between two points
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 ¶
Models that do not require points operate on indices. These indices may or may not refer to points. An ByIndex implementation provides the same functionality as a 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 ByIndex implementations are available.
Bin: select from a slice of measure by some function Location: adds fixed location costs to another measure Constant: always returns the same cost Matrix: looks up cost from a row to a column index Override: overrides some other measure given a condition Power: takes some other measure to a power Scale: scales some other measure by a constant Sparse: sparse matrix measure with a backup Sum: adds the costs of other measures together Truncate: truncates cost values provided by another measure Location: adds cost of visiting a location to another measure
In addition, the package provides Indexed, which adapts any ByPoint into a ByIndex. In addition to the ByPoint to be converted, Indexed accepts a fixed slice of points that it will use to look up the positions of indices passed to Cost.
Deprecated: This package is deprecated and will be removed in the next major release. Use github.com/nextmv-io/sdk/nextroute instead.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Threads(1)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
Index ¶
- func ByClockwise(center Point, points []Point) sort.Interfacedeprecated
- func IsTriangular(m any) booldeprecated
- func LessClockwise(center, a, b Point) booldeprecated
- func NewTimeDependentMeasure(startTime int, measures []ByIndexAndTime, fallback measure.ByIndex) (measure.DependentByIndex, error)deprecated
- type Alternatedeprecated
- type Attributesdeprecated
- type Backlogdeprecated
- type ByIndexdeprecated
- func Bin(measures []measure.ByIndex, selector func(from, to int) int) ByIndexdeprecated
- func Constant(c float64) ByIndexdeprecated
- func DebugOverride(defaultByIndex ByIndex, overrideByIndex ByIndex, ...) ByIndexdeprecated
- func Indexed(m ByPoint, points []Point) ByIndexdeprecated
- func Location(m ByIndex, costs []float64, durationGroups DurationGroups) (ByIndex, error)deprecated
- func Matrix(arcs [][]float64) ByIndexdeprecated
- func Override(defaultByIndex ByIndex, overrideByIndex ByIndex, ...) ByIndexdeprecated
- func OverrideZeroPoints(points []Point, m ByIndex) ByIndexdeprecated
- func Power(m ByIndex, exponent float64) ByIndexdeprecated
- func Scale(m ByIndex, constant float64) ByIndexdeprecated
- func Sparse(m ByIndex, arcs map[int]map[int]float64) ByIndexdeprecated
- func Sum(m ...measure.ByIndex) ByIndexdeprecated
- func Truncate(m ByIndex, lower, upper float64) ByIndexdeprecated
- func Unique(m ByIndex, references []int) ByIndexdeprecated
- type ByIndexAndTimedeprecated
- type ByIndexLoaderdeprecated
- type ByPointdeprecated
- func ConstantByPoint(c float64) ByPointdeprecated
- func EuclideanByPoint() ByPointdeprecated
- func HaversineByPoint() ByPointdeprecated
- func ScaleByPoint(m ByPoint, constant float64) ByPointdeprecated
- func TaxicabByPoint() ByPointdeprecated
- type ByPointLoaderdeprecated
- type DependentByIndexdeprecated
- type DurationGroupdeprecated
- type DurationGroupsdeprecated
- type Jobdeprecated
- type Limitdeprecated
- type Optiondeprecated
- func Alternates(alternates []Alternate) Optiondeprecated
- func Attribute(vehicles []Attributes, stops []Attributes) Optiondeprecated
- func Backlogs(backlogs []Backlog) Optiondeprecated
- func Capacity(quantities []int, capacities []int) Optiondeprecated
- func Constraint(constraint VehicleConstraint, ids []string) Optiondeprecated
- func Ends(ends []Position) Optiondeprecated
- func Filter(compatible func(vehicle, location int) bool) Optiondeprecated
- func FilterWithRoute(...) Optiondeprecated
- func Grouper(groups [][]string) Optiondeprecated
- func InitializationCosts(initializationCosts []float64) Optiondeprecated
- func LimitDistances(maxDistances []float64, ignoreTriangular bool) Optiondeprecated
- func LimitDurations(maxDurations []float64, ignoreTriangular bool) Optiondeprecated
- func Limits(routeLimits []Limit, ignoreTriangular bool) Optiondeprecated
- func Maximize() Optiondeprecated
- func Minimize() Optiondeprecated
- func MultiWindows(windows [][]TimeWindow, maxWaitTimes []int) Optiondeprecated
- func Precedence(precedences []Job) Optiondeprecated
- func Selector(selector func(PartialPlan) model.Domain) Optiondeprecated
- func ServiceGroups(serviceGroups []ServiceGroup) Optiondeprecated
- func Services(serviceTimes []Service) Optiondeprecated
- func Shifts(shifts []TimeWindow) Optiondeprecated
- func Sorter(...) Optiondeprecated
- func Starts(starts []Position) Optiondeprecated
- func Threads(threads int) Optiondeprecated
- func TravelDistanceMeasures(travelDistanceMeasures []measure.ByIndex) Optiondeprecated
- func TravelTimeDependentMeasures(timeMeasures []measure.DependentByIndex) Optiondeprecated
- func TravelTimeMeasures(timeMeasures []measure.ByIndex) Optiondeprecated
- func Unassigned(penalties []int) Optiondeprecated
- func Update(v VehicleUpdater, f PlanUpdater) Optiondeprecated
- func ValueFunctionDependentMeasures(valueFunctionMeasures []measure.DependentByIndex) Optiondeprecated
- func ValueFunctionMeasures(valueFunctionMeasures []measure.ByIndex) Optiondeprecated
- func Velocities(velocities []float64) Optiondeprecated
- func Windows(windows []Window) Optiondeprecated
- type PartialPlandeprecated
- type PartialVehicledeprecated
- type Plandeprecated
- type PlanUpdaterdeprecated
- type PlannedStopdeprecated
- type PlannedVehicledeprecated
- type Pointdeprecated
- type Positiondeprecated
- type Routerdeprecated
- type Service
- type ServiceGroupdeprecated
- type Stopdeprecated
- type TimeWindowdeprecated
- type Timesdeprecated
- type Triangulardeprecated
- type VehicleConstraintdeprecated
- type VehicleDatadeprecated
- type VehicleUpdaterdeprecated
- type Windowdeprecated
Examples ¶
- Package
- Alternates
- Attribute
- Backlogs
- Bin
- Capacity
- Constant
- ConstantByPoint
- Constraint
- DebugOverride
- DependentIndexed
- Ends
- EuclideanByPoint
- Filter
- FilterWithRoute
- Grouper
- HaversineByPoint
- Indexed
- InitializationCosts
- IsTriangular
- LimitDistances
- LimitDurations
- Limits
- Matrix
- Maximize
- Minimize
- MultiWindows
- NewRouter
- Override
- Power
- Precedence
- Router (Format)
- Router (Options)
- Router (Plan)
- Scale
- Selector
- ServiceGroups
- Services
- Shifts
- Sorter
- Sparse
- Starts
- Sum
- TaxicabByPoint
- Threads
- TravelDistanceMeasures
- TravelTimeMeasures
- Truncate
- Unassigned
- Update
- ValueFunctionMeasures
- Velocities
- Windows
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ByClockwise
deprecated
added in
v0.20.0
ByClockwise implements sort.Interface for sorting points clockwise around a central point.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func IsTriangular
deprecated
added in
v0.20.4
IsTriangular returns true if the triangle inequality holds for the provided measure. It returns false if the measure does not implement the Triangular interface or the triangle inequality does not hold.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
Check if some of the measures hold for the triangle inequality.
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { // Haversine measure. haversine := route.HaversineByPoint() fmt.Println(route.IsTriangular(haversine)) // Euclidean measure. euclidean := route.EuclideanByPoint() fmt.Println(route.IsTriangular(euclidean)) // Matrix measure. matrix := route.Matrix([][]float64{}) fmt.Println(route.IsTriangular(matrix)) }
Output: true true false
func LessClockwise
deprecated
added in
v0.20.0
LessClockwise returns true if a is closer to a central point than b, and false if it is not.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func NewTimeDependentMeasure
deprecated
added in
v0.21.1
func NewTimeDependentMeasure( startTime int, measures []ByIndexAndTime, fallback measure.ByIndex, ) (measure.DependentByIndex, error)
NewTimeDependentMeasure returns a new NewTimeDependentMeasure which implements a cost function. It takes a startTime (e.g. vehicle start) byIndexAndTime measures, where each measure is given with an endTime (exclusive) up until the measure will be used and a fallback measure.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Types ¶
type Alternate
deprecated
Alternate represents alternate stops, a list of stops for a vehicle.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Attributes
deprecated
Attributes holds the ID of a vehicle or stop and corresponding compatibility attributes for that vehicle/stop.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Backlog
deprecated
Backlog represents the backlog, a list of stops for a vehicle.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type ByIndex
deprecated
ByIndex estimates the cost of going from one index to another.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func Bin
deprecated
added in
v0.20.0
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { constant1 := route.Constant(1.234) constant2 := route.Constant(4.321) bin := route.Bin( []route.ByIndex{constant1, constant2}, func(from, to int) int { if from == 0 && to == 1 { return 0 } return 1 }, ) fmt.Println(bin.Cost(0, 1)) fmt.Println(bin.Cost(1, 0)) }
Output: 1.234 4.321
func Constant
deprecated
Constant measure always estimates the same cost.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { constant := route.Constant(1.234) fmt.Println(constant.Cost(1, 0)) fmt.Println(constant.Cost(0, 0)) fmt.Println(constant.Cost(0, 1)) }
Output: 1.234 1.234 1.234
func DebugOverride
deprecated
added in
v0.20.0
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { defaultByIndex := route.Constant(1.234) overrideByIndex := route.Constant(4.321) condition := func(from, to int) bool { return from > 0 } override := route.DebugOverride( defaultByIndex, overrideByIndex, condition, ) fmt.Println(override.Cost(0, 0)) fmt.Println(override.Cost(0, 1)) fmt.Println(override.Cost(1, 0)) }
Output: 1.234 1.234 4.321
func Indexed
deprecated
Indexed creates a ByIndex measure from the given ByPoint measure and wrapping the provided points.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { haversineByPoint := route.HaversineByPoint() points := []route.Point{ {135.772695, 34.967146}, {135.78506, 34.994857}, } indexed := route.Indexed(haversineByPoint, points) fmt.Println(int(indexed.Cost(0, 1))) }
Output: 3280
func Location
deprecated
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func Matrix
deprecated
added in
v0.20.0
Matrix measure returns pre-computed cost between two locations. Cost is assumed to be asymmetric.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.Matrix([][]float64{ { 0, 1, }, }) cost := byPoint.Cost(0, 0) fmt.Println(int(cost)) cost = byPoint.Cost(0, 1) fmt.Println(int(cost)) }
Output: 0 1
func Override
deprecated
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { defaultByIndex := route.Constant(1.234) overrideByIndex := route.Constant(4.321) condition := func(from, to int) bool { return from > 0 } override := route.Override( defaultByIndex, overrideByIndex, condition, ) fmt.Println(override.Cost(0, 0)) fmt.Println(override.Cost(0, 1)) fmt.Println(override.Cost(1, 0)) }
Output: 1.234 1.234 4.321
func OverrideZeroPoints
deprecated
added in
v0.20.10
OverrideZeroPoints overrides points that have been passed as placeholders [0,0] to build the matrix with zero values.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func Power
deprecated
added in
v0.20.0
Power raises the cost of some other measure to an exponent.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.Power(route.Constant(2), 2) cost := byPoint.Cost(0, 1) fmt.Println(int(cost)) }
Output: 4
func Scale
deprecated
Scale the cost of some other measure by a constant.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byIndex := route.Constant(1.234) scaled := route.Scale(byIndex, 2.0) fmt.Println(scaled.Cost(0, 1)) }
Output: 2.468
func Sparse
deprecated
added in
v0.20.0
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { costMap := make(map[int]map[int]float64) costMap[0] = map[int]float64{} costMap[0][1] = 10 byPoint := route.Sparse(route.Constant(1), costMap) cost := byPoint.Cost(0, 1) fmt.Println(int(cost)) cost = byPoint.Cost(1, 2) fmt.Println(int(cost)) }
Output: 10 1
func Sum
deprecated
added in
v0.20.0
Sum adds other measures together.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.Sum(route.Constant(2), route.Constant(1)) cost := byPoint.Cost(0, 1) fmt.Println(int(cost)) }
Output: 3
func Truncate
deprecated
added in
v0.20.0
Truncate the cost of some other measure.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { truncatedByUpper := route.Truncate(route.Constant(10), 1, 8) cost := truncatedByUpper.Cost(0, 1) fmt.Println(int(cost)) truncatedByLower := route.Truncate(route.Constant(0), 1, 8) cost = truncatedByLower.Cost(0, 1) fmt.Println(int(cost)) }
Output: 8 1
func Unique
deprecated
added in
v1.0.3
Unique returns a ByIndex that uses a reference slice to map the indices of a point to the index of the measure. m represents a matrix of unique points. references maps a stop (by index) to an index in m.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type ByIndexAndTime
deprecated
added in
v0.21.1
ByIndexAndTime holds a Measure and an EndTime (exclusive) up until this measure is to be used as a Unix timestamp. ByIndexAndTime is to be used with NewTimeDependentMeasure which a slice of ByIndexAndTime.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type ByIndexLoader
deprecated
added in
v0.20.2
type ByIndexLoader struct {
// contains filtered or unexported fields
}
ByIndexLoader can be embedded in schema structs and unmarshals a ByIndex JSON object into the appropriate implementation.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func (ByIndexLoader) MarshalJSON
deprecated
added in
v0.20.2
func (l ByIndexLoader) MarshalJSON() ([]byte, error)
MarshalJSON returns the JSON representation for the underlying Byindex.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func (*ByIndexLoader) To ¶ added in v0.20.2
func (l *ByIndexLoader) To() ByIndex
To returns the underlying ByIndex.
func (*ByIndexLoader) UnmarshalJSON
deprecated
added in
v0.20.2
func (l *ByIndexLoader) UnmarshalJSON(b []byte) error
UnmarshalJSON converts the bytes into the appropriate implementation of ByIndex.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type ByPoint
deprecated
ByPoint estimates the cost of going from one point to another.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func ConstantByPoint
deprecated
ConstantByPoint measure always estimates the same cost.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.ConstantByPoint(1.234) measure := byPoint.Cost( route.Point{135.772695, 34.967146}, route.Point{135.78506, 34.994857}, ) fmt.Println(measure) }
Output: 1.234
func EuclideanByPoint
deprecated
added in
v0.20.0
func EuclideanByPoint() ByPoint
EuclideanByPoint computes straight line distance connecting two indices.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.EuclideanByPoint() cost := byPoint.Cost( route.Point{135.772695, 34.967146}, route.Point{135.78506, 34.994857}, ) fmt.Println(int(cost * 1000)) }
Output: 30
func HaversineByPoint
deprecated
func HaversineByPoint() ByPoint
HaversineByPoint estimates meters connecting two points along the surface of the earth.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.HaversineByPoint() measure := byPoint.Cost( route.Point{135.772695, 34.967146}, route.Point{135.78506, 34.994857}, ) fmt.Println(int(measure)) }
Output: 3280
func ScaleByPoint
deprecated
added in
v0.20.2
ScaleByPoint scales the cost of some other measure by a constant.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func TaxicabByPoint
deprecated
added in
v0.20.0
func TaxicabByPoint() ByPoint
TaxicabByPoint adds absolute distances between two points in all dimensions.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "github.com/nextmv-io/sdk/route" ) func main() { byPoint := route.TaxicabByPoint() cost := byPoint.Cost( route.Point{135.772695, 34.967146}, route.Point{135.78506, 34.994857}, ) fmt.Println(int(cost * 1000)) }
Output: 40
type ByPointLoader
deprecated
added in
v0.20.2
type ByPointLoader struct {
// contains filtered or unexported fields
}
ByPointLoader can be embedded in schema structs and unmarshals a ByPoint JSON object into the appropriate implementation.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func (ByPointLoader) MarshalJSON
deprecated
added in
v0.20.2
func (l ByPointLoader) MarshalJSON() ([]byte, error)
MarshalJSON returns the JSON representation for the underlying ByPoint.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func (*ByPointLoader) To
deprecated
added in
v0.20.2
func (l *ByPointLoader) To() ByPoint
To returns the underlying ByPoint.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func (*ByPointLoader) UnmarshalJSON
deprecated
added in
v0.20.2
func (l *ByPointLoader) UnmarshalJSON(b []byte) error
UnmarshalJSON converts the bytes into the appropriate implementation of ByPoint.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type DependentByIndex
deprecated
added in
v0.21.1
type DependentByIndex = measure.DependentByIndex
DependentByIndex is a measure uses a custom cost func to calculate parameter dependent costs for connecting to points by index.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func DependentIndexed
deprecated
added in
v0.21.1
func DependentIndexed( timeDependent bool, cost func( from, to int, data *measure.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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
Example ¶
package main import ( "fmt" "time" "github.com/nextmv-io/sdk/route" ) func main() { t := time.Now() indexed1 := route.Constant(1000) indexed2 := route.Scale(indexed1, 2) measures := []route.ByIndex{indexed1, indexed2} endTimes := []time.Time{ t.Add(2000 * time.Second), t.Add(5000 * time.Second), } byIndex := make([]route.ByIndexAndTime, len(measures)) for i, m := range measures { byIndex[i] = route.ByIndexAndTime{ Measure: m, EndTime: int(endTimes[i].Unix()), } } etds := []int{ int(t.Add(500 * time.Second).Unix()), int(t.Add(3000 * time.Second).Unix()), } dependentMeasure, err := route.NewTimeDependentMeasure( int(t.Unix()), byIndex, measures[0], ) if err != nil { panic(err) } fmt.Println(dependentMeasure.Cost(0, 1, &route.VehicleData{ Index: 0, Times: route.Times{ EstimatedDeparture: etds, }, })) fmt.Println(dependentMeasure.Cost(1, 0, &route.VehicleData{ Index: 1, Times: route.Times{ EstimatedDeparture: etds, }, })) }
Output: 1000 2000
type DurationGroup
deprecated
type DurationGroup = measure.DurationGroup
DurationGroup groups stops by index which have additional service costs attached to them.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type DurationGroups
deprecated
type DurationGroups = measure.DurationGroups
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type Job
deprecated
type Job struct { PickUp string `json:"pick_up,omitempty"` DropOff string `json:"drop_off,omitempty"` }
Job represents a combination of one pick-up and one drop-off that must be served together with the pick-up preceding the drop-off.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Limit
deprecated
Limit holds a measure which will be limited by the given value.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Option
deprecated
An Option configures a Router.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
func Alternates
deprecated
Alternates sets a slice of alternate stops per vehicle. The vehicle will be assigned exactly one stop from the list of alternate stops, which are passed into this option, and any other stops from the list of stops that solve the TSP/VRP cost optimally.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. Alternate stops are configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } alt := []route.Alternate{ { VehicleID: "v1", Stops: []string{"Kiyomizu-dera", "Gionmachi"}, }, } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Alternates(alt)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } } ], "route_duration": 1189, "route_distance": 11882 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Attribute
deprecated
func Attribute(vehicles []Attributes, stops []Attributes) Option
Attribute sets a compatibility filter for stops and vehicles. It takes two arguments, vehicles and stops which define a slice of compatibility attributes for stops and vehicles. Stops that are not provided are compatible with any vehicle. Vehicles that are not provided are only compatible with stops without attributes.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. An attribute compatibility filter is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define compatibility attributes. vehicleAttributes := []route.Attributes{ { ID: "v1", Attributes: []string{"Cooling System"}, }, { ID: "v2", Attributes: []string{"Large"}, }, } stopAttributes := []route.Attributes{ { ID: "Fushimi Inari Taisha", Attributes: []string{"Cooling System"}, }, { ID: "Arashiyama Bamboo Forest", Attributes: []string{"Large"}, }, { ID: "Kinkaku-ji", Attributes: []string{"Large"}, }, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Attribute(vehicleAttributes, stopAttributes), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 909, "route_distance": 9089 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } } ], "route_duration": 575, "route_distance": 5752 } ] }
func Backlogs
deprecated
Backlogs sets the backlog for the specified vehicles. A backlog is an unordered list of stops that a vehicle has to serve.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. One vehicle has a backlog.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define backlog for vehicle one. backlog := []route.Backlog{ { VehicleID: "v1", Stops: []string{"Kinkaku-ji", "Kyoto Imperial Palace"}, }, } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Backlogs(backlog)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Capacity
deprecated
Capacity adds a capacity constraint to the list of constraints and takes two arguments: quantities and capacities. Quantities represent the change in vehicle capacity indexed by stop. Capacities represent the maximum capacity indexed by vehicle. The quantities and capacities must match the length of stops and vehicles, respectively. To specify multiple capacity constraints, this option may be used several times with the corresponding quantities and capacities.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. The stops have quantities that must be fulfilled. The vehicles have starting locations and a maximum capacity that they can service.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define vehicle start locations. starts := []route.Position{ {Lon: 135.737230, Lat: 35.043810}, // v1 {Lon: 135.771716, Lat: 34.951317}, // v2 } // Defines stop quantities and vehicle capacities. quantities := []int{ -1, // "Fushimi Inari Taisha" -1, // "Kiyomizu-dera" -3, // "Nijō Castle" -1, // "Kyoto Imperial Palace" -1, // "Gionmachi" -3, // "Kinkaku-ji" -3, // "Arashiyama Bamboo Forest" } capacities := []int{ 9, // v1 4, // v2 } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Starts(starts), route.Capacity(quantities, capacities), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "v1-start", "position": { "lon": 135.73723, "lat": 35.04381 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 1116, "route_distance": 11155 }, { "id": "v2", "route": [ { "id": "v2-start", "position": { "lon": 135.771716, "lat": 34.951317 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } } ], "route_duration": 908, "route_distance": 9084 } ] }
func Constraint
deprecated
func Constraint(constraint VehicleConstraint, ids []string) Option
Constraint sets a custom constraint for specified vehicles. It takes two arguments, the constraint to be applied and a list of vehicles, indexed by ID, to which the constraint shall be applied.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A custom constraint is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) // A custom type that implements Violated to fulfill the VehicleConstraint // interface. type CustomConstraint struct { count int } // Violated the method that must be implemented to be a used as a // VehicleConstraint. func (c CustomConstraint) Violated( vehicle route.PartialVehicle, ) (route.VehicleConstraint, bool) { violated := len(vehicle.Route()) > c.count if violated { return nil, true } return c, false } func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Create a custom constraint. constraint := CustomConstraint{count: 6} // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Threads(1), route.Constraint(constraint, []string{"v1", "v2"}), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 448, "route_distance": 4482 }, { "id": "v2", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 1086, "route_distance": 10858 } ] }
func Ends
deprecated
Ends sets the ending locations indexed by vehicle. The length must match the vehicles' length.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. The vehicles have starting and ending locations. Vehicle v1 starts at a point with no ending being set. Vehicle v2 starts and ends at the same geographical position. Endings could also be set as a standalone option.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define vehicle start and end locations. starts := []route.Position{ {Lon: 135.737230, Lat: 35.043810}, // v1 {Lon: 135.758794, Lat: 34.986080}, // v2 } ends := []route.Position{ {}, // v1 {Lon: 135.758794, Lat: 34.986080}, // v2 } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Starts(starts), route.Ends(ends), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "v1-start", "position": { "lon": 135.73723, "lat": 35.04381 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 664, "route_distance": 6637 }, { "id": "v2", "route": [ { "id": "v2-start", "position": { "lon": 135.758794, "lat": 34.98608 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "v2-end", "position": { "lon": 135.758794, "lat": 34.98608 } } ], "route_duration": 1484, "route_distance": 14834 } ] }
func Filter
deprecated
Filter adds a custom vehicle filter to the list of filters. A filter checks which location is in general compatible with a vehicle. If no filter is given all locations are compatible with all vehicles and, thus, any location can be inserted into any route.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A filter is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define a filter. In this example v2 is not compatible with the location 5 // and 6 filter := func(v, l int) bool { if v == 1 { // v2 if l == 6 || l == 5 { // "Arashiyama Bamboo Forest" and "Kinkaku-ji" return false } } return true } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Threads(1), route.Filter(filter)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get last solution and print JSON out. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } } ], "route_duration": 575, "route_distance": 5752 }, { "id": "v2", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 909, "route_distance": 9089 } ] }
func FilterWithRoute
deprecated
func FilterWithRoute( filter func( vehicleCandidates model.Domain, locations model.Domain, routes [][]int, ) model.Domain, ) Option
FilterWithRoute adds a new VehicleFilter. Compared to the Filter option, the FilterWithRoute option is more flexible. It defines a function that takes an IntDomain of candidate vehicles, an IntDomain of locations that will be assigned to a particular vehicle, and a slice of routes for all vehicles. It returns an IntDomain representing vehicles that cannot service the domain of locations.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A filter with route information is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/model" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define unassignment penalties to allow for unassigning stops penalties := []int{100000, 100000, 100000, 100000, 100000, 100000, 100000} // Define a filter. In this example a vehicle may not have more than 3 stops maxStops := 3 filter := func( vehicles, locations model.Domain, routes [][]int, ) model.Domain { vehiclesToRemove := model.NewDomain() locationCount := locations.Len() // Determine vehicles which can get the set of locations assigned iter := vehicles.Iterator() for iter.Next() { index := iter.Value() // Remove vehicle from options, if assigning the locations would // overflow the maximum number of stops (start&end do not count // towards maximum number of stops; negative maximum indicates // unlimited number of stops) if len(routes[index])-2+locationCount > maxStops { vehiclesToRemove = vehiclesToRemove.Add(index) } } return vehiclesToRemove } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Unassigned(penalties), route.FilterWithRoute(filter), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "vehicles": [ { "id": "v1", "route": [ { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 448, "route_distance": 4482 }, { "id": "v2", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } } ], "route_duration": 511, "route_distance": 5106 } ] }
func Grouper
deprecated
Grouper adds a custom location group to the list of location groups. When one or more groups of locations are defined, the router engine will ensure that all locations of a group will be assigned to the same route. If no groups are given, locations can be assigned together in the same routes without the need to assign any other locations to that route.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. Groups are configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define groups. groups := [][]string{ {"Fushimi Inari Taisha", "Kiyomizu-dera", "Nijō Castle"}, {"Gionmachi", "Kinkaku-ji", "Arashiyama Bamboo Forest"}, } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Grouper(groups)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1639, "route_distance": 16394 }, { "id": "v2", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } } ], "route_duration": 0, "route_distance": 0 } ] }
func InitializationCosts
deprecated
InitializationCosts set the vehicle initialization costs indexed by vehicle. The length must match the vehicles' length.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. Initialization costs are configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } initializationCosts := []float64{100000, 0} // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Threads(1), route.InitializationCosts(initializationCosts), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [], "route_duration": 0, "route_distance": 0 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1818, "route_distance": 18180 } ] }
func LimitDistances
deprecated
LimitDistances limits the distances of the routes by the given values. The values are indexed by vehicle and must be given in meters. To not limit a route to any value, use model.MaxInt.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A distance limit constraint is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define route limits. routeLimits := []float64{10000.0, 10000.0} ignoreTriangularity := true // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.LimitDistances(routeLimits, ignoreTriangularity), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 909, "route_distance": 9089 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } } ], "route_duration": 575, "route_distance": 5752 } ] }
func LimitDurations
deprecated
LimitDurations limits the the durations of the routes to the given values. The values are indexed by vehicle and must be given in seconds. To not limit a route to any value, use model.MaxInt.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A durations limit constraint is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define route limits. routeLimits := []float64{1000.0, 1000.0} ignoreTriangularity := true // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.LimitDurations(routeLimits, ignoreTriangularity), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 909, "route_distance": 9089 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } } ], "route_duration": 575, "route_distance": 5752 } ] }
func Limits
deprecated
Limits adds a route limit constraint to the list of constraints. The limit constraint can be used to limit the routes. The option takes two arguments: Firstly, the routeLimits struct which is indexed by vehicle and has two fields:
- The value in the unit of the given measure.
- The value to which the route is limited in the unit of the given measure. To not limit the route to any value, use model.MaxInt
Secondly, a flag to ignore the triangular inequality.
PLEASE NOTE: If you want to limit the route's duration or length please use the options LimitDistance and LimitDuration, respectively.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A limit constraint is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/model" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define route limits. routeLimits := []route.Limit{ { Measure: route.Constant(42.0), Value: 1000000, }, { Measure: route.Constant(42.0), Value: float64(model.MaxInt), }, } ignoreTriangularity := true // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Limits(routeLimits, ignoreTriangularity), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Maximize
deprecated
func Maximize() Option
Maximize sets the solver type of the router to maximize the value with a hybrid solver that uses decision diagrams and ALNS.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using one vehicle. The route distance is maximized.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Maximize()) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } } ], "route_duration": 4569, "route_distance": 45702 } ] }
func Minimize
deprecated
func Minimize() Option
Minimize is deprecated. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Minimize sets the solver type of the router to minimize the value with a hybrid solver that uses decision diagrams and ALNS. This is the default solver that the router engine uses.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using one vehicle. The route distance is minimized.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Minimize()) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1818, "route_distance": 18180 } ] }
func MultiWindows
deprecated
added in
v0.20.10
func MultiWindows(windows [][]TimeWindow, maxWaitTimes []int) Option
MultiWindows adds a time window constraint to the list of constraints. The method takes in multiple windows per stop, which are indexed by stop and represent several fixed time frames in which the stop must be served. Furthermore, a wait time per stop must be specified where -1 means that a vehicle may wait indefinitely until a window opens. Service times at the stops can be optionally added using the Services option.
PLEASE NOTE: this option requires using the Shift option.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles with mutiple time windows. The stops have time windows.
package main import ( "context" "encoding/json" "fmt" "time" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } serviceTimes := []route.Service{ { ID: "Gionmachi", Duration: 900, }, } // Define time windows for every stop. windows := [][]route.TimeWindow{ { { Start: time.Date(2020, 10, 17, 7, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 10, 0, 0, 0, time.UTC), }, { Start: time.Date(2020, 10, 17, 13, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, }, {}, {}, {}, {}, {}, {}, } maxWaitTimes := []int{900, 0, 0, 0, 0, 0, 0} // Define shifts for every vehicle shifts := []route.TimeWindow{ { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Services(serviceTimes), route.Shifts(shifts), route.MultiWindows(windows, maxWaitTimes), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 }, "estimated_arrival": "2020-10-17T09:05:33Z", "estimated_departure": "2020-10-17T09:05:33Z", "estimated_service": "2020-10-17T09:05:33Z" }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 }, "estimated_arrival": "2020-10-17T09:08:31Z", "estimated_departure": "2020-10-17T09:08:31Z", "estimated_service": "2020-10-17T09:08:31Z" }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 }, "estimated_arrival": "2020-10-17T09:13:15Z", "estimated_departure": "2020-10-17T09:28:15Z", "estimated_service": "2020-10-17T09:13:15Z" }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 }, "estimated_arrival": "2020-10-17T09:30:15Z", "estimated_departure": "2020-10-17T09:30:15Z", "estimated_service": "2020-10-17T09:30:15Z" }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 }, "estimated_arrival": "2020-10-17T09:35:43Z", "estimated_departure": "2020-10-17T09:35:43Z", "estimated_service": "2020-10-17T09:35:43Z" } ], "route_duration": 2143, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" } ], "route_duration": 0, "route_distance": 0 } ] }
func Precedence
deprecated
Precedence adds a precedence constraint to the list of constraints. It takes one argument as a slice of jobs. Each job defines a pick-up and drop-off by ID. The pick-up must precede the drop-off in the route.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. In addition precedences for stops are defined. The vehicles have no starting locations and no maximum capacity that they can service.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Defines precedences for stops. In each couple the first ID precedes the // second ID. precedences := []route.Job{ {PickUp: "Fushimi Inari Taisha", DropOff: "Kiyomizu-dera"}, {PickUp: "Nijō Castle", DropOff: "Kiyomizu-dera"}, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Precedence(precedences), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } } ], "route_duration": 1517, "route_distance": 15162 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Selector
deprecated
func Selector(selector func(PartialPlan) model.Domain) Option
Selector sets the given custom location selector. The location selector lets you define a function which selects the locations that will be inserted next into the solution. If no custom location selector is given, the location with the lowest index will be inserted next.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A custom selector is configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/model" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Stop score indexed by stop score := []int{5, 4, 6, 7, 3, 2, 1} // Define a location selector. This location selector looks for the highest // score of a stop among the not yet assigned stops and returns it, wrapped // in a model.Domain selector := func(p route.PartialPlan) model.Domain { index := -1 highestScore := 0 for _, l := range p.Unplanned().Slice() { if score[l] > highestScore { index = l highestScore = score[l] } } if index != -1 { return model.NewDomain(model.NewRange(index, index)) } return model.NewDomain() } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Threads(1), route.Selector(selector), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func ServiceGroups
deprecated
func ServiceGroups(serviceGroups []ServiceGroup) Option
ServiceGroups adds an additional service time for a group of stops. Whenever a stop in the group is visited from another stop that is not part of it, the specified duration is added.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A service group and starting locations are configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } serviceGroups := []route.ServiceGroup{ { Group: []string{"Gionmachi", "Kinkaku-ji"}, Duration: 300, }, } starts := []route.Position{ {Lon: 135.672009, Lat: 35.017209}, {Lon: 135.672009, Lat: 35.017209}, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.ServiceGroups(serviceGroups), route.Starts(starts), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "v1-start", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 2418, "route_distance": 18180 }, { "id": "v2", "route": [ { "id": "v2-start", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Services
deprecated
Services adds a service time to the given stops. For stops not in the slice, a service time of zero seconds is applied.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles with service times.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } serviceTimes := []route.Service{ { ID: "Fushimi Inari Taisha", Duration: 900, }, { ID: "Arashiyama Bamboo Forest", Duration: 900, }, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Services(serviceTimes), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 2143, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 900, "route_distance": 0 } ] }
func Shifts
deprecated
func Shifts(shifts []TimeWindow) Option
Shifts adds shifts to the vehicles. Shifts are indexed by vehicle and represent a time window on its shift's start and end time. When using the Windows option, using the Shifts option is required. Shifts are additionally used to:
- enable the calculation of the estimated arrival and departure at stops
- set the start time of the route when using the Windows option, given that time tracking is needed for the Window constraint.
If the Measures option is not used, a default Haversine measure will be used. If the TimeMeasures option is not used, the measures will be scaled with a constant velocity of 10 m/s.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by // github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles with shifts and service time.
package main import ( "context" "encoding/json" "fmt" "time" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } serviceTimes := []route.Service{ { ID: "Fushimi Inari Taisha", Duration: 900, }, } // Define shifts for every vehicle shifts := []route.TimeWindow{ { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Services(serviceTimes), route.Shifts(shifts), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 }, "estimated_arrival": "2020-10-17T09:05:33Z", "estimated_departure": "2020-10-17T09:05:33Z", "estimated_service": "2020-10-17T09:05:33Z" }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 }, "estimated_arrival": "2020-10-17T09:08:31Z", "estimated_departure": "2020-10-17T09:08:31Z", "estimated_service": "2020-10-17T09:08:31Z" }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 }, "estimated_arrival": "2020-10-17T09:13:15Z", "estimated_departure": "2020-10-17T09:13:15Z", "estimated_service": "2020-10-17T09:13:15Z" }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 }, "estimated_arrival": "2020-10-17T09:15:15Z", "estimated_departure": "2020-10-17T09:15:15Z", "estimated_service": "2020-10-17T09:15:15Z" }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 }, "estimated_arrival": "2020-10-17T09:20:43Z", "estimated_departure": "2020-10-17T09:35:43Z", "estimated_service": "2020-10-17T09:20:43Z" } ], "route_duration": 2143, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" } ], "route_duration": 0, "route_distance": 0 } ] }
func Sorter
deprecated
func Sorter( sorter func( p PartialPlan, locations model.Domain, vehicles model.Domain, random *rand.Rand, ) []int, ) Option
Sorter sets the given custom vehicle sorter. The vehicle sorter lets you define a function which returns the vehicle indices in a specific order. The underlying engine will try to assign the locations to each vehicle in that returned order.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A vehicle sorter is configured.
package main import ( "context" "encoding/json" "fmt" "math/rand" "sort" "github.com/nextmv-io/sdk/model" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Threads(1), route.Sorter( func(_ route.PartialPlan, _, vehicles model.Domain, _ *rand.Rand, ) []int { orderedVehicles := vehicles.Slice() // try to assign to the given vehicles in the reverse order sort.SliceStable(orderedVehicles, func(i, j int) bool { return orderedVehicles[i] > orderedVehicles[j] }) return orderedVehicles }), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 }, { "id": "v2", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 } ] }
func Starts
deprecated
Starts sets the starting locations indexed by vehicle. The length must match the vehicles' length.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. The vehicles have starting locations.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define vehicle start locations. starts := []route.Position{ {Lon: 135.737230, Lat: 35.043810}, // v1 {Lon: 135.771716, Lat: 34.951317}, // v2 } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Starts(starts)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "v1-start", "position": { "lon": 135.73723, "lat": 35.04381 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 664, "route_distance": 6637 }, { "id": "v2", "route": [ { "id": "v2-start", "position": { "lon": 135.771716, "lat": 34.951317 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 } }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 } } ], "route_duration": 1085, "route_distance": 10851 } ] }
func Threads
deprecated
Threads sets the number of threads that the internal solver uses. The router engine's solver is a hybrid solver that uses a Decision Diagram (DD) solver and various ALNS solvers with DD sub-solvers. If threads = 1, it means that only the first solver is used, which corresponds to pure DD. As a default, threads are calculated based on the number of machine processors, using the following expression: runtime.GOMAXPROCS(0) / 2.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. Use a single thread.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Threads(1)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func TravelDistanceMeasures
deprecated
added in
v0.22.1
TravelDistanceMeasures sets custom distance measures for every vehicle to calculate the travel distance, and should be indexed as such. If no distance measures are provided, a default haversine measure will be used to calculate distances between stops.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using custom distance measures.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } count := len(stops) points := make([]route.Point, count+2*len(vehicles)) for s, stop := range stops { point := route.Point{ stop.Position.Lon, stop.Position.Lat, } points[s] = point } measures := make([]route.ByIndex, len(vehicles)) // Haversine measure and override cost of going to/from an empty // point. m := route.Indexed(route.HaversineByPoint(), points) m = route.Override( m, route.Constant(0), func(from, to int) bool { return points[from] == nil || points[to] == nil }, ) for v := range vehicles { measures[v] = route.Scale(m, 10.0) } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.TravelDistanceMeasures(measures), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 124286 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func TravelTimeDependentMeasures
deprecated
added in
v0.21.1
func TravelTimeDependentMeasures(timeMeasures []measure.DependentByIndex) Option
TravelTimeDependentMeasures sets custom dependent time measures for every vehicle, and should be indexed as such. If no custom time measures are provided, a default time measure will be used, based on haversine using a velocity of 10 m/s if no custom velocities are given using the Velocities option. Time measures are used to:
- calculate travel time in the Window option and check if time windows are met.
- calculated route duration, the estimated time of arrival and departure at stops.
PLEASE NOTE: When defining a custom TravelTimeMeasure, this measure must not account for any service times. To account for services times please use the Services option.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by // github.com/nextmv-io/sdk/nextroute.
func TravelTimeMeasures
deprecated
TravelTimeMeasures sets custom time measures for every vehicle, and should be indexed as such. If no custom time measures are provided, a default time measure will be used, based on haversine using a velocity of 10 m/s if no custom velocities are given using the Velocities option. Time measures are used to:
- calculate travel time in the Window option and check if time windows are met.
- calculated route duration, the estimated time of arrival and departure at stops.
PLEASE NOTE: When defining a custom TravelTimeMeasure, this measure must not account for any service times. To account for services times please use the Services option.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by // github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles with shifts. Each vehicle has a travel time measure.
package main import ( "context" "encoding/json" "fmt" "time" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define time windows for every stop. windows := []route.Window{ {}, {}, {}, {}, { TimeWindow: route.TimeWindow{ Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 9, 15, 0, 0, time.UTC), }, MaxWait: -1, }, {}, {}, } // Define shifts for every vehicle shifts := []route.TimeWindow{ { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 9, 30, 0, 0, time.UTC), }, { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 9, 30, 0, 0, time.UTC), }, } count := len(stops) points := make([]route.Point, count+2*len(vehicles)) for s, stop := range stops { point := route.Point{ stop.Position.Lon, stop.Position.Lat, } points[s] = point } measures := make([]route.ByIndex, len(vehicles)) // Haversine measure and override cost of going to/from an empty // point. m := route.Indexed(route.HaversineByPoint(), points) m = route.Override( m, route.Constant(0), func(from, to int) bool { return points[from] == nil || points[to] == nil }, ) for v := range vehicles { // v1 and v2 have a speed of 7.0 m/s measures[v] = route.Scale(m, 1/7.0) } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.TravelTimeMeasures(measures), route.Shifts(shifts), route.Windows(windows), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 }, "estimated_arrival": "2020-10-17T09:07:49Z", "estimated_departure": "2020-10-17T09:07:49Z", "estimated_service": "2020-10-17T09:07:49Z" }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 }, "estimated_arrival": "2020-10-17T09:10:41Z", "estimated_departure": "2020-10-17T09:10:41Z", "estimated_service": "2020-10-17T09:10:41Z" }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 }, "estimated_arrival": "2020-10-17T09:17:27Z", "estimated_departure": "2020-10-17T09:17:27Z", "estimated_service": "2020-10-17T09:17:27Z" }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 }, "estimated_arrival": "2020-10-17T09:21:41Z", "estimated_departure": "2020-10-17T09:21:41Z", "estimated_service": "2020-10-17T09:21:41Z" }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 }, "estimated_arrival": "2020-10-17T09:29:37Z", "estimated_departure": "2020-10-17T09:29:37Z", "estimated_service": "2020-10-17T09:29:37Z" } ], "route_duration": 1777, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" } ], "route_duration": 0, "route_distance": 0 } ] }
func Unassigned
deprecated
Unassigned sets the unassigned penalties indexed by stop. The length must match the stops' length.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. The stops have unassigned penalties.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define unassigned penalties. penalties := []int{ 0, // "Fushimi Inari Taisha" 0, // "Kiyomizu-dera" 200000, // "Nijō Castle" 200000, // "Kyoto Imperial Palace" 200000, // "Gionmachi" 200000, // "Kinkaku-ji" 200000, // "Arashiyama Bamboo Forest" } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Unassigned(penalties), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [ { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } } ], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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 } } ], "route_duration": 795, "route_distance": 7946 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Update
deprecated
func Update(v VehicleUpdater, f PlanUpdater) Option
Update sets the collection of functions that are called when transitioning from one store to another in the router's Decision Diagram search for the best solution in the time alloted. Updating information is useful for two purposes:
- setting a custom value function (objective) that will be optimized.
- bookkeeping of custom data.
The option takes the following arguments:
- VehicleUpdater: replaces the value function of each vehicle. Can be nil if more than one vehicle is present.
- PlanUpdater: replaces the value function of the full plan. Can be nil if only one vehicle is present.
User-defined custom types must implement the interfaces. When routing multiple vehicles, the vehicleUpdater interface may be nil, if only information at the fleet level is updated.
To customize the value function that will be optimized, the third parameter in either of the interfaces must be true. If the last parameter is false, the default value is used and it corresponds to the configured measure.
To achieve efficient customizations, always try to update the components of the store that changed.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by // github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. A custom transition update is provided to keep track of locations: a type that maps a stop's ID to its route position. The value function for routing stops that are assigned to the vehicle is modified. To achieve this, the sample implementations of the VehicleUpdater and PlanUpdater interfaces are used.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) // Custom data to implement the VehicleUpdater interface. type vehicleData struct { stops []route.Stop score map[string]int Locations map[string]int `json:"locations,omitempty"` } // Track the index in the route for each stop. Customize value function to // incorporate the vehicle's score. func (d vehicleData) Update( p route.PartialVehicle, ) (route.VehicleUpdater, int, bool) { d.Locations = map[string]int{} route := p.Route() for i := 1; i < len(route)-1; i++ { stop := d.stops[route[i]] d.Locations[stop.ID] = i } vehicleID := p.ID() value := p.Value() * d.score[vehicleID] return d, value, true } // Custom data to implement the PlanUpdater interface. type planData struct { stops []route.Stop Locations map[string]int `json:"locations,omitempty"` vehicleValues map[string]int planValue int } // Track the index of the route for each stop in each vehicle route. Customize // value function to incorporate the custom vehicle engine's value. func (d planData) Update( pp route.PartialPlan, vehicles []route.PartialVehicle, ) (route.PlanUpdater, int, bool) { locations := make(map[string]int, len(d.Locations)) for stopdID, i := range d.Locations { locations[stopdID] = i } d.Locations = locations values := make(map[string]int, len(d.vehicleValues)) for vehicleID, i := range d.vehicleValues { values[vehicleID] = i } d.vehicleValues = values for _, vehicle := range vehicles { vehicleID := vehicle.ID() updater := vehicle.Updater().(vehicleData) for stopdID, i := range updater.Locations { d.Locations[stopdID] = i } value := vehicle.Value() d.planValue -= d.vehicleValues[vehicleID] d.vehicleValues[vehicleID] = value d.planValue += d.vehicleValues[vehicleID] } for it := pp.Unassigned().Iterator(); it.Next(); { location := it.Value() stop := d.stops[location] delete(d.Locations, stop.ID) } return d, d.planValue, true } func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Declare custom score and data types that implement the interfaces. score := map[string]int{ "v1": 10, "v2": 1, } v := vehicleData{ stops: stops, score: score, } f := planData{ stops: stops, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Update(v, f), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get last solution and print JSON out. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 }, { "id": "v2", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 1243, "route_distance": 12428 } ] }
func ValueFunctionDependentMeasures
deprecated
added in
v0.21.1
func ValueFunctionDependentMeasures( valueFunctionMeasures []measure.DependentByIndex, ) Option
ValueFunctionDependentMeasures sets custom dependent measures for every vehicle to calculate the overall solution costs, and should be indexed as such. If no custom measures are provided, a default haversine measure will be used to calculate costs (distances) between stops. Note that if your value function measures do represent time and you are using the window option with wait times, in order to see those wait times reflected in your value function, you will have to override the value function by using the `Update()` function. In the `Update()` function you can request a `TimeTracker` from the `state` and use it to get access to time information the route.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
func ValueFunctionMeasures
deprecated
ValueFunctionMeasures sets custom measures for every vehicle to calculate the overall solution costs, and should be indexed as such. If no custom measures are provided, a default haversine measure will be used to calculate costs (distances) between stops. Note that if your value function measures do represent time and you are using the window option with wait times, in order to see those wait times reflected in your value function, you will have to override the value function by using the `Update()` function. In the `Update()` function you can request a `TimeTracker` from the `state` and use it to get access to time information the route.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles with shifts. Each vehicle has a value function measure.
package main import ( "context" "encoding/json" "fmt" "time" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define time windows for every stop. windows := []route.Window{ {}, {}, {}, {}, { TimeWindow: route.TimeWindow{ Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 9, 15, 0, 0, time.UTC), }, MaxWait: -1, }, {}, {}, } // Define shifts for every vehicle shifts := []route.TimeWindow{ { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 9, 30, 0, 0, time.UTC), }, { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 9, 30, 0, 0, time.UTC), }, } count := len(stops) points := make([]route.Point, count+2*len(vehicles)) for s, stop := range stops { point := route.Point{ stop.Position.Lon, stop.Position.Lat, } points[s] = point } measures := make([]route.ByIndex, len(vehicles)) // Haversine measure and override cost of going to/from an empty // point. m := route.Indexed(route.HaversineByPoint(), points) m = route.Override( m, route.Constant(0), func(from, to int) bool { return points[from] == nil || points[to] == nil }, ) for v := range vehicles { // v1 and v2 have a speed of 7.0 m/s measures[v] = route.Scale(m, 1/7.0) } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.ValueFunctionMeasures(measures), route.Shifts(shifts), route.Windows(windows), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 }, "estimated_arrival": "2020-10-17T09:05:33Z", "estimated_departure": "2020-10-17T09:05:33Z", "estimated_service": "2020-10-17T09:05:33Z" }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 }, "estimated_arrival": "2020-10-17T09:08:31Z", "estimated_departure": "2020-10-17T09:08:31Z", "estimated_service": "2020-10-17T09:08:31Z" }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 }, "estimated_arrival": "2020-10-17T09:13:15Z", "estimated_departure": "2020-10-17T09:13:15Z", "estimated_service": "2020-10-17T09:13:15Z" }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 }, "estimated_arrival": "2020-10-17T09:15:15Z", "estimated_departure": "2020-10-17T09:15:15Z", "estimated_service": "2020-10-17T09:15:15Z" }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 }, "estimated_arrival": "2020-10-17T09:20:43Z", "estimated_departure": "2020-10-17T09:20:43Z", "estimated_service": "2020-10-17T09:20:43Z" } ], "route_duration": 1243, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" } ], "route_duration": 0, "route_distance": 0 } ] }
func Velocities
deprecated
Velocities sets the speed for all vehicles to define a corresponding TravelTimeMeasure based on haversine distance and is indexed by vehicle. The length must match the vehicles' length.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. Velocities for the travel time measure are configured.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } velocities := []float64{5, 7} // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles, route.Velocities(velocities)) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 2485, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ] }
func Windows
deprecated
Windows adds a time window constraint to the list of constraints. The method takes in windows, which are indexed by stop and represent a fixed timeframe in which the stop must be served. Service times at the stops can be optionally added using the Services option.
PLEASE NOTE: this option requires using the Shift option.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
Create routes to visit seven landmarks in Kyoto using two vehicles with shifts. The stops have time windows.
package main import ( "context" "encoding/json" "fmt" "time" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } serviceTimes := []route.Service{ { ID: "Gionmachi", Duration: 900, }, } // Define time windows for every stop. windows := []route.Window{ { TimeWindow: route.TimeWindow{ Start: time.Date(2020, 10, 17, 7, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 12, 0, 0, 0, time.UTC), }, MaxWait: 900, }, {}, {}, {}, {}, {}, {}, } // Define shifts for every vehicle shifts := []route.TimeWindow{ { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, { Start: time.Date(2020, 10, 17, 9, 0, 0, 0, time.UTC), End: time.Date(2020, 10, 17, 17, 0, 0, 0, time.UTC), }, } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Services(serviceTimes), route.Shifts(shifts), route.Windows(windows), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" }, { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 }, "estimated_arrival": "2020-10-17T09:05:33Z", "estimated_departure": "2020-10-17T09:05:33Z", "estimated_service": "2020-10-17T09:05:33Z" }, { "id": "Kyoto Imperial Palace", "position": { "lon": 135.762057, "lat": 35.025431 }, "estimated_arrival": "2020-10-17T09:08:31Z", "estimated_departure": "2020-10-17T09:08:31Z", "estimated_service": "2020-10-17T09:08:31Z" }, { "id": "Gionmachi", "position": { "lon": 135.775682, "lat": 35.002457 }, "estimated_arrival": "2020-10-17T09:13:15Z", "estimated_departure": "2020-10-17T09:28:15Z", "estimated_service": "2020-10-17T09:13:15Z" }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 }, "estimated_arrival": "2020-10-17T09:30:15Z", "estimated_departure": "2020-10-17T09:30:15Z", "estimated_service": "2020-10-17T09:30:15Z" }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 }, "estimated_arrival": "2020-10-17T09:35:43Z", "estimated_departure": "2020-10-17T09:35:43Z", "estimated_service": "2020-10-17T09:35:43Z" } ], "route_duration": 2143, "route_distance": 12428 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 }, "estimated_arrival": "2020-10-17T09:00:00Z", "estimated_departure": "2020-10-17T09:00:00Z", "estimated_service": "2020-10-17T09:00:00Z" } ], "route_duration": 0, "route_distance": 0 } ] }
type PartialPlan
deprecated
type PartialPlan interface { // Unassigned returns an Integer Domain with unassigned stop indices. // These are stops explicitly excluded from being served by a vehicle. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Unassigned() model.Domain // Unplanned returns an Integer Domain with not yet assigned or unassigned // stops indices. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Unplanned() model.Domain // Value return the value of this plan. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Value() int // Vehicles returns a slice of vehicles part of this partial plan. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Vehicles() []PartialVehicle }
PartialPlan is an (incomplete) Plan that operates on the internal solver data structures. Certain router options that customize solver internals have to work with this data structure.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type PartialVehicle
deprecated
type PartialVehicle interface { // ID returns the vehicle ID. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. ID() string // Updater returns either nil in case no custom VehicleUpdater was used or // the custom VehicleUpdater that was used for this vehicle. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Updater() VehicleUpdater // Route returns the route of the vehicle represented by a sequence of stop // indices. The first and last indices are always the starting and ending // locations of the vehicle, respectively. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Route() []int // Value return the value of vehicle. Usually this is the cost of the route. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Value() int // Times returns a the estimated time of arrival (ETA), estimated time of // when service starts (ETS) and estimated time of departure (ETD) for each // stop in the route. Usually ETA is the same as ETS, unless there is a // waiting time before a time window opens, which is when the service // actually starts (ETS). // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Times() measure.Times }
PartialVehicle represents a Vehicle that operates on the internal solver data structures. Certain router options that customize solver internals have to work with this data structure.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Plan
deprecated
type Plan struct { Unassigned []Stop `json:"unassigned"` Vehicles []PlannedVehicle `json:"vehicles"` }
Plan describes a solution to a Vehicle Routing Problem.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type PlanUpdater
deprecated
type PlanUpdater interface {
Update(PartialPlan, []PartialVehicle) (PlanUpdater, int, bool)
}
PlanUpdater defines an interface that is used to override the router's default value function. The Update function takes a Plan and a slice of PartialVehicles as an input and returns three values, a PlanUpdater with potentially updated bookkeeping data, a new solution value and a bool value to indicate wether the vehicle's solution value received an update. The second parameter is a slice of PartialVehicles which may have been updated. All vehicles not part of that slice have definitely not changed. This knowledge can be used to more efficiently update the value of a plan. See the documentation of route.Update() for example usage.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type PlannedStop
deprecated
type PlannedStop struct { Stop EstimatedArrival *time.Time `json:"estimated_arrival,omitempty"` EstimatedDeparture *time.Time `json:"estimated_departure,omitempty"` EstimatedService *time.Time `json:"estimated_service,omitempty"` }
PlannedStop describes a stop as part of a Vehicle's route of solution to a Vehicle Routing Problem.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type PlannedVehicle
deprecated
type PlannedVehicle struct { ID string `json:"id"` Route []PlannedStop `json:"route"` RouteDuration int `json:"route_duration"` RouteDistance int `json:"route_distance"` }
PlannedVehicle holds information about the vehicle in a solution to a Vehicle Routing Problem.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Point
deprecated
Point represents a point in space. It may have any dimension.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
func BuildMatrixRequestPoints
deprecated
added in
v0.20.10
BuildMatrixRequestPoints builds a slice of points in the correct format to request a matrix from any of the supported platforms (e.g. OSRM, Routingkit, Google, HERE). It takes the stops to be routed, start and end stops of vehicles (optional) and the number of to be used.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type Position
deprecated
Position represents a geographical location.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Router
deprecated
type Router interface { // Options configures the router with the given options. An error is // returned if validation issues exist. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Options(...Option) error // Solver receives solve options and returns a Solver interface. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Solver(store.Options) (store.Solver, error) /* Plan returns a variable which holds information about the current set of vehicles with their respective routes and any unassigned stops. The Plan variable can be used to retrieve the values from the Store of a Solution. router, err := route.NewRouter( stops, vehicles, route.Capacity(quantities, capacities), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } solution := solver.Last(context.Background()) s := solution.Store p := router.Plan() vehicles, unassigned := p.Get(s).Vehicles, p.Get(s).Unassigned Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by [github.com/nextmv-io/sdk/nextroute]. */ Plan() store.Var[Plan] // Format configures a custom output format for a solution. // // Deprecated: This package is deprecated and will be removed in the next major release. // It is used with the router engine which was replaced by // [github.com/nextmv-io/sdk/nextroute]. Format(func(*Plan) any) }
A Router is an engine that solves Vehicle Routing Problems.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example (Format) ¶
Create routes to visit seven landmarks in Kyoto using one vehicle. A custom output is provided. To achieve this, the router internal Format function is used.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{"v1", "v2"} // Declare the router and its solver. router, err := route.NewRouter(stops, vehicles) if err != nil { panic(err) } router.Format(func(p *route.Plan) any { m := make(map[string]int) m["num_routes"] = len(p.Vehicles) m["num_unassigned"] = len(p.Unassigned) return m }) solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get last solution and print JSON out. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "num_routes": 2, "num_unassigned": 0 }
Example (Options) ¶
Create routes to visit seven landmarks in Kyoto using two vehicles. The vehicles have starting locations. Endings are configured via the Options function in a separate step.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define vehicle start locations. starts := []route.Position{ {Lon: 135.737230, Lat: 35.043810}, // v1 {Lon: 135.758794, Lat: 34.986080}, // v2 } // Declare the router. Ends are omitted from the initial set of options. router, err := route.NewRouter(stops, vehicles, route.Starts(starts)) if err != nil { panic(err) } // Define ending locations and configure them as a separate step. ends := []route.Position{ {}, // v1 {Lon: 135.758794, Lat: 34.986080}, // v2 } err = router.Options(route.Ends(ends)) if err != nil { panic(err) } // Declare the solver. solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "v1-start", "position": { "lon": 135.73723, "lat": 35.04381 } }, { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 664, "route_distance": 6637 }, { "id": "v2", "route": [ { "id": "v2-start", "position": { "lon": 135.758794, "lat": 34.98608 } }, { "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": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "v2-end", "position": { "lon": 135.758794, "lat": 34.98608 } } ], "route_duration": 1484, "route_distance": 14834 } ] }
Example (Plan) ¶
Use the Plan func to get direct access to the underlying Store and variables.
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { // Define stops and vehicles. stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, { ID: "Kyoto Imperial Palace", Position: route.Position{Lon: 135.762057, Lat: 35.025431}, }, { ID: "Gionmachi", Position: route.Position{Lon: 135.775682, Lat: 35.002457}, }, { ID: "Kinkaku-ji", Position: route.Position{Lon: 135.728898, Lat: 35.039705}, }, { ID: "Arashiyama Bamboo Forest", Position: route.Position{Lon: 135.672009, Lat: 35.017209}, }, } vehicles := []string{ "v1", "v2", } // Define unassigned penalties. penalties := []int{ 0, // "Fushimi Inari Taisha" 0, // "Kiyomizu-dera" 200000, // "Nijō Castle" 200000, // "Kyoto Imperial Palace" 200000, // "Gionmachi" 200000, // "Kinkaku-ji" 200000, // "Arashiyama Bamboo Forest" } // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Unassigned(penalties), route.Threads(1), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem. last := solver.Last(context.Background()) plan := router.Plan().Get(last.Store) // Extract unassigned stops from the plan. unassigned := plan.Unassigned b, err := json.MarshalIndent(unassigned, "", " ") if err != nil { panic(err) } fmt.Println("--- unassigned") fmt.Println(string(b)) // Extract the routes from the plan. plannedVehicles := plan.Vehicles b, err = json.MarshalIndent(plannedVehicles, "", " ") if err != nil { panic(err) } fmt.Println("--- vehicles") fmt.Println(string(b)) }
Output: --- unassigned [ { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } }, { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } } ] --- vehicles [ { "id": "v1", "route": [ { "id": "Kinkaku-ji", "position": { "lon": 135.728898, "lat": 35.039705 } }, { "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 } } ], "route_duration": 795, "route_distance": 7946 }, { "id": "v2", "route": [ { "id": "Arashiyama Bamboo Forest", "position": { "lon": 135.672009, "lat": 35.017209 } } ], "route_duration": 0, "route_distance": 0 } ]
func NewRouter
deprecated
NewRouter returns a router interface. It receives a set of stops that must be serviced by a fleet of vehicles and a list of options. When an option is applied, an error is returned if there are validation issues. The router is composable, meaning that several options may be used or none at all. The options, unless otherwise noted, can be used independently of each other.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
Example ¶
package main import ( "context" "encoding/json" "fmt" "github.com/nextmv-io/sdk/route" "github.com/nextmv-io/sdk/store" ) func main() { stops := []route.Stop{ { ID: "Fushimi Inari Taisha", Position: route.Position{Lon: 135.772695, Lat: 34.967146}, }, { ID: "Kiyomizu-dera", Position: route.Position{Lon: 135.785060, Lat: 34.994857}, }, { ID: "Nijō Castle", Position: route.Position{Lon: 135.748134, Lat: 35.014239}, }, } vehicles := []string{ "v1", "v2", } quantities := []int{-1, -1, -1} capacities := []int{2, 2} // Declare the router and its solver. router, err := route.NewRouter( stops, vehicles, route.Capacity(quantities, capacities), ) if err != nil { panic(err) } solver, err := router.Solver(store.DefaultOptions()) if err != nil { panic(err) } // Get the last solution of the problem and print it. last := solver.Last(context.Background()) b, err := json.MarshalIndent(last.Store, "", " ") if err != nil { panic(err) } fmt.Println(string(b)) }
Output: { "unassigned": [], "vehicles": [ { "id": "v1", "route": [ { "id": "Kiyomizu-dera", "position": { "lon": 135.78506, "lat": 34.994857 } }, { "id": "Fushimi Inari Taisha", "position": { "lon": 135.772695, "lat": 34.967146 } } ], "route_duration": 328, "route_distance": 3280 }, { "id": "v2", "route": [ { "id": "Nijō Castle", "position": { "lon": 135.748134, "lat": 35.014239 } } ], "route_duration": 0, "route_distance": 0 } ] }
type Service ¶
Service is a deprecated struct. It is used with the router engine which was replaced by the nextroute engine.
Service holds the ID of a stop and corresponding time to service the stop in seconds.
type ServiceGroup
deprecated
type ServiceGroup struct { Group []string `json:"group,omitempty"` Duration int `json:"duration,omitempty"` }
ServiceGroup holds a group of stops and the service time duration (in seconds) to be added for every approach to one of the stops in the group.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Stop
deprecated
Stop to service in a Vehicle Routing Problem.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type TimeWindow
deprecated
type TimeWindow struct { Start time.Time `json:"start,omitempty"` End time.Time `json:"end,omitempty"` }
TimeWindow represents a time window for a shift of a vehicle or a stop.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Times
deprecated
Times holds the estimated time of arrival (ETA), the estimated time of when service starts (ETS) and estimated time of departure (ETD).
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type Triangular
deprecated
type Triangular = measure.Triangular
Triangular indicates that the triangle inequality holds for every measure that implements it.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type VehicleConstraint
deprecated
type VehicleConstraint interface { // Violated takes a PartialPlan and returns true if the vehicle with the // current route is not operationally valid. Often custom constraint hold // internal state. The first return value can be used to return a new // VehicleConstraint with updated state or nil in case the solution is not // operationally valid. Violated(PartialVehicle) (VehicleConstraint, bool) }
VehicleConstraint defines an interface that needs to be implemented when creating a custom vehicle constraint.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type VehicleData
deprecated
added in
v0.21.1
type VehicleData = measure.VehicleData
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.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/measure.
type VehicleUpdater
deprecated
type VehicleUpdater interface {
Update(PartialVehicle) (VehicleUpdater, int, bool)
}
VehicleUpdater defines an interface that is used to override the vehicle's default value function. The Update function takes a PartialVehicle as an input and returns three values, a VehicleUpdater with potentially updated bookkeeping data, a new solution value and a bool value to indicate wether the vehicle's solution value received an update. See the documentation of Update() for example usage.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.
type Window
deprecated
type Window struct { TimeWindow TimeWindow `json:"time_window,omitempty"` MaxWait int `json:"max_wait,omitempty"` }
Window represents a fixed timeframe in which the stop must be served. The duration represents the time it takes to service the stop. The max wait attribute defines what the allowed time is for vehicles arriving to stops before the window is open.
Deprecated: This package is deprecated and will be removed in the next major release. It is used with the router engine which was replaced by github.com/nextmv-io/sdk/nextroute.