How To Guides

Using Router engine options

A how-to guide for configuring options for the Nextmv router

The Nextmv router is configured through a list of options, which are used to customize your routing app. They can be passed directly to the NewRouter function or through the Options method. Options are composable, meaning any number of options can be passed (or none at all).

The following is a list of short guides on how to use the different router options. This how-to guide assumes you already reviewed the router tutorial. The introductory example, where routes are created to visit seven landmarks in Kyoto using two vehicles, is used as a base for each of the options below. Unless otherwise noted, options work independently of each other so the guides can be viewed in any order.

To execute any of the examples, specify the path to the input.json file, your output.json file and set solver limits using command-line flags.

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
  • In this guide, whenever output.json is printed, we are represeting transient fields 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.
  • 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.
OptionDescription
OptionsOverview on using the Options method.
CapacitySet capacities for vehicles and quantities (demanded or offered) at stops.
PrecedenceAdd pickups and deliveries or specify multiple pickups before dropoffs and vice versa.
ServicesAdd times required to service stops.
WindowsConfigure time windows for stops.
AttributeRestrict stop-to-vehicle matching based on compatibility attributes.
LimitDurationsSet travel time limits for routes.
LimitDistancesSet distance limits for routes.
UnassignedUse penalties to discourage but permit unassigned stops (useful when a problem is infeasible).
GrouperCustomize the assigner to determine which stops must be served together along the same route (part of the same group).
ServiceGroupsAdd times required to service a group of stops.
Starts & EndsDetermine locations where a vehicle should start and/or end its route. This option may be used to set up depots, as in the traditional definition of a VRP.
ShiftsSet shifts for vehicles in which the routes have to operate. It also enables estimated time of arrival and departure in the output.
BacklogsEstablish a pre-assigned route for vehicles.
VelocitiesAdd velocities to vehicles to be used with the default Haversine TravelTimeMeasures.
InitializationCostsAdd initialization costs to vehicles.
AlternatesSpecify a set of alternate stops per vehicle of which exactly one stop will be assigned to the vehicle.
UpdatePersonalize the value function and bookkeeping of custom data.
LimitsSet custom limits for routes, based on custom measures.
ConstraintCreate a custom constraint that restricts how stops are routed for a vehicle.
ValueFunctionMeasures & TravelTimeMeasuresCustomize the measure (cost of going from one location to another) that is optimized for each vehicle and the time measure used for keeping track of time.
FilterCreate a custom filter that restricts which stops are eligible to be serviced by which vehicles.
FilterWithRouteLike Filter, but more flexible.
FormatChange the marshalled format of router.
Minimize & MaximizeSet the solver type to be a minimizer or maximizer.
SelectorCustomize the assigner to determine the order in which stops are selected for assignment.
SorterCustomize the assigner to determine the order in which vehicles are selected for assignment.
ThreadsCustomize ALNS implementation.

Configure Options

router is configured through a list of options that are passed in to the NewRouter function. The opts ...Option argument implies that any number of options can be passed, or none at all. Sometimes, not all the options needed to configure the router are available at the time it is instantiated. The Options function allows the router to be configured at any time after it has been declared.

Example

In this example, the Options function is showcased using vehicle's start and end locations.

The main.go used to configure a vehicle's start and end locations can be modified to pass the vehicle end locations using the Options method, as opposed to configuring this option as an argument for the NewRouter function:

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

// This struct describes the expected json input by the runner.
type input struct {
	Stops    []route.Stop     `json:"stops,omitempty"`
	Vehicles []string         `json:"vehicles,omitempty"`
	Starts   []route.Position `json:"starts,omitempty"`
	Ends     []route.Position `json:"ends,omitempty"`
}

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

	// Set the ending locations for each vehicle using the Options function.
	if err := router.Options(route.Ends(i.Ends)); err != nil {
		return nil, err
	}

	return router.Solver(opt)
}
Copy

Executing the code above with the start and end locations sample input.json file will result in the same solution as passing the option directly through the NewRouter function.

Capacity

