route

package
v0.16.0-dev.0-6 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 11, 2022 License: Apache-2.0 Imports: 6 Imported by: 0

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) {
		// Outer decision: number of vehicles.
		s := store.New()
		x := store.NewVar(s, 0)
		solver := s.
			Generate(
				store.Scope(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
					cost := solution.Statistics.Value

					return store.
						// Use some generating condition.
						If(...).
						Then(func(s store.Store) 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 *cost })
						}).
						// Operationally valid if all stops are assigned.
						With(func(s store.Store) bool { return len(unassigned) == 0 })
				}),
			).
			Value(x.Get).
			Maximizer(opt)

		return solver, 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": "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        }
      ],
      "route_duration": 1243
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 0
    }
  ]
}

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Alternate 

type Alternate struct {
	VehicleID string   `json:"vehicle_id"`
	Stops     []string `json:"stops"`
}

Alternate represents alternate stops, a list of stops for a vehicle.

type Attributes 

type Attributes struct {
	ID         string   `json:"id"`
	Attributes []string `json:"attributes"`
}

Attributes holds the ID of a vehicle or stop and corresponding compatibility attributes for that vehicle/stop.

type Backlog 

type Backlog struct {
	VehicleID string   `json:"vehicle_id"`
	Stops     []string `json:"stops"`
}

Backlog represents the backlog, a list of stops for a vehicle.

type ByIndex 

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

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

func Constant 

func Constant(c float64) ByIndex

Constant measure always estimates the same cost.

func Indexed 

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

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

func Override 

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

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

func Scale 

func Scale(m ByIndex, constant float64) ByIndex

Scale the cost of some other measure by a constant.

type ByPoint 

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

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

func ConstantByPoint 

func ConstantByPoint(c float64) ByPoint

ConstantByPoint measure always estimates the same cost.

func HaversineByPoint 

func HaversineByPoint() ByPoint

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

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 Limit 

type Limit struct {
	Measure ByIndex
	Value   float64
}

Limit holds a measure which will be limited by the given value.

type Option 

type Option func(Router) error

An Option configures a Router.

func Alternates 

func Alternates(alternates []Alternate) Option

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": "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
          }
        }
      ],
      "route_duration": 1189
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 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": "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": 909
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        },
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 575
    }
  ]
}

func Backlogs 

func Backlogs(backlogs []Backlog) Option

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
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 0
    }
  ]
}

func Capacity 

func Capacity(quantities []int, capacities []int) Option

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
    },
    {
      "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
    }
  ]
}

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.

func Ends 

func Ends(ends []Position) Option

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
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "v2-start",
          "position": {
            "lon": 135.758794,
            "lat": 34.98608
          }
        },
        {
          "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "v2-end",
          "position": {
            "lon": 135.758794,
            "lat": 34.98608
          }
        }
      ],
      "route_duration": 1484
    }
  ]
}

func Filter 

func Filter(compatible func(vehicle, location int) bool) Option

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.

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.

func Grouper 

func Grouper(groups [][]string) Option

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": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          }
        }
      ],
      "route_duration": 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": "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
    }
  ]
}

func InitializationCosts 

func InitializationCosts(initializationCosts []float64) Option

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
    },
    {
      "id": "v2",
      "route": [
        {
          "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
          }
        },
        {
          "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": 1818
    }
  ]
}

func LimitDistances 

func LimitDistances(maxDistances []float64, ignoreTriangular bool) Option

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": "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": 909
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        },
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 575
    }
  ]
}

func LimitDurations 

func LimitDurations(maxDurations []float64, ignoreTriangular bool) Option

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": "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": 909
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        },
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 575
    }
  ]
}

func Limits 

func Limits(routeLimits []Limit, ignoreTriangular bool) Option

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": "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        }
      ],
      "route_duration": 1243
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 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
    }
  ]
}

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": "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
          }
        },
        {
          "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": 1818
    }
  ]
}

func Precedence 

func Precedence(precedences []Job) Option

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),
	)
	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
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 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.

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
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "v2-start",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 0
    }
  ]
}

func Services 

func Services(serviceTimes []Service) Option

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": "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        }
      ],
      "route_duration": 2143
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 900
    }
  ]
}

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": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          },
          "estimated_arrival": "2020-10-17T09:00:00Z",
          "estimated_departure": "2020-10-17T09:15:00Z"
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          },
          "estimated_arrival": "2020-10-17T09:20:28Z",
          "estimated_departure": "2020-10-17T09:20:28Z"
        },
        {
          "id": "Gionmachi",
          "position": {
            "lon": 135.775682,
            "lat": 35.002457
          },
          "estimated_arrival": "2020-10-17T09:22:28Z",
          "estimated_departure": "2020-10-17T09:22:28Z"
        },
        {
          "id": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          },
          "estimated_arrival": "2020-10-17T09:27:12Z",
          "estimated_departure": "2020-10-17T09:27:12Z"
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          },
          "estimated_arrival": "2020-10-17T09:30:10Z",
          "estimated_departure": "2020-10-17T09:30:10Z"
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          },
          "estimated_arrival": "2020-10-17T09:35:43Z",
          "estimated_departure": "2020-10-17T09:35:43Z"
        }
      ],
      "route_duration": 2143
    },
    {
      "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"
        }
      ],
      "route_duration": 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.

