Solving Vehicle Routing Problems with a time dependent measure

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 time-dependent-measure template This template can be used to adhere to traffic situations like rush hours. To get the template, simply run the following command.

nextmv sdk init -t time-dependent-measure

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

tree time-dependent-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 routing problem that is solved by the template using time dependent measures.
• 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 time-dependent-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.

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

But before we look into the solver function, we will examine the struct that represents the needed data used by the app.

The input struct lists the two required input fields, Stops, Vehicles and Shifts. Stops describes the list of locations to visit, Vehicles is an array of vehicle IDs and Shifts hold the start and end time of the drivers/vehicles shift. To learn about additional options that can be used and how they're used, check out the how-to guide on router engine options.

type input struct {
	Stops    []route.Stop       \`json:"stops"\`
	Vehicles []string           \`json:"vehicles"\`
	Shifts   []route.TimeWindow \`json:"shifts"\`
}

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

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.

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

Next, we create two measures that will be used to calculate costs to go from one stop to another dependent on the estimated time of departure of the starting stop. To create them we first need the list of points:

points := make([]measure.Point, len(i.Stops)+2*len(i.Vehicles))
for i, s := range i.Stops {
	points[i] = measure.Point{
		s.Position.Lon, s.Position.Lat,
	}
}

Note that the list of points has a length of len(i.Stops)+2*len(i.Vehicles) so that we can create a full matrix for each stop and each vehicle in the input.

Given the points we can now create the first measure m1 and set all costs that occur for coming from or going to a vehicle start/end to zero. We do this by using an override function on the measure: The second measure m2 is simply the same as m1 - scaled by the factor 2.

m1 := measure.Indexed(measure.HaversineByPoint(), points)
m1 = measure.Override(m1, measure.Constant(0), func(from, to int) bool {
	return from > len(points)-1 || to > len(points)-1
})
m2 := measure.Scale(m1, 2)

To later use the measures accordingly we need to combine each measure with an end time up until this measure will be used when internally compared to the estimated time of departure.

byIndexAndTime := make([][]route.ByIndexAndTime, len(i.Shifts))
for shiftIndex, t := range i.Shifts {
	byIndexAndTime[shiftIndex] = make([]route.ByIndexAndTime, 2)
	byIndexAndTime[shiftIndex][0] = route.ByIndexAndTime{
		Measure: m1,
		EndTime: int(t.Start.Add(30 * time.Second).Unix()),
	}
	byIndexAndTime[shiftIndex][1] = route.ByIndexAndTime{
		Measure: m2,
		EndTime: int(t.Start.Add(60 * time.Second).Unix()),
	}
}

In order to use a time dependent measure one needs to be created per vehicle. This can be done via the NewTimeDependentMeasure function which requires a start time (which is usually the shift start of that vehicle), the slice of measure/end time combination we previously created and a fallback measure.

dependentMeasures := make([]measure.DependentByIndex, len(i.Vehicles))
for index := range i.Vehicles {
	// Create a time dependent measure client.
	dependentMeasure, err := route.NewTimeDependentMeasure(
		int(i.Shifts[index].Start.Unix()),
		byIndexAndTime[index],
		m1,
	)
	dependentMeasures[index] = dependentMeasure
}

Lastly, we create a new routing engine and pass in the required parameters:

router, err := route.NewRouter(
	i.Stops,
	i.Vehicles,
	route.Shifts(i.Shifts),
	route.ValueFunctionDependentMeasures(dependentMeasures),
)

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
}

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.