# Capacitated Vehicle Routing Problem

## Overview

The Capacitated Vehicle Routing Problem (CVRP) is a vehicle routing problem with additional constraints on the capacities of the vehicles. In a CVRP, each location has a demand—a physical quantity, such as weight or volume, corresponding to the item to be picked up or delivered there. In addition, each vehicle has a maximum capacity for the total quantity it can carry. Note that if a vehicle is making pick-ups and deliveries, the total amount it is carrying can increase and decrease along its route.

A CVRP can be represented by a graph with distances assigned to the edges and demands assigned to the nodes.

You can solve CVRPs using the OR-Tools vehicle routing library. The routing library is an added layer on top of the constraint programming solver. See RoutingModel for detailed information about the available methods for setting up and solving routing problems.

## Example

On this page, we'll walk through an example of using OR-Tools to solve a CVRP.
The example that we use below is derived from cvrp.py by Tin Arm Engineering.

This example follows the VRP example and adds the following constraints: we are given a demand at each location, and each vehicle has a maximum capacity of 15.
You can see a map of this city below with the locations to visit in blue and the company location in black. The demands are shown below and to the right of each location. The problem 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.

### Manhattan distance

Like in the VRP example, we will use the Manhattan distance.

## Solving the example with OR-Tools

The following section, walk through a Python implementation to solve this example.

### Model the problem

The following code creates the data for the problem.

```class Vehicle():
"""Stores the property of a vehicle"""
def __init__(self):
"""Initializes the vehicle properties"""
self._capacity = 15

@property
def capacity(self):
"""Gets vehicle capacity"""
return self._capacity

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._vehicle = Vehicle()
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

self._demands = \
[0, # depot
1, 1, # row 0
2, 4,
2, 4,
8, 8,
1, 2,
1, 2,
4, 4,
8, 8]

@property
def vehicle(self):
"""Gets a vehicle"""
return self._vehicle

@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

@property
def demands(self):
"""Gets demands at each location"""
return self._demands
```

The data consists of:

• a `vehicle` object — The vehicle properties (here, the capacity).
• a `num_vehicles` variable — The number of vehicles in the fleet.
• `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.
• 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 evaluator

The code that computes the Manhattan distance 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 code that defines the arc cost is shown below.
note: As in the TSP example, we precompute the distance matrix in order to speed up the evaluator.

```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]
```

In addition to the distance evaluator, the solver also requires a demand dimension to take into account the capacity constraint.

#### Define the demand evaluator

First we define the evaluator for the location's demand, which simply returns the values of the one-dimensional array of demands.

```class CreateDemandEvaluator(object): # pylint: disable=too-few-public-methods
"""Creates callback to get demands at each location."""
def __init__(self, data):
"""Initializes the demand array."""
self._demands = data.demands

def demand_evaluator(self, from_node, to_node):
"""Returns the demand of the current node"""
del to_node
return self._demands[from_node]
```

#### Define the demand Dimension

The code that defines the demand dimension is show below.

```def add_capacity_constraints(routing, data, demand_evaluator):
capacity = "Capacity"
demand_evaluator,
0, # null capacity slack
data.vehicle.capacity, # vehicle maximum capacity
True, # start cumul to zero
capacity)
```

### 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])
index = self.assignment.Value(self.routing.NextVar(index))

node_index = self.routing.IndexToNode(index)
total_dist += route_dist
plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
print(plan_output)
print('Total Distance of all routes: {0}m'.format(total_dist))
```

In the method `print()`, for each vehicle we display the route (i.e. the list of visited nodes) and compute the distance and the load of the route.
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.

### Main function

Now, we have everything to create the main function.

First, we instantiate the problem data:

```    data = DataProblem()
```

Then we instantiate the routing model solver:

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

Then we provide our distance evaluator so the solver can compute the weight of each edge.

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

And we do the same with our demand evaluator so the solver can compute the demands of each node.

```    demand_evaluator = CreateDemandEvaluator(data).demand_evaluator
```

We have to specify the heuristic used to find the first solution:

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

Finaly, we can run the solver:

```    assignment = routing.SolveWithParameters(search_parameters)
```

And print the solution:

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

### Running the program

Enter the following code into the terminal:

`python examples/python/cvrp.py`

The following output appears:

```Route for vehicle 0:
Distance of the route: 2192m

Route for vehicle 1:
Distance of the route: 2192m

Route for vehicle 2:
Distance of the route: 1324m

Route for vehicle 3:
Distance of the route: 1164m

Total Distance of all routes: 6872m
```

## The entire program

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

```"""Capacitated 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 Vehicle():
"""Stores the property of a vehicle"""
def __init__(self):
"""Initializes the vehicle properties"""
self._capacity = 15

@property
def capacity(self):
"""Gets vehicle capacity"""
return self._capacity

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._vehicle = Vehicle()
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

self._demands = \
[0, # depot
1, 1, # row 0
2, 4,
2, 4,
8, 8,
1, 2,
1, 2,
4, 4,
8, 8]

@property
def vehicle(self):
"""Gets a vehicle"""
return self._vehicle

@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

@property
def demands(self):
"""Gets demands at each location"""
return self._demands

#######################
# 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]

class CreateDemandEvaluator(object): # pylint: disable=too-few-public-methods
"""Creates callback to get demands at each location."""
def __init__(self, data):
"""Initializes the demand array."""
self._demands = data.demands

def demand_evaluator(self, from_node, to_node):
"""Returns the demand of the current node"""
del to_node
return self._demands[from_node]

capacity = "Capacity"
demand_evaluator,
0, # null capacity slack
data.vehicle.capacity, # vehicle maximum capacity
True, # start cumul to zero
capacity)

###########
# 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])
index = self.assignment.Value(self.routing.NextVar(index))

node_index = self.routing.IndexToNode(index)
total_dist += route_dist
plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
print(plan_output)
print('Total Distance of all routes: {0}m'.format(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)
demand_evaluator = CreateDemandEvaluator(data).demand_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()
```

There are several examples of vehicle routing problems with other types of constraints on GitHub (look for examples that have "vrp" in their names.)