func Starts 

func Starts(starts []Position) Option

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
    },
    {
      "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
    }
  ]
}

func Threads 

func Threads(threads int) Option

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": "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        }
      ],
      "route_duration": 1243
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 0
    }
  ]
}

func TravelTimeMeasures 

func TravelTimeMeasures(timeMeasures []ByIndex) Option

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"
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          },
          "estimated_arrival": "2020-10-17T09:07:49Z",
          "estimated_departure": "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"
        },
        {
          "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"
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          },
          "estimated_arrival": "2020-10-17T09:21:41Z",
          "estimated_departure": "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"
        }
      ],
      "route_duration": 1777
    },
    {
      "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"
        }
      ],
      "route_duration": 0
    }
  ]
}

func Unassigned 

func Unassigned(penalties []int) Option

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": "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": 795
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 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.

func ValueFunctionMeasures 

func ValueFunctionMeasures(valueFunctionMeasures []ByIndex) Option

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": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          },
          "estimated_arrival": "2020-10-17T09:00:00Z",
          "estimated_departure": "2020-10-17T09:00:00Z"
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          },
          "estimated_arrival": "2020-10-17T09:05:28Z",
          "estimated_departure": "2020-10-17T09:05:28Z"
        },
        {
          "id": "Gionmachi",
          "position": {
            "lon": 135.775682,
            "lat": 35.002457
          },
          "estimated_arrival": "2020-10-17T09:07:28Z",
          "estimated_departure": "2020-10-17T09:07:28Z"
        },
        {
          "id": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          },
          "estimated_arrival": "2020-10-17T09:12:12Z",
          "estimated_departure": "2020-10-17T09:12:12Z"
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          },
          "estimated_arrival": "2020-10-17T09:15:10Z",
          "estimated_departure": "2020-10-17T09:15:10Z"
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          },
          "estimated_arrival": "2020-10-17T09:20:43Z",
          "estimated_departure": "2020-10-17T09:20:43Z"
        }
      ],
      "route_duration": 1243
    },
    {
      "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"
        }
      ],
      "route_duration": 0
    }
  ]
}

func Velocities 

func Velocities(velocities []float64) Option

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": "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        }
      ],
      "route_duration": 2485
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 0
    }
  ]
}

func Windows 

func Windows(windows []Window) Option

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": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          },
          "estimated_arrival": "2020-10-17T09:00:00Z",
          "estimated_departure": "2020-10-17T09:00:00Z"
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          },
          "estimated_arrival": "2020-10-17T09:05:28Z",
          "estimated_departure": "2020-10-17T09:05:28Z"
        },
        {
          "id": "Gionmachi",
          "position": {
            "lon": 135.775682,
            "lat": 35.002457
          },
          "estimated_arrival": "2020-10-17T09:07:28Z",
          "estimated_departure": "2020-10-17T09:22:28Z"
        },
        {
          "id": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          },
          "estimated_arrival": "2020-10-17T09:27:12Z",
          "estimated_departure": "2020-10-17T09:27:12Z"
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          },
          "estimated_arrival": "2020-10-17T09:30:10Z",
          "estimated_departure": "2020-10-17T09:30:10Z"
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          },
          "estimated_arrival": "2020-10-17T09:35:43Z",
          "estimated_departure": "2020-10-17T09:35:43Z"
        }
      ],
      "route_duration": 2143
    },
    {
      "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"
        }
      ],
      "route_duration": 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
}

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"`
}

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"`
}

PlannedVehicle holds information about the vehicle in a solution to a Vehicle Routing Problem.

type Point 

type Point []float64

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

type Position 

type Position struct {
	Lon float64 `json:"lon"`
	Lat float64 `json:"lat"`
}

Position represents a geographical location.

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.Variable[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 (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
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "v2-start",
          "position": {
            "lon": 135.758794,
            "lat": 34.98608
          }
        },
        {
          "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
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "v2-end",
          "position": {
            "lon": 135.758794,
            "lat": 34.98608
          }
        }
      ],
      "route_duration": 1484
    }
  ]
}
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": "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": 795
  },
  {
    "id": "v2",
    "route": [
      {
        "id": "Arashiyama Bamboo Forest",
        "position": {
          "lon": 135.672009,
          "lat": 35.017209
        }
      }
    ],
    "route_duration": 0
  }
]

func NewRouter 

func NewRouter(
	stops []Stop,
	vehicles []string,
	opts ...Option,
) (Router, error)

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": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          }
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          }
        }
      ],
      "route_duration": 328
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        }
      ],
      "route_duration": 0
    }
  ]
}

type Service 

type Service struct {
	ID       string `json:"id"`
	Duration int    `json:"duration"`
}

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 Stop 

type Stop struct {
	ID       string   `json:"id"`
	Position Position `json:"position"`
}

Stop to service in a Vehicle Routing Problem.

type TimeWindow 

type TimeWindow struct {
	Start time.Time `json:"start"`
	End   time.Time `json:"end"`
}

TimeWindow represents a time window for a shift of a vehicle or a stop.

type Triangular 

type Triangular interface {
	Triangular() bool
}

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

Source Files

View all Source files

Directories

Path Synopsis
google module
here module
osrm module
routingkit module

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.