## Overview

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem. In a VRP, the goal is to find the optimal set of routes for a fleet of vehicles delivering goods or services to various locations. The VRP was first proposed by Dantzig and Ramser in 1959.

Like the TSP, the VRP can be represented by a graph with distances assigned to the edges.

If you try to find a set of routes with the least total distance, with no additional constraints on the vehicles, the optimal solution is to assign all locations to a single vehicle and leave the rest idle. In this case, the problem reduces to a TSP.

A more interesting problem is to minimize the length of the longest single route for all vehicles, as shown in the next example.

VRPs can also have additional constraints on the vehicles—for example, lower and upper bounds on the number of locations each vehicle visits, or the length of each route.

In later sections, we'll discuss other types of VRP constraints, including:

- Capacity constraints: the total demand of the locations on a vehicle's route cannot exceed its capacity. For example, the demands might be the sizes of packages the vehicle has to deliver to each location, where the total size of all the packages can't exceed the vehicle's carrying capacity.
- Time windows:
each location must be serviced within a time window
[a
_{i}, b_{i}] and waiting times are allowed. - Precedence relations between pairs of locations: for example,
location
*j*cannot be visited before location*i*.

You can solve VRPs using the OR-Tools vehicle routing library. The routing library is a layer on top of the constraint programming solver. The section RoutingModel describes the C++ methods for solving routing problems.

## Example: minimizing the longest single route

In this example, a company needs to visit some customer locations in a
city made up of identical rectangular blocks.
A map of the city is shown below, with the company
location marked in black and the locations to visit in blue.
The problem is to find an assignment of routes for which the longest
single route has minimum distance. (**Note:** this is *not* the same problem
as minimizing the total length of all routes.)

### Manhattan distance

This example uses a definition of distance that differs from the usual Euclidean metric,
called the Manhattan distance.
The Manhattan distance between two points, (x_{1}, y_{1}) and
(x_{2}, y_{2}), is the absolute value of the difference in their x
coordinates plus the absolute value of the difference in the y coordinates:

|x_{2}- x_{1}| + |y_{2}- y_{1}|

This distance is motivated by routing problems in a city that is laid out in rectangular blocks (like Manhattan), where you can only travel in directions parallel to the sides of the blocks. In this situation, the formula above gives the travel distance between any two street locations in the city. (For example, if you have to go four blocks east and seven blocks north, your travel distance is eleven blocks.)

## Solving the example with OR-Tools

The following sections walk through a Python program that solves the problem in this example.

### Model the problem

The following code defines the data for the problem.

class CityBlock(): """City block definition""" @property def width(self): """Gets Block size West to East""" return 228/2 @property def height(self): """Gets Block size North to South""" return 80 class DataProblem(): """Stores the data for the problem""" def __init__(self): """Initializes the data for the problem""" self._num_vehicles = 4 # Locations in block unit locations = \ [(4, 4), # depot (2, 0), (8, 0), # row 0 (0, 1), (1, 1), (5, 2), (7, 2), (3, 3), (6, 3), (5, 5), (8, 5), (1, 6), (2, 6), (3, 7), (6, 7), (0, 8), (7, 8)] # locations in meters using the city block dimension city_block = CityBlock() self._locations = [( loc[0]*city_block.width, loc[1]*city_block.height) for loc in locations] self._depot = 0 @property def num_vehicles(self): """Gets number of vehicles""" return self._num_vehicles @property def locations(self): """Gets locations""" return self._locations @property def num_locations(self): """Gets number of locations""" return len(self.locations) @property def depot(self): """Gets depot location index""" return self._depot

The data consists of:

- a
`num_vehicles`

variable — The number of vehicles in the fleet. - a
`locations`

array — A two-dimensional array of points in the plane. - a
`depot`

variable — The depot index in the locations array. we assume that all vehicles start at the same location, called the depot. Alternatively, you can allow vehicles to start and end any location.

### Define the distance function

The function that calculates the Manhattan distance between points is shown below.

def manhattan_distance(position_1, position_2): """Computes the Manhattan distance between two points""" return (abs(position_1[0] - position_2[0]) + abs(position_1[1] - position_2[1]))

The following class creates the distance function that is passed to the solver. As in the TSP example, the computed distances between nodes are stored in a matrix to speed up the function call.

class CreateDistanceEvaluator(object): # pylint: disable=too-few-public-methods """Creates callback to return distance between points.""" def __init__(self, data): """Initializes the distance matrix.""" self._distances = {} # precompute distance between location to have distance callback in O(1) for from_node in xrange(data.num_locations): self._distances[from_node] = {} for to_node in xrange(data.num_locations): if from_node == to_node: self._distances[from_node][to_node] = 0 else: self._distances[from_node][to_node] = ( manhattan_distance( data.locations[from_node], data.locations[to_node])) def distance_evaluator(self, from_node, to_node): """Returns the manhattan distance between the two nodes""" return self._distances[from_node][to_node]

### Add a distance dimension

