Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem, whose goal is to find the optimal set of routes for a fleet of vehicles delivering goods or services to various locations. Like the TSP, the Vehicle Routing Problem can be represented by a graph with distances assigned to the edges. Vehicle routing problems also have other constraints, which can include any combination of the following:

• 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.
• Maximum number of locations that each vehicle can visit.
• Time (or distance) constraints: the duration (or length) of each route cannot exceed a fixed bound.
• Time windows: each location must be serviced within a time window [ai , bi] and waiting times are allowed.
• Precedence relations between pairs of locations: for example, location j cannot be visited before location i.

On this page, we'll walk through an example of using OR-Tools to solve a VRP with capacity constraints. There are several examples of other types of vehicle routing problems on github — look for examples that have "cvrptw" in their names.

Capacitated Vehicle Routing Problems

In the capacitated vehicle routing problem (CVRP), we are given a demand at each location, and each vehicle's maximum capacity. The constraint is to find an assignment of routes to vehicles so that the total demand of the locations on a vehicle's route does not exceed its capacity.

In this example, we assume that all vehicles start at the same location, called the depot. Alternatively, you can allow vehicles to start and end any location.

The following sections present an example of a CVRP, and shows how to solve it using OR-Tools.

Create the data

The following code creates the data for the problem.

```def create_data_array():

locations = [[82, 76], [96, 44], [50, 5], [49, 8], [13, 7], [29, 89], [58, 30], [84, 39],
[14, 24], [12, 39], [3, 82], [5, 10], [98, 52], [84, 25], [61, 59], [1, 65],
[88, 51], [91, 2], [19, 32], [93, 3], [50, 93], [98, 14], [5, 42], [42, 9],
[61, 62], [9, 97], [80, 55], [57, 69], [23, 15], [20, 70], [85, 60], [98, 5]]

demands = [0, 19, 21, 6, 19, 7, 12, 16, 6, 16, 8, 14, 21, 16, 3, 22, 18,
19, 1, 24, 8, 12, 4, 8, 24, 24, 2, 20, 15, 2, 14, 9]
data = [locations, demands]
return data```

The data consists of two arrays:

• `locations` — A two-dimensional array of points in the plane.
• `demands` — An array of demands, in which `demands[i]` is the demand at location i.

Declare the solver

The program uses the routing model solver, the same solver used in the TSP example. The following code declares the solver.

```  data = create_data_array()
locations = data[0]
demands = data[1]
num_locations = len(locations)
depot = 0    # The depot is the start and end point of each route.
num_vehicles = 5

# Create routing model.
if num_locations > 0:
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

# Setting first solution heuristic: the
# method for finding a first solution to the problem.
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# The 'PATH_CHEAPEST_ARC' method does the following:
# Starting from a route "start" node, connect it to the node which produces the
# cheapest route segment, then extend the route by iterating on the last
# node added to the route.

# Put a callback to the distance function here. The callback takes two
# arguments (the from and to node indices) and returns the distance between
# these nodes.

dist_between_locations = CreateDistanceCallback(locations)
dist_callback = dist_between_locations.Distance
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

# Put a callback to the demands.
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand

# Add a dimension for demand.
slack_max = 0
vehicle_capacity = 100
fix_start_cumul_to_zero = True
demand = "Demand"
fix_start_cumul_to_zero, demand)
```

Create the distance callback

This example uses a definition of distance that differs from the usual Euclidean metric, called the Manhattan distance. The Manhattan distance between two points, (x1, y1) and (x2, y2), is the absolute value of the difference in their x coordinates plus the absolute value of the difference in the y coordinates:

`|x2 - x1| + |y2 - y1|`
This distance is motivated by routing problems in a city that is layed 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.)

The code that creates the distance callback is shown below.

```def distance(x1, y1, x2, y2):
# Manhattan distance
dist = abs(x1 - x2) + abs(y1 - y2)

return dist
class CreateDistanceCallback(object):
"""Create callback to calculate distances between points."""

def __init__(self, locations):
"""Initialize distance array."""
size = len(locations)
self.matrix = {}

for from_node in xrange(size):
self.matrix[from_node] = {}
for to_node in xrange(size):
x1 = locations[from_node][0]
y1 = locations[from_node][1]
x2 = locations[to_node][0]
y2 = locations[to_node][1]
self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

def Distance(self, from_node, to_node):
return self.matrix[from_node][to_node]```

