Solving Vehicle Routing Problems with a unique 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.

Introduction

This guide will walk you through our unique-matrix-measure template. Apps running in our app environment are self-contained and thus, have no access to outside resources while the app is running, all needed information needs to be passed within the input data. The input data size can become quite big and in this guide we will show you a method to reduce this data size. The requirement for this method to work is that you have many stops at the same location. To get the template, simply run the following commands.

nextmv sdk init -t unique-matrix-measure

You can check that all files are available in the newly created unique-matrix-measure folder. Running the tree command, you should see the file structure.

ls -v unique-matrix-measure

• 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 unique-matrix-measure.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 . -- \
    -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.

Dissecting the routing app

The first part of the main.go defines a package name, imports packages required, and defines 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/measure"
	"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)
	}
}

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 required input fields, Stops and Vehicles, Starts and Ends (both optional), as well as fields for UniquePoints and UniqueMatrix. UniquePoints is a unique set of locations that need to be visited. And UniqueMatrix represents a matrix of costs for going from each of the unique points to another. Stops describes the list of locations to visit. It does that by referencing the 0-based index to the set of UniquePoints. For that reason all those stops are represented by the stop struct which holds only an ID and the aforementioned Reference to the UniquePoints array. Vehicles is an array of vehicle IDs.

type stop struct {
	ID        string \`json:"id"\`
	Reference int    \`json:"reference"\`
}
type input struct {
	Stops        []stop           \`json:"stops"\`
	Vehicles     []string         \`json:"vehicles"\`
	Starts       []stop           \`json:"starts"\`
	Ends         []stop           \`json:"ends"\`
	UniquePoints []route.Position \`json:"unique_points"\`
	UniqueMatrix [][]float64      \`json:"unique_matrix"\`
}

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

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

To be able to run the routing model we first need to convert the unique matrix into a full matrix the way the solver expect it. Before we start doing this, we will do some basic validation on the data to make sure that it is complete.

checkInput(i)

The checkInput function validates that the UniqueMatrix represents size-wise the UniquePoints and that, if given, the Starts and Ends have the length of the Vehicles which is a requirement of the routing engine.

func checkInput(i input) {
	if len(i.UniqueMatrix) != len(i.UniquePoints) {
		panic("number of matrix rows must match unique points size")
	}
	for _, row := range i.UniqueMatrix {
		if len(row) != len(i.UniquePoints) {
			panic("matrix rows size must match unique points size")
		}
	}

	if len(i.Starts) > 0 && len(i.Starts) != len(i.Vehicles) {
		panic("if starts are given they must match the number of vehicles")
	}

	if len(i.Ends) > 0 && len(i.Ends) != len(i.Vehicles) {
		panic("if ends are given they must match the number of vehicles")
	}
}

Next we will create a new matrix fullMatrix which has the size the solver requires. The solver require this size because it needs to calculate costs to each location, including the start and end location of each vehicle.

matrixSize := len(i.Stops) + 2*len(i.Vehicles)
fullMatrix := make([][]float64, matrixSize)

Next we create a helper variable joinedStops which holds all stops from the input: Stops, Starts and Ends. This will make it easier to access the required data by index. The code for joining the stops looks like this:

func joinStops(i input, matrixSize int) []stop {
	joinedStops := make([]stop, matrixSize)
	// Set default reference to -1.
	for index := range joinedStops {
		joinedStops[index].Reference = -1
	}

	// Copy stops to slice.
	copy(joinedStops, i.Stops)

	// Fill joined stops alternating with Starts if applicable.
	if len(i.Starts) > 0 {
		for index := len(i.Stops); index < matrixSize; index += 2 {
			joinedStops[index] = i.Starts[(index-len(i.Stops))/2]
		}
	}

	// Fill joined stops alternating with Ends if applicable.
	if len(i.Ends) > 0 {
		for index := len(i.Stops) + 1; index < matrixSize; index += 2 {
			joinedStops[index] = i.Ends[(index-len(i.Stops)-1)/2]
		}
	}
	return joinedStops
}

We first set each stop to have a reference of -1. We do this because we need to detect if Starts or Ends are present. Without setting the default value to -1 all references would have a reference to 0 which is a valid reference index. Note that we are adding the Starts and Ends alternating because the solver requires them to be in this format: [stop-1, ..., stop-n, vehicle-1-start, vehicle-1-end, ..., vehicle-m-start, vehicle-m-end]

Now we loop over the each row and each cell in a row of the fullMatrix to fill the matrix with the correct costs. Because the joinedStops holds the stops in the correct order we can simply access the stops there and get the references to the UniquePoints which at the same time are the indices for the UniqueMatrix. If we find a reference of -1 we know that this is value is not given and we skip over, leaving the default value of 0 in the fullMatrix untouched.

for stopIndex1 := range fullMatrix {
	// Create an row filled with 0.
	fullMatrix[stopIndex1] = make([]float64, matrixSize)

	// Get first reference index.
	refIndex1 := joinedStops[stopIndex1].Reference
	for stopIndex2 := range fullMatrix[stopIndex1] {
		// Get second reference index and look up costs.
		refIndex2 := joinedStops[stopIndex2].Reference
		if refIndex1 != -1 && refIndex2 != -1 {
			cost := i.UniqueMatrix[refIndex1][refIndex2]
			fullMatrix[stopIndex1][stopIndex2] = cost
		}
	}
}

Before we can pass all of our data into the routing engine, we need to make it compatible with it. This means we need to pass the fullMatrix for each vehicle as an ByIndex measure, the stops may not use a reference to a location but have the location directly incorporated as its position, and the starts and ends need to be passed in as positions.

byIndex := measure.Matrix(fullMatrix)
byIndexMeasures := make([]measure.ByIndex, len(i.Vehicles))
for v := range i.Vehicles {
	byIndexMeasures[v] = byIndex
}
stops := make([]route.Stop, len(i.Stops))
for stopIndex, s := range i.Stops {
	stops[stopIndex] = route.Stop{
		ID:       s.ID,
		Position: i.UniquePoints[s.Reference],
	}
}

starts := make([]route.Position, len(i.Starts))
for stopIndex, s := range i.Starts {
	starts[stopIndex] = i.UniquePoints[s.Reference]
}

ends := make([]route.Position, len(i.Ends))
for stopIndex, s := range i.Ends {
	ends[stopIndex] = i.UniquePoints[s.Reference]
}

With all the data prepared we create a new routing engine:

router, err := route.NewRouter(
	stops,
	i.Vehicles,
	route.Starts(starts),
	route.Ends(ends),
	route.ValueFunctionMeasures(byIndexMeasures),
)

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)

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.