To solve this VRP, you need to create a distance
*dimension*, which computes
the cumulative distance traveled by each vehicle along its route. You can then
set a cost equal to the maximum of the total distances along each route.

For more information, see Dimensions.

To add a distance dimension, use the solver's
`AddDimension`

method.
The following code creates a dimension for the distance and sets the cumulative distance cost.

def add_distance_dimension(routing, distance_evaluator): """Add Global Span constraint""" distance = "Distance" maximum_distance = 3000 routing.AddDimension( distance_evaluator, 0, # null slack maximum_distance, # maximum distance per vehicle True, # start cumul to zero distance) distance_dimension = routing.GetDimensionOrDie(distance) # Try to minimize the max distance among vehicles. # /!\ It doesn't mean the standard deviation is minimized distance_dimension.SetGlobalSpanCostCoefficient(100)

In this case, the significant inputs to the function `add_distance_dimension`

are the following:

`distance_evaluator`

— Returns the distance between locations.`maximum_distance`

— The maximum distance that each vehicle can travel.

The main function calls `add_distance_dimension`

after
calling `CreateDistanceEvaluator`

.

add_distance_dimension(routing, distance_evaluator)

### Define the solution printer

The code that outputs the solution is shown below.

class ConsolePrinter(): """Print solution to console""" def __init__(self, data, routing, assignment): """Initializes the printer""" self._data = data self._routing = routing self._assignment = assignment @property def data(self): """Gets problem data""" return self._data @property def routing(self): """Gets routing model""" return self._routing @property def assignment(self): """Gets routing model""" return self._assignment def print(self): """Prints assignment on console""" # Inspect solution. total_dist = 0 for vehicle_id in xrange(self.data.num_vehicles): index = self.routing.Start(vehicle_id) plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id) route_dist = 0 while not self.routing.IsEnd(index): node_index = self.routing.IndexToNode(index) next_node_index = self.routing.IndexToNode( self.assignment.Value(self.routing.NextVar(index))) route_dist += manhattan_distance( self.data.locations[node_index], self.data.locations[next_node_index]) plan_output += ' {node_index} -> '.format( node_index=node_index) index = self.assignment.Value(self.routing.NextVar(index)) node_index = self.routing.IndexToNode(index) total_dist += route_dist plan_output += ' {node_index}\n'.format( node_index=node_index) plan_output += 'Distance of the route {0}: {dist}\n'.format( vehicle_id, dist=route_dist) print(plan_output) print('Total Distance of all routes: {dist}'.format(dist=total_dist))

The method `print()`

displays the route for each vehicle
(i.e. the list of visited nodes), and computes the distance of the routes.
Note that these distances include the distance from the depot to the first
location in the route and the distance from the last location back to the depot.

### Main function

Now, you have everything to create the main function.

First, you create the problem data:

data = DataProblem()

Next, create the routing model solver:

routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot)

Then, provide the distance evaluator so the solver can compute the distances between locations.

distance_evaluator = CreateDistanceEvaluator(data).distance_evaluator routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)

Next, add the distance dimension.

add_distance_dimension(routing, distance_evaluator)

You also have to specify a heuristic method to find the first solution:

search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

Finally, you can run the solver:

assignment = routing.SolveWithParameters(search_parameters)

And print the solution:

printer = ConsolePrinter(data, routing, assignment) printer.print()

### Running the program

When you run the program, it displays the following output:

Route for vehicle 0: 0 -> 8 -> 6 -> 2 -> 5 -> 0 Distance of the route 0: 1552 Route for vehicle 1: 0 -> 7 -> 1 -> 4 -> 3 -> 0 Distance of the route 1: 1552 Route for vehicle 2: 0 -> 9 -> 10 -> 16 -> 14 -> 0 Distance of the route 2: 1552 Route for vehicle 3: 0 -> 12 -> 11 -> 15 -> 13 -> 0 Distance of the route 3: 1552 Total Distance of all routes: 6208

The graph below shows the assigned routes.

### The entire program

The entire program that minimizes the longest single route is shown below.

