Dans le problème d'itinéraire des véhicules (VRP), l'objectif est de trouver des itinéraires optimaux pour plusieurs véhicules se déplaçant dans un ensemble de lieux. Lorsqu'il n'y a qu'un seul véhicule, cela revient au problème du commercial voyageur.
Mais qu'entendons-nous par "itinéraires optimaux" pour un VRP ? Une réponse est les itinéraires avec la distance totale la plus faible. Toutefois, s'il n'y a pas d'autres contraintes, la solution optimale consiste à n'attribuer qu'un seul véhicule pour visiter tous les sites et de trouver l'itinéraire le plus court pour ce véhicule. C'est essentiellement le même problème que le TSP.
Pour définir des itinéraires optimaux, il est préférable de réduire la longueur de l'itinéraire unique le plus long parmi tous les véhicules. Il s'agit de la définition appropriée si l'objectif est d'effectuer toutes les livraisons dès que possible. L'exemple VRP ci-dessous trouve les itinéraires optimaux définis de cette manière.
Dans les sections suivantes, nous décrirons d'autres façons de généraliser le TSP en ajoutant des contraintes aux véhicules, y compris:
- Contraintes de capacité: les véhicules doivent récupérer des objets à chaque endroit où ils se rendent, mais ont une capacité de charge maximale.
- Time windows (Fenêtres de temps) : chaque lieu doit être visité dans une fenêtre temporelle spécifique.
Exemple VRP
Cette section présente un exemple de VRP dans lequel l'objectif est de minimiser l'itinéraire unique le plus long.
Imaginez une entreprise qui doit rendre visite à ses clients dans une ville composée de blocs rectangulaires identiques. Le schéma de la ville est illustré ci-dessous, avec l'emplacement de l'entreprise en noir et les établissements à visiter en bleu.
Résoudre l'exemple VRP avec les outils OR
Les sections suivantes expliquent comment résoudre l'exemple VRP à l'aide des outils OR.
Créer les données
La fonction suivante crée les données pour le problème.
Python
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["distance_matrix"] = [
# fmt: off
[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],
# fmt: on
]
data["num_vehicles"] = 4
data["depot"] = 0
return data
C++
struct DataModel {
const std::vector<std::vector<int64_t>> 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;
};
Les données sont constituées des éléments suivants:
distance_matrix: tableau des distances entre des points géographiques (indiquées en mètres)num_vehicles: nombre de véhicules dans le parc.depot: index du dépôt, c'est-à-dire l'emplacement où tous les véhicules commencent et terminent leur itinéraire.
Coordonnées du lieu
Pour configurer l'exemple et calculer la matrice des distances, nous avons attribué les coordonnées x-y suivantes aux lieux indiqués dans le diagramme d'une ville:
[(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
Notez que les coordonnées des lieux ne sont pas incluses dans les données du problème: tout ce dont vous avez besoin pour résoudre le problème est la matrice des distances, que nous avons précalculée. Vous n'avez besoin des données de localisation que pour identifier les emplacements dans la solution, indiqués par leurs indices (0, 1, 2, etc.) dans la liste ci-dessus.
Dans cet exemple et d'autres exemples, l'affichage des coordonnées du lieu et du diagramme de ville a pour principal objectif de fournir une représentation visuelle du problème et de sa solution. Mais ce n'est pas essentiel pour résoudre un VRP.
Pour faciliter la configuration du problème, les distances entre les lieux sont calculées à l'aide de la distance de Manhattan, où la distance entre deux points (x1, y1) et (x2, y2) est définie comme étant |x1 - x2| + 1 à | -1. Pour calculer des distances, vous pouvez utiliser la méthode la plus adaptée à votre problème. Vous pouvez également obtenir une matrice des distances pour n'importe quel ensemble de lieux dans le monde à l'aide de l'API Google Distance Matrix. Pour savoir comment procéder, consultez API Distance Matrix.
Définir le rappel de distance
Comme dans l'exemple TSP, la fonction suivante crée le rappel de distance, qui renvoie les distances entre les lieux et le transmet au résolveur. Il définit également les frais de l'arc, qui définissent le coût du déplacement, comme étant les distances des 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](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int 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);
Ajouter une dimension de distance
Pour résoudre ce VRP, vous devez créer une dimension de distance, qui calcule la distance cumulée parcourue par chaque véhicule le long de son itinéraire. Vous pouvez ensuite définir un coût proportionnel au maximum des distances totales de chaque itinéraire. Les programmes de calcul d'itinéraires utilisent des dimensions pour suivre les quantités accumulées sur l'itinéraire d'un véhicule. Pour en savoir plus, consultez la section Dimensions.
Le code suivant crée la dimension de distance à l'aide de la méthode AddDimension du résolveur. L'argument transit_callback_index correspond à l'index de la valeur distance_callback.
Python
dimension_name = "Distance"
routing.AddDimension(
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);
La méthode SetGlobalSpanCostCoefficient définit un coefficient élevé (100) pour le travers global des routes, qui, dans cet exemple, correspond au maximum des distances des routes. Ainsi, le champ global est le facteur prédominant dans la fonction objectif, de sorte que le programme réduit la longueur du plus long itinéraire.
Ajouter l'imprimante de la solution
La fonction qui imprime la solution est illustrée ci-dessous.
Python
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
max_route_distance = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print(f"Maximum of the route distances: {max_route_distance}m")
C++
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
int64_t max_route_distance{0};
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance{0};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{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) {
// Solution cost.
logger.info("Objective : " + solution.objectiveValue());
// 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)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// 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);
}
La fonction affiche les itinéraires des véhicules et les distances totales de ces itinéraires.
Vous pouvez également commencer par enregistrer les routes dans une liste ou un tableau, puis les imprimer.
Fonction principale
La majeure partie du code de la fonction principale du programme VRP est identique à celle de l'exemple du TSP précédent. Consultez la section TSP pour obtenir une description de ce code. La nouveauté, c'est la dimension Distance décrite ci-dessus.
Exécuter les programmes
Les programmes complets sont affichés dans la section suivante. Lorsque vous exécutez les programmes, ils affichent la sortie suivante:
Objective: 177500 Route for vehicle 0: 0 -> 9 -> 10 -> 2 -> 6 -> 5 -> 0 Distance of the route: 1712m Route for vehicle 1: 0 -> 16 -> 14 -> 8 -> 0 Distance of the route: 1484m Route for vehicle 2: 0 -> 7 -> 1 -> 4 -> 3 -> 0 Distance of the route: 1552m Route for vehicle 3: 0 -> 13 -> 15 -> 11 -> 12 -> 0 Distance of the route: 1552m Maximum of the route distances: 1712m
Les points géographiques des itinéraires sont indiqués par leur indice dans la liste des lieux. Toutes les routes commencent et se terminent au dépôt (0).
Le diagramme ci-dessous présente les itinéraires attribués, dans lesquels les index de lieux ont été convertis en coordonnées x-y correspondantes.
Terminer les programmes
La liste complète des programmes permettant de réduire le plus long itinéraire est présentée ci-dessous.
Python
"""Simple Vehicles Routing Problem (VRP).
This is a sample using the routing library python wrapper to solve a VRP
problem.
A description of the problem can be found here:
http://en.wikipedia.org/wiki/Vehicle_routing_problem.
Distances are in meters.
"""
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"] = [
# fmt: off
[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],
# fmt: on
]
data["num_vehicles"] = 4
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
max_route_distance = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print(f"Maximum of the route distances: {max_route_distance}m")
def main():
"""Entry point of the program."""
# 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)
# Add Distance constraint.
dimension_name = "Distance"
routing.AddDimension(
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)
else:
print("No solution found !")
if __name__ == "__main__":
main()
C++
#include <algorithm>
#include <cstdint>
#include <sstream>
#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_t>> 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_t max_route_distance{0};
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance{0};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{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](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int 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);
// Add Distance constraint.
routing.AddDimension(transit_callback_index, 0, 3000,
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.
if (solution != nullptr) {
PrintSolution(data, manager, routing, *solution);
} else {
LOG(INFO) << "No solution found.";
}
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::VrpGlobalSpan();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingDimension;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;
/** Minimal VRP.*/
public class VrpGlobalSpan {
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) {
// Solution cost.
logger.info("Objective : " + solution.objectiveValue());
// 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 {
Loader.loadNativeLibraries();
// 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);
// Add Distance constraint.
routing.addDimension(transitCallbackIndex, 0, 3000,
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;
using Google.OrTools.ConstraintSolver;
/// <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)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// 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);
// Add Distance constraint.
routing.AddDimension(transitCallbackIndex, 0, 3000,
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);
}
}
Utiliser l'API Google Distance Matrix
Cette section explique comment utiliser l'API Google Distance Matrix pour créer la matrice des distances pour tout ensemble de lieux définis par des adresses, ou par des latitudes et des longitudes. Vous pouvez utiliser l'API pour calculer la matrice des distances pour de nombreux types de problèmes d'itinéraire.
Pour utiliser l'API, vous avez besoin d'une clé API. Voici comment en obtenir un.
Exemple
À titre d'exemple, nous allons étudier un programme Python qui crée la matrice des distances pour un ensemble de 16 lieux situés dans la ville de Memphis, dans le Tennessee.
La matrice des distances est une matrice 16 x 16 dont l'entrée i, j correspond à la distance entre les emplacements i et j. Voici les adresses des différents établissements.
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'
]
Requêtes API
Une requête API Distance Matrix est une longue chaîne contenant les éléments suivants:
- Adresse de l'API:
https://maps.googleapis.com/maps/api/distancematrix/json?. La fin de la requête,json, demande la réponse au format JSON. - Options de requête. Dans cet exemple,
units=imperialdéfinit la langue de la réponse sur l'anglais. - Adresses de départ: points de départ du voyage Exemple :
&origins=3610+Hacks+Cross+Rd+Memphis+TN.
Dans l'adresse, les espaces sont remplacés par le caractère+. Si vous saisissez plusieurs adresses, elles sont séparées par un signe|. - Adresses de destination: lieux d'arrivée. Exemple :
&destinations=3734+Elvis+Presley+Blvd+Memphis+TN - Clé API: identifiants de la requête, au format
&key=YOUR_API_KEY.
Voici la requête complète pour le point de départ et la destination uniques indiqués ci-dessus après "Adresses de départ" et "Adresses de destination".
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
Voici la réponse à la demande.
{
"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"
}
La réponse contient la distance de trajet (en miles et en mètres) et la durée du trajet (en minutes et en secondes) entre les deux adresses.
Consultez la documentation de l'API Distance Matrix pour en savoir plus sur les requêtes et les réponses.
Calculer la matrice des distances
Pour calculer la matrice des distances, nous souhaitons envoyer une requête unique contenant les 16 adresses en tant qu'adresses de départ et de destination.
Ce n'est toutefois pas possible, car cela nécessiterait des paires point de départ-destination 16x16=256, alors que l'API est limitée à 100 paires de ce type par requête. Nous devons donc faire plusieurs demandes.
Étant donné que chaque ligne de la matrice contient 16 entrées, nous pouvons calculer au maximum six lignes par requête (nécessite des paires 6x16=96). Nous pouvons calculer la matrice entière en trois
requêtes, qui renvoient 6 lignes, 6 lignes et 4 lignes.
Le code suivant calcule la matrice des distances comme suit:
- Divisez les 16 adresses en deux groupes de six adresses et un groupe de quatre adresses.
- Pour chaque groupe, créez et envoyez une requête pour les adresses de départ du groupe et toutes les adresses de destination. Consultez Créer et envoyer une requête.
- Utilisez la réponse pour créer les lignes correspondantes de la matrice, puis concaténez les lignes (qui ne sont que des listes Python). Consultez Construire des lignes de la matrice des distances.
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
Créer et envoyer une demande
La fonction suivante crée et envoie une requête pour un ensemble donné d'adresses d'origine et de destination.
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
La sous-fonction build_address_string concatène les adresses séparées par une barre verticale |.
Le code restant de la fonction assemble les parties de la requête décrite ci-dessus et envoie la requête. La ligne
response = json.loads(jsonResult)
convertit le résultat brut en objet Python.
Créer des lignes de la matrice
La fonction suivante crée des lignes de la matrice de distances à l'aide de la réponse renvoyée par la fonction send_request.
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
La ligne
row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
extrait les distances entre les lieux pour une ligne de la réponse. Vous pouvez comparer cela à une partie de la réponse (convertie par json.loads) pour un point de départ et une destination, comme indiqué ci-dessous.
{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']}
Si vous souhaitez créer une matrice temporelle contenant les temps de trajet entre des lieux, remplacez 'distance' par 'duration' dans la fonction build_distance_matrix.
Exécuter le programme
Dans la fonction principale, le code suivant exécute le programme
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)
Lorsque vous exécutez le programme, il imprime la matrice des distances, comme illustré ci-dessous.
[[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]]
Matrice des temps de trajet
Comme indiqué ci-dessus, vous souhaitez créer une matrice de temps de trajet entre des lieux (plutôt que des distances). Il vous suffit de remplacer 'distance' par 'duration' dans la fonction build_distance_matrix. Lorsque vous exécutez le programme avec cette modification, il affiche la matrice de temps de trajet suivante:
[[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]]
Utiliser la matrice des distances dans un programme VRP
Pour voir comment utiliser la matrice des distances présentée ci-dessus dans un programme VRP, remplacez la matrice des distances de l'exemple VRP précédent par celui ci-dessus. Remplacez également la valeur du paramètre maximum_distance dans la dimension Distance par 70000. Lorsque vous exécutez le programme modifié, il renvoie le résultat suivant.
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
Programme complet
Le programme complet est présenté ci-dessous.
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()