Common Vehicle 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

Saving solutions

To save a solution to a VRP, first create an array containing the solution's routes, whose ith row contains the locations in route i. The following Python function gets the routes from the solution.

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

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

If you add this function to the Python program for the vehicle routing problem, and then call the function by

assignment = routing.SolveWithParameters(search_parameters)

if assignment:
  # Get routes.
  routes = get_routes_array(assignment, num_routes, routing)
  print("Routes: ", routes)

the program displays the following:

Routes: [[14, 2, 3, 23, 4, 11, 28, 6, 26], [27, 24], [20, 5, 25, 10, 15, 22, 9, 8, 18, 29],
         [12, 1, 16, 30], [13, 21, 31, 19, 17, 7]]

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

At this point, you can save the routes array to a file, and later restore the solution from the saved file.

Specifying initial routes for a search

This section shows how to specify a set of initial routes for a VRP search. We'll use the problem set up in the previous VRP program as an example. To create the initial routes, do the following steps:

  1. Set up the routing model and declare the solver, as described in the previous example.
  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 gets the routes array and creates the initial assignment:

CloseModelWithParameters(search_parameters)
initial_routes = [[11], [17, 19, 2, 28, 4], [20, 5, 25, 10, 15, 9, 8, 23],
                  [27, 24, 6, 13, 21, 31, 3], [30, 26, 16, 12, 1, 7, 14, 29, 18, 22]]
initial_assignment = routing.ReadAssignmentFromRoutes(initial_routes, True)
print("Initial routes: ", initial_routes, "\n")
print("Total distance: " + str(initial_assignment.ObjectiveValue()) + "\n")
final_assignment = routing.SolveFromAssignmentWithParameters(initial_assignment, search_parameters)

Note: CloseModelWithParameters(search_parameters) is only necessary if you add search parameters different from the defaults. If you omit this line, the default search parameters are used.

If you add this code to the previous VRP example and run the program, it returns the following:

Initial routes:  [[11], [17, 19, 2, 28, 4], [20, 5, 25, 10, 15, 9, 8, 23],
                  [27, 24, 6, 13, 21, 31, 3], [30, 26, 16, 12, 1, 7, 14, 29, 18, 22]]

Total distance: 1600

Final routes:  [[14, 2, 3, 23, 4, 11, 28, 6, 26, 0], [27, 24, 0],
                [20, 5, 25, 10, 15, 22, 9, 8, 18, 29, 0], [12, 1, 16, 30, 0],
                [13, 21, 31, 19, 17, 7, 0]]

Total distance: 970

Here's the entire program for this example.

from __future__ import print_function
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
class CreateDistanceCallback(object):
  """Create callback to calculate distances between points."""

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

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

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

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

def main():
  # Create the data.
  data = create_data_array()
  locations = data[0]
  demands = data[1]
  num_locations = len(locations)
  depot = 0    # The depot is the start and end point of each route.
  num_routes = 5

  # Create routing model.
  if num_locations > 0:
    routing = pywrapcp.RoutingModel(num_locations, num_routes, depot)
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    # Callback to the distance function.

    dist_between_locations = CreateDistanceCallback(locations)
    dist_callback = dist_between_locations.Distance
    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

    # Put a callback to the demands.
    demands_at_locations = CreateDemandCallback(demands)
    demands_callback = demands_at_locations.Demand

    # Add a dimension for demand.
    slack_max = 0
    vehicle_capacity = 100
    fix_start_cumul_to_zero = True
    demand = "Demand"
    routing.AddDimension(demands_callback, slack_max, vehicle_capacity,
                         fix_start_cumul_to_zero, demand)
    # The following line is only necessary if you have added search parameters different from the
    # default parameters. If you omit this line, the search uses default search parameters.
    routing.CloseModelWithParameters(search_parameters)
    # Set initial routes.
    initial_routes = [[11], [17, 19, 2, 28, 4], [20, 5, 25, 10, 15, 9, 8, 23],
                      [27, 24, 6, 13, 21, 31, 3], [30, 26, 16, 12, 1, 7, 14, 29, 18, 22]]

    initial_assignment = routing.ReadAssignmentFromRoutes(initial_routes, True)
    print("Initial routes: ", initial_routes, "\n")
    print("Total distance: " + str(initial_assignment.ObjectiveValue()) + "\n")
    final_assignment = routing.SolveFromAssignmentWithParameters(initial_assignment, search_parameters)
    if final_assignment:
      final_routes = get_routes_array(final_assignment, num_routes, routing)
      print("Final routes: ", final_routes, "\n")
      print("Total distance: " + str(final_assignment.ObjectiveValue()) + "\n")
    else:
      print('No solution found.')
  else:
    print('Specify an instance greater than 0.')

