Common Routing Tasks

The following sections explain how to do some common tasks related to solving vehicle routing problems.

Search limits

Vehicle routing problems with many locations can take a long time to solve. For such problems, it is a good idea to set a search limit, which terminates the search after a specified length of time or number of solutions returned. When the solver reaches the limit, you can save the latest solution to a file. If later you want to try to find a better solution, you can restart the search, using the saved solution as an initial point.

To set a time limit for a search, add the following search parameter before the call to the solver.

search_parameters.time_limit_ms = 30000

This stops the search after 30000 milliseconds (or 30 seconds). See Changing the search strategy for a complete example with a time limit.

To set a limit on the number of solutions returned, add the following.

search_parameters.solution_limit = 100

Storing solutions in an array

At times you may find it convenient to store the routes in a VRP solution in an array. For example, you might want to perform multiple searches, using different parameters, and then compare the saved results.

The following Python function gets the routes from a solution and saves them in an array.

def get_routes_array(assignment, num_vehicles, routing):
  # Get the routes for an assignent and return as a list of lists.
  routes = []
  for route_nbr in range(num_vehicles):
    node = routing.Start(route_nbr)
    route = []

    while not routing.IsEnd(node):
      index = routing.NodeToIndex(node)
      route.append(index)
      node = assignment.Value(routing.NextVar(node))
    routes.append(route)
  return routes

You can add this function to a Python program for a VRP, and call it as follows:

assignment = routing.SolveWithParameters(search_parameters)
routes = get_routes_array(assignment, num_routes, routing)

The result is an array whose rows correspond to the routes.

Another reason for storing a solution in an array is that you can save the array to a file, and later restore the solution from the saved file.

Here's a program that uses the function shown above.

"""Vehicle Routing Problem"""
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():
  """Stores the data for the problem"""
  # Locations
  num_vehicles = 4
  depot = 0
  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)]
  num_locations = len(locations)
  dist_matrix = {}

  for from_node in range(num_locations):
    dist_matrix[from_node] = {}

    for to_node in range(num_locations):
      dist_matrix[from_node][to_node] = (
        manhattan_distance(locations[from_node], locations[to_node]))

  return [num_vehicles, depot, locations, dist_matrix]

###################################
# Distance callback and dimension #
####################################

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 CreateDistanceCallback(dist_matrix):

  def dist_callback(from_node, to_node):
    return dist_matrix[from_node][to_node]

  return dist_callback


def add_distance_dimension(routing, dist_callback):
  """Add Global Span constraint"""
  distance = "Distance"
  maximum_distance = 3000
  routing.AddDimension(
    dist_callback,
    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.
  distance_dimension.SetGlobalSpanCostCoefficient(100)

####################
# Get Routes Array #
####################
def get_routes_array(assignment, num_vehicles, routing):
  # Get the routes for an assignent and return as a list of lists.
  routes = []
  for route_nbr in range(num_vehicles):
    node = routing.Start(route_nbr)
    route = []

    while not routing.IsEnd(node):
      index = routing.NodeToIndex(node)
      route.append(index)
      node = assignment.Value(routing.NextVar(node))
    routes.append(route)
  return routes

########
# Main #
########

def main():
  """Entry point of the program"""
  # Instantiate the data problem.
  [num_vehicles, depot, locations, dist_matrix] = create_data()
  num_locations = len(locations)
  # Create Routing Model
  routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
  # Define weight of each edge
  dist_callback = CreateDistanceCallback(dist_matrix)
  routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
  add_distance_dimension(routing, dist_callback)
  # 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)
  routes = get_routes_array(assignment, num_vehicles, routing)
  print("Routes array:")
  print(routes)

if __name__ == '__main__':
  main()

When you run this program,the program prints the routes in the following array:

Routes array:
[[10, 16, 14, 9, 20], [13, 15, 21], [5, 6, 2, 8, 22], [12, 11, 3, 4, 1, 7, 23]]

Note that the array does not include the start and end locations of the routes (which in this case consists of just the depot).

Setting initial routes for a search

This section shows how to specify a set of initial routes for a VRP. To create the initial routes, do the following steps:

  1. Set up the routing model and declare the solver.
  2. Define an array containing the initial routes. (In this example, the array is defined explicitly in the program, but if you have previously saved a solution to a file, you can create the array from the file.)
  3. Create the initial assignment using the method ReadAssignmentFromRoutes.

Here's some Python code that takes a random array of initial routes, and creates the initial assignment:

initial_routes = [[8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6]]
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
dist_callback = create_dist_callback(dist_matrix)
add_distance_dimension(routing, dist_callback)
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
initial_assignment = routing.ReadAssignmentFromRoutes(initial_routes, True)

Note that the initial routes do not include the depot.

The following program uses this code to set the initial routes and then performs a search.

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

###########################
# Problem Data Definition #
###########################

def create_data():
  """Stores the data for the problem"""
  # Locations
  num_vehicles = 4
  depot = 0
  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)]
  num_locations = len(locations)
  dist_matrix = {}

  for from_node in range(num_locations):
    dist_matrix[from_node] = {}

    for to_node in range(num_locations):
      dist_matrix[from_node][to_node] = (
        manhattan_distance(
          locations[from_node],
          locations[to_node]))

  return [num_vehicles, depot, locations, dist_matrix]

