# Vehicle Routing with Time Windows

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 in 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.

The following sections give an example of this type of problem and present a Python program to solve it. The capacity contraints in the problem are the same as in the CVRP example, described in the previous section. 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.

As in the previous vehicle routing example, we assume that all vehicles start and end at the depot. Alternatively, you can allow vehicles to start and end any location.

### Create the data

The following code creates the data for the problem. The arrays `start_times` and ``` end_times``` contain the start times and end times (in seconds) of the time windows. Vehicles must make deliveries at each node between the start time and the end time. Note that there is no time window at the depot. We arbitrarily set the start and end times at the depot to 0, but this has no effect on the results.

```def create_data_array():

locations = [[820, 760], [960, 440], [500, 50], [490, 80], [130, 70], [290, 890], [580, 300],
[840, 390], [140, 240], [120, 390], [30, 820], [50, 100], [980, 520], [840, 250],
[610, 590], [10, 650], [880, 510], [910, 20], [190, 320], [930, 30], [500, 930],
[980, 140], [50, 420], [420, 90], [610, 620], [90, 970], [800, 550], [570, 690],
[230, 150], [200, 700], [850, 600], [980, 50]]

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]

start_times =  [0, 508, 103, 493, 225, 531, 89,
565, 540, 108, 602, 466, 356, 303,
399, 382, 362, 521, 23, 489, 445,
318, 380, 55, 574, 515, 110, 310,
387, 491, 328, 73]

# tw_duration is the width of the time windows.
tw_duration = 2150

# In this example, the width is the same at each location, so we define the end times to be
# start times + tw_duration. For problems in which the time window widths vary by location,
# you can explicitly define the list of end_times, as we have done for start_times.
end_times = [0] * len(start_times)

for i in range(len(start_times)):
end_times[i] = start_times[i] + tw_duration
data = [locations, demands, start_times, end_times]
return data```

Since we have added time constraints to the problem, 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 callbacks 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 callbacks to calculate each of these times.

### Create the service time callback

The following code creates a callback for the service times. We assume that the service time is equal to the demand times a constant, the `time_per_demand_unit`.

```# Service time (proportional to demand) callback.
class CreateServiceTimeCallback(object):
"""Create callback to get time windows at each location."""

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

def ServiceTime(self, from_node, to_node):
return int(self.matrix[from_node] * self.time_per_demand_unit)```

### Create the travel time callback

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

```# Create the travel time callback (equals distance divided by speed).
class CreateTravelTimeCallback(object):
"""Create callback to get travel times between locations."""

def __init__(self, dist_callback, speed):
self.dist_callback = dist_callback
self.speed = speed

def TravelTime(self, from_node, to_node):
travel_time = self.dist_callback(from_node, to_node) / self.speed
return int(travel_time)```

### Create the total time callback

The following code creates the callback for total time — the service time plus the travel time to the next location.

```# Create total_time callback (equals service time plus travel time).
class CreateTotalTimeCallback(object):
"""Create callback to get total times between locations."""

def __init__(self, service_time_callback, travel_time_callback):
self.service_time_callback = service_time_callback
self.travel_time_callback = travel_time_callback

def TotalTime(self, from_node, to_node):
service_time = self.service_time_callback(from_node, to_node)
travel_time = self.travel_time_callback(from_node, to_node)
return service_time + travel_time```

The section Dimensions explains dimensions and shows how to set the demands dimension for the vehicle routing problem. In this example, you also need to define a dimension for time. You can do so by the following code:

```    # Add time dimension.
time_per_demand_unit = 3
horizon = 24 * 3600
time = "Time"
speed = 1

service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
service_time_callback = service_times.ServiceTime

travel_times = CreateTravelTimeCallback(dist_callback, speed)
travel_time_callback = travel_times.TravelTime

total_times = CreateTotalTimeCallback(service_time_callback, travel_time_callback)
total_time_callback = total_times.TotalTime

routing.AddDimension(total_time_callback,  # total time function callback
horizon,
horizon,
fix_start_cumul_to_zero,
time)```

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

