Vehicle Routing Problem

Overview

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem. In a VRP, the goal is to find the optimal set of routes for a fleet of vehicles delivering goods or services to various locations. The VRP was first proposed by Dantzig and Ramser in 1959.

Like the TSP, the VRP can be represented by a graph with distances assigned to the edges.

If you try to find a set of routes with the least total distance, with no additional constraints on the vehicles, the optimal solution is to assign all locations to a single vehicle and leave the rest idle. In this case, the problem reduces to a TSP.

A more interesting problem is to minimize the length of the longest single route for all vehicles, as shown in the next example.

VRPs can also have additional constraints on the vehicles—for example, lower and upper bounds on the number of locations each vehicle visits, or the length of each route.

In later sections, we'll discuss other types of VRP constraints, including:

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

You can solve VRPs using the OR-Tools vehicle routing library. The routing library is a layer on top of the constraint programming solver. The section RoutingModel describes the C++ methods for solving routing problems.

Example: minimizing the longest single route

In this example, a company needs to visit some customer locations in a city made up of identical rectangular blocks. A map of the city is shown below, with the company location marked in black and the locations to visit in blue. The problem is to find an assignment of routes for which the longest single route has minimum distance. (Note: this is not the same problem as minimizing the total length of all routes.)

Manhattan distance

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 laid 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.)

Solving the example with OR-Tools

The following sections walk through a Python program that solves the problem in this example.

Model the problem

The following code defines the data for the problem.

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

    @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

The data consists of:

  • a num_vehicles variable — The number of vehicles in the fleet.
  • a locations array — A two-dimensional array of points in the plane.
  • 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 function

The function that calculates the Manhattan distance between points 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 following class creates the distance function that is passed to the solver. As in the TSP example, the computed distances between nodes are stored in a matrix to speed up the function call.

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]

Add a distance dimension

To solve this VRP, you need to create a distance dimension, which computes the cumulative distance traveled by each vehicle along its route. You can then set a cost equal to the maximum of the total distances along each route.

For more information, see Dimensions.

To add a distance dimension, use the solver's AddDimension method. The following code creates a dimension for the distance and sets the cumulative distance cost.

def add_distance_dimension(routing, distance_evaluator):
    """Add Global Span constraint"""
    distance = "Distance"
    maximum_distance = 3000
    routing.AddDimension(
        distance_evaluator,
        0, # null slack
        maximum_distance, # maximum distance per vehicle
        True, # start cumul to zero
        distance)
    distance_dimension = routing.GetDimensionOrDie(distance)
    # Try to minimize the max distance among vehicles.
    # /!\ It doesn't mean the standard deviation is minimized
    distance_dimension.SetGlobalSpanCostCoefficient(100)

In this case, the significant inputs to the function add_distance_dimension are the following:

  • distance_evaluator — Returns the distance between locations.
  • maximum_distance — The maximum distance that each vehicle can travel.

The main function calls add_distance_dimension after calling CreateDistanceEvaluator.

    add_distance_dimension(routing, distance_evaluator)

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])
                plan_output += ' {node_index} -> '.format(
                    node_index=node_index)
                index = self.assignment.Value(self.routing.NextVar(index))

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

The method print() displays the route for each vehicle (i.e. the list of visited nodes), and computes the distance of the routes. Note that these distances 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, you have everything to create the main function.

First, you create the problem data:

    data = DataProblem()

Next, create the routing model solver:

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

Then, provide the distance evaluator so the solver can compute the distances between locations.

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

Next, add the distance dimension.

    add_distance_dimension(routing, distance_evaluator)

You also have to specify a heuristic method to find the first solution:

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

Finally, you can run the solver:

    assignment = routing.SolveWithParameters(search_parameters)

And print the solution:

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

Running the program

When you run the program, it displays the following output:

Route for vehicle 0:
 0 ->  8 ->  6 ->  2 ->  5 ->  0
Distance of the route 0: 1552

Route for vehicle 1:
 0 ->  7 ->  1 ->  4 ->  3 ->  0
Distance of the route 1: 1552

Route for vehicle 2:
 0 ->  9 ->  10 ->  16 ->  14 ->  0
Distance of the route 2: 1552

Route for vehicle 3:
 0 ->  12 ->  11 ->  15 ->  13 ->  0
Distance of the route 3: 1552

Total Distance of all routes: 6208

The graph below shows the assigned routes.

The entire program

The entire program that minimizes the longest single route is shown below.

"""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 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._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

    @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

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

def add_distance_dimension(routing, distance_evaluator):
    """Add Global Span constraint"""
    distance = "Distance"
    maximum_distance = 3000
    routing.AddDimension(
        distance_evaluator,
        0, # null slack
        maximum_distance, # maximum distance per vehicle
        True, # start cumul to zero
        distance)
    distance_dimension = routing.GetDimensionOrDie(distance)
    # Try to minimize the max distance among vehicles.
    # /!\ It doesn't mean the standard deviation is minimized
    distance_dimension.SetGlobalSpanCostCoefficient(100)

###########
# 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])
                plan_output += ' {node_index} -> '.format(
                    node_index=node_index)
                index = self.assignment.Value(self.routing.NextVar(index))

            node_index = self.routing.IndexToNode(index)
            total_dist += route_dist
            plan_output += ' {node_index}\n'.format(
                node_index=node_index)
            plan_output += 'Distance of the route {0}: {dist}\n'.format(
                vehicle_id,
                dist=route_dist)
            print(plan_output)
        print('Total Distance of all routes: {dist}'.format(dist=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)
    add_distance_dimension(routing, distance_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()

Dimensions

This section provides more information about dimensions, which keep track of quantities that accumulate along vehicle routes. In the previous VRP example the quantity is the total distance each vehicle travels. Another example is given by the capacitated vehicle routing problem, in which the vehicles pick up and deliver packages. In that case, the dimension tracks the total amount of packages (by either size or weight) carried by each vehicle.

Each dimension contains a callback for the quantity accumulated along each route, along with related data and variables. You can add a dimension to a routing problem using the solver's AddDimension method. See Add a distance dimension for an example.

Internally, a dimension stores two types of variables that are linked to quantities that change along routes:

  • Transit variables — The increase or decrease of the quantity on each edge .
  • Cumulative variables — The total accumulated quantity at each node.

In more general routing problems, you can minimize the global dimension span of a quantity, which is the difference between the largest value of the cumulative variables at the end of each vehicle's route, minus the smallest value of the cumulative variables of the cumulative variables at the start of each vehicle's route. In other words, for a fleet of k vehicles whose the first node of the route for the vehicle i is starti and the last node is endi, the global span is:

max({cumul(end1),...,cumul(endk)}) - min({cumul(start1),...,cumul(startk)})

When the quantity is distance, the cumulative variables at the start of each route are zero, because no distance has been travelled at the start. However, for other quantities, such as the total weight of packages carried by each vehicle, the cumulative variables might be greater than zero at the start—for example, if some packages are loaded onto the vehicle at the depot.

Send feedback about...