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.

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 follows the 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.

Manhattan distance

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

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 Dimension

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

Demand Dimension

Like in the CVRP example we add a Manhattan distance evaluator to the problem.

Time Dimension

In addition to the distance and 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):
    """Add Global Span constraint"""
    time = "Time"
    horizon = 120
    routing.AddDimension(
        time_evaluator,
        horizon, # allow waiting time
        horizon, # maximum time per vehicle
        True, # start cumul to zero
        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 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.

Add time window constraints

The following code adds time window constraints.

    time_dimension = routing.GetDimensionOrDie(time)
    for location_idx, time_window in enumerate(data.time_windows):
        time_dimension.CumulVar(location_idx).SetRange(time_window[0], time_window[1])

Note that time_dimension.CumulVar(location) is the cumulative time for the vehicle along its route.
So for each location, the code time_dimension.CumulVar(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].

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])
                load_var = capacity_dimension.CumulVar(index)
                route_load = self.assignment.Value(load_var)
                time_var = time_dimension.CumulVar(index)
                time_min = self.assignment.Min(time_var)
                time_max = self.assignment.Max(time_var)
                plan_output += ' {0} Load({1}) Time({2},{3}) ->'.format(node_index, route_load, time_min, time_max)
                index = self.assignment.Value(self.routing.NextVar(index))

            node_index = self.routing.IndexToNode(index)
            load_var = capacity_dimension.CumulVar(index)
            route_load = self.assignment.Value(load_var)
            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 += ' {0} Load({1}) Time({2},{3})\n'.format(node_index, route_load, time_min, time_max)
            plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
            plan_output += 'Load of the route: {0}\n'.format(route_load)
            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
    add_time_window_constraints(routing, 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:
 0 Load(0) Time(0,0) -> 12 Load(0) Time(5,13) -> 13 Load(2) Time(17,25) -> 15 Load(6) Time(45,52) -> 11 Load(14) Time(88,95) -> 0 Load(15) Time(99,120)
Distance of the route: 1780m
Load of the route: 15
Time of the route: 99min

Route for vehicle 1:
 0 Load(0) Time(0,0) -> 5 Load(0) Time(3,6) -> 8 Load(2) Time(15,18) -> 6 Load(10) Time(57,60) -> 2 Load(14) Time(80,85) -> 0 Load(15) Time(94,120)
Distance of the route: 1712m
Load of the route: 15
Time of the route: 94min

Route for vehicle 2:
 0 Load(0) Time(0,0) -> 7 Load(0) Time(2,5) -> 4 Load(8) Time(46,49) -> 3 Load(12) Time(67,70) -> 1 Load(14) Time(80,85) -> 0 Load(15) Time(91,120)
Distance of the route: 1552m
Load of the route: 15
Time of the route: 91min

Route for vehicle 3:
 0 Load(0) Time(0,0) -> 9 Load(0) Time(2,10) -> 14 Load(1) Time(10,18) -> 16 Load(5) Time(32,40) -> 10 Load(13) Time(76,85) -> 0 Load(15) Time(92,120)
Distance of the route: 1552m
Load of the route: 15
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): # 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]

def add_capacity_constraints(routing, data, demand_evaluator):
    """Adds capacity constraint"""
    capacity = "Capacity"
    routing.AddDimension(
        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]

def add_time_window_constraints(routing, data, time_evaluator):
    """Add Global Span constraint"""
    time = "Time"
    horizon = 120
    routing.AddDimension(
        time_evaluator,
        horizon, # allow waiting time
        horizon, # maximum time per vehicle
        True, # start cumul to zero
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    for location_idx, time_window in enumerate(data.time_windows):
        time_dimension.CumulVar(location_idx).SetRange(time_window[0], time_window[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])
                load_var = capacity_dimension.CumulVar(index)
                route_load = self.assignment.Value(load_var)
                time_var = time_dimension.CumulVar(index)
                time_min = self.assignment.Min(time_var)
                time_max = self.assignment.Max(time_var)
                plan_output += ' {0} Load({1}) Time({2},{3}) ->'.format(node_index, route_load, time_min, time_max)
                index = self.assignment.Value(self.routing.NextVar(index))

            node_index = self.routing.IndexToNode(index)
            load_var = capacity_dimension.CumulVar(index)
            route_load = self.assignment.Value(load_var)
            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 += ' {0} Load({1}) Time({2},{3})\n'.format(node_index, route_load, time_min, time_max)
            plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
            plan_output += 'Load of the route: {0}\n'.format(route_load)
            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)
    # Add Capacity constraint
    demand_evaluator = CreateDemandEvaluator(data).demand_evaluator
    add_capacity_constraints(routing, data, demand_evaluator)
    # Add Time Window constraint
    time_evaluator = CreateTimeEvaluator(data).time_evaluator
    add_time_window_constraints(routing, 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.)

Send feedback about...

Optimization
Optimization