# Vehicle Routing Problem

## Overview

In the Vehicle Routing Problem (VRP), the goal is to find optimal routes for multiple vehicles visiting a set of locations. (When there's only one vehicle, it reduces to the Traveling Salesman Problem.)

But what do we mean by "optimal routes" for a VRP? One answer is the routes with the least total distance. However, if there are no other constraints, the optimal solution is to assign just one vehicle to visit all locations, and find the shortest route for that vehicle. This is essentially the same problem as the TSP.

A better way to define optimal routes is to minimize the length of the longest single route among all vehicles. This is the right definition if the goal is to complete all deliveries as soon as possible. The VRP example below finds optimal routes defined this way.

In later sections, we'll describe other ways of generalizing the TSP by adding constraints on the vehicles, including:

• Capacity constraints: the vehicles need to pick up items at each location they visit, but have a maximum carrying capacity.
• Time windows: each location must be visited within a specific time window.

## VRP example

This section presents an example of a VRP in which the goal is to minimize the longest single route.

Imagine a company that needs to visit its customers 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.

## Solving the VRP example with OR-Tools

The following sections explain how to solve the VRP example with OR-Tools.

### Create the data

The following function creates the data for the problem.

### Python

```def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[
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['num_vehicles'] = 4
data['depot'] = 0
return data```

### C++

```struct DataModel {
const std::vector<std::vector<int64>> distance_matrix{
{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},
};
const int num_vehicles = 4;
const RoutingIndexManager::NodeIndex depot{0};
};```

### Java

```static class DataModel {
public final long[][] distanceMatrix = {
{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},
};
public final int vehicleNumber = 4;
public final int depot = 0;
}```

### C#

```class DataModel {
public long[,] DistanceMatrix = {
{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}
};
public int VehicleNumber = 4;
public int Depot = 0;
};```

The data consists of:

• `distance_matrix`: An array of distances between locations on meters.
• `num_locations`: The number of locations.
• `num_vehicles`: The number of vehicles in the fleet.
• `depot`: The index of the depot, the location where all vehicles start and end their routes.

### Location coordinates

To set up the example and compute the distance matrix, we have assigned the following x-y coordinates to the locations shown in the city diagram:

```[(456, 320), # location 0 - the depot
(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```

Note that the location coordinates are not included in the problem data: all you need to solve the problem is the distance matrix, which we have pre-computed. You only need the location data to identify the locations in the solution, which are denoted by their indices (0, 1, 2 ...) in the above list.

The main purpose of showing the location coordinates and the city diagram in this and other examples is to provide a visual display of the problem and its solution. But this is not essential for solving a VRP.

For convenience in setting up the problem, the distances between locations 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. Or, you can obtain a distance matrix for any set of locations in the world using the Google Distance Matrix API. See Distance Matrix API for an example of how to do this.

### Define the distance callback

As in the TSP example, the following function creates the distance callback, which returns the distances between locations, and passes it to the solver. It also sets the arc costs, which define the cost of travel, to be the distances of the arcs.

### Python

```def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)```

### C++

```const int transit_callback_index = routing.RegisterTransitCallback(
[&data, &manager](int64 from_index, int64 to_index) -> int64 {
// Convert from routing variable Index to distance matrix NodeIndex.
auto from_node = manager.IndexToNode(from_index).value();
auto to_node = manager.IndexToNode(to_index).value();
return data.distance_matrix[from_node][to_node];
});
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);```

### Java

```final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);```

### C#

```int transitCallbackIndex = routing.RegisterTransitCallback(
(long fromIndex, long toIndex) => {
// Convert from routing variable Index to distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.DistanceMatrix[fromNode, toNode]; }
);
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);```

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 proportional to the maximum of the total distances along each route. Routing programs use dimensions to keep track of quantities that accumulate over a vehicle's route. See Dimensions for more details.

The following code creates the distance dimension, using the solver's `AddDimension` method. The argument `transit_callback_index` is the index for the distance_callback.

### Python

```dimension_name = 'Distance'
transit_callback_index,
0,  # no slack
3000,  # vehicle maximum travel distance
True,  # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)```

### C++

```routing.AddDimension(transit_callback_index, 0, 3000,
true,  // start cumul to zero
"Distance");
routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100);```

### Java

```routing.addDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);```

### C#

```routing.AddDimension(transitCallbackIndex, 0, 3000,
true,  // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
distanceDimension.SetGlobalSpanCostCoefficient(100);```

The method `SetGlobalSpanCostCoefficient` sets a large coefficient (`100`) for the global span of the routes, which in this example is the maximum of the distances of the routes. This makes the global span the predominant factor in the objective function, so the program minimizes the length of the longest route.

The function that prints the solution is shown below.

### Python

```def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
max_route_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_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print('Maximum of the route distances: {}m'.format(max_route_distance))

```

### C++

```void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
int64 max_route_distance{0};
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64 index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64 route_distance{0};
std::stringstream route;
while (routing.IsEnd(index) == false) {
route << manager.IndexToNode(index).value() << " -> ";
int64 previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
max_route_distance = std::max(route_distance, max_route_distance);
}
LOG(INFO) << "Maximum of the route distances: " << max_route_distance << "m";
LOG(INFO) << "";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}```

### Java

```/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Inspect solution.
long maxRouteDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
logger.info(route + manager.indexToNode(index));
logger.info("Distance of the route: " + routeDistance + "m");
maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
}
logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
}```

### C#

```/// <summary>
///   Print the solution.
/// </summary>
static void PrintSolution(
in DataModel data,
in RoutingModel routing,
in RoutingIndexManager manager,
in Assignment solution) {
// Inspect solution.
long maxRouteDistance = 0;
for (int i = 0; i < data.VehicleNumber; ++i) {
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false) {
Console.Write("{0} -> ", manager.IndexToNode((int)index));
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
maxRouteDistance = Math.Max(routeDistance, maxRouteDistance);
}
Console.WriteLine("Maximum distance of the routes: {0}m", maxRouteDistance);
}```

The function displays the routes for the vehicles and the total distances of the routes.

Alternatively, you can first save the routes to a list or array, and then print them.

### Main function

Most of the code in the main function for the VRP program is the same as in the previous TSP example. See the TSP section for a description of that code. What's new is the distance dimension, described above.

### Running the programs

The complete programs are shown in the next section. When you run the programs, they display 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 locations in the routes are denoted by their indices in the locations list. All routes begin and end at the depot (`0`).

The diagram below shows the assigned routes, in which the location indices have been converted to the corresponding x-y coordinates.

### Complete programs

The complete programs that minimizes the longest single route are shown below.

### Python

```"""Vehicles Routing Problem (VRP)."""

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

def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[
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['num_vehicles'] = 4
data['depot'] = 0
return data

def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
max_route_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_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print('Maximum of the route distances: {}m'.format(max_route_distance))

def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

dimension_name = 'Distance'
transit_callback_index,
0,  # no slack
3000,  # vehicle maximum travel distance
True,  # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)

if __name__ == '__main__':
main()```

### C++

```#include <vector>

#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"

namespace operations_research {
struct DataModel {
const std::vector<std::vector<int64>> distance_matrix{
{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},
};
const int num_vehicles = 4;
const RoutingIndexManager::NodeIndex depot{0};
};

//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
int64 max_route_distance{0};
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64 index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64 route_distance{0};
std::stringstream route;
while (routing.IsEnd(index) == false) {
route << manager.IndexToNode(index).value() << " -> ";
int64 previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
max_route_distance = std::max(route_distance, max_route_distance);
}
LOG(INFO) << "Maximum of the route distances: " << max_route_distance << "m";
LOG(INFO) << "";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

void VrpGlobalSpan() {
// Instantiate the data problem.
DataModel data;

// Create Routing Index Manager
RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
data.depot);

// Create Routing Model.
RoutingModel routing(manager);

// Create and register a transit callback.
const int transit_callback_index = routing.RegisterTransitCallback(
[&data, &manager](int64 from_index, int64 to_index) -> int64 {
// Convert from routing variable Index to distance matrix NodeIndex.
auto from_node = manager.IndexToNode(from_index).value();
auto to_node = manager.IndexToNode(to_index).value();
return data.distance_matrix[from_node][to_node];
});

// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

true,  // start cumul to zero
"Distance");
routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100);

// Setting first solution heuristic.
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);

// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(searchParameters);

// Print solution on console.
PrintSolution(data, manager, routing, *solution);
}
}  // namespace operations_research

int main(int argc, char** argv) {
operations_research::VrpGlobalSpan();
return EXIT_SUCCESS;
}```

### Java

```package com.google.ortools.constraintsolver.samples;
import java.util.logging.Logger;

/** Minimal VRP.*/
public class VrpGlobalSpan {
static {
}

private static final Logger logger = Logger.getLogger(VrpGlobalSpan.class.getName());

static class DataModel {
public final long[][] distanceMatrix = {
{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},
};
public final int vehicleNumber = 4;
public final int depot = 0;
}

/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Inspect solution.
long maxRouteDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
logger.info(route + manager.indexToNode(index));
logger.info("Distance of the route: " + routeDistance + "m");
maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
}
logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
}

public static void main(String[] args) throws Exception {
// Instantiate the data problem.
final DataModel data = new DataModel();

// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);

// Create and register a transit callback.
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});

// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);

// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();

// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);

// Print solution on console.
printSolution(data, routing, manager, solution);
}
}```

### C#

```using System;
using System.Collections.Generic;

/// <summary>
///   Minimal TSP using distance matrix.
/// </summary>
public class VrpGlobalSpan {
class DataModel {
public long[,] DistanceMatrix = {
{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}
};
public int VehicleNumber = 4;
public int Depot = 0;
};

/// <summary>
///   Print the solution.
/// </summary>
static void PrintSolution(
in DataModel data,
in RoutingModel routing,
in RoutingIndexManager manager,
in Assignment solution) {
// Inspect solution.
long maxRouteDistance = 0;
for (int i = 0; i < data.VehicleNumber; ++i) {
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false) {
Console.Write("{0} -> ", manager.IndexToNode((int)index));
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
maxRouteDistance = Math.Max(routeDistance, maxRouteDistance);
}
Console.WriteLine("Maximum distance of the routes: {0}m", maxRouteDistance);
}

public static void Main(String[] args) {
// Instantiate the data problem.
DataModel data = new DataModel();

// Create Routing Index Manager
RoutingIndexManager manager = new RoutingIndexManager(
data.DistanceMatrix.GetLength(0),
data.VehicleNumber,
data.Depot);

// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);

// Create and register a transit callback.
int transitCallbackIndex = routing.RegisterTransitCallback(
(long fromIndex, long toIndex) => {
// Convert from routing variable Index to distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.DistanceMatrix[fromNode, toNode]; }
);

// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

true,  // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
distanceDimension.SetGlobalSpanCostCoefficient(100);

// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy =
FirstSolutionStrategy.Types.Value.PathCheapestArc;

// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);

// Print solution on console.
PrintSolution(data, routing, manager, solution);
}
}```

## 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',
'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):
API_key = data["API_key"]
# Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
max_elements = 100
# Maximum number of rows that can be computed per request (6 in this example).
# num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).
distance_matrix = []
# Send q requests, returning max_rows rows per request.
for i in range(q):
distance_matrix += build_distance_matrix(response)

# Get the remaining remaining r rows, if necessary.
if r > 0:
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."""
# Build a pipe-separated string of addresses
for i in range(len(addresses) - 1):

request = request + '&origins=' + origin_address_str + '&destinations=' + \
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 time matrix, containing travel times between locations, replace `'distance'` with `'duration'` in the function `build_distance_matrix`.

### 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()
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]]
```

### Travel time matrix

As mentioned above, it you want to create a matrix of travel times between locations (instead of distances), simply replace `'distance'` with `'duration'` in the function `build_distance_matrix`. When you run the program with that change, it displays the following travel time matrix:

```[[0, 1232, 1599, 964, 1488, 1441, 1291, 1323, 978, 1228, 1493, 1617, 1570, 765, 1272, 1359],
[1333, 0, 653, 922, 542, 495, 864, 297, 917, 622, 783, 671, 624, 1059, 985, 904],
[1669, 643, 0, 1291, 447, 161, 1021, 461, 1258, 862, 715, 419, 198, 1395, 855, 904],
[1062, 862, 1262, 0, 946, 1104, 360, 926, 61, 482, 995, 1237, 1190, 589, 761, 839],
[1626, 600, 475, 1008, 0, 317, 688, 505, 976, 630, 446, 475, 428, 1271, 587, 648],
[1537, 511, 166, 1158, 314, 0, 889, 402, 1125, 730, 697, 430, 313, 1262, 837, 770],
[1388, 891, 1022, 374, 668, 863, 0, 731, 341, 259, 731, 1110, 1091, 869, 496, 570],
[1407, 303, 489, 934, 492, 410, 725, 0, 901, 482, 692, 580, 587, 1132, 845, 814],
[1060, 914, 1215, 55, 899, 1057, 314, 880, 0, 435, 949, 1190, 1144, 528, 714, 792],
[1314, 651, 855, 475, 605, 696, 260, 491, 443, 0, 700, 830, 783, 970, 489, 596],
[1530, 801, 697, 990, 427, 625, 709, 721, 957, 663, 0, 542, 634, 1084, 338, 387],
[1704, 678, 370, 1355, 508, 430, 1074, 598, 1322, 866, 564, 0, 297, 1405, 703, 752],
[1612, 586, 215, 1201, 416, 359, 1070, 506, 1169, 773, 639, 313, 0, 1312, 778, 827],
[861, 1074, 1441, 610, 1337, 1282, 869, 1164, 555, 990, 1157, 1433, 1386, 0, 936, 1022],
[1375, 1045, 899, 795, 629, 825, 588, 901, 762, 549, 408, 744, 836, 929, 0, 107],
[1428, 947, 957, 885, 692, 750, 599, 867, 852, 637, 362, 803, 894, 982, 111, 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'
'1921+Elvis+Presley+Blvd+Memphis+TN',
'149+Union+Avenue+Memphis+TN',
'1034+Audubon+Drive+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):
API_key = data["API_key"]
# Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
max_elements = 100
# Maximum number of rows that can be computed per request (6 in this example).
# num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).
distance_matrix = []
# Send q requests, returning max_rows rows per request.
for i in range(q):
distance_matrix += build_distance_matrix(response)

# Get the remaining remaining r rows, if necessary.
if r > 0:
distance_matrix += build_distance_matrix(response)
return distance_matrix

""" Build and send request for the given origin and destination addresses."""
# Build a pipe-separated string of addresses
for i in range(len(addresses) - 1):

request = request + '&origins=' + origin_address_str + '&destinations=' + \
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()