###################################
# Distance callback and dimension #
###################################

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_dist_callback(dist_matrix):

  def dist_callback(from_node, to_node):
    return dist_matrix[from_node][to_node]

  return dist_callback

def add_distance_dimension(routing, dist_callback):
  """Add Global Span constraint"""
  distance = "Distance"
  maximum_distance = 3000
  routing.AddDimension(
    dist_callback,
    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.
  distance_dimension.SetGlobalSpanCostCoefficient(100)

################
# Print Routes #
################

def print_routes(num_vehicles, locations, routing, assignment):
  """Prints assignment on console"""
  total_dist = 0

  for vehicle_id in range(num_vehicles):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
    route_dist = 0

    while not routing.IsEnd(index):
      node = routing.IndexToNode(index)
      next_node = routing.IndexToNode(
        assignment.Value(routing.NextVar(index)))
      route_dist += manhattan_distance(
        locations[node],
        locations[next_node])
      plan_output += ' {node} -> '.format(
        node=node)
      index = assignment.Value(routing.NextVar(index))

    node = routing.IndexToNode(index)
    total_dist += route_dist
    plan_output += ' {node}\n'.format(
      node=node)
    plan_output += 'Distance of 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():
  # Create the data.
  [num_vehicles, depot, locations, dist_matrix] = create_data()
  num_locations = len(locations)

  # Create routing model.
  if num_locations > 0:

    # Set initial routes.
    initial_routes = [[8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6]]
    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
    dist_callback = create_dist_callback(dist_matrix)
    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
    add_distance_dimension(routing, dist_callback)
    initial_assignment = routing.ReadAssignmentFromRoutes(initial_routes, True)

    print("Initial assignment:\n")
    print_routes(num_vehicles, locations, routing, initial_assignment)

    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
    final_assignment = routing.SolveFromAssignmentWithParameters(initial_assignment, search_parameters)

    if final_assignment:
      print("\nFinal assignment:\n")
      print_routes(num_vehicles, locations, routing, final_assignment)
    else:
      print('No solution found.')
  else:
    print('Specify an instance greater than 0.')


if __name__ == '__main__':
  main()

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

Initial assignment:

Route for vehicle 0:
 0 ->  8 ->  16 ->  14 ->  13 ->  12 ->  11 ->  0
Distance of route 0: 22

Route for vehicle 1:
 0 ->  3 ->  4 ->  9 ->  10 ->  0
Distance of route 1: 24

Route for vehicle 2:
 0 ->  15 ->  1 ->  0
Distance of route 2: 24

Route for vehicle 3:
 0 ->  7 ->  5 ->  2 ->  6 ->  0
Distance of route 3: 18

Total distance of all routes: 88

Final assignment:

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

Route for vehicle 1:
 0 ->  12 ->  11 ->  15 ->  13 ->  0
Distance of route 1: 16

Route for vehicle 2:
 0 ->  3 ->  4 ->  1 ->  7 ->  0
Distance of route 2: 16

Route for vehicle 3:
 0 ->  5 ->  2 ->  6 ->  8 ->  0
Distance of route 3: 16

Total distance of all routes: 64

Not surprisingly, the final routes have shorter total distance than the initial routes.

Setting start and end locations for routes

So far, we have assumed that all vehicles start and end at a single location, the depot. You can also set possibly different start and end locations for each vehicle in the problem. To do so, pass two vectors, containing the indices of the start and end locations, as inputs to the RoutingModel method in the main function. Here's some example code to do this in a problem with four vehicles:

start_locations = [8, 3, 15, 7]
end_locations = [11, 10, 1, 6]
routing = pywrapcp.RoutingModel(num_locations, num_vehicles,
                                start_locations, end_locations)

Here's a complete program that sets the start and end locations this way.

"""Vehicle Routing Problem"""
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():
  """Stores the data for the problem"""
  # Locations
  num_vehicles = 4
  depot = 0
  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)]
  num_locations = len(locations)
  dist_matrix = {}

  for from_node in range(num_locations):
    dist_matrix[from_node] = {}

    for to_node in range(num_locations):
      dist_matrix[from_node][to_node] = (
        manhattan_distance(
          locations[from_node],
          locations[to_node]))

  return [num_vehicles, depot, locations, dist_matrix]