Adding capacities to vehicles is a common task in vehicle routing problems. This is known as the capacitated vehicle routing problem (CVRP). Stops have quantities associated to them that decrease or increase a vehicle's capacity. For example, a fuel-delivery truck can only hold a certain volume of fuel or a meal-delivery courier can only deliver three orders simultaneously, to keep them from losing freshness. In the case of sourcing, stops increase the vehicle's capacity since the vehicle is only performing pickups.

router provides the Capacity option to configure a capacity constraint for the routing problem. This is done by specifying the stops' quantities and the vehicles' capacities. A stop's quantity:

  • decreases a vehicle's capacity if it is negative;
  • increases a vehicle's capacity if it is positive.

The Capacity option may be used multiple times if various dimensions need to be limited (for example, limiting weight and volume).

The aim of this example is to add a quantity demanded to stops and a limited capacity to vehicles.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the capacity of each vehicle is not exceeded and the stops are assigned in a fashion that minimizes the route distance.

{
  "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"],
  "quantities": [-1, -1, -1, -1, -1, -1, -1],
  "capacities": [3, 4]
}
Copy

Precedence

Pickups & deliveries are widely used in vehicle routing problems because often one or more items need to be picked up along the route before they are delivered to a customer. This is known as the vehicle routing problem with pickups & deliveries (VRPPD).

router provides the Precedence option to configure a precedence relation between stops. This is done by adding a list of precedence jobs. For each job, it is specified that a stop (pick up) must precede another stop (drop off) in the same route. A stop may appear in several jobs, meaning that the option allows you to specify many pickups before a drop off and vice versa.

The aim of this example is to define two precedence instructions.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that one vehicle serves the stop Arashiyama Bamboo Forest whereas the other services the rest of the stops. Note that in the extended route the precedence constraints are fulfilled and Fushimi Inari Taisha and Gionmachi are visited before Kiyomizu-dera.

{
  "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"],
  "precedences": [
    { "pick_up": "Fushimi Inari Taisha", "drop_off": "Kiyomizu-dera" },
    { "pick_up": "Gionmachi", "drop_off": "Kiyomizu-dera" }
  ]
}
Copy

Service Times

In vehicle routing problems it is often useful to account for the amount of time required to service a stop. This allows for a VRP model that aligns more closely with reality because loading and unloading times are represented in the model. This information can be added to the model using the Services option.

The Services option is often combined with the Shifts and the Windows options.

In this example, you define service times for a few stops.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the route durations in the output file now not only accounts for the travel time but also the given service times.

{
  "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"],
  "service_times": [
    {
      "id": "Fushimi Inari Taisha",
      "duration": 900
    },
    {
      "id": "Kiyomizu-dera",
      "duration": 900
    },
    {
      "id": "Kyoto Imperial Palace",
      "duration": 900
    },
    {
      "id": "Kinkaku-ji",
      "duration": 900
    }
  ]
}
Copy

Windows

In vehicle routing problems stops often have to be serviced within specific time windows. E.g., in a bike sharing problem the stations have to be filled up with bikes while they are empty or bikes have to be picked up while they are full. This is known as the vehicle routing problem with time windows (VRPTW). You can configure time windows for stops with the provided windows option.

The Windows option must be used together with the Shifts option.

The Windows option is often used together with the Services option.

Here, you define time windows and service times for certain stops and define shifts for both vehicles.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that given the shift availability of the vehicles, stops Fushimi Inari Taisha and Kiyomizu-dera are assigned to vehicle v1 as they must be serviced before 12 pm. On the other hand, stops Arashiyama Bamboo Forest and Kinkaku-ji are assigned to vehicle v2, given that they must be visited after mid-day.

