## 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 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 function defines the data for the problem.

def create_data_model(): """Stores the data for the problem""" data = {} # Locations in block units _locations = \ [(4, 4), # depot (2, 0), (8, 0), # locations to visit (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)] # Multiply coordinates in block units by the dimensions of an average city block, 114m x 80m, # to get location coordinates. data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations] data["num_locations"] = len(data["locations"]) data["num_vehicles"] = 4 data["depot"] = 0 return data

The data consists of:

`num_vehicles`

: The number of vehicles in the fleet.`_locations`

: A two-dimensional array of points in the plane. Note that the function multiplies the coordinates of the points in the array by constants to make the example data—`data["locations"]`

—similar in scale to real city blocks.`depot`

: 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 callback

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 function creates the distance callback 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.

def create_distance_callback(data): """Creates callback to return distance between points.""" _distances = {} for from_node in range(data["num_locations"]): _distances[from_node] = {} for to_node in range(data["num_locations"]): if from_node == to_node: _distances[from_node][to_node] = 0 else: _distances[from_node][to_node] = ( manhattan_distance(data["locations"][from_node], data["locations"][to_node])) def distance_callback(from_node, to_node): """Returns the manhattan distance between the two nodes""" return _distances[from_node][to_node] return distance_callback

### 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_callback): """Add Global Span constraint""" distance = 'Distance' maximum_distance = 3000 # Maximum distance per vehicle. routing.AddDimension( distance_callback, 0, # null slack maximum_distance, True, # start cumul to zero distance) distance_dimension = routing.GetDimensionOrDie(distance) # Try to minimize the max distance among vehicles. distance_dimension.SetGlobalSpanCostCoefficient(100)

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

are the following:

`distance_callback`

— Returns the distance between locations.`maximum_distance`

— The maximum distance that each vehicle can travel.

The main function calls `add_distance_dimension`

after
calling `create_distance_callback`

.

add_distance_dimension(routing, distance_callback)

### Define the solution printer

The code that outputs the solution is shown below.

def print_solution(data, routing, assignment): """Print routes on console.""" total_distance = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) distance = 0 while not routing.IsEnd(index): plan_output += ' {} ->'.format(routing.IndexToNode(index)) previous_index = index index = assignment.Value(routing.NextVar(index)) distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id) plan_output += ' {}\n'.format(routing.IndexToNode(index)) plan_output += 'Distance of route: {}m\n'.format(distance) print(plan_output) total_distance += distance print('Total distance of all routes: {}m'.format(total_distance))

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 = create_data_model()

Next, declare the routing model solver:

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

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

distance_callback = create_distance_callback(data) routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)

Next, add the distance dimension.

add_distance_dimension(routing, distance_callback)

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) # pylint: disable=no-member

Finally, you can run the solver:

assignment = routing.SolveWithParameters(search_parameters)

And print the solution:

if assignment: print_solution(data, routing, assignment)

### Running the program

The complete program is shown in the next section. When you run the program, it displays the following output:

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

The graph below shows the assigned routes.

### The entire program

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

from __future__ import print_function from ortools.constraint_solver import pywrapcp from ortools.constraint_solver import routing_enums_pb2 ########################### # Problem Data Definition # ########################### def create_data_model(): """Stores the data for the problem""" data = {} # Locations in block units _locations = \ [(4, 4), # depot (2, 0), (8, 0), # locations to visit (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)] # Multiply coordinates in block units by the dimensions of an average city block, 114m x 80m, # to get location coordinates. data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations] data["num_locations"] = len(data["locations"]) data["num_vehicles"] = 4 data["depot"] = 0 return data ####################### # 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])) def create_distance_callback(data): """Creates callback to return distance between points.""" _distances = {} for from_node in range(data["num_locations"]): _distances[from_node] = {} for to_node in range(data["num_locations"]): if from_node == to_node: _distances[from_node][to_node] = 0 else: _distances[from_node][to_node] = ( manhattan_distance(data["locations"][from_node], data["locations"][to_node])) def distance_callback(from_node, to_node): """Returns the manhattan distance between the two nodes""" return _distances[from_node][to_node] return distance_callback def add_distance_dimension(routing, distance_callback): """Add Global Span constraint""" distance = 'Distance' maximum_distance = 3000 # Maximum distance per vehicle. routing.AddDimension( distance_callback, 0, # null slack maximum_distance, True, # start cumul to zero distance) distance_dimension = routing.GetDimensionOrDie(distance) # Try to minimize the max distance among vehicles. distance_dimension.SetGlobalSpanCostCoefficient(100) ########### # Printer # ########### def print_solution(data, routing, assignment): """Print routes on console.""" total_distance = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) distance = 0 while not routing.IsEnd(index): plan_output += ' {} ->'.format(routing.IndexToNode(index)) previous_index = index index = assignment.Value(routing.NextVar(index)) distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id) plan_output += ' {}\n'.format(routing.IndexToNode(index)) plan_output += 'Distance of route: {}m\n'.format(distance) print(plan_output) total_distance += distance print('Total distance of all routes: {}m'.format(total_distance)) ######## # Main # ######## def main(): """Entry point of the program""" # Instantiate the data problem. data = create_data_model() # Create Routing Model routing = pywrapcp.RoutingModel( data["num_locations"], data["num_vehicles"], data["depot"]) # Define weight of each edge distance_callback = create_distance_callback(data) routing.SetArcCostEvaluatorOfAllVehicles(distance_callback) add_distance_dimension(routing, distance_callback) # Setting first solution heuristic (cheapest addition). search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # pylint: disable=no-member # Solve the problem. assignment = routing.SolveWithParameters(search_parameters) if assignment: print_solution(data, routing, assignment) if __name__ == '__main__': main()

## Dimensions

A *dimension* is an object the routing solver uses
to keep track of
quantities that accumulate along vehicle routes. The example in the
preceding section uses a dimension to track
the distance traveled by each vehicle. The example adds the
dimension using the solver's
`AddDimension`

method.

Another example, presented in the next section,
uses a dimension to track the total load of the items
carried by a vehicle (such as their weight or volume). That example uses a slightly different
dimension, created by the
`AddDimensionWithVechicleCapacity`

method, which takes a vector of
maximum capacities for each vehicle. Several other methods for creating dimensions
are described in the
Routing Model
reference page. See methods whose names start with `AddDimension`

.

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.

The preceding VRP example uses a distance dimension to minimize
the *global
dimension span* of the distance traveled. This is the difference
between the largest value of the cumulative variables at the end of the vehicle routes,
minus the smallest value of the
cumulative variables at the start of the routes. 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.