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 route distance —or the duration of the route with the longest travel time—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 the next example, a company needs to visit some customer locations in a city made up of identical rectangular blocks. A diagram of the city is shown below, with the company location marked in black and the locations to visit in blue.

Location coordinates

To set up the example, we have assigned the following coordinates to the locations shown in the diagram:

[(456, 320), # location 0
(228, 0),    # location 1
(912, 0),    # location 2
(0, 80),     # location 3
(114, 80),   # location 4
(570, 160),  # location 5
(798, 160),  # location 6
(342, 240),  # location 7
(684, 240),  # location 8
(570, 400),  # location 9
(912, 400),  # location 10
(114, 480),  # location 11
(228, 480),  # location 12
(342, 560),  # location 13
(684, 560),  # location 14
(0, 640),    # location 15
(798, 640)]  # location 16

We have calculated the distances between locations and stored them in an array, shown in the next section.

Note: For convenience, the distances in this example are calculated using Manhattan distance, in which the distance between two points, (x1, y1) and (x2, y2) is defined to be |x1 - x2| + |y1 - y2|. However, there is no special reason to use this definition. You can use whatever method is best suited to your problem to calculate distances between locations. See Distance Matrix API for an example of creating a distance matrix using the Google Distance Matrix API.

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():
  """Creates the data for the example."""
  data = {}
  # Array of distances between locations.
  _distances = \
          [
           [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
           [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
           [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
           [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
           [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
           [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
           [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
           [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
           [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
           [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
           [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
           [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
           [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
           [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
           [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
           [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
           [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
          ]
  data["distances"] = _distances
  data["num_locations"] = len(_distances)
  data["num_vehicles"] = 4
  data["depot"] = 0
  return data

The data consists of:

  • distances: The distance matrix—an array of distances between locations.
  • num_locations: The number of locations.
  • num_vehicles: The number of vehicles in the fleet.
  • depot: The index of the depot. we assume that all vehicles start at the same location, called the depot. Alternatively, you can allow vehicles to start and end any location.

Note that it is not necessary to create an array for the location coordinates: all the essential information for the problem is contained in the distance matrix.

Define the distance callback

The following function creates the distance callback that is passed to the solver.

def create_distance_callback(data):
  """Creates callback to return distance between points."""
  distances = data["distances"]

  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)
    route_dist = 0
    while not routing.IsEnd(index):
      node_index = routing.IndexToNode(index)
      next_node_index = routing.IndexToNode(
        assignment.Value(routing.NextVar(index)))
      route_dist += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
      plan_output += ' {0} ->'.format(node_index)
      index = assignment.Value(routing.NextVar(index))
    plan_output += ' {}\n'.format(routing.IndexToNode(index))
    plan_output += 'Distance of route: {}m\n'.format(route_dist)
    print(plan_output)
    total_distance += route_dist
  print('Total distance of all routes: {}m'.format(total_distance))

The print_solution() function displays the route for each vehicle (the visited locations), and the distances 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.

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():
  """Creates the data for the example."""
  data = {}
  # Array of distances between locations.
  _distances = \
          [
           [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
           [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
           [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
           [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
           [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
           [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
           [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
           [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
           [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
           [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
           [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
           [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
           [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
           [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
           [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
           [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
           [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
          ]
  data["distances"] = _distances
  data["num_locations"] = len(_distances)
  data["num_vehicles"] = 4
  data["depot"] = 0
  return data
#######################
# Problem Constraints #
#######################
def create_distance_callback(data):
  """Creates callback to return distance between points."""
  distances = data["distances"]

  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)
    route_dist = 0
    while not routing.IsEnd(index):
      node_index = routing.IndexToNode(index)
      next_node_index = routing.IndexToNode(
        assignment.Value(routing.NextVar(index)))
      route_dist += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
      plan_output += ' {0} ->'.format(node_index)
      index = assignment.Value(routing.NextVar(index))
    plan_output += ' {}\n'.format(routing.IndexToNode(index))
    plan_output += 'Distance of route: {}m\n'.format(route_dist)
    print(plan_output)
    total_distance += route_dist
  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()

Using the Google Distance Matrix API

The section shows how to use the Google Distance Matrix API to create the distance matrix for any set of locations defined by addresses, or by latitudes and longitudes. You can use the API to calculate the distance matrix for many types of routing problems.

To use the API, you'll need an API key. Here's how to obtain one.

Example

As an example, we'll walk through a Python program that creates the distance matrix for a set of 16 locations in the city of Memphis, Tennessee. The distance matrix is a 16 x 16 matrix whose i, j entry is the distance between locations i and j. Here are the addresses for the locations.

  data['addresses'] = ['3610+Hacks+Cross+Rd+Memphis+TN', # depot
                       '1921+Elvis+Presley+Blvd+Memphis+TN',
                       '149+Union+Avenue+Memphis+TN',
                       '1034+Audubon+Drive+Memphis+TN',
                       '1532+Madison+Ave+Memphis+TN',
                       '706+Union+Ave+Memphis+TN',
                       '3641+Central+Ave+Memphis+TN',
                       '926+E+McLemore+Ave+Memphis+TN',
                       '4339+Park+Ave+Memphis+TN',
                       '600+Goodwyn+St+Memphis+TN',
                       '2000+North+Pkwy+Memphis+TN',
                       '262+Danny+Thomas+Pl+Memphis+TN',
                       '125+N+Front+St+Memphis+TN',
                       '5959+Park+Ave+Memphis+TN',
                       '814+Scott+St+Memphis+TN',
                       '1005+Tillman+St+Memphis+TN'
                      ]

API requests

A Distance Matrix API request is a long string containing the following:

  • API address: https://maps.googleapis.com/maps/api/distancematrix/json?. The end of the request, json, asks for the response in JSON.
  • Request options. In this example, units=imperial sets the language of the response to English.
  • Origin addresses: Travel starting points. For example
    &origins=3610+Hacks+Cross+Rd+Memphis+TN.
    Spaces in the address are replaced with the + character. Multiple addresses are separated by a |.
  • Destination addresses: Travel ending points. For example
    &destinations=3734+Elvis+Presley+Blvd+Memphis+TN
  • The API key: Credentials for the request, in the form
    &key=YOUR_API_KEY.

Here's the entire request for the single origin and single destination shown above after "Origin addresses" and "Destination addresses."

https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial&origins=3610+Hacks+Cross+Rd+Memphis+TN&destinations=3734+Elvis+Presley+Blvd+Memphis+TN&key=YOUR_API_KEY

Here's the response to the request.

{
   "destination_addresses" : [ "1921 Elvis Presley Blvd, Memphis, TN 38106, USA" ],
   "origin_addresses" : [ "3610 Hacks Cross Rd, Memphis, TN 38125, USA" ],
   "rows" : [
      {
         "elements" : [
            {
               "distance" : {
                  "text" : "15.2 mi",
                  "value" : 24392
               },
               "duration" : {
                  "text" : "21 mins",
                  "value" : 1264
               },
               "status" : "OK"
            }
         ]
      }
   ],
   "status" : "OK"
}

The response contains the travel distance (in miles and meters), and the travel duration (in minutes and seconds), between the two addresses.

See the Distance Matrix API documentation for details about requests and responses.

Compute the distance matrix

To compute the distance matrix, we would like to send a single request containing all 16 addresses as both the origin and destination addresses. However, we can't because this would require 16 x 16 = 256 origin-destination pairs, while the API is restricted to 100 such pairs per request. So we need to make multiple requests.

Since each row of the matrix contains 16 entries, we can compute at most six rows per request (requiring 6 x 16 = 96 pairs). We can compute the whole matrix in three requests, which return 6 rows, 6 rows, and 4 rows.

The following code computes the distance matrix as follows:

  • Divide the 16 addresses into two groups of six addresses and one group of four addresses.
  • For each group, build and send a request for the origin addresses in the group and all destination addresses. See Build and send a request.
  • Use the response to build the corresponding rows of the matrix, and concatenate the rows (which are just Python lists). See Build rows of the distance matrix.
  • def create_distance_matrix(data):
      addresses = data["addresses"]
      API_key = data["API_key"]
      # Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
      max_elements = 100
      num_addresses = len(addresses) # 16 in this example.
      # Maximum number of rows that can be computed per request (6 in this example).
      max_rows = max_elements // num_addresses
      # num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).
      q, r = divmod(num_addresses, max_rows)
      dest_addresses = addresses
      distance_matrix = []
      # Send q requests, returning max_rows rows per request.
      for i in range(q):
        origin_addresses = addresses[i * max_rows: (i + 1) * max_rows]
        response = send_request(origin_addresses, dest_addresses, API_key)
        distance_matrix += build_distance_matrix(response)
    
      # Get the remaining remaining r rows, if necessary.
      if r > 0:
        origin_addresses = addresses[q * max_rows: q * max_rows + r]
        response = send_request(origin_addresses, dest_addresses, API_key)
        distance_matrix += build_distance_matrix(response)
      return distance_matrix

    Build and send a request

    The following function builds and sends a request for a given set of origin and destination addresses.

    def send_request(origin_addresses, dest_addresses, API_key):
      """ Build and send request for the given origin and destination addresses."""
      def build_address_str(addresses):
        # Build a pipe-separated string of addresses
        address_str = ''
        for i in range(len(addresses) - 1):
          address_str += addresses[i] + '|'
        address_str += addresses[-1]
        return address_str
    
      request = 'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial'
      origin_address_str = build_address_str(origin_addresses)
      dest_address_str = build_address_str(dest_addresses)
      request = request + '&origins=' + origin_address_str + '&destinations=' + \
                           dest_address_str + '&key=' + API_key
      jsonResult = urllib.urlopen(request).read()
      response = json.loads(jsonResult)
      return response

    The sub-function build_address_string concatenates addresses separated by the pipe character, '|'.

    The remaining code in the function assembles the parts of the request described above, and sends the request. The line

    response = json.loads(jsonResult)

    converts the raw result to a Python object.

    Build rows of the matrix

    The following function builds rows of the distance matrix, using the response returned by the send_request function.

    def build_distance_matrix(response):
      distance_matrix = []
      for row in response['rows']:
        row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
        distance_matrix.append(row_list)
      return distance_matrix

    The line

    row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]

    extracts the distances between locations for a row of the response. You can compare this with a portion of the response (converted by json.loads) for a single origin and destination, shown below.

    {u'status': u'OK', u'rows':
    [{u'elements': [{u'duration': {u'text': u'21 mins', u'value': 1264},
                     u'distance': {u'text': u'15.2 mi', u'value': 24392},
                     u'status': u'OK'}]}],
                     u'origin_addresses': [u'3610 Hacks Cross Rd, Memphis, TN 38125, USA'],
                     u'destination_addresses': [u'1921 Elvis Presley Blvd, Memphis, TN 38106, USA']}
    

    If you want to create a duration matrix, containing travel times between locations, replace 'distance' with 'duration' in the build_distance_matrix function.

    Run the program

    The following code in the main function runs the program

    def main():
      """Entry point of the program"""
      # Create the data.
      data = create_data()
      addresses = data['addresses']
      API_key = data['API_key']
      distance_matrix = create_distance_matrix(data)
      print(distance_matrix)

    When you run the program, it prints the distance matrix, as shown below.

    [[0, 24392, 33384, 14963, 31992, 32054, 20866, 28427, 15278, 21439, 28765, 34618, 35177, 10612, 26762, 27278],
     [25244, 0, 8314, 10784, 6922, 6984, 10678, 3270, 10707, 7873, 11350, 9548, 10107, 19176, 12139, 13609],
     [34062, 8491, 0, 14086, 4086, 1363, 11008, 4239, 13802, 9627, 7179, 1744, 925, 27994, 9730, 10531],
     [15494, 13289, 13938, 0, 11065, 12608, 4046, 10970, 581, 5226, 10788, 15500, 16059, 5797, 9180, 9450],
     [33351, 7780, 4096, 11348, 0, 2765, 7364, 4464, 11064, 6736, 3619, 4927, 5485, 20823, 6170, 7076],
     [32731, 7160, 1363, 12755, 2755, 0, 9677, 3703, 12471, 8297, 7265, 2279, 2096, 26664, 9816, 9554],
     [19636, 10678, 11017, 4038, 7398, 9687, 0, 9159, 3754, 2809, 7099, 10740, 11253, 8970, 5491, 5928],
     [29097, 3270, 4257, 11458, 4350, 3711, 9159, 0, 11174, 6354, 10160, 5178, 5258, 23029, 10620, 12419],
     [15809, 10707, 13654, 581, 10781, 12324, 3763, 10687, 0, 4943, 10504, 15216, 15775, 5216, 8896, 9166],
     [21831, 7873, 9406, 5226, 6282, 8075, 2809, 6354, 4943, 0, 6967, 10968, 11526, 10159, 5119, 6383],
     [28822, 11931, 6831, 11802, 3305, 6043, 7167, 10627, 11518, 7159, 0, 5361, 6422, 18351, 3267, 4068],
     [35116, 9545, 1771, 15206, 4648, 2518, 10967, 5382, 14922, 10747, 5909, 0, 1342, 29094, 8460, 9260],
     [36058, 10487, 927, 16148, 5590, 2211, 11420, 9183, 15864, 11689, 6734, 1392, 0, 30036, 9285, 10086],
     [11388, 19845, 28838, 5797, 20972, 27507, 8979, 23880, 5216, 10159, 18622, 29331, 29890, 0, 16618, 17135],
     [27151, 11444, 9719, 10131, 6193, 8945, 5913, 10421, 9847, 5374, 3335, 8249, 9309, 16680, 0, 1264],
     [27191, 14469, 10310, 9394, 7093, 9772, 5879, 13164, 9110, 6422, 3933, 8840, 9901, 16720, 1288, 0]]
    

    Using the distance matrix in a VRP program

    To see how to use the distance matrix shown above in a VRP program, replace the distance matrix in the previous VRP example with the one above. Also, change the value of the maximum_distance parameter in the distance dimension to 70000. When you run the modified program, it returns the following output.

    Route for vehicle 0:
     0 -> 1 -> 7 -> 5 -> 4 -> 8 -> 0
    Distance of route: 61001m
    
    Route for vehicle 1:
     0 -> 0
    Distance of route: 0m
    
    Route for vehicle 2:
     0 -> 3 -> 2 -> 12 -> 11 -> 6 -> 0
    Distance of route: 61821m
    
    Route for vehicle 3:
     0 -> 13 -> 9 -> 10 -> 14 -> 15 -> 0
    Distance of route: 59460m
    
    Total distance of all routes: 182282m

    Entire program

    The entire program is shown below.

    from __future__ import division
    from __future__ import print_function
    import requests
    import json
    import urllib
    
    
    def create_data():
      """Creates the data."""
      data = {}
      data['API_key'] = 'YOUR_API_KEY'
      data['addresses'] = ['3610+Hacks+Cross+Rd+Memphis+TN', # depot
                           '1921+Elvis+Presley+Blvd+Memphis+TN',
                           '149+Union+Avenue+Memphis+TN',
                           '1034+Audubon+Drive+Memphis+TN',
                           '1532+Madison+Ave+Memphis+TN',
                           '706+Union+Ave+Memphis+TN',
                           '3641+Central+Ave+Memphis+TN',
                           '926+E+McLemore+Ave+Memphis+TN',
                           '4339+Park+Ave+Memphis+TN',
                           '600+Goodwyn+St+Memphis+TN',
                           '2000+North+Pkwy+Memphis+TN',
                           '262+Danny+Thomas+Pl+Memphis+TN',
                           '125+N+Front+St+Memphis+TN',
                           '5959+Park+Ave+Memphis+TN',
                           '814+Scott+St+Memphis+TN',
                           '1005+Tillman+St+Memphis+TN'
                          ]
      return data
    
    def create_distance_matrix(data):
      addresses = data["addresses"]
      API_key = data["API_key"]
      # Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
      max_elements = 100
      num_addresses = len(addresses) # 16 in this example.
      # Maximum number of rows that can be computed per request (6 in this example).
      max_rows = max_elements // num_addresses
      # num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).
      q, r = divmod(num_addresses, max_rows)
      dest_addresses = addresses
      distance_matrix = []
      # Send q requests, returning max_rows rows per request.
      for i in range(q):
        origin_addresses = addresses[i * max_rows: (i + 1) * max_rows]
        response = send_request(origin_addresses, dest_addresses, API_key)
        distance_matrix += build_distance_matrix(response)
    
      # Get the remaining remaining r rows, if necessary.
      if r > 0:
        origin_addresses = addresses[q * max_rows: q * max_rows + r]
        response = send_request(origin_addresses, dest_addresses, API_key)
        distance_matrix += build_distance_matrix(response)
      return distance_matrix
    
    def send_request(origin_addresses, dest_addresses, API_key):
      """ Build and send request for the given origin and destination addresses."""
      def build_address_str(addresses):
        # Build a pipe-separated string of addresses
        address_str = ''
        for i in range(len(addresses) - 1):
          address_str += addresses[i] + '|'
        address_str += addresses[-1]
        return address_str
    
      request = 'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial'
      origin_address_str = build_address_str(origin_addresses)
      dest_address_str = build_address_str(dest_addresses)
      request = request + '&origins=' + origin_address_str + '&destinations=' + \
                           dest_address_str + '&key=' + API_key
      jsonResult = urllib.urlopen(request).read()
      response = json.loads(jsonResult)
      return response
    
    def build_distance_matrix(response):
      distance_matrix = []
      for row in response['rows']:
        row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
        distance_matrix.append(row_list)
      return distance_matrix
    
    ########
    # Main #
    ########
    def main():
      """Entry point of the program"""
      # Create the data.
      data = create_data()
      addresses = data['addresses']
      API_key = data['API_key']
      distance_matrix = create_distance_matrix(data)
      print(distance_matrix)
    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...