{
  "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"],
  "hard_windows": [
    {
      "time_window": {
        "start": "2020-10-17T10:00:00-06:00",
        "end": "2020-10-17T12:00:00-06:00"
      },
      "max_wait": -1
    },
    {
      "time_window": {
        "start": "2020-10-17T10:00:00-06:00",
        "end": "2020-10-17T12:00:00-06:00"
      },
      "max_wait": -1
    },
    {},
    {},
    {},
    {
      "time_window": {
        "start": "2020-10-17T12:00:00-06:00",
        "end": "2020-10-17T14:00:00-06:00"
      },
      "max_wait": -1
    },
    {
      "time_window": {
        "start": "2020-10-17T12:00:00-06:00",
        "end": "2020-10-17T14:00:00-06:00"
      },
      "max_wait": -1
    }
  ],
  "shifts": [
    {
      "start": "2020-10-17T10:00:00-06:00",
      "end": "2020-10-17T12:00:00-06:00"
    },
    {
      "start": "2020-10-17T12:00:00-06:00",
      "end": "2020-10-17T14:00:00-06:00"
    }
  ],
  "service_times": [
    {
      "id": "Fushimi Inari Taisha",
      "duration": 900
    },
    {
      "id": "Kiyomizu-dera",
      "duration": 900
    },
    {
      "id": "Kyoto Imperial Palace",
      "duration": 900
    },
    {
      "id": "Kinkaku-ji",
      "duration": 900
    }
  ]
}
Copy

Attribute

In vehicle routing problems stops can sometimes only be served by specific vehicles. E.g., some delivery items may need a cooling system to keep fresh or maybe larger items must be delivered on a truck and do not fit in a smaller vehicle.

The Attribute option configures compatibility attributes for stops and vehicles separately. This is done by specifying a list of attributes for stops and vehicles, respectively. Stops that have configured attributes are only compatible with vehicles that match at least one of them. Stops that do not have any specified attributes are compatible with any vehicle. Vehicles that do not have any specified attributes are only compatible with stops without attributes.

The aim of this example is to define compatibility attributes for stops and vehicles.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the stop Fushimi Inari Taisha has been assigned to v1 and the stops Arashiyama Bamboo Forest and Kinkaku-ji have been assigned to v2 due to the compatibility attributes. All other stops are cost-optimally assigned to the vehicles.

{
  "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"],
  "vehicle_attributes": [
    {
      "id": "v1",
      "attributes": ["A"]
    },
    {
      "id": "v2",
      "attributes": ["B"]
    }
  ],
  "stop_attributes": [
    {
      "id": "Fushimi Inari Taisha",
      "attributes": ["A", "C"]
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "attributes": ["B"]
    },
    {
      "id": "Kinkaku-ji",
      "attributes": ["B"]
    }
  ]
}
Copy

Limit Durations

In vehicle routing problems it is sometimes required to limit routes. To limit the route length or duration router offers the LimitDistances and LimitDurations options. For all other use cases, utilize the provided Limits option to configure custom limits for vehicles.

To limit the route's duration, a slice of values must be provided representing the allowed time. The values must be provided in the same unit as the underlying TravelTimeMeasures. If you did not use the TravelTimeMeasure option to use your own travel time measure, the values must be provided in seconds. In addition, a flag must be specified to ignore or adhere to the triangle inequality.

The aim of this example is to define limits for vehicles and an unassigned penalty to be able to receive a solution.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that two stops are unassigned in the solution. Because of the route's limitation, it was not possible to add them to either of the two routes anymore.

{
  "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"],
  "limits": [500, 500],
  "ignore_triangularity": true,
  "penalties": [2000000, 2000000, 2000000, 2000000, 2000000, 2000000, 2000000]
}
Copy

Limit Distances

Sometimes it is required to limit routes. To limit the route length or duration, router offers the LimitDistances and LimitDurations options. For all other use cases, utilize the provided Limits option to configure custom limits for vehicles.

To limit the route's length, a slice of values representing the maximum length must be provided. The values must be given in meters as the underlying measure uses this unit. In addition, a flag must be specified to ignore or adhere to the triangle inequality.

The aim of this example is to define distance limits for vehicles and an unassigned penalty to be able to receive a solution.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that one stop is unassigned in the solution. Because of the route's limitation, it was not possible to add it to either of the two routes anymore.

{
  "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"],
  "limits": [9000, 9000],
  "ignore_triangularity": true,
  "penalties": [2000000, 2000000, 2000000, 2000000, 2000000, 2000000, 2000000]
}
Copy