"""Vehicle Routing Problem""" from __future__ import print_function from six.moves import xrange from ortools.constraint_solver import pywrapcp from ortools.constraint_solver import routing_enums_pb2 ########################### # Problem Data Definition # ########################### class CityBlock(): """City block definition""" @property def width(self): """Gets Block size West to East""" return 228/2 @property def height(self): """Gets Block size North to South""" return 80 class DataProblem(): """Stores the data for the problem""" def __init__(self): """Initializes the data for the problem""" self._num_vehicles = 4 # Locations in block unit locations = \ [(4, 4), # depot (2, 0), (8, 0), # row 0 (0, 1), (1, 1), (5, 2), (7, 2), (3, 3), (6, 3), (5, 5), (8, 5), (1, 6), (2, 6), (3, 7), (6, 7), (0, 8), (7, 8)] # locations in meters using the city block dimension city_block = CityBlock() self._locations = [( loc[0]*city_block.width, loc[1]*city_block.height) for loc in locations] self._depot = 0 @property def num_vehicles(self): """Gets number of vehicles""" return self._num_vehicles @property def locations(self): """Gets locations""" return self._locations @property def num_locations(self): """Gets number of locations""" return len(self.locations) @property def depot(self): """Gets depot location index""" return self._depot ####################### # Problem Constraints # ####################### def manhattan_distance(position_1, position_2): """Computes the Manhattan distance between two points""" return (abs(position_1[0] - position_2[0]) + abs(position_1[1] - position_2[1])) class CreateDistanceEvaluator(object): # pylint: disable=too-few-public-methods """Creates callback to return distance between points.""" def __init__(self, data): """Initializes the distance matrix.""" self._distances = {} # precompute distance between location to have distance callback in O(1) for from_node in xrange(data.num_locations): self._distances[from_node] = {} for to_node in xrange(data.num_locations): if from_node == to_node: self._distances[from_node][to_node] = 0 else: self._distances[from_node][to_node] = ( manhattan_distance( data.locations[from_node], data.locations[to_node])) def distance_evaluator(self, from_node, to_node): """Returns the manhattan distance between the two nodes""" return self._distances[from_node][to_node] def add_distance_dimension(routing, distance_evaluator): """Add Global Span constraint""" distance = "Distance" maximum_distance = 3000 routing.AddDimension( distance_evaluator, 0, # null slack maximum_distance, # maximum distance per vehicle True, # start cumul to zero distance) distance_dimension = routing.GetDimensionOrDie(distance) # Try to minimize the max distance among vehicles. # /!\ It doesn't mean the standard deviation is minimized distance_dimension.SetGlobalSpanCostCoefficient(100) ########### # Printer # ########### class ConsolePrinter(): """Print solution to console""" def __init__(self, data, routing, assignment): """Initializes the printer""" self._data = data self._routing = routing self._assignment = assignment @property def data(self): """Gets problem data""" return self._data @property def routing(self): """Gets routing model""" return self._routing @property def assignment(self): """Gets routing model""" return self._assignment def print(self): """Prints assignment on console""" # Inspect solution. total_dist = 0 for vehicle_id in xrange(self.data.num_vehicles): index = self.routing.Start(vehicle_id) plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id) route_dist = 0 while not self.routing.IsEnd(index): node_index = self.routing.IndexToNode(index) next_node_index = self.routing.IndexToNode( self.assignment.Value(self.routing.NextVar(index))) route_dist += manhattan_distance( self.data.locations[node_index], self.data.locations[next_node_index]) plan_output += ' {node_index} -> '.format( node_index=node_index) index = self.assignment.Value(self.routing.NextVar(index)) node_index = self.routing.IndexToNode(index) total_dist += route_dist plan_output += ' {node_index}\n'.format( node_index=node_index) plan_output += 'Distance of the route {0}: {dist}\n'.format( vehicle_id, dist=route_dist) print(plan_output) print('Total Distance of all routes: {dist}'.format(dist=total_dist)) ######## # Main # ######## def main(): """Entry point of the program""" # Instantiate the data problem. data = DataProblem() # Create Routing Model routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot) # Define weight of each edge distance_evaluator = CreateDistanceEvaluator(data).distance_evaluator routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator) add_distance_dimension(routing, distance_evaluator) # Setting first solution heuristic (cheapest addition). search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. assignment = routing.SolveWithParameters(search_parameters) printer = ConsolePrinter(data, routing, assignment) printer.print() if __name__ == '__main__': main()

## Dimensions

This section provides more information about *dimensions*, which keep track of
quantities that accumulate along vehicle routes. In the previous VRP example
the quantity is the total distance each vehicle travels. Another example is
given by the
capacitated vehicle routing problem, in which the
vehicles pick up and deliver packages. In that case, the dimension tracks the total amount of
packages (by either size or weight) carried by each vehicle.

Each dimension contains a callback for the quantity accumulated along each route,
along with related data and variables.
You can add a dimension to a routing problem using the solver's
`AddDimension`

method. See
Add a distance dimension for an example.

Internally, a dimension stores two types of variables that are linked to quantities that change along routes:

*Transit variables*— The increase or decrease of the quantity on each edge .*Cumulative variables*— The total accumulated quantity at each node.

In more general routing problems, you can minimize the *global
dimension span* of a quantity, which is the difference
between the largest value of the cumulative variables at the end of each vehicle's route,
minus the smallest value of the
cumulative variables of the cumulative variables at the start of each vehicle's route. In
other words, for a fleet of *k* vehicles whose the first node of
the route for the vehicle *i* is *start _{i}* and the last node is

*end*, the global span is:

_{i}max({cumul(end_{1}),...,cumul(end_{k})}) - min({cumul(start_{1}),...,cumul(start_{k})})

When the quantity is distance, the cumulative variables at the start of each route are zero, because no distance has been travelled at the start. However, for other quantities, such as the total weight of packages carried by each vehicle, the cumulative variables might be greater than zero at the start—for example, if some packages are loaded onto the vehicle at the depot.