• `total_time_callback` — 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 in Add time window constraints.
• `fix_start_cumul_to_zero` — Since the value is `True`, the cumulative variable for time is set to 0 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.

To add time window constraints for the problem, first access the time dimension by its name as follows:

`time_dimension = routing.GetDimensionOrDie(time)`

Next, set ranges for the arrival time at each location:

```    for location in range(1, num_locations):
start = start_times[location]
end = end_times[location]
time_dimension.CumulVar(location).SetRange(start, end)```
Note that `time_dimension.CumulVar(location)` is the cumulative time for the vehicle along its route. So for each location, the command
`time_dimension.CumulVar(location).SetRange(start, end)`
requires the cumulative time to be in the window for that location, as specified by ``` start_times``` and `end_times`.

### 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:
size = len(locations)
# Solution cost.
print "Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n"
# Inspect solution.
capacity_dimension = routing.GetDimensionOrDie(capacity);
time_dimension = routing.GetDimensionOrDie(time);

for vehicle_nbr in range(num_vehicles):
index = routing.Start(vehicle_nbr)
plan_output = 'Route {0}:'.format(vehicle_nbr)

while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
plan_output += \
node_index=node_index,
tmin=str(assignment.Min(time_var)),
tmax=str(assignment.Max(time_var)))
index = assignment.Value(routing.NextVar(index))

node_index = routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
plan_output += \
node_index=node_index,
tmin=str(assignment.Min(time_var)),
tmax=str(assignment.Max(time_var)))
print plan_output
print "\n"
else:
print 'No solution found.'
else:
print 'Specify an instance greater than 0.'```

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.

The output of the program is shown below.

```Total distance of all routes: 10560

Route 0: 0 Load(0) Time(0, 0) ->  27 Load(0) Time(320, 330) ->  18 Load(20) Time(1130, 1140) ->

Route 1: 0 Load(0) Time(0, 0) ->  21 Load(0) Time(780, 978) ->  31 Load(12) Time(906, 1104) ->

Route 2: 0 Load(0) Time(0, 0) ->  20 Load(0) Time(490, 684) ->  5 Load(8) Time(764, 958) ->

Route 3: 0 Load(0) Time(0, 0) ->  24 Load(0) Time(574, 2146) ->  30 Load(24) Time(906, 2478) ->