Unassigned

Vehicle routing problems are infeasible if no solution satisfies the set of considerations specific to the problem. For example, stop quantities may exceed a vehicle's capacity, in which case the vehicle can not service all stops. Another example is a vehicle having to fulfill time windows but not being able to arrive at a certain stop in the desired time frame. When a problem is infeasible, router will return an empty solution state because, by default, it must assign all stops to the solution.

router provides the Unassigned option to configure penalties for stops. When the stops can not be serviced due to a consideration (constraint) being violated, the solver attempts to make the solution feasible by leaving stops unassigned. The penalties are added to the value of the solution for the stops that are not assigned. Normally, the value of these penalties is larger than the assignment cost.

In this example, the stops' demands exceed the vehicles' capacity and penalties are provided to leave stops unassigned.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that there are three stops that were not assigned, as the total stop quantity exceeds the total vehicle capacity. The stops that are assigned minimize the total distance.

{
  "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"],
  "quantities": [-1, -1, -1, -1, -1, -1, -1],
  "capacities": [2, 2],
  "penalties": [10000, 10000, 10000, 10000, 10000, 10000, 10000]
}
Copy

Grouper

In vehicle routing problems stops often have to be serviced in the same route together. In many cases this is a simple pickup/dropoff problem which you can easily address with our precedence option. However, in some cases you may need to address more specific requirements that involve setting up groups that are served by the same vehicle.

router provides the Grouper option to set up groups of stops. This is done by adding a stop matrix that defines the groups.

The aim of this example is to create two groups of stops by ID that must be served together.

Save the included input.json and main.go in your project folder. This creates 2 groups which you then pass into the Grouper option. Execute the example and you'll see from the output.json file that stops which are grouped together are assigned to the same route. In this case both groups are assigned to the same vehicle for optimality reasons.

{
  "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"],
  "groups": [
    ["Fushimi Inari Taisha", "Kiyomizu-dera", "Nijō Castle"],
    ["Gionmachi", "Kinkaku-ji", "Arashiyama Bamboo Forest"]
  ]
}
Copy

Service Groups

In vehicle routing problems you sometimes need to account for the amount of extra time required to enter a building or a fenced area. This allows for a more realistic VRP model that includes more than just loading and unloading times. This information can be added to the model using the ServiceGroups option.

The ServiceGroups option is often combined with the Services, Shifts and Windows options.

In this example, you define a service group of a few stops. In addition, the Shifts option is used to have ETA and ETD in the output.

Save the included input.json and main.go in your project folder. Execute the example and open the output.json file. The estimated arrival and departure of the stops show that for the stops Fushimi Inari Taisha and Kiyomizu-dera the service time has been applied only once for both stops, because they were approached as one group. Also, the service time was applied to Nijō Castle again, since it was approached as an isolated stop.

{
  "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"],
  "service_groups": [
    {
      "group": ["Fushimi Inari Taisha", "Kiyomizu-dera", "Nijō Castle"],
      "duration": 900
    }
  ],
  "shifts": [
    {
      "start": "2020-10-17T10:00:00-06:00"
    },
    {
      "start": "2020-10-17T12:00:00-06:00"
    }
  ]
}
Copy

Start and Ends

Traditional vehicle routing problems require a depot where a route starts and ends. On the other hand, open vehicle routing problems (OVRP) do not specify an ending location for a vehicle. router provides the Starts and Ends options to configure starting and ending locations for the vehicles, respectively. These options are independent of each other, so you could solve VRPs by configuring the same starts and ends or OVRPs by configuring either of those.

In this example, vehicle v1 has a starting location (but no end) and vehicle v2 has the same starting and ending locations.

Save the included input.json and main.go in your project folder. Note that the starts and ends indices map to the indices of the vehicles. This means that the starting location of vehicle v1 is {"lon": 135.73723, "lat": 35.04381} and it has an empty ending location.Execute the example and you'll see from the output.json file that v1 has two stops assigned and is an open route, whereas v2 has five stops assigned in a closed route.