def get_routes_array(assignment, num_routes, routing):
  routes = []
  for vehicle_nbr in range(num_routes):
    index = routing.Start(vehicle_nbr)
    route = []

    while not routing.IsEnd(index):
      index = assignment.Value(routing.NextVar(index))
      node_index = routing.IndexToNode(index)
      route.append(node_index)
    # Remove last node (the depot).
    route = route[:-1]
    routes.append(route)
  return routes

def create_data_array():

  locations = [[82, 76], [96, 44], [50, 5], [49, 8], [13, 7], [29, 89], [58, 30], [84, 39],
               [14, 24], [12, 39], [3, 82], [5, 10], [98, 52], [84, 25], [61, 59], [1, 65],
               [88, 51], [91, 2], [19, 32], [93, 3], [50, 93], [98, 14], [5, 42], [42, 9],
               [61, 62], [9, 97], [80, 55], [57, 69], [23, 15], [20, 70], [85, 60], [98, 5]]

  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]
  data = [locations, demands]
  return data

if __name__ == '__main__':
  main()

Setting start and end locations for routes

So far, we have assumed that all vehicles start and end at a single location, the depot. Next, we'll show how to specify different start and end locations for each vehicle in the problem. To do so, pass two vectors, containing the start and end locations, as inputs to the function that creates the routing model. Here's an example.

start_locations = [0, 3, 15, 21, 7]
end_locations = [2, 20, 7, 11, 1]
routing = pywrapcp.RoutingModel(num_locations, num_vehicles,
                                start_locations, end_locations)

When you run the previous example with these inputs, the program returns routes that begin and end at the specified locations.

Total distance of all routes: 599

Route for vehicle 0:

0 -> 2

Distance of route 0: 103
Demand met by vehicle 0: 0

Route for vehicle 1:

3 -> 23 -> 28 -> 18 -> 9 -> 22 -> 10 -> 25 -> 5 -> 20

Distance of route 1: 194
Demand met by vehicle 1: 83

Route for vehicle 2:

15 -> 29 -> 27 -> 24 -> 14 -> 30 -> 7

Distance of route 2: 123
Demand met by vehicle 2: 63

Route for vehicle 3:

21 -> 12 -> 16 -> 26 -> 6 -> 8 -> 4 -> 11

Distance of route 3: 187
Demand met by vehicle 3: 78

Route for vehicle 4:

7 -> 13 -> 17 -> 19 -> 31 -> 1

Distance of route 4: 95
Demand met by vehicle 4: 68

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 callback to make the distance from the depot to all other nodes 0. Since the callback defines the distance between from_node and to_node, we want the callback to return 0 when either from_node or to_node is the depot. To do this, just add the following conditional to the callback:

if from_node == depot or to_node == depot:
          self.matrix[from_node][to_node] = 0
Here's the modified callback:
class CreateDistanceCallback(object):
  """Create callback to calculate distances between points."""
  def __init__(self, locations):
    """Initialize distance array."""
    size = len(locations)
    depot = 0
    self.matrix = {}

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

Note that coordinates of the depot no longer have any effect on the distance callback, so you could define them arbitrarily.

Here's the new output:

Total distance of all routes: 441

Route for vehicle 0:

0 -> 28 -> 4 -> 11 -> 0

Distance of route 0: 29
Demand met by vehicle 0: 48

Route for vehicle 1:

0 -> 29 -> 5 -> 20 -> 27 -> 6 -> 2 -> 3 -> 23 -> 0

Distance of route 1: 169
Demand met by vehicle 1: 84

Route for vehicle 2:

0 -> 8 -> 18 -> 9 -> 22 -> 15 -> 10 -> 25 -> 0

Distance of route 2: 104
Demand met by vehicle 2: 81

Route for vehicle 3:

0 -> 1 -> 12 -> 16 -> 30 -> 14 -> 24 -> 0

Distance of route 3: 61
Demand met by vehicle 3: 99

Route for vehicle 4:

0 -> 17 -> 19 -> 31 -> 21 -> 13 -> 7 -> 26 -> 0

Distance of route 4: 78
Demand met by vehicle 4: 98

To remove the depot from the displayed routes (since it isn't meaningful in this case), make the following changes to the code shown in Invoke the solver:

  1. In the loop that begins with
    while not routing.IsEnd(index_next):
    add the following conditional:
    if node_index != depot:
                route += str(node_index) + " -> "
  2. In the code following the loop, delete the following line:
    route += str(node_index) + " -> " + str(node_index_next)

Send feedback about...

Optimization
Optimization