Create the demands callback

In addition to the distance callback, the solver also requires a callback for the demands, which simply returns the values of the one-dimensional array of demands. The code for the demands callback is shown below.

```# Demand callback
class CreateDemandCallback(object):
"""Create callback to get demands at each location."""

def __init__(self, demands):
self.matrix = demands

def Demand(self, from_node, to_node):
return self.matrix[from_node]```

Dimensions

Routing problems involve quantities that accumulate along a vehicle's route. In this example, such a quantity is demand — say, the weight or volume of a package that must be delivered. For every location where a vehicle stops along its route, the total demand on the vehicle increases by the demand at that location. (Other examples of these types of quantities are the distance a vehicle travels, or its travel time.)

The routing solver stores each quantity of this type in an object called a dimension. The dimension contains a callback for the quantity, along with related data and variables. You can add a dimension to a routing problem using the solver's `AddDimension` method. The following code creates a dimension for the demand in this example.

```    # Put a callback to the demands.
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand

# Add a dimension for demand.
slack_max = 0
vehicle_capacity = 100
fix_start_cumul_to_zero = True
demand = "Demand"
fix_start_cumul_to_zero, demand)```
In this case, the significant inputs to the method are the following:
• `demands_callback` — Returns the demand at each location.
• `vehicle_capacity` — The maximum capacity of each vehicle. The `vehicle_capacity` defines the capacity constraint for the problem, by setting a maximum value for the sum of the demands over each vehicle's route.
Variables

Internally, a dimension stores two types of variables that are linked to the quantity:

• Transit variables — The increase or decrease of the quantity at each location.
• Cumulative variables — The total accumulated quantity at each location.
While these variables are not used in this example, the section Vehicle Routing with Time Windows presents an example in which the cumulative variable for time is used to set time windows for stops at each location.

Invoke the solver and display the results

The following code invokes the solver and displays the output.

```    # Solve, displays a solution if any.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
# Display solution.
# Solution cost.
print "Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n"

for vehicle_nbr in range(num_vehicles):
index = routing.Start(vehicle_nbr)
index_next = assignment.Value(routing.NextVar(index))
route = ''
route_dist = 0
route_demand = 0

while not routing.IsEnd(index_next):
node_index = routing.IndexToNode(index)
node_index_next = routing.IndexToNode(index_next)
route += str(node_index) + " -> "
# Add the distance to the next node.
route_dist += dist_callback(node_index, node_index_next)
route_demand += demands[node_index_next]
index = index_next
index_next = assignment.Value(routing.NextVar(index))

node_index = routing.IndexToNode(index)
node_index_next = routing.IndexToNode(index_next)
route += str(node_index) + " -> " + str(node_index_next)
route_dist += dist_callback(node_index, node_index_next)
print "Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n"
print "Distance of route " + str(vehicle_nbr) + ": " + str(route_dist)
print "Demand met by vehicle " + str(vehicle_nbr) + ": " + str(route_demand) + "\n"
else:
print 'No solution found.'
else:
print 'Specify an instance greater than 0.'```

In addition to the routes, the program also calculates the total distance and total demand of each route. You can check that the total demand for each route does not exceed the capacity, so the capacity constraint is satisfied.

Here is the output of the program.

```Total distance of all routes: 970

Route for vehicle 0:

0 -> 14 -> 2 -> 3 -> 23 -> 4 -> 11 -> 28 -> 6 -> 26 -> 0

Distance of route 0: 300
Demand met by vehicle 0: 100

Route for vehicle 1:

0 -> 27 -> 24 -> 0

Distance of route 1: 78
Demand met by vehicle 1: 44

Route for vehicle 2:

0 -> 20 -> 5 -> 25 -> 10 -> 15 -> 22 -> 9 -> 8 -> 18 -> 29 -> 0

Distance of route 2: 316
Demand met by vehicle 2: 98

Route for vehicle 3:

0 -> 12 -> 1 -> 16 -> 30 -> 0

Distance of route 3: 96
Demand met by vehicle 3: 72

Route for vehicle 4:

0 -> 13 -> 21 -> 31 -> 19 -> 17 -> 7 -> 0

Distance of route 4: 180
Demand met by vehicle 4: 96```