{
  "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"],
  "starts": [
    { "lon": 135.73723, "lat": 35.04381 },
    { "lon": 135.758794, "lat": 34.98608 }
  ],
  "ends": [{}, { "lon": 135.758794, "lat": 34.98608 }]
}
Copy

Shifts

In vehicle routing problems it is often necessary to not only know the best route but also the estimated time of arrival (ETA) per stop on the route to inform customers. By default, router provides the route duration but not the ETA because the time reference for the start of the route is missing. To add this information, router provides the Shifts option. If the given shifts not only specify the start times but also a shift's end time, router will make sure that the routes are completed within the given shift's start and end.

The Shifts option is often combined with the Windows option and the Services option.

In this example, you define shifts for both vehicles, but only one vehicle has a start and end time defined.

Save the included input.json and main.go in your project folder. Execute the example and open the output.json file. The output now includes estimated time of arrival and departure (note, these times are equal for each stop in this example) in addition to route duration. To take into account service times at a stop, please use the Services option. Because of the short time window that the shift offers for v1, most stops are assigned to v2.

{
  "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"],
  "shifts": [
    {
      "start": "2020-10-17T10:00:00-06:00",
      "end": "2020-10-17T10:15:00-06:00"
    },
    {
      "start": "2020-10-17T12:00:00-06:00"
    }
  ]
}
Copy

Backlogs

In vehicle routing problems it is sometimes needed to assign stops directly to vehicles. This can be the case if only some vehicles do have a specific configuration, such as a cooling system. Another common use is that sometimes routes from previous decisions exist that cannot be changed.

router provides the Backlogs option to configure backlogs for vehicles. This is done by setting a list of stops for a vehicle.

The aim of this example is to define a backlog for a vehicle.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that both stops, Arashiyama Bamboo Forest and Kinkaku-ji, which have been defined in a backlog for vehicle v1, are assigned to that vehicle.

{
  "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"],
  "backlogs": [
    {
      "vehicle_id": "v1",
      "stops": ["Arashiyama Bamboo Forest", "Kinkaku-ji"]
    }
  ]
}
Copy

Velocities

The default TravelTimeMeasures inrouter are constructed as a Haversine measure with the default velocity of 10m/s. It is likely that the Haversine measures (distances) used provide accurate enough results but the default velocity (10m/s) does not match your vehicles and thus, the calculated times are not leading to the expected results. In this case you can use the Velocities option and provide more accurate velocities to be used for the calculation of time of arrivals. However, if you are still not satisfied with the results, you can create your own TravelTimeMeasure that is not based on Haversine. You can read more on custom TravelTimeMeasures here.

In this example, you define velocities for every vehicle.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the routes have not changes compared to other examples because the solution cost is still calculated by the same Haversine measure. However, you can see that the route_duration in the output is very long as a result of the slow velocities provided in the input 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"],
  "velocities": [1.5, 1.5]
}
Copy

Initialization Cost

Adding initialization costs to vehicles is a common task in vehicle routing problems. The activation or initialization of a vehicle can be useful if a vehicle isn't permanently in the fleet, but has to be rented. for example. If this vehicle isn't needed in a solution, then the rental cost can be saved. router provides the InitializationCosts option to configure the costs per vehicle that are added to the value function when a vehicle is used. This is done by specifying the vehicles' initialization costs.

The aim of this example is to add initialization costs to vehicles. v1 has an expensive initialization cost associated with it, while v2 does not.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that all stops are assigned to v2 given that v1 is the most expensive vehicle to operate.

{
  "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"],
  "initialization_costs": [100000, 0]
}
Copy

Alternates

In vehicle routing problems you may want your drivers to have a break at specific locations that are especially suitable for this. router provides the Alternates option to configure such stops for each vehicle. router will then add exactly one of those stops optimally to the vehicle's route.

The Alternates option is often combined with the Windows and the Services option to enforce a driver's break during the given time window for the specified "service time".

The aim of this example is to define alternate stops (or breaks) for a vehicle. Note, this example also uses the Capacity option for illustrative purposes.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that only one alternate stop was assigned to each vehicle. In this example, Nijō Castle was assigned to v1 and Kiyomizu-dera was assigned to v2.

