Capacitated Vehicle Routing Problem with Time Windows

Overview

Many vehicle routing problems involve scheduling deliveries or service calls to customers. A natural constraint for these problems is that a customer can only receive a delivery or service during a specified window of time.

For example, a company might need to schedule a time window when a customer will be at home. Problems like these are called Vehicle Routing Problems with Time Windows (VRPTW).

Example

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

This example extends the previous CVRP example. The capacity constraints in the problem are the same as the previous example. This example adds time windows and shows how to calculate the total time it takes a vehicle to get from one location to the next.

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 time windows (in minutes) are shown above of each location. The objective is to minimize the sum of travel time and waiting time needed to supply all customers during the acceptable time windows, while ensuring that the total demand on each vehicle's route does not exceed its capacity.

Solving the example with OR-Tools

The following section walks 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
# Travel speed: 5km/h to convert in m/min
self._speed = 5 * 60 / 3.6

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

@property
def speed(self):
"""Gets the average travel speed of a vehicle"""
return self._speed

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, # 1, 2
2, 4, # 3, 4
2, 4, # 5, 6
8, 8, # 7, 8
1, 2, # 9,10
1, 2, # 11,12
4, 4, # 13, 14
8, 8] # 15, 16

self._time_windows = \
[(0, 0),
(75, 85), (75, 85), # 1, 2
(60, 70), (45, 55), # 3, 4
(0, 8), (50, 60), # 5, 6
(0, 10), (10, 20), # 7, 8
(0, 10), (75, 85), # 9, 10
(85, 95), (5, 15), # 11, 12
(15, 25), (10, 20), # 13, 14
(45, 55), (30, 40)] # 15, 16

@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

@property
def time_per_demand_unit(self):
"""Gets the time (in min) to load a demand"""
return 5 # 5 minutes/unit

@property
def time_windows(self):
"""Gets (start time, end time) for each locations"""
return self._time_windows
```

The data consists of:

• a `vehicle` object — The vehicle properties (here, the capacity and speed).
• 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.
• `time_windows` — An array of time windows, in which `time_windows[i]` is the time window at location i.
• `time_per_demand_unit` — Time to serve a demand of one unit.
• 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.

Distance evaluator

As in the CVRP example we add a distance evaluator using the Manhattan distance.

Demand dimension

As in the CVRP example we add a demand dimension to the problem. See Dimensions.

Time dimension

In addition to the demand dimension, the solver also requires a time dimension to take into account the time window constraints.

We need a way to calculate the time a vehicle must spend at a location and the travel time to the next location on its route. More specifically, we must write an evaluator to calculate the following:

• The service time — how long it takes to make a delivery or provide a service at each location. In this example, we assume the service time is proportional to the demand at the location
• The travel time between locations. We assume that all vehicles travel at the same speed, so travel time is just the distance between locations divided by speed.
• The total time between locations, which is the service time at the starting location plus the travel time to the next location.

The following sections create function to calculate each of these times.

Calculate the service time

The following code calculates the service times at each location. We assume that the service time is equal to the demand times a constant, the `time_per_demand_unit`.

```    @staticmethod
def service_time(data, node):
"""Gets the service time for the specified location."""
return data.demands[node] * data.time_per_demand_unit```

Calculate the travel time

The following code calculates the travel time between locations, which divides the distance between locations by the vehicle's constant speed.

```    @staticmethod
def travel_time(data, from_node, to_node):
"""Gets the travel times between two locations."""
if from_node == to_node:
travel_time = 0
else:
travel_time = manhattan_distance(
data.locations[from_node],
data.locations[to_node]) / data.vehicle.speed
return travel_time```

Create the time evaluator

The following code computes the total time — the service time plus the travel time to the next location.

```    def __init__(self, data):
"""Initializes the total time matrix."""
self._total_time = {}
# precompute total time to have time callback in O(1)
for from_node in xrange(data.num_locations):
self._total_time[from_node] = {}
for to_node in xrange(data.num_locations):
if from_node == to_node:
self._total_time[from_node][to_node] = 0
else:
self._total_time[from_node][to_node] = int(
self.service_time(data, from_node) +
self.travel_time(data, from_node, to_node))```

The code that defines the time evaluator is shown below.
note: As in the TSP example, we precompute the total time matrix in order to speed up the evaluator.

```    def time_evaluator(self, from_node, to_node):
"""Returns the total time between the two nodes"""
return self._total_time[from_node][to_node]```

Define the time dimension

The section Dimension explains dimensions. In this example, you need to define a dimension for time.
You can do so by the following code:

```def add_time_window_constraints(routing, data, time_evaluator):
time = "Time"
horizon = 120
time_evaluator,
horizon, # allow waiting time
horizon, # maximum time per vehicle
False, # don't force start cumul to zero since we are giving TW to start nodes
time)```

The significant inputs to the `AddDimension` method are the following:

• `time_evaluator` — Returns the service time plus travel time to the next location.
• `horizon` — An upper bound for the accumulated time over each vehicle's route. This sets a global time window of [0, horizon] for all locations. To set the individual time windows at each location, you need to set ranges on the cumulative variable for time, as shown below in Add time window constraints.
• set the start cumul to zero — Since the value is `False`, the cumulative variable for time is not set to zero at the start of each vehicle's route.
• `time` — The name of the dimension, which you can use to access data or variables stored in it.

The following code adds time window constraints for all locations.

```    time_dimension = routing.GetDimensionOrDie(time)
for location_idx, time_window in enumerate(data.time_windows):
if location_idx == 0:
continue
index = routing.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
for vehicle_id in xrange(data.num_vehicles):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data.time_windows[0][0], data.time_windows[0][1])

