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 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 function defines the data for the problem.

def create_data_model():
  """Stores the data for the problem"""
  data = {}
  # Locations in block units
  _locations = \
          [(4, 4), # depot
           (2, 0), (8, 0), # locations to visit
           (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)]
  # Multiply coordinates in block units by the dimensions of an average city block, 114m x 80m,
  # to get location coordinates.
  data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations]
  data["num_locations"] = len(data["locations"])
  data["num_vehicles"] = 4
  data["depot"] = 0
  return data

The data consists of:

  • num_vehicles: The number of vehicles in the fleet.
  • _locations: A two-dimensional array of points in the plane. Note that the function multiplies the coordinates of the points in the array by constants to make the example data—data["locations"]—similar in scale to real city blocks.
  • depot: 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 callback

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 function creates the distance callback 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.

def create_distance_callback(data):
  """Creates callback to return distance between points."""
  _distances = {}

  for from_node in range(data["num_locations"]):
    _distances[from_node] = {}
    for to_node in range(data["num_locations"]):
      if from_node == to_node:
        _distances[from_node][to_node] = 0
      else:
        _distances[from_node][to_node] = (
            manhattan_distance(data["locations"][from_node],
                               data["locations"][to_node]))

  def distance_callback(from_node, to_node):
    """Returns the manhattan distance between the two nodes"""
    return _distances[from_node][to_node]

  return distance_callback

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_callback):
  """Add Global Span constraint"""
  distance = 'Distance'
  maximum_distance = 3000  # Maximum distance per vehicle.
  routing.AddDimension(
      distance_callback,
      0,  # null slack
      maximum_distance,
      True,  # start cumul to zero
      distance)
  distance_dimension = routing.GetDimensionOrDie(distance)
  # Try to minimize the max distance among vehicles.
  distance_dimension.SetGlobalSpanCostCoefficient(100)

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

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

The main function calls add_distance_dimension after calling create_distance_callback.

  add_distance_dimension(routing, distance_callback)

Define the solution printer

The code that outputs the solution is shown below.

def print_solution(data, routing, assignment):
  """Print routes on console."""
  total_distance = 0
  for vehicle_id in range(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
    distance = 0
    while not routing.IsEnd(index):
      plan_output += ' {} ->'.format(routing.IndexToNode(index))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
    plan_output += ' {}\n'.format(routing.IndexToNode(index))
    plan_output += 'Distance of route: {}m\n'.format(distance)
    print(plan_output)
    total_distance += distance
  print('Total distance of all routes: {}m'.format(total_distance))

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 = create_data_model()

Next, declare the routing model solver:

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

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

  distance_callback = create_distance_callback(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)

Next, add the distance dimension.

  add_distance_dimension(routing, distance_callback)

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) # pylint: disable=no-member

Finally, you can run the solver:

  assignment = routing.SolveWithParameters(search_parameters)

And print the solution:

  if assignment:
    print_solution(data, routing, assignment)

Running the program

The complete program is shown in the next section. When you run the program, it displays the following output:

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

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

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

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

Total distance of all routes: 6208m

The graph below shows the assigned routes.

The entire program

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

from __future__ import print_function
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

###########################
# Problem Data Definition #
###########################
def create_data_model():
  """Stores the data for the problem"""
  data = {}
  # Locations in block units
  _locations = \
          [(4, 4), # depot
           (2, 0), (8, 0), # locations to visit
           (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)]
  # Multiply coordinates in block units by the dimensions of an average city block, 114m x 80m,
  # to get location coordinates.
  data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations]
  data["num_locations"] = len(data["locations"])
  data["num_vehicles"] = 4
  data["depot"] = 0
  return data
#######################
# 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]))
def create_distance_callback(data):
  """Creates callback to return distance between points."""
  _distances = {}

  for from_node in range(data["num_locations"]):
    _distances[from_node] = {}
    for to_node in range(data["num_locations"]):
      if from_node == to_node:
        _distances[from_node][to_node] = 0
      else:
        _distances[from_node][to_node] = (
            manhattan_distance(data["locations"][from_node],
                               data["locations"][to_node]))

  def distance_callback(from_node, to_node):
    """Returns the manhattan distance between the two nodes"""
    return _distances[from_node][to_node]

  return distance_callback
def add_distance_dimension(routing, distance_callback):
  """Add Global Span constraint"""
  distance = 'Distance'
  maximum_distance = 3000  # Maximum distance per vehicle.
  routing.AddDimension(
      distance_callback,
      0,  # null slack
      maximum_distance,
      True,  # start cumul to zero
      distance)
  distance_dimension = routing.GetDimensionOrDie(distance)
  # Try to minimize the max distance among vehicles.
  distance_dimension.SetGlobalSpanCostCoefficient(100)
###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Print routes on console."""
  total_distance = 0
  for vehicle_id in range(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
    distance = 0
    while not routing.IsEnd(index):
      plan_output += ' {} ->'.format(routing.IndexToNode(index))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
    plan_output += ' {}\n'.format(routing.IndexToNode(index))
    plan_output += 'Distance of route: {}m\n'.format(distance)
    print(plan_output)
    total_distance += distance
  print('Total distance of all routes: {}m'.format(total_distance))
########
# Main #
########
def main():
  """Entry point of the program"""
  # Instantiate the data problem.
  data = create_data_model()
  # Create Routing Model
  routing = pywrapcp.RoutingModel(
      data["num_locations"],
      data["num_vehicles"],
      data["depot"])
  # Define weight of each edge
  distance_callback = create_distance_callback(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)
  add_distance_dimension(routing, distance_callback)
  # Setting first solution heuristic (cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # pylint: disable=no-member
  # Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  if assignment:
    print_solution(data, routing, assignment)
if __name__ == '__main__':
  main()

Dimensions

A dimension is an object the routing solver uses to keep track of quantities that accumulate along vehicle routes. The example in the preceding section uses a dimension to track the distance traveled by each vehicle. The example adds the dimension using the solver's AddDimension method.

Another example, presented in the next section, uses a dimension to track the total load of the items carried by a vehicle (such as their weight or volume). That example uses a slightly different dimension, created by the AddDimensionWithVechicleCapacity method, which takes a vector of maximum capacities for each vehicle. Several other methods for creating dimensions are described in the Routing Model reference page. See methods whose names start with AddDimension.

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.

The preceding VRP example uses a distance dimension to minimize the global dimension span of the distance traveled. This is the difference between the largest value of the cumulative variables at the end of the vehicle routes, minus the smallest value of the cumulative variables at the start of the routes. 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...