{
  "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"],
  "alternate_stops": [
    {
      "vehicle_id": "v1",
      "stops": ["Nijō Castle", "Kiyomizu-dera"]
    },
    {
      "vehicle_id": "v2",
      "stops": ["Nijō Castle", "Kiyomizu-dera"]
    }
  ],
  "quantities": [-1, -1, -1, -1, -1, 0, 0],
  "capacities": [3, 3]
}
Copy

Value Functions and State Updates

router uses decision diagrams to search for the best solution in the time alloted. Sometimes you may want to interact with state transitions to keep track of custom information. In particular, custom information may be used to calculate the value function to optimize. router provides the Update option to:

  • Create a personalized value function.
  • Perform bookkeeping of custom data.

The Update option takes two arguments: VehicleUpdater, which replaces the value function of each vehicle and PlanUpdater, which replaces the value function for the entire plan. You can specify custom types to implement these interfaces and personalize the state transitions. The user-defined custom types that implement the interfaces will be marshalled to be part of the output. To achieve efficient customizations, always try to update the components of the state that changed, as opposed to the complete state in both the vehicle and plan.

To customize the value function that will be optimized by each interface, the integer return value from the Update method in either interface must not be nil. If the value is nil, the default value is used and it corresponds to the configured measure.

The Update option is often used together with the Sorter option.

In this example, custom data is updated and a personalized value function is used. A custom type is used to save the locations, which map a stop's ID to its index in the corresponding route. The value function is modified to apply a score which is different for each vehicle.

Save the included input.json and main.go in your project folder. Execute the example and open the output.json file. Note that an updater object is marshalled as part of the output holding the information for the locations indicating the route position for each stop. Most of the stops are assigned to the vehicle with the lowest score.

{
  "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"],
  "score": { "v1": 10, "v2": 1 }
}
Copy

Route Limits

In vehicle routing problems it is sometimes required to limit routes. To limit the route length or duration, router offers the LimitDistances and LimitDurations options. For all other use cases it provides the Limits option to configure limits for vehicles. This is done by setting a list of values and custom measures that must not be exceeded. The values must be provided in the same unit as the underlying measure for the vehicles. In addition, a flag must be specified to ignore or adhere to the triangle inequality.

The aim of this example is to define custom limits for vehicles. The number of stops is limited to 4. A constant measure is used so the "cost" of going from one stop to another is simply 1.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json that the routes do not hold more than 4 stops. The limit is set to 3 in the input.json because it counts transitions among stops, meaning that there are 3 transitions performed in 4 stops.

{
  "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"],
  "limits": [3, 3],
  "ignore_triangularity": true
}
Copy

Custom Constraint

router works with common constraints for vehicle routing problems out of the box, such as capacity or limits. But some problems may need very specific constraints.

router provides the Constraint option to add a custom constraint. This is done by defining a custom type that implements the Constraint interface on the vehicle. An instance of this type is then passed into the Constraint option with the vehicle IDs to which this constraint should be applied. It is possible to use the Constraint option multiple times to add multiple custom constraints.

Constraints make sure that when stops are being inserted into a route, the route is still feasible. Filters, however, are used to prevent assigning stops to a vehicle that they are incompatible with under any circumstance. It is often good practice to also make use of a filter when using a custom constraint.

For this example, three vehicle are used and a custom type is defined to create a custom constraint: stops assigned together must have matching labels. To achieve this, a labels key is added to the input indexed the same as the stops and a custom constraint is created. The label of the first stop in the route is compared against all other labels. If there is a difference, the constraint is violated.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that stops routed together have matching labels.

{
  "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", "v3"],
  "labels": [
    "vegan",
    "vegan",
    "non-vegan",
    "non-vegan",
    "non-vegan",
    "vegan",
    "non-vegan"
  ]
}
Copy

Measures - Cost