###################################
# Distance callback and dimension #
###################################


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 CreateDistanceCallback(dist_matrix):

  def dist_callback(from_node, to_node):
    return dist_matrix[from_node][to_node]

  return dist_callback


def add_distance_dimension(routing, dist_callback):
  """Add Global Span constraint"""
  distance = "Distance"
  maximum_distance = 3000
  routing.AddDimension(
    dist_callback,
    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.
  distance_dimension.SetGlobalSpanCostCoefficient(100)

################
# Print Routes #
################

def print_routes(num_vehicles, locations, routing, assignment):
  """Prints assignment on console"""
  total_dist = 0

  for vehicle_id in range(num_vehicles):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
    route_dist = 0

    while not routing.IsEnd(index):
      node = routing.IndexToNode(index)
      next_node = routing.IndexToNode(
        assignment.Value(routing.NextVar(index)))
      route_dist += manhattan_distance(
        locations[node],
        locations[next_node])
      plan_output += ' {node} -> '.format(
        node=node)
      index = assignment.Value(routing.NextVar(index))

    node = routing.IndexToNode(index)
    total_dist += route_dist
    plan_output += ' {node}\n'.format(
      node=node)
    plan_output += 'Distance of 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"""
  # Create data.
  [num_vehicles, depot, locations, dist_matrix] = create_data()
  num_locations = len(locations)
  # Create Routing Model
  start_locations = [8, 3, 15, 7]
  end_locations = [11, 10, 1, 6]
  routing = pywrapcp.RoutingModel(num_locations, num_vehicles, start_locations, end_locations)

  dist_callback = CreateDistanceCallback(dist_matrix)
  add_distance_dimension(routing, dist_callback)
  routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
  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)
  print_routes(num_vehicles, locations, routing, assignment)

if __name__ == '__main__':
  main()

When you run program, you get the following output, in which the routes start and end at the specificed locations:

Route for vehicle 0:
 8 ->  16 ->  14 ->  13 ->  12 ->  11
Distance of route 0: 14

Route for vehicle 1:
 3 ->  4 ->  0 ->  9 ->  10
Distance of route 1: 12

Route for vehicle 2:
 15 ->  1
Distance of route 2: 10

Route for vehicle 3:
 7 ->  5 ->  2 ->  6
Distance of route 3: 11

Total distance of all routes: 47

The total distance is shorter than in the previous example because the vehicles are not required to start or end at the depot.

Allowing arbitrary start and end locations

In other versions of the vehicle routing problem, vehicles are allowed to start and end at arbitrary locations. To set up the problem this way, simply modify the distance callback so that distance from the depot to any other location is 0. This turns the depot into a dummy location, whose position has no effect on the optimal routes.

