Tutorials

Solving Vehicle Routing Problems

Learn to model a routing problem 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 template. To get the template, simply run the following command.

nextmv init -t routing
Copy

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

tree routing
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.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 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 two required input fields, Stops and Vehicles, as well as a list of available options. Stops describes the list of locations to visit, and Vehicles is an array of vehicle IDs. To learn about the additional options 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"`
	InitializationCosts []float64            `json:"initialization_costs"`
	Starts              []route.Position     `json:"starts"`
	Ends                []route.Position     `json:"ends"`
	Quantities          []int                `json:"quantities"`
	Capacities          []int                `json:"capacities"`
	Precedences         []route.Job          `json:"precedences"`
	Windows             []route.Window       `json:"windows"`
	Shifts              []route.TimeWindow   `json:"shifts"`
	Penalties           []int                `json:"penalties"`
	Backlogs            []route.Backlog      `json:"backlogs"`
	VehicleAttributes   []route.Attributes   `json:"vehicle_attributes"`
	StopAttributes      []route.Attributes   `json:"stop_attributes"`
	Velocities          []float64            `json:"velocities"`
	Groups              [][]string           `json:"groups"`
	ServiceTimes        []route.Service      `json:"service_times"`
	AlternateStops      []route.Alternate    `json:"alternate_stops"`
	Limits              []route.Limit        `json:"limits"`
	DurationLimits      []float64            `json:"duration_limits"`
	DistanceLimits      []float64            `json:"distance_limits"`
	ServiceGroups       []route.ServiceGroup `json:"service_groups"`
}
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.

router, err := route.NewRouter(
	i.Stops,
	i.Vehicles,
	route.Threads(2),
	route.Velocities(i.Velocities),
	route.Starts(i.Starts),
	route.Ends(i.Ends),
	route.Capacity(i.Quantities, i.Capacities),
	route.Precedence(i.Precedences),
	route.Services(i.ServiceTimes),
	route.Shifts(i.Shifts),
	route.Windows(i.Windows),
	route.Unassigned(i.Penalties),
	route.InitializationCosts(i.InitializationCosts),
	route.Backlogs(i.Backlogs),
	route.LimitDurations(
		i.DurationLimits,
		true, /*ignoreTriangular*/
	),
	route.LimitDistances(
		i.DistanceLimits,
		true, /*ignoreTriangular*/
	),
	route.Attribute(i.VehicleAttributes, i.StopAttributes),
	route.Grouper(i.Groups),
	route.Alternates(i.AlternateStops),
	route.ServiceGroups(i.ServiceGroups),
)
Copy

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

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.

Page last updated

Go to on-page nav menu