Tutorials

Solving Vehicle Routing Problems with the route package

Learn the basics of using the Nextmv route package

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 route package exposes the router engine. The Nextmv router is a convenient, simple interface for solving various types of vehicle routing problems (VRP) and single vehicle problems (commonly known as the traveling salesman problem, TSP).

router employs a hybrid solver with two search strategies: ALNS and Decision Diagrams. router receives a set of stops that must be serviced by a fleet of vehicles and a list of options to configure. Several default options are provided, such as measures, to make routing problems easier to solve. router returns routes for each vehicle, a list of unassigned stops (if any), and search output statistics. In this tutorial, you will learn how to use the Nextmv router with a practical example.

This example aims to create routes to visit seven landmarks in Kyoto using two vehicles.

base-input

To start working with the router engine you can use the Nextmv CLI to initialize a ready-to-go routing template. However, this tutorial outlines the very basic steps of working with router and creates a routing program from scratch.

Somewhere in your computer, create a Go module called router. You should obtain an output similar to the one depicted.

go mod init router
Copy

Now add the Nextmv SDK to your dependencies. You should observe the latest version being pulled as part of the output.

go get github.com/nextmv-io/sdk@latest
Copy

You should now have a go.mod file that looks like this:

module router

go 1.19

require github.com/nextmv-io/sdk v0.20.6 // indirect
Copy

Save the following information in an input.json file.

{
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": ["v1", "v2"]
}
Copy

To proceed with running the example, create a main.go file and use the code snippet below.

package main

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

func main() {
	run.Run(solver)
}

// input expected by the runner.
type input struct {
	Stops    []route.Stop `json:"stops"`
	Vehicles []string     `json:"vehicles"`
}

func solver(i input, opt store.Options) (store.Solver, error) {
	// Define base router.
	router, err := route.NewRouter(
		i.Stops,
		i.Vehicles,
		route.Threads(1),
	)
	if err != nil {
		return nil, err
	}

	return router.Solver(opt)
}
Copy

Note that the Threads option is used to avoid randomization and obtain consistent results. It may produce sub-optimal solutions and should be used mainly for testing.

Your application should roughly contain this structure:

.
├── go.mod
├── go.sum
├── input.json
└── main.go
Copy

To execute the example, specify the path to the input.json file and your output.json file using command-line flags. Limits are also specified for the solver duration and diagram expansion.

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

The solution should look similar to this one:

{
  "options": {
    "diagram": {
      "expansion": {
        "limit": 1
      },
      "width": 10
    },
    "limits": {
      "duration": "5s",
      "nodes": 0,
      "solutions": 0
    },
    "search": {
      "buffer": 100
    },
    "sense": "minimize"
  },
  "statistics": {
    "bounds": {
      "lower": -9223372036854776000,
      "upper": 12429
    },
    "search": {
      "deferred": 188,
      "expanded": 188,
      "explored": 181,
      "filtered": 0,
      "generated": 188,
      "reduced": 0,
      "restricted": 188,
      "solutions": 4
    },
    "time": {
      "elapsed": "\u003c\u003cPRESENCE\u003e\u003e",
      "elapsed_seconds": "\u003c\u003cPRESENCE\u003e\u003e",
      "start": "\u003c\u003cPRESENCE\u003e\u003e"
    },
    "value": 12429
  },
  "store": {
    "unassigned": [],
    "vehicles": [
      {
        "id": "v1",
        "route": [
          {
            "id": "Kinkaku-ji",
            "position": {
              "lat": 35.039705,
              "lon": 135.728898
            }
          },
          {
            "id": "Nijō Castle",
            "position": {
              "lat": 35.014239,
              "lon": 135.748134
            }
          },
          {
            "id": "Kyoto Imperial Palace",
            "position": {
              "lat": 35.025431,
              "lon": 135.762057
            }
          },
          {
            "id": "Gionmachi",
            "position": {
              "lat": 35.002457,
              "lon": 135.775682
            }
          },
          {
            "id": "Kiyomizu-dera",
            "position": {
              "lat": 34.994857,
              "lon": 135.78506
            }
          },
          {
            "id": "Fushimi Inari Taisha",
            "position": {
              "lat": 34.967146,
              "lon": 135.772695
            }
          }
        ],
        "route_duration": 1243
      },
      {
        "id": "v2",
        "route": [
          {
            "id": "Arashiyama Bamboo Forest",
            "position": {
              "lat": 35.017209,
              "lon": 135.672009
            }
          }
        ],
        "route_duration": 0
      }
    ]
  },
  "version": {
    "sdk": "\u003c\u003cPRESENCE\u003e\u003e"
  }
}
Copy

You can see that one vehicle has six stops assigned and the other just a single stop, which is the farthest from the others. 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.

base-output

See the guide on how-to use router engine options for additional options that can be added to extend this basic example. For further understanding of how the router engine works as part of the route package, check out the technical reference.

Page last updated