Measures determine the cost of connecting two things together. In routing this means the cost of going from one location to another. This cost can be calculated using a generic measure that simply computes distance or duration, but it can also represent any type of KPI as well, such as monetary value. router offers the following options to interact with custom measures:

  • ValueFunctionMeasures. Modify the measures that represent the routing cost being optimized (used to obtain the best solution).
  • TravelTimeMeasures. Modify the measures used to calculate the route durations and the estimated time of arrival/departure when using the Windows or Shifts option. TravelTimeMeasures must not account for any service times. Service times have to be added using Services option.

These options require a list of measures per vehicle. Nextmv provides several prebuilt measures and functionality to go with them. The measure interface is standardized, enabling measures to be used interchangeably within router. Nextmv can be used with any mapping service - we have customers using Open Source Routing Machine (OSRM), Google Maps Distance Matrix API, GraphHopper and proprietary internal mapping services.

You can read more about measures in the technical reference.

  • When creating your own measure, it is very important to index stops and vehicles in the expected way. For the measure to work correctly, indices should be given following the format:

    [stop-1, ..., stop-n, vehicle-1-start, vehicle-1-end, ..., vehicle-m-start, vehicle-m-end]

  • When creating your own custom TravelTimeMeasure, please make sure that it does not account for any service times and use the Services option instead.

  • If ValueFunctionMeasures and/or TravelTimeMeasures are not provided, router will default to a Haversine measure for distance calculations and assume a constant speed of 10 m/s for duration. Note, this default speed can be changed using the Velocities option.
  • If you don't want the solver to consider the cost of going from one location to another, set the corresponding cost to be 0. For example, if vehicles don't have ending locations, the cost of going from a vehicle's end to any other location should be 0.

In this example, the TravelTimeMeasures option is set, the Gionmachi stop has has a time window in which is must be serviced, and vehicle Shifts are also used.

Save the included input.json and main.go in your project folder. To create the measure, points are passed to it. These points are indexed following the hint given above, where all the stops are listed first and the vehicles after. Note that since vehicle locations are not given, corresponding points take on the zero value. Execute the example and you'll see from the output.json file that v1 receives most of the stops. One of the stops has a hard window of 15 minutes. Given the shift constraint of 1800 seconds (30 minutes), neither vehicle can service all stops within the given time frame.

{
  "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"],
  "shifts": [
    {
      "start": "2020-10-17T09:00:00-06:00",
      "end": "2020-10-17T09:30:00-06:00"
    },
    {
      "start": "2020-10-17T09:00:00-06:00",
      "end": "2020-10-17T09:30:00-06:00"
    }
  ]
}
Copy

Filter

In vehicle routing problems, sometimes not all stops can be served by every vehicle. router offers the Attribute option to add a compatibility check. For most cases, theFilteroption gives enough flexibility while maintaining simplicity. However, some problems may need to check for general compatibility but also have access to the current solution's route. In this case you can use the FilterWithRoute option.

Filters are used to prevent assigning stops to a vehicle that they are incompatible with under any circumstance. However, if a stop is suitable for a vehicle according to the given filters, assigning it to a vehicle might not result in a valid solution in the current solution. This is checked and limited by the given constraints, e.g. capacities or custom constraints. This means filters are used to exclude stops from being assigned to certain vehicles, while Constraints make sure that when stops are being inserted into a route, the the route is still feasible.

router provides the Filter to add a custom filter.

The aim of this example is to define a function to create a custom filter using the Filter option.

The Filter option works by defining a compatibility function which checks if a vehicle is compatible with a stop. Often the Filter option is combined with the custom constraints option. It is possible to use the Filter option multiple times to add multiple filters.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the stops Arashiyama Bamboo Forest and Kinkaku-ji are assigned to vehicle v1 because they are not compatible with v2, due to the custom filter.

{
  "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

FilterWithRoute

FilterWithRoute adds a new VehicleFilter. Compared to the Filter option, the FilterWithRoute option is more flexible. It defines a function that takes an integer domain of candidate vehicles, and locations that will be assigned to a particular vehicle. It also receives a slice of routes for all vehicles. It returns an integer domain representing vehicles that cannot service the domain of locations.

The aim of this example is to define a function to create a custom filter using the FilterWithRoute option, where a vehicle can not be assigned more than 3 stops.

{
  "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"],
  "penalties": [10000, 10000, 10000, 10000, 10000, 10000, 10000]
}
Copy

