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.
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.Interface
- func IsTriangular(m any) bool
- func LessClockwise(center, a, b Point) bool
- type Alternate
- type Attributes
- type Backlog
- type ByIndex
- func Bin(measures []measure.ByIndex, selector func(from, to int) int) ByIndex
- func Constant(c float64) ByIndex
- func DebugOverride(defaultByIndex ByIndex, overrideByIndex ByIndex, ...) ByIndex
- func Indexed(m ByPoint, points []Point) ByIndex
- func Location(m ByIndex, costs []float64, durationGroups DurationGroups) (ByIndex, error)
- func Matrix(arcs [][]float64) ByIndex
- func Override(defaultByIndex ByIndex, overrideByIndex ByIndex, ...) ByIndex
- func OverrideZeroPoints(points []Point, m ByIndex) ByIndex
- func Power(m ByIndex, exponent float64) ByIndex
- func Scale(m ByIndex, constant float64) ByIndex
- func Sparse(m ByIndex, arcs map[int]map[int]float64) ByIndex
- func Sum(m ...measure.ByIndex) ByIndex
- func Truncate(m ByIndex, lower, upper float64) ByIndex
- type ByIndexAndTime
- type ByIndexLoader
- type ByPoint
- type ByPointLoader
- type DependentByIndex
- type DurationGroup
- type DurationGroups
- type Job
- type Limit
- type Option
- func Alternates(alternates []Alternate) Option
- func Attribute(vehicles []Attributes, stops []Attributes) Option
- func Backlogs(backlogs []Backlog) Option
- func Capacity(quantities []int, capacities []int) Option
- func Constraint(constraint VehicleConstraint, ids []string) Option
- func Ends(ends []Position) Option
- func Filter(compatible func(vehicle, location int) bool) Option
- func FilterWithRoute(...) Option
- func Grouper(groups [][]string) Option
- func InitializationCosts(initializationCosts []float64) Option
- func LimitDistances(maxDistances []float64, ignoreTriangular bool) Option
- func LimitDurations(maxDurations []float64, ignoreTriangular bool) Option
- func Limits(routeLimits []Limit, ignoreTriangular bool) Option
- func Maximize() Option
- func Minimize() Option
- func MultiWindows(windows [][]TimeWindow, maxWaitTimes []int) Option
- func Precedence(precedences []Job) Option
- func Selector(selector func(PartialPlan) model.Domain) Option
- func ServiceGroups(serviceGroups []ServiceGroup) Option
- func Services(serviceTimes []Service) Option
- func Shifts(shifts []TimeWindow) Option
- func Sorter(...) Option
- func Starts(starts []Position) Option
- func Threads(threads int) Option
- func TravelDistanceMeasures(travelDistanceMeasures []ByIndex) Option
- func TravelTimeDependentMeasures(timeMeasures []DependentByIndex) Option
- func TravelTimeMeasures(timeMeasures []ByIndex) Option
- func Unassigned(penalties []int) Option
- func Update(v VehicleUpdater, f PlanUpdater) Option
- func ValueFunctionDependentMeasures(valueFunctionMeasures []DependentByIndex) Option
- func ValueFunctionMeasures(valueFunctionMeasures []ByIndex) Option
- func Velocities(velocities []float64) Option
- func Windows(windows []Window) Option
- type PartialPlan
- type PartialVehicle
- type Plan
- type PlanUpdater
- type PlannedStop
- type PlannedVehicle
- type Point
- type Position
- type Router
- type Service
- type ServiceGroup
- type Stop
- type TimeWindow
- type Times
- type Triangular
- type VehicleConstraint
- type VehicleData
- type VehicleUpdater
- type Window
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 ¶ added in v0.20.0
ByClockwise implements sort.Interface for sorting points clockwise around a central point.
func IsTriangular ¶ 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.
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 ¶ added in v0.20.0
LessClockwise returns true if a is closer to a central point than b, and false if it is not.
Types ¶
type Attributes ¶
Attributes holds the ID of a vehicle or stop and corresponding compatibility attributes for that vehicle/stop.
type ByIndex ¶
ByIndex estimates the cost of going from one index to another.
func Bin ¶ 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.
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 ¶
Constant measure always estimates the same cost.
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 ¶ 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.
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 ¶
Indexed creates a ByIndex measure from the given ByPoint measure and wrapping the provided points.
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 ¶
func Location( m ByIndex, costs []float64, durationGroups DurationGroups, ) (ByIndex, error)
Location measure returns the sum of the cost computed by the passed in measure and the specified cost of the 'to' location. This cost is read from the passed in costs slice.
func Matrix ¶ added in v0.20.0
Matrix measure returns pre-computed cost between two locations. Cost is assumed to be asymmetric.
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 ¶
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.
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 ¶ added in v0.20.10
OverrideZeroPoints overrides points that have been passed as placeholders [0,0] to build the matrix with zero values.
func Power ¶ added in v0.20.0
Power raises the cost of some other measure to an exponent.
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 ¶
Scale the cost of some other measure by a constant.
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 ¶ 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.
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 ¶ added in v0.20.0
Sum adds other measures together.
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 ¶ added in v0.20.0
Truncate the cost of some other 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
type ByIndexAndTime ¶ 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.
type ByIndexLoader ¶ 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.
func (ByIndexLoader) MarshalJSON ¶ added in v0.20.2
func (l ByIndexLoader) MarshalJSON() ([]byte, error)
MarshalJSON returns the JSON representation for the underlying Byindex.
func (*ByIndexLoader) To ¶ added in v0.20.2
func (l *ByIndexLoader) To() ByIndex
To returns the underlying ByIndex.
func (*ByIndexLoader) UnmarshalJSON ¶ added in v0.20.2
func (l *ByIndexLoader) UnmarshalJSON(b []byte) error
UnmarshalJSON converts the bytes into the appropriate implementation of ByIndex.
type ByPoint ¶
ByPoint estimates the cost of going from one point to another.
func ConstantByPoint ¶
ConstantByPoint measure always estimates the same cost.
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 ¶ added in v0.20.0
func EuclideanByPoint() ByPoint
EuclideanByPoint computes straight line distance connecting two indices.
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 ¶
func HaversineByPoint() ByPoint
HaversineByPoint estimates meters connecting two points along the surface of the earth.
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 ¶ added in v0.20.2
ScaleByPoint scales the cost of some other measure by a constant.
func TaxicabByPoint ¶ added in v0.20.0
func TaxicabByPoint() ByPoint
TaxicabByPoint adds absolute distances between two points in all dimensions.
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 ¶ 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.
func (ByPointLoader) MarshalJSON ¶ added in v0.20.2
func (l ByPointLoader) MarshalJSON() ([]byte, error)
MarshalJSON returns the JSON representation for the underlying ByPoint.
func (*ByPointLoader) To ¶ added in v0.20.2
func (l *ByPointLoader) To() ByPoint
To returns the underlying ByPoint.
func (*ByPointLoader) UnmarshalJSON ¶ added in v0.20.2
func (l *ByPointLoader) UnmarshalJSON(b []byte) error
UnmarshalJSON converts the bytes into the appropriate implementation of ByPoint.
type DependentByIndex ¶ 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.
func DependentIndexed ¶ 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.
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
func NewTimeDependentMeasure ¶ added in v0.21.1
func NewTimeDependentMeasure( startTime int, measures []ByIndexAndTime, fallback ByIndex, ) (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.
type DurationGroup ¶
type DurationGroup = measure.DurationGroup
DurationGroup groups stops by index which have additional service costs attached to them.
type DurationGroups ¶
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.
type Job ¶
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.
type Option ¶
An Option configures a Router.
func Alternates ¶
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.
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 ¶
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.
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 ¶
Backlogs sets the backlog for the specified vehicles. A backlog is an unordered list of stops that a vehicle has to serve.
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 ¶
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.
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 ¶
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.
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 ¶
Ends sets the ending locations indexed by vehicle. The length must match the vehicles' length.
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 ¶
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.
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 ¶
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.
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 ¶
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.
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 ¶
InitializationCosts set the vehicle initialization costs indexed by vehicle. The length must match the vehicles' length.
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 ¶
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.
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 ¶
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.
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 ¶
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.
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 ¶
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.
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 ¶
func Minimize() Option
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.
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 ¶ 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.
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 ¶
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.
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 ¶
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.
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 ¶
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.
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 ¶
Services adds a service time to the given stops. For stops not in the slice, a service time of zero seconds is applied.
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 ¶
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.
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 ¶
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.
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 ¶
Starts sets the starting locations indexed by vehicle. The length must match the vehicles' length.
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 ¶
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.
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 ¶ 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.
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 ¶ added in v0.21.1
func TravelTimeDependentMeasures(timeMeasures []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.
func TravelTimeMeasures ¶
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.
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 ¶
Unassigned sets the unassigned penalties indexed by stop. The length must match the stops' length.
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 ¶
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.
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 ¶ added in v0.21.1
func ValueFunctionDependentMeasures( valueFunctionMeasures []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.
func ValueFunctionMeasures ¶
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.
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 ¶
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.
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 ¶
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.
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 ¶
type PartialPlan interface { // Unassigned returns an Integer Domain with unassigned stop indices. // These are stops explicitly excluded from being served by a vehicle. Unassigned() model.Domain // Unplanned returns an Integer Domain with not yet assigned or unassigned // stops indices. Unplanned() model.Domain // Value return the value of this plan. Value() int // Vehicles returns a slice of vehicles part of this partial plan. 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.
type PartialVehicle ¶
type PartialVehicle interface { // ID returns the vehicle ID. ID() string // Updater returns either nil in case no custom VehicleUpdater was used or // the custom VehicleUpdater that was used for this vehicle. 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. Route() []int // Value return the value of vehicle. Usually this is the cost of the route. 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). Times() 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.
type Plan ¶
type Plan struct { Unassigned []Stop `json:"unassigned"` Vehicles []PlannedVehicle `json:"vehicles"` }
Plan describes a solution to a Vehicle Routing Problem.
type PlanUpdater ¶
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.
type PlannedStop ¶
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.
type PlannedVehicle ¶
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.
type Point ¶
Point represents a point in space. It may have any dimension.
func BuildMatrixRequestPoints ¶ 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.
type Router ¶
type Router interface { // Options configures the router with the given options. An error is // returned if validation issues exist. Options(...Option) error // Solver receives solve options and returns a Solver interface. 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 */ Plan() store.Var[Plan] // Format configures a custom output format for a solution. Format(func(*Plan) any) }
A Router is an engine that solves Vehicle Routing Problems.
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 ¶
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.
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 holds the ID of a stop and corresponding time to service the stop in seconds.
type ServiceGroup ¶
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.
type TimeWindow ¶
TimeWindow represents a time window for a shift of a vehicle or a stop.
type Times ¶
Times holds the estimated time of arrival (ETA), the estimated time of when service starts (ETS) and estimated time of departure (ETD).
type Triangular ¶
type Triangular = measure.Triangular
Triangular indicates that the triangle inequality holds for every measure that implements it.
type VehicleConstraint ¶
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.
type VehicleData ¶ 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.
type VehicleUpdater ¶
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.
type Window ¶
type Window struct { TimeWindow TimeWindow `json:"time_window"` MaxWait int `json:"max_wait"` }
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.