Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem, whose goal is to find the optimal set of routes for a fleet of vehicles delivering goods or services to various locations. Like the TSP, the Vehicle Routing Problem can be represented by a graph with distances assigned to the edges. Vehicle routing problems can also have other constraints, including the following:

  • 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.
  • Maximum number of locations that each vehicle can visit.
  • Time (or distance) constraints: the duration (or length) of each route cannot exceed a fixed bound.
  • 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.

On this page, we'll walk through an example of using OR-Tools to solve a VRP with capacity constraints. There are several examples of other types of vehicle routing problems on github — look for examples that have "cvrptw" in their names.

Capacitated Vehicle Routing Problems

In the capacitated vehicle routing problem (CVRP), we are given a demand at each location, and each vehicle's maximum capacity. The problem is to find an assignment of routes to vehicles so that the total demand of the locations on a vehicle's route does not exceed its capacity.

In this example, we assume that all vehicles start at the same location, called the depot. Alternatively, you can allow vehicles to start and end any location.

The following sections present an example of a CVRP, and shows how to solve it using OR-Tools.

Create the data

The following code creates the data for the problem.

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

The data consists of two arrays:

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

Declare the solver

The program uses the routing model solver, the same solver used in the TSP example. The following code declares the solver.

  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_vehicles = 5

  # Create routing model.
  if num_locations > 0:
    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, 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)

Create the distance callback

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

The code that creates the distance callback is shown below.

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

Create the demands callback

In addition to the distance callback, the solver also requires a callback for the demands, which simply returns the values of the one-dimensional array of demands. The code for the demands callback is shown below.

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

Dimensions

Routing problems involve quantities that accumulate along a vehicle's route. In this example, such a quantity is demand — say, the weight or volume of a package that must be delivered. For every location where a vehicle stops along its route, the total demand on the vehicle increases by the demand at that location. (Other examples of these types of quantities are the distance a vehicle travels, or its travel time.)

The routing solver stores each quantity of this type in an object called a dimension. The dimension contains a callback for the quantity, along with related data and variables. You can add a dimension to a routing problem using the solver's AddDimension method. The following code creates a dimension for the demand in this example.

    # 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)
In this case, the significant inputs to the method are the following:
  • demands_callback — Returns the demand at each location.
  • vehicle_capacity — The maximum capacity of each vehicle. The vehicle_capacity defines the capacity constraint for the problem, by setting a maximum value for the sum of the demands over each vehicle's route.
Variables

Internally, a dimension stores two types of variables that are linked to the quantity:

  • Transit variables — The increase or decrease of the quantity at each location.
  • Cumulative variables — The total accumulated quantity at each location.
While these variables are not used in this example, the section Vehicle Routing with Time Windows presents an example in which the cumulative variable for time is used to set time windows for stops at each location.

Invoke the solver and display the results

The following code invokes the solver and displays the output.

    # Solve, displays a solution if any.
    assignment = routing.SolveWithParameters(search_parameters)
    if assignment:
      # Display solution.
      # Solution cost.
      print "Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n"

      for vehicle_nbr in range(num_vehicles):
        index = routing.Start(vehicle_nbr)
        index_next = assignment.Value(routing.NextVar(index))
        route = ''
        route_dist = 0
        route_demand = 0

        while not routing.IsEnd(index_next):
          node_index = routing.IndexToNode(index)
          node_index_next = routing.IndexToNode(index_next)
          route += str(node_index) + " -> "
          # Add the distance to the next node.
          route_dist += dist_callback(node_index, node_index_next)
          # Add demand.
          route_demand += demands[node_index_next]
          index = index_next
          index_next = assignment.Value(routing.NextVar(index))

        node_index = routing.IndexToNode(index)
        node_index_next = routing.IndexToNode(index_next)
        route += str(node_index) + " -> " + str(node_index_next)
        route_dist += dist_callback(node_index, node_index_next)
        print "Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n"
        print "Distance of route " + str(vehicle_nbr) + ": " + str(route_dist)
        print "Demand met by vehicle " + str(vehicle_nbr) + ": " + str(route_demand) + "\n"
    else:
      print 'No solution found.'
  else:
    print 'Specify an instance greater than 0.'

In addition to the routes, the program also calculates the total distance and total demand of each route. You can check that the total demand for each route does not exceed the capacity, so the capacity constraint is satisfied.

Here is the output of the program.

Total distance of all routes: 970

Route for vehicle 0:

0 -> 14 -> 2 -> 3 -> 23 -> 4 -> 11 -> 28 -> 6 -> 26 -> 0

Distance of route 0: 300
Demand met by vehicle 0: 100

Route for vehicle 1:

0 -> 27 -> 24 -> 0

Distance of route 1: 78
Demand met by vehicle 1: 44

Route for vehicle 2:

0 -> 20 -> 5 -> 25 -> 10 -> 15 -> 22 -> 9 -> 8 -> 18 -> 29 -> 0

Distance of route 2: 316
Demand met by vehicle 2: 98

Route for vehicle 3:

0 -> 12 -> 1 -> 16 -> 30 -> 0

Distance of route 3: 96
Demand met by vehicle 3: 72

Route for vehicle 4:

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

Distance of route 4: 180
Demand met by vehicle 4: 96

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.

The entire program

The entire program for the capacitated vehicle routing problem is shown below.

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_vehicles = 5

  # Create routing model.
  if num_locations > 0:
    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, 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)

    # Solve, displays a solution if any.
    assignment = routing.SolveWithParameters(search_parameters)
    if assignment:
      # Display solution.
      # Solution cost.
      print "Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n"

      for vehicle_nbr in range(num_vehicles):
        index = routing.Start(vehicle_nbr)
        index_next = assignment.Value(routing.NextVar(index))
        route = ''
        route_dist = 0
        route_demand = 0

        while not routing.IsEnd(index_next):
          node_index = routing.IndexToNode(index)
          node_index_next = routing.IndexToNode(index_next)
          route += str(node_index) + " -> "
          # Add the distance to the next node.
          route_dist += dist_callback(node_index, node_index_next)
          # Add demand.
          route_demand += demands[node_index_next]
          index = index_next
          index_next = assignment.Value(routing.NextVar(index))

        node_index = routing.IndexToNode(index)
        node_index_next = routing.IndexToNode(index_next)
        route += str(node_index) + " -> " + str(node_index_next)
        route_dist += dist_callback(node_index, node_index_next)
        print "Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n"
        print "Distance of route " + str(vehicle_nbr) + ": " + str(route_dist)
        print "Demand met by vehicle " + str(vehicle_nbr) + ": " + str(route_demand) + "\n"
    else:
      print 'No solution found.'
  else:
    print 'Specify an instance greater than 0.'

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

Enviar comentarios sobre…