Solving Vehicle Routing Problems with a custom matrix

nextmv sdk install

The Nextmv Software Development Kit (SDK) lets you automate any operational decision in a way that looks and feels like writing other code. It provides the guardrails to turn your data into automated decisions and test and deploy them into production environments.

This guide will walk you through our routing-matrix-input and measure-matrix templates. Given that our app environment is self-contained and thus, has no access to outside resources while the app is running, all needed information needs to be passed within the input data. The goal of this guide is to enable you to use custom distance or travel time matrices in our app environment. To get the templates, simply run the following commands.

nextmv sdk init -t routing-matrix-input

Let's start looking at the routing-matrix-input first. You can check that all files are available in the newly created routing-matrix-input folder. Running the tree command, you should see the file structure.

tree routing-matrix-input

• README.md gives a short introduction to the routing problem and shows you how to run the template.
• go.mod and go.sum define a Go module and are used to manage dependencies, including the Nextmv SDK.
• input.json describes the input data for a specific routing problem that is solved by the template.
• license contains the Apache License 2.0 under which we distribute this template.
• main.go contains the actual code of the Nextmv routing app.
• The routing-matrix-input.code-workspace file should be used to open the template in Visual Studio Code. It is pre-configured for you so that you can run and debug the template without any further steps.

Now you can run the template with the Nextmv CLI, reading from the input.json file and writing to an output.json file. The following command shows you how to specify solver limits as well. You should obtain an output similar to the one shown.

nextmv sdk run main.go -- \
    -runner.input.path input.json \
    -runner.output.path output.json \
    -limits.duration 5s \
    -diagram.expansion.limit 1

Note that transient fields like timestamps, duration, versions, etc. are represented with dummy values due to their dynamic nature. I.e., every time the input is run or the version is bumped, these fields will have a different value.

Now we will show you, step by step, what the code inside the main.go achieves.

The first part of the main.go defines a package name, imports packages that are needed by the code below and a main function which is the starting point for the app. In the main function the Run function from the Nextmv run package is being called. This function executes a solver which is passed in the form of the solver function further down in the file.

package main

import (
	"log"
	"time"

	"github.com/nextmv-io/sdk/route"
	"github.com/nextmv-io/sdk/run"
	"github.com/nextmv-io/sdk/store"
)

func main() {
	err := run.Run(solver)
	if err != nil {
		log.Fatal(err)
	}
}

But before we look into the solver function, we will examine the different structs that represent the needed data used by the app.

The input struct lists the four required input fields, Stops and Vehicles, DurationMatrix and DistanceMatrix, as well as optional fields for Starts and Ends. Stops describes the list of locations to visit, and Vehicles is an array of vehicle IDs. Both matrices, DurationMatrix and DistanceMatrix represent the point to point costs in distance and travel time, respectively. The optional fields represent fixed start and end positions of the vehicles used.