Note that `time_dimension.CumulVar(routing.NodeToIndex(location))` is the cumulative time a vehicle spent before visiting this location along its route.
So for each location, the code `time_dimension.CumulVar(routing.NodeToIndex(location)).SetRange(time_window[0], time_window[1])` requires the cumulative time to be in the window for that location, as specified by `data.time_windows[i]`.
To set a constraint on the start or the end node of the i-th vehicle, you must use `time_dimension.CumulVar(routing.start(i))` or `time_dimension.CumulVar(routing.end(i))` respectively.

Note that by default, only the `CumulVar` is "exported" in the solution object. So if you want to display the value of the `SlackVar` you must add it to the solution using `routing.AddToAssignment(time_dimension.SlackVar(index))`.

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.
capacity_dimension = self.routing.GetDimensionOrDie('Capacity')
time_dimension = self.routing.GetDimensionOrDie('Time')
total_dist = 0
total_time = 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])
time_var = time_dimension.CumulVar(index)
time_min = self.assignment.Min(time_var)
time_max = self.assignment.Max(time_var)
slack_var = time_dimension.SlackVar(index)
slack_min = self.assignment.Min(slack_var)
slack_max = self.assignment.Max(slack_var)
plan_output += ' {0} Load({1}) Time({2},{3}) Slack({4},{5}) ->'.format(
node_index,
time_min, time_max,
slack_min, slack_max)
index = self.assignment.Value(self.routing.NextVar(index))

node_index = self.routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
route_time = self.assignment.Value(time_var)
time_min = self.assignment.Min(time_var)
time_max = self.assignment.Max(time_var)
total_dist += route_dist
total_time += route_time
plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
plan_output += 'Time of the route: {0}min\n'.format(route_time)
print(plan_output)
print('Total Distance of all routes: {0}m'.format(total_dist))
print('Total Time of all routes: {0}min'.format(total_time))
```

The program uses the following variables, returned by the solver, to display the output.

```load_var = capacity_dimension.CumulVar(index)
time_var = time_dimension.CumulVar(index)```

`load_var` contains the cumulative load (just another word for demand) at each location. This is the sum of the demands at the previously visited locations on the route.

`time_var` contains the delivery time windows, calculated by the solver, at each location. A vehicle can make its delivery at any time in the time window for a location, and still make it to the next location on its route within the scheduled delivery time window for that location.

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

This is the same than the previous CVRP example, except we add the time window constraints.

```    time_evaluator = CreateTimeEvaluator(data).time_evaluator

Running the program

Enter the following code into the terminal:

`python examples/python/cvrptw.py`

The following output appears:

```Route for vehicle 0:
Distance of the route: 1780m
Time of the route: 99min

Route for vehicle 1:
Distance of the route: 1712m
Time of the route: 94min

Route for vehicle 2:
Distance of the route: 1552m
Time of the route: 91min

Route for vehicle 3:
Distance of the route: 1552m
Time of the route: 92min

Total Distance of all routes: 6596m
Total Time of all routes: 376min
```

You can check that the right-hand endpoint of the delivery window for each location (other than the depot) is contained in the delivery window for the next location on the route. This means that a vehicle can arrive at any time during the time window for a location, and still get to the next location in time to make its delivery.

