Tutorials

Solving Vehicle Routing Problems with the route package

Learn the basics of using the Nextmv route package

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

Create a Go module called router. Start by creating a router directory somewhere in your workspace.

mkdir router
Copy

Change directories into the router folder.

cd router
Copy

Initialize the Go module.

go mod init router
Copy

Now add the Nextmv SDK to your dependencies.

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

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

module router

go 1.18

require github.com/nextmv-io/sdk vX.Y.Z // 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:

  "store": {
    "unassigned": [],
    "vehicles": [
      {
        "id": "v1",
        "route": [
          {
            "id": "Fushimi Inari Taisha",
            "position": {
              "lat": 34.967146,
              "lon": 135.772695
            }
          },
          {
            "id": "Kiyomizu-dera",
            "position": {
              "lat": 34.994857,
              "lon": 135.78506
            }
          },
          {
            "id": "Gionmachi",
            "position": {
              "lat": 35.002457,
              "lon": 135.775682
            }
          },
          {
            "id": "Kyoto Imperial Palace",
            "position": {
              "lat": 35.025431,
              "lon": 135.762057
            }
          },
          {
            "id": "Nijō Castle",
            "position": {
              "lat": 35.014239,
              "lon": 135.748134
            }
          },
          {
            "id": "Kinkaku-ji",
            "position": {
              "lat": 35.039705,
              "lon": 135.728898
            }
          }
        ],
        "route_duration": 1243
      },
      {
        "id": "v2",
        "route": [
          {
            "id": "Arashiyama Bamboo Forest",
            "position": {
              "lat": 35.017209,
              "lon": 135.672009
            }
          }
        ],
        "route_duration": 0
      }
    ]
  },
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.

base-output

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

Page last updated