type input struct {
	Stops          []route.Stop       \`json:"stops"\`
	Vehicles       []string           \`json:"vehicles"\`
	Starts         []route.Position   \`json:"starts"\`
	Ends           []route.Position   \`json:"ends"\`
	Shifts         []route.TimeWindow \`json:"shifts"\`
	DurationMatrix [][]float64        \`json:"duration_matrix"\`
	DistanceMatrix [][]float64        \`json:"distance_matrix"\`
}

The solver function is where the model is defined. The function's signature adheres to the run.Run function we saw earlier already.

func solver(i input, opts store.Options) (store.Solver, error) {

When you first ran the template you passed in the parameter -runner.input.path followed by the path to an input file. This file is automatically parsed and converted to our input struct. Other option arguments are also interpreted automatically passed to the solver as an Options struct.

Similar to the options you passed in when you ran the template, -limits.duration and -diagram.expansion.limit you can also set these values directly in your main.go if you'd prefer not to pass them from the command line.

opts.Diagram.Expansion.Limit = 1
if opts.Limits.Duration == 0 {
	opts.Limits.Duration = 10 * time.Second
}

The routing model itself is composable by options. Since the input file in this example contains only one measure matrix for distance and duration but the routing interface expects one measure matrix per vehicle, we first create slices of measures to be passed in. These slices will then be filled with duplicates of the passed measures. Since the routing interface expects route.ByIndex measures we convert the matrix format into a ByIndex format using the route.Matrix() function. The complete implementation looks like this:

distanceMatrices := make([]route.ByIndex, len(i.Vehicles))
durationMatrices := make([]route.ByIndex, len(i.Vehicles))
for j := range i.Vehicles {
	distanceMatrices[j] = route.Matrix(i.DistanceMatrix)
	durationMatrices[j] = route.Matrix(i.DurationMatrix)
}

Now that the data pre-processing is done, we can use the routing model:

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

if len(i.Starts) > 0 {
	err = router.Options(route.Starts(i.Starts))
	if err != nil {
		panic("error using starts option")
	}
}
if len(i.Ends) > 0 {
	err = router.Options(route.Ends(i.Ends))
	if err != nil {
		panic("error using ends option")
	}
}

You can see that the options for ValueFunctionMeasures, TravelTimeMeasures and Shifts are always used but the options for Starts and Ends are only used if data for them is available in the input file.

Finally, we return a solver for our router passing in options that were given at the very beginning by the calling function. This solver is then executed by the run.Run function from the beginning.

return router.Solver(opts)

For further understanding of how the router engine works as part of the route package, check out the route package how-to guide and the technical reference.

Creating a routing app with a custom model in a contained environment is very straight forward, once the needed matrices are given in the correct form factor in the input file. But how can you generate such an input file?

Let's look at the measure-matrix template now which does exactly this.

We will start analogously and first check that all files are available in the previously created measure-matrix folder. Running the tree command, you should see the file structure.

tree measure-matrix

• README.md gives a short introduction about the matrix generation and shows you how to run the template.
• go.mod and go.sum define a Go module and are used to manage dependencies, including the Nextmv SDK.
• input.json describes the input data for a specific routing problem that is solved by the template.
• license contains the Apache License 2.0 under which we distribute this template.
• main.go contains the actual code of the Nextmv routing app.
• The measure-matrix.code-workspace file should be used to open the template in Visual Studio Code. It is pre-configured for you so that you can run and debug the template without any further steps.

Running the app will directly create a file called routing-input.json which can be directly consumed by the routing app we looked at before.

Looking at the main.go the obligatory package and import definition are available in this app as well:

// package main holds the implementation of the measure generation.
package main

import (
	"encoding/json"
	"fmt"
	"os"
	"strconv"
	"time"

	"github.com/nextmv-io/sdk/route"
	"github.com/nextmv-io/sdk/route/osrm"
)

Two structs are defined, input and output. input represents the data needed to create a measure which we can then transform into a format that can be read by our routing app. This format is represented by the output struct.

type input struct {
	Stops    []route.Point
	Starts   []route.Point
	Ends     []route.Point
	Vehicles []string
}

type output struct {
	Stops          []route.Stop       \`json:"stops"\`
	Vehicles       []string           \`json:"vehicles"\`
	Starts         []route.Position   \`json:"starts"\`
	Ends           []route.Position   \`json:"ends"\`
	Shifts         []route.TimeWindow \`json:"shifts"\`
	DurationMatrix [][]float64        \`json:"duration_matrix"\`
	DistanceMatrix [][]float64        \`json:"distance_matrix"\`
}

The app starts running in the main() function and first creates a new input struct which holds a few stops in Berlin to visit, a set of available vehicles and some optional data as starts and ends. These represent fixed start and end locations for each vehicle.

input := input{
	Stops: []route.Point{
		{53.21077, 13.57843},
		{52.51017, 13.80583},
	},
	Starts: []route.Point{},
	Ends: []route.Point{
		{52.81254, 13.35778},
		{},
	},
	Vehicles: []string{"vehicle-1", "vehicle-2"},
}

When using our clients to retrieve matrices you need to pass a slice of measure.Points in specific format. You can read more about measures and the different providers we support here. For convenience there is a function that can be used to create this slice easily:

points, err := route.BuildMatrixRequestPoints(
	input.Stops,
	input.Starts,
	input.Ends,
	len(input.Vehicles),
)
if err != nil {
	panic(err)
}

Now that we have the points we can create a client of the provider of our choice and to retrieve the desired matrices. The template uses our OSRM client but you can simply replace it and use one of our other clients for Google, Here or Routingkit as well.

client := osrm.DefaultClient(
	"<YOUR-OSRM-SERVER-URL>",
	true,
)
err = client.SnapRadius(0)
if err != nil {
	panic(err)
}

// Get distance matrices.
distanceMatrix, durationMatrix, err := osrm.DistanceDurationMatrices(
	client,
	points,
	0,
)
if err != nil {
	panic(err)
}

The last step before writing everything to our output struct is to override costs in the matrix that may not be correct for our needs. If it was decided to not or only partially use start and end locations for vehicles, it can be that, depending on the provider, an infinite cost is applied to reach an "empty" location. But for our routing case what we mean by an "empty" location is that there are no costs attached to reaching this point. For that reason there is a function that does exactly this: set the costs when going to or coming from such "empty" point to zero.

distanceMatrix = route.OverrideZeroPoints(
	points,
	distanceMatrix,
)
durationMatrix = route.OverrideZeroPoints(
	points,
	durationMatrix,
)

We can then convert the data into a routing app friendly and serializable format. To do that we use three helper functions:

• A function to convert []route.Point to []route.Stop:

func convertToStop(points []route.Point) []route.Stop {
	stops := make([]route.Stop, len(points))
	for i, p := range points {
		stops[i] = route.Stop{
			ID: fmt.Sprintf("stop-%s", strconv.Itoa(i)),
			Position: route.Position{
				Lon: p[1],
				Lat: p[0],
			},
		}
	}
	return stops
}

• A function to convert []route.Point to []route.Position:

func convertToPosition(points []route.Point) []route.Position {
	position := make([]route.Position, len(points))
	for i, p := range points {
		if len(p) == 0 {
			return []route.Position{}
		}
		position[i] = route.Position{
			Lon: p[1],
			Lat: p[0],
		}
	}
	return position
}

• A function to convert route.ByIndex to [][]float64:

func makeFloatMatrix(matrix route.ByIndex, length int) [][]float64 {
	out := make([][]float64, length)
	for i := 0; i < length; i++ {
		out[i] = make([]float64, length)
		for j := 0; j < length; j++ {
			out[i][j] = matrix.Cost(i, j)
		}
	}
	return out
}

With those helper function we create our output which serves as an input for our routing app:

now := time.Date(2022, 10, 17, 9, 0, 0, 0, time.UTC)
out := output{
	Stops:    convertToStop(input.Stops),
	Starts:   convertToPosition(input.Starts),
	Ends:     convertToPosition(input.Ends),
	Vehicles: input.Vehicles,
	Shifts: []route.TimeWindow{
		{
			Start: now,
			End:   now.Add(24 * time.Hour),
		},
		{
			Start: now,
			End:   now.Add(24 * time.Hour),
		},
	},
	DistanceMatrix: makeFloatMatrix(distanceMatrix, len(points)),
	DurationMatrix: makeFloatMatrix(durationMatrix, len(points)),
}

An finally, we write the output into a file routing-input.json.

file, _ := json.MarshalIndent(out, "", " ")
err = os.WriteFile("routing-input.json", file, 0o644)
if err != nil {
	panic(err)
}