To interpret the output, take a look at the third location in Route 0, in the first line of the output above:

`13 Load(2) Time(17, 25)`
This tells us the following:
• The location is node 13.
• The cumulative load of the previously visited locations (not including node 13) is 2.
• The solution time window at this location is (17, 25). This means that the vehicle for route 0 should arrive at node 13 at some time during this time window to keep to the given schedule.

The entire program

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

```"""Capacitated Vehicle Routing Problem with Time Windows (CVRPTW).
"""
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
# Travel speed: 5km/h to convert in m/min
self._speed = 5 * 60 / 3.6

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

@property
def speed(self):
"""Gets the average travel speed of a vehicle"""
return self._speed

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, # 1, 2
2, 4, # 3, 4
2, 4, # 5, 6
8, 8, # 7, 8
1, 2, # 9,10
1, 2, # 11,12
4, 4, # 13, 14
8, 8] # 15, 16

self._time_windows = \
[(0, 0),
(75, 85), (75, 85), # 1, 2
(60, 70), (45, 55), # 3, 4
(0, 8), (50, 60), # 5, 6
(0, 10), (10, 20), # 7, 8
(0, 10), (75, 85), # 9, 10
(85, 95), (5, 15), # 11, 12
(15, 25), (10, 20), # 13, 14
(45, 55), (30, 40)] # 15, 16

@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

@property
def time_per_demand_unit(self):
"""Gets the time (in min) to load a demand"""
return 5 # 5 minutes/unit

@property
def time_windows(self):
"""Gets (start time, end time) for each locations"""
return self._time_windows

#######################
# 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):
"""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):
"""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)

class CreateTimeEvaluator(object):
"""Creates callback to get total times between locations."""
@staticmethod
def service_time(data, node):
"""Gets the service time for the specified location."""
return data.demands[node] * data.time_per_demand_unit

@staticmethod
def travel_time(data, from_node, to_node):
"""Gets the travel times between two locations."""
if from_node == to_node:
travel_time = 0
else:
travel_time = manhattan_distance(
data.locations[from_node],
data.locations[to_node]) / data.vehicle.speed
return travel_time

def __init__(self, data):
"""Initializes the total time matrix."""
self._total_time = {}
# precompute total time to have time callback in O(1)
for from_node in xrange(data.num_locations):
self._total_time[from_node] = {}
for to_node in xrange(data.num_locations):
if from_node == to_node:
self._total_time[from_node][to_node] = 0
else:
self._total_time[from_node][to_node] = int(
self.service_time(data, from_node) +
self.travel_time(data, from_node, to_node))

def time_evaluator(self, from_node, to_node):
"""Returns the total time between the two nodes"""
return self._total_time[from_node][to_node]

time = "Time"
horizon = 120
time_evaluator,
horizon, # allow waiting time
horizon, # maximum time per vehicle
False, # don't force start cumul to zero since we are giving TW to start nodes
time)
time_dimension = routing.GetDimensionOrDie(time)
for location_idx, time_window in enumerate(data.time_windows):
if location_idx == 0:
continue
index = routing.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
for vehicle_id in xrange(data.num_vehicles):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data.time_windows[0][0], data.time_windows[0][1])

###########
# 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.
capacity_dimension = self.routing.GetDimensionOrDie('Capacity')
time_dimension = self.routing.GetDimensionOrDie('Time')
total_dist = 0
total_time = 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])
time_var = time_dimension.CumulVar(index)
time_min = self.assignment.Min(time_var)
time_max = self.assignment.Max(time_var)
slack_var = time_dimension.SlackVar(index)
slack_min = self.assignment.Min(slack_var)
slack_max = self.assignment.Max(slack_var)
plan_output += ' {0} Load({1}) Time({2},{3}) Slack({4},{5}) ->'.format(
node_index,
time_min, time_max,
slack_min, slack_max)
index = self.assignment.Value(self.routing.NextVar(index))

node_index = self.routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
route_time = self.assignment.Value(time_var)
time_min = self.assignment.Min(time_var)
time_max = self.assignment.Max(time_var)
total_dist += route_dist
total_time += route_time
plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
plan_output += 'Time of the route: {0}min\n'.format(route_time)
print(plan_output)
print('Total Distance of all routes: {0}m'.format(total_dist))
print('Total Time of all routes: {0}min'.format(total_time))

########
# 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
time_evaluator = CreateTimeEvaluator(data).time_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.)