Tutorials

Solving Vehicle Routing Problems with a custom matrix

Learn to model a routing problem with a custom matrix with the Nextmv SDK

This tutorial assumes you already completed the steps described in the 5-minute getting started experience. To test that the Nextmv CLI is correctly configured, you can optionally run the following command on your terminal. It will get some files that are necessary to work with the Nextmv Platform. You can see the expected output as well.

nextmv install
Copy

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.

Introduction

This tutorial 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 tutorial 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 init -t routing-matrix-input
Copy

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
Copy
  • 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 run local main.go -- \
    -runner.input.path input.json \
    -runner.output.path output.json \
    -limits.duration 5s \
    -diagram.expansion.limit 1
Copy

Note that transient fields are represented with "\u003c\u003cPRESENCE\u003e\u003e", which is the unicode representation of "<<PRESENCE>>", due to their dynamic nature: every time the input is run, these fields will have a different value. This representation is compliant with the jsonassert package.

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

Dissecting the routing app

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)
	}
}
Copy

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

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

The Solver

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) {
Copy

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
}
Copy

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)
}
Copy

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")
	}
}
Copy

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.

Returning the solver

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)
Copy

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

Interim result

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.

Building matrices to be consumed by a routing app

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

Dissecting the matrix app

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"
)
Copy

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

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"},
}
Copy

Note that it is ok to provide starts and ends or not. It is also ok to partially provide starts and ends as shown in the example. The only requirement is that if you want to use a start or end location for only a few vehicles you need to make sure to provide empty data for all other vehicles. This is because we are using the indices of each slice to map vehicles with the start/end locations.

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)
}
Copy

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)
}
Copy

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,
)
Copy

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
}
Copy
  • 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
}
Copy
  • 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
}
Copy

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)),
}
Copy

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)
}
Copy

Page last updated

Go to on-page nav menu