Format

By default, router marshals the solution with basic information, similar to this structure:

{
  "unassigned": [
    {
      "id": "...",
      "position": {...}
    },
    {...}
  ],
  "vehicles": [
    {
      "id": "...",
      "route": [
        {
          "id": "...",
          "position": {...}
        },
        {...}
      ],
      "route_duration": ...
    },
    {...}
  ]
}
Copy

In the above snippet, only the unassigned stops and the routes assigned to the vehicles are shown. Sometimes it is useful to modify the output to achieve a desired structure or to showcase custom information.

router provides the Format method to customize the output displayed for the store key. The Format method takes one argument: a callback function where any type may be returned. The returned type should comply with JSON encoding.

The aim of this example is to define a custom output when using multiple vehicles. To modify the default output, only the total number of routes and unassigned stops are displayed.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the marshalled solution state is different than the base router solution.

{
  "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

Minimize and Maximize

Not every vehicle routing problem is about minimizing time or distance. Sometimes, you want to maximize profit or another measure of your business. router provides the Minimize and Maximize options to configure the desired solver type to minimize or maximize the target value, respectively. As a default, router uses minimization as its configuration.

For this example, only one vehicle is used. To minimize the total route distance, the same code from the base router example can be used, given that minimization is the default configuration. The solution for minimization (default or via the Minimize option) should look similar to the below:

{
  "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"]
}
Copy

To maximize you can keep the same inputs, but run a different program. Save the new main.go in your project folder. Execute the example and you'll see from the output.json file that by using the Maximize option, the route distance for a single vehicle is maximized to be the longest possible.

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

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

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

	return router.Solver(opt)
}
Copy

Selector

By default, router looks in the list of stops yet to be assigned and selects the one with the lowest index. However, it may be useful to select the next stop to be inserted into a route differently, which means that the default behaviour needs to overridden.

router provides the Selector option to set up a custom selector for stops. This is done by writing a function that selects the next stop or even multiple stops.

For this example, you define a function in code, not in the input file, to create a custom selector.

Save the included input.json and main.go in your project folder. You create a function to select the next stop based on a score which is then passed into the Selector option. Execute the example and you'll see from the output.json file that the highest priority stops were selected and assigned first.

{
  "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"],
  "score": [5, 4, 6, 7, 3, 2, 1]
}
Copy

Sorter

By default, router determines the order in which the solver attempts to assign locations to vehicles by predicting the cost of that assignment. However, when the value function is overridden, the cost prediction for an assignment should also be adjusted. Its goal is to order vehicles in such a way that those vehicles come first where the assignment of the given locations is cheap in terms of the overridden value function. router provides the Sorter option to set up a custom sorter for vehicles. This is done by writing a function that returns a sorted list of vehicle indices.

In this example, you define a function in code, not in the input file, to create a custom sorter. Note that this change is only needed when you also change the value function and this example is only to demonstrate the usage of the option. To keep the example simple it does not evaluate the cost of an assignment in terms of a changed value function.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the the highest priority stops were selected and assigned first.

{
  "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"],
  "score": [1, 2]
}
Copy

ALNS

router relies on the ALNS heuristic to solve a routing problem. The underlying solver of the router is hybrid, meaning it is composed of Decision Diagrams (DD) and ALNS solvers. The ALNS solvers also use DDs to find a feasible solution. After feasible solutions are encountered, ALNS is activated to search for the best solution in the time alloted. To customize how ALNS is used in the router, the following options are provided:

  • Threads: Sets the number of threads that the hybrid solver uses. If the number is one, it means that only the first solver is used, which corresponds to pure DD. As a default, threads are calculated based on the number of machine processors

The aim of this example is to briefly show how you can interact with the configuration of the ALNS heuristic. The number of threads are specified as part of the input.

Save the included input.json and main.go in your project folder. Execute the example and you'll see from the output.json file that the stops are assigned in a fashion that minimizes the route distance.

{
  "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

Page last updated

Go to on-page nav menu