Note that the distances for each route include the distance from the depot to the first location in the route and the distance from the last location back to the depot.

The entire program

The entire program for the capacitated vehicle routing problem is shown below.

```import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

def distance(x1, y1, x2, y2):
# Manhattan distance
dist = abs(x1 - x2) + abs(y1 - y2)

return dist
class CreateDistanceCallback(object):
"""Create callback to calculate distances between points."""

def __init__(self, locations):
"""Initialize distance array."""
size = len(locations)
self.matrix = {}

for from_node in xrange(size):
self.matrix[from_node] = {}
for to_node in xrange(size):
x1 = locations[from_node][0]
y1 = locations[from_node][1]
x2 = locations[to_node][0]
y2 = locations[to_node][1]
self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

def Distance(self, from_node, to_node):
return self.matrix[from_node][to_node]

# Demand callback
class CreateDemandCallback(object):
"""Create callback to get demands at each location."""

def __init__(self, demands):
self.matrix = demands

def Demand(self, from_node, to_node):
return self.matrix[from_node]

def main():
# Create the data.
data = create_data_array()
locations = data[0]
demands = data[1]
num_locations = len(locations)
depot = 0    # The depot is the start and end point of each route.
num_vehicles = 5

# Create routing model.
if num_locations > 0:
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

# Setting first solution heuristic: the
# method for finding a first solution to the problem.
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# The 'PATH_CHEAPEST_ARC' method does the following:
# Starting from a route "start" node, connect it to the node which produces the
# cheapest route segment, then extend the route by iterating on the last
# node added to the route.

# Put a callback to the distance function here. The callback takes two
# arguments (the from and to node indices) and returns the distance between
# these nodes.

dist_between_locations = CreateDistanceCallback(locations)
dist_callback = dist_between_locations.Distance
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

# Put a callback to the demands.
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand

# Add a dimension for demand.
slack_max = 0
vehicle_capacity = 100
fix_start_cumul_to_zero = True
demand = "Demand"
fix_start_cumul_to_zero, demand)

# Solve, displays a solution if any.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
# Display solution.
# Solution cost.
print "Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n"

for vehicle_nbr in range(num_vehicles):
index = routing.Start(vehicle_nbr)
index_next = assignment.Value(routing.NextVar(index))
route = ''
route_dist = 0
route_demand = 0

while not routing.IsEnd(index_next):
node_index = routing.IndexToNode(index)
node_index_next = routing.IndexToNode(index_next)
route += str(node_index) + " -> "
# Add the distance to the next node.
route_dist += dist_callback(node_index, node_index_next)
route_demand += demands[node_index_next]
index = index_next
index_next = assignment.Value(routing.NextVar(index))

node_index = routing.IndexToNode(index)
node_index_next = routing.IndexToNode(index_next)
route += str(node_index) + " -> " + str(node_index_next)
route_dist += dist_callback(node_index, node_index_next)
print "Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n"
print "Distance of route " + str(vehicle_nbr) + ": " + str(route_dist)
print "Demand met by vehicle " + str(vehicle_nbr) + ": " + str(route_demand) + "\n"
else:
print 'No solution found.'
else:
print 'Specify an instance greater than 0.'

def create_data_array():

locations = [[82, 76], [96, 44], [50, 5], [49, 8], [13, 7], [29, 89], [58, 30], [84, 39],
[14, 24], [12, 39], [3, 82], [5, 10], [98, 52], [84, 25], [61, 59], [1, 65],
[88, 51], [91, 2], [19, 32], [93, 3], [50, 93], [98, 14], [5, 42], [42, 9],
[61, 62], [9, 97], [80, 55], [57, 69], [23, 15], [20, 70], [85, 60], [98, 5]]

demands = [0, 19, 21, 6, 19, 7, 12, 16, 6, 16, 8, 14, 21, 16, 3, 22, 18,
19, 1, 24, 8, 12, 4, 8, 24, 24, 2, 20, 15, 2, 14, 9]
data = [locations, demands]
return data
if __name__ == '__main__':
main()```

Options for start and end locations

