Solving Vehicle Routing Problems with Clustered Routes

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 cluster-tsp template. This templates is a variation of the routing template and in order to focus on the aspect of pre-clustering it only uses a small subset of the options shown in the routing template. To get the cluster-tsp template, simply run the following command.

nextmv sdk init -t cluster-tsp

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 cluster-tsp

• README.md gives a short introduction to the cluster-tsp 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 cluster-tsp 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 sdk run . -- \
    -runner.input.path input.json \
    -runner.output.path output.json \
    -limits.duration 10s

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.

Since this template is based on the routing template, we will focus on the part where and how the clustering is done and only briefly mention the parts specific to routing. If you want to know more about the mechanics of the router, please read our routing template how-to guide.

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"
	"math"
	"strconv"
	"time"

	"github.com/nextmv-io/sdk/cluster/kmeans"
	"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 different structs that represent the needed data used by the app.

The input struct lists the two required input fields, Stops and Vehicles, as well as StopWeights and ClusterCapacities that we will take into account in our cluster model. 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.

// \`solver\` to use the new structure.
type input struct {
	Stops             []route.Stop \`json:"stops"\`
	Vehicles          []string     \`json:"vehicles"\`
	StopWeight        []int        \`json:"stop_weight"\`
	ClusterCapacities []int        \`json:"cluster_capacities"\`

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

// information on the options available to you.

In the routing template we directly created a router and used the input data to add optional constraints. In this template we will first create a set of clusters which we will then use to solve multiple TSP problems per vehicle. To do this we use the Attribute option from the router package and create a 1:1 relation between every stop and a vehicle. This happens in the cluster() function where the returned values vehicleAttributes and stopAttributes represent this relation.

// must be served by 1 vehicle.

The cluster() function takes the input data and does four things:

• Build clusters by calling the clusterSolution() function:

func cluster(input input) ([]route.Attributes, []route.Attributes, error) {

• Create a vehicle attribute for each vehicle:

vehicleAttributes := make([]route.Attributes, 0)
stopAttributes := make([]route.Attributes, 0)
for i, v := range input.Vehicles {
	vehicleAttributes = append(vehicleAttributes, route.Attributes{
		ID:         v,
		Attributes: []string{strconv.Itoa(i)},
	})

• Loop over each cluster from step 1 create a stop attribute for each point in the cluster for the same vehicle:

for clusterIndex, c := range solution.Clusters() {
	for _, stopIndex := range c.Indices() {
		attr := strconv.Itoa(clusterIndex)
		stopAttributes = append(
			stopAttributes,
			route.Attributes{
				ID:         input.Stops[stopIndex].ID,
				Attributes: []string{attr},
			})
	}

• Return the attributes to be used by the router engine:

}

Now, lets look at at the clusterSolutions() function in detail where all the magic happens. First, we create some variables that we will need later on:

func clusterSolution(input input) (kmeans.Solution, error) {
	maximumPoints := make([]int, len(input.Vehicles))
	maximumValues := make([]int, len(input.Vehicles))
	values := make([][]int, len(input.Vehicles))
	points := make([]measure.Point, len(input.Stops))

We need those variables to pass the following information to the k-means clustering model:

• maximumPoints represents the number of points that can be assigned to a cluster at most. Since in this example will create as many clusters as we have vehicles, this is equivalent to the maximum number of stops for a route.
• maximumValues represents the max capacity for each vehicle.
• values represent the value or weight of each stop per vehicle.
• points is another representation of the stops from the input data that is expected by the k-means model.
• weights represents the weight or value a stop has. It is directly related to the variable values.

To gather all the information needed we loop over each stop and each vehicle in the input data:

for i, w := range input.Stops {
	weights[i] = input.StopWeight[i]
	points[i] = measure.Point{w.Position.Lat, w.Position.Lon}
}

for idx := 0; idx < len(input.Vehicles); idx++ {
	maximumPoints[idx] = int(
		math.Ceil(float64(len(input.Stops)) / float64(len(input.Vehicles))),
	)

Next we will create a new k-means model and pass in the points, the number of clusters/vehicles, the constraints MaximumPoints and MaximumSumValue.

}

// We create a kmeans model using options.
model, err := kmeans.NewModel(
	points,
	len(input.Vehicles),

For this model we then create a solver and solve options.

}
if err != nil {
	return nil, err
}

We can now finally solve the clustering model and return the solution:

	SetMeasure(measure.EuclideanByPoint()).
if err != nil {

Back in our solver function we can now use the variables vehicleAttributes and stopAttributes and pass them into the router engine:

// Define base router.
router, err := route.NewRouter(
	i.Stops,
	i.Vehicles,
	route.Attribute(vehicleAttributes, stopAttributes),

Because of the Attribute option, solving this routing model will result in solving multiple TSP problems. Each TSP is represented by the cluster we created and will add all stops of that cluster to the vehicle's route.

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.