Route 4: 0 Load(0) Time(0, 0) ->  26 Load(0) Time(230, 1430) ->  13 Load(2) Time(576, 1776) ->
```

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 there.

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

`18 Load(20) Time(1130, 1140)`
This tells us the following:
• The location is node 18.
• The cumulative load of the previously visited locations (not including node 18) is 20.
• The solution time window at this location is (1130, 1140). This means that the vehicle for route 0 should arrive at node 18 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.

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

# Distance callback

class CreateDistanceCallback(object):
"""Create callback to calculate distances and travel times between points."""

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

for from_node in xrange(num_locations):
self.matrix[from_node] = {}
for to_node in xrange(num_locations):
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 int(self.matrix[from_node][to_node])

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

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

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

# Service time (proportional to demand) callback.
class CreateServiceTimeCallback(object):
"""Create callback to get time windows at each location."""

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

def ServiceTime(self, from_node, to_node):
return int(self.matrix[from_node] * self.time_per_demand_unit)
# Create the travel time callback (equals distance divided by speed).
class CreateTravelTimeCallback(object):
"""Create callback to get travel times between locations."""

def __init__(self, dist_callback, speed):
self.dist_callback = dist_callback
self.speed = speed

def TravelTime(self, from_node, to_node):
travel_time = self.dist_callback(from_node, to_node) / self.speed
return int(travel_time)
# Create total_time callback (equals service time plus travel time).
class CreateTotalTimeCallback(object):
"""Create callback to get total times between locations."""

def __init__(self, service_time_callback, travel_time_callback):
self.service_time_callback = service_time_callback
self.travel_time_callback = travel_time_callback

def TotalTime(self, from_node, to_node):
service_time = self.service_time_callback(from_node, to_node)
travel_time = self.travel_time_callback(from_node, to_node)
return service_time + travel_time
def main():
# Create the data.
data = create_data_array()
locations = data[0]
demands = data[1]
start_times = data[2]
end_times = data[3]
num_locations = len(locations)
depot = 0
num_vehicles = 5
search_time_limit = 400000

# Create routing model.
if num_locations > 0:

# The number of nodes of the VRP is num_locations.
# Nodes are indexed from 0 to num_locations - 1. By default the start of
# a route is node 0.
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters = pywrapcp.DefaultRoutingSearchParameters()

# Callbacks to the distance function and travel time functions here.
dist_between_locations = CreateDistanceCallback(locations)
dist_callback = dist_between_locations.Distance

routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand

VehicleCapacity = 100;
NullCapacitySlack = 0;
fix_start_cumul_to_zero = True
capacity = "Capacity"

fix_start_cumul_to_zero, capacity)
time_per_demand_unit = 3
horizon = 24 * 3600
time = "Time"
speed = 1

service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
service_time_callback = service_times.ServiceTime

travel_times = CreateTravelTimeCallback(dist_callback, speed)
travel_time_callback = travel_times.TravelTime

total_times = CreateTotalTimeCallback(service_time_callback, travel_time_callback)
total_time_callback = total_times.TotalTime

routing.AddDimension(total_time_callback,  # total time function callback
horizon,
horizon,
fix_start_cumul_to_zero,
time)
time_dimension = routing.GetDimensionOrDie(time)
for location in range(1, num_locations):
start = start_times[location]
end = end_times[location]
time_dimension.CumulVar(location).SetRange(start, end)
# Solve displays a solution if any.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
size = len(locations)
# Solution cost.
print "Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n"
# Inspect solution.
capacity_dimension = routing.GetDimensionOrDie(capacity);
time_dimension = routing.GetDimensionOrDie(time);

for vehicle_nbr in range(num_vehicles):
index = routing.Start(vehicle_nbr)
plan_output = 'Route {0}:'.format(vehicle_nbr)

while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
plan_output += \
node_index=node_index,
tmin=str(assignment.Min(time_var)),
tmax=str(assignment.Max(time_var)))
index = assignment.Value(routing.NextVar(index))

node_index = routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
plan_output += \
node_index=node_index,
tmin=str(assignment.Min(time_var)),
tmax=str(assignment.Max(time_var)))
print plan_output
print "\n"
else:
print 'No solution found.'
else:
print 'Specify an instance greater than 0.'

def create_data_array():

locations = [[820, 760], [960, 440], [500, 50], [490, 80], [130, 70], [290, 890], [580, 300],
[840, 390], [140, 240], [120, 390], [30, 820], [50, 100], [980, 520], [840, 250],
[610, 590], [10, 650], [880, 510], [910, 20], [190, 320], [930, 30], [500, 930],
[980, 140], [50, 420], [420, 90], [610, 620], [90, 970], [800, 550], [570, 690],
[230, 150], [200, 700], [850, 600], [980, 50]]

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]

start_times =  [0, 508, 103, 493, 225, 531, 89,
565, 540, 108, 602, 466, 356, 303,
399, 382, 362, 521, 23, 489, 445,
318, 380, 55, 574, 515, 110, 310,
387, 491, 328, 73]

# tw_duration is the width of the time windows.
tw_duration = 2150

# In this example, the width is the same at each location, so we define the end times to be
# start times + tw_duration. For problems in which the time window widths vary by location,
# you can explicitly define the list of end_times, as we have done for start_times.
end_times = [0] * len(start_times)

for i in range(len(start_times)):
end_times[i] = start_times[i] + tw_duration
data = [locations, demands, start_times, end_times]
return data
if __name__ == '__main__':
main()```