So far, we have assumed that all vehicles start and end at a fixed location. Next, let's take a look at some other options for the start and end locations.

Specifying start and end locations

To specify the start and end locations for each vehicle in the problem, simply pass two vectors for the start and end locations as inputs to the function that creates the routing model. Here's an example.

```start_locations = [0, 3, 15, 21, 7]
end_locations = [2, 20, 7, 11, 1]
routing = pywrapcp.RoutingModel(num_locations, num_vehicles,
start_locations, end_locations)```

When you run the previous example with these inputs, the program returns routes that begin and end at the specified locations.

```Total distance of all routes: 599

Route for vehicle 0:

0 -> 2

Distance of route 0: 103
Demand met by vehicle 0: 0

Route for vehicle 1:

3 -> 23 -> 28 -> 18 -> 9 -> 22 -> 10 -> 25 -> 5 -> 20

Distance of route 1: 194
Demand met by vehicle 1: 83

Route for vehicle 2:

15 -> 29 -> 27 -> 24 -> 14 -> 30 -> 7

Distance of route 2: 123
Demand met by vehicle 2: 63

Route for vehicle 3:

21 -> 12 -> 16 -> 26 -> 6 -> 8 -> 4 -> 11

Distance of route 3: 187
Demand met by vehicle 3: 78

Route for vehicle 4:

7 -> 13 -> 17 -> 19 -> 31 -> 1

Distance of route 4: 95
Demand met by vehicle 4: 68```

Allowing arbitrary start and end locations

In other versions of the vehicle routing problem, vehicles are allowed to start and end at arbitrary locations. To set up the problem this way, simply modify the distance callback so that distance from the depot to any other location is 0. This turns the depot into a dummy location, whose position has no effect on the optimal routes.

Here's how to modify the distance callback to make the distance from the depot to all other nodes 0. Since the callback defines the distance between `from_node` and `to_node`, we want the callback to return 0 when either from_node or to_node is the depot. To do this, just add the following conditional to the callback:

```if from_node == depot or to_node == depot:
self.matrix[from_node][to_node] = 0```
Here's the modified callback:
```class CreateDistanceCallback(object):
"""Create callback to calculate distances between points."""
def __init__(self, locations):
"""Initialize distance array."""
size = len(locations)
depot = 0
self.matrix = {}

for from_node in xrange(size):
self.matrix[from_node] = {}
for to_node in xrange(size):
if from_node == depot or to_node == depot:
# Define the distance from the depot to any node to be 0.
self.matrix[from_node][to_node] = 0
else:
x1 = locations[from_node][0]
y1 = locations[from_node][1]
x2 = locations[to_node][0]
y2 = locations[to_node][1]
self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

def Distance(self, from_node, to_node):
return self.matrix[from_node][to_node]```
Note that coordinates of the depot no longer have any effect on the distance callback, so you could define them arbitrarily.

Here's the new output:

```Total distance of all routes: 441

Route for vehicle 0:

0 -> 28 -> 4 -> 11 -> 0

Distance of route 0: 29
Demand met by vehicle 0: 48

Route for vehicle 1:

0 -> 29 -> 5 -> 20 -> 27 -> 6 -> 2 -> 3 -> 23 -> 0

Distance of route 1: 169
Demand met by vehicle 1: 84

Route for vehicle 2:

0 -> 8 -> 18 -> 9 -> 22 -> 15 -> 10 -> 25 -> 0

Distance of route 2: 104
Demand met by vehicle 2: 81

Route for vehicle 3:

0 -> 1 -> 12 -> 16 -> 30 -> 14 -> 24 -> 0

Distance of route 3: 61
Demand met by vehicle 3: 99

Route for vehicle 4:

0 -> 17 -> 19 -> 31 -> 21 -> 13 -> 7 -> 26 -> 0

Distance of route 4: 78
Demand met by vehicle 4: 98```

To remove the depot from the displayed routes (since it isn't meaningful in this case), make the following changes to the code shown in Invoke the solver:

1. In the loop that begins with
`while not routing.IsEnd(index_next):`
```if node_index != depot:
route += str(node_index) + " -> "```
2. In the code following the loop, delete the following line:
`route += str(node_index) + " -> " + str(node_index_next)`