Here's how to modify the distance matrix to make the distance from the depot to all other nodes 0.

  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)]
  num_locations = len(locations)
  dist_matrix = {}

  for from_node in range(num_locations):
    dist_matrix[from_node] = {}

    for to_node in range(num_locations):
      if from_node == depot or to_node == depot:
            # Define the distance from the depot to any node to be 0.
            self.matrix[from_node][to_node] = 0
        else:
          dist_matrix[from_node][to_node] = (
            manhattan_distance(locations[from_node], locations[to_node]))
Note that dist_matrix[from_node]{to_node] is 0 when either from_node or to_node is the depot.

Here's a complete program that uses this modified distance matrix:

"""Vehicle Routing Problem"""
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():
  """Stores the data for the problem"""
  # Locations
  num_vehicles = 4
  depot = 0
  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)]
  num_locations = len(locations)
  dist_matrix = {}

  for from_node in range(num_locations):
    dist_matrix[from_node] = {}

    for to_node in range(num_locations):
      if from_node == depot or to_node == depot:
            # Define the distance from the depot to any node to be 0.
            self.matrix[from_node][to_node] = 0
        else:
          dist_matrix[from_node][to_node] = (
            manhattan_distance(locations[from_node], locations[to_node]))
  return [num_vehicles, depot, locations, dist_matrix]

###################################
# Distance callback and dimension #
###################################

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 CreateDistanceCallback(dist_matrix):

  def dist_callback(from_node, to_node):
    return dist_matrix[from_node][to_node]

  return dist_callback

def add_distance_dimension(routing, dist_callback):
  """Add Global Span constraint"""
  distance = "Distance"
  maximum_distance = 3000
  routing.AddDimension(
    dist_callback,
    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.
  distance_dimension.SetGlobalSpanCostCoefficient(100)

################
# Print Routes #
################

def print_routes(num_vehicles, locations, routing, assignment):
  """Prints assignment on console"""
  total_dist = 0

  for vehicle_id in range(num_vehicles):
    index = routing.Start(vehicle_id)
    # Skip depot - vehicles starting at arbitray locations.
    node = routing.IndexToNode(index)
    next_node = routing.IndexToNode(
      assignment.Value(routing.NextVar(index)))
    index = routing.NodeToIndex(next_node)
    node = routing.IndexToNode(index)
    next_node = routing.IndexToNode(
      assignment.Value(routing.NextVar(index)))
    plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
    route_dist = 0

    while not routing.IsEnd(index):
      node = routing.IndexToNode(index)
      next_node = routing.IndexToNode(
        assignment.Value(routing.NextVar(index)))
      route_dist += manhattan_distance(
        locations[node],
        locations[next_node])

      index = assignment.Value(routing.NextVar(index))

      if routing.IsEnd(index):
        plan_output += ' {node} '.format(
          node=node)
      else:
        plan_output += ' {node} -> '.format(
          node=node)

    total_dist += route_dist
    plan_output += '\nDistance of 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.
  [num_vehicles, depot, locations, dist_matrix] = create_data()
  num_locations = len(locations)
  # Create Routing Model
  routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
  # Define weight of each edge
  dist_callback = CreateDistanceCallback(dist_matrix)
  routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
  add_distance_dimension(routing, dist_callback)
  # 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)
  print_routes(num_vehicles, locations, routing, assignment)

if __name__ == '__main__':
  main()

Note that the print_routes function has been modified from the earlier examples so as not to display the depot in the routes.

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

Route for vehicle 0:
 15 ->  11 ->  12 ->  13 ->  14 ->  16
Distance of route 0: 18

Route for vehicle 1:
 3 ->  4 ->  1
Distance of route 1: 9

Route for vehicle 2:
 7 ->  8
Distance of route 2: 6

Route for vehicle 3:
 2 ->  6 ->  5 ->  9 ->  10
Distance of route 3: 16

Total distance of all routes: 49

Send feedback about...

Optimization
Optimization