В задаче выбора маршрута транспортных средств (VRP) цель состоит в том, чтобы найти оптимальные маршруты для нескольких транспортных средств, посещающих набор мест. (Когда имеется только один автомобиль, это сводится к задаче коммивояжера.)
Но что мы подразумеваем под «оптимальными маршрутами» для VRP? Один из ответов — маршруты с наименьшим общим расстоянием. Однако, если нет других ограничений, оптимальным решением будет назначить только одно транспортное средство для посещения всех мест и найти кратчайший маршрут для этого транспортного средства. По сути, это та же проблема, что и TSP.
Лучший способ определить оптимальные маршруты — минимизировать длину самого длинного маршрута среди всех транспортных средств. Это правильное определение, если цель состоит в том, чтобы завершить все поставки как можно скорее. В приведенном ниже примере VRP определяются оптимальные маршруты, определенные таким образом.
В последующих разделах мы опишем другие способы обобщения TSP путем добавления ограничений на транспортные средства, в том числе:
- Ограничения по вместимости : транспортные средства должны забирать предметы в каждом месте, которое они посещают, но имеют максимальную грузоподъемность.
- Временные окна : каждое место необходимо посетить в течение определенного временного окна.
Пример VRP
В этом разделе представлен пример VRP, целью которого является минимизация самого длинного одиночного маршрута.
Представьте себе компанию, которой необходимо посетить своих клиентов в городе, состоящем из одинаковых прямоугольных кварталов. Схема города показана ниже: расположение компании отмечено черным цветом, а места для посещения — синим.
Решение примера VRP с помощью OR-Tools
В следующих разделах объясняется, как решить пример VRP с помощью OR-Tools.
Создайте данные
Следующая функция создает данные для задачи.
Питон
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С++
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};
};Джава
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;
}С#
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;
};Данные состоят из:
-
distance_matrix: Массив расстояний между локациями в метрах. -
num_vehicles: количество автомобилей в парке. -
depot: индекс депо, место, где все транспортные средства начинают и заканчивают свой маршрут.
Координаты местоположения
Чтобы настроить пример и вычислить матрицу расстояний, мы присвоили следующие координаты x - y местам, показанным на диаграмме города :
[(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
Обратите внимание, что координаты местоположения не включены в данные задачи: все, что вам нужно для решения задачи, — это матрица расстояний, которую мы предварительно вычислили. Вам нужны только данные о местоположении, чтобы идентифицировать местоположения в решении, которые обозначены их индексами (0, 1, 2...) в приведенном выше списке.
Основная цель показа координат местоположения и схемы города в этом и других примерах — обеспечить наглядное отображение проблемы и ее решения. Но это не существенно для решения ВРП.
Для удобства постановки задачи расстояния между местоположениями рассчитываются с использованием Манхэттенского расстояния , в котором расстояние между двумя точками ( x 1 , y 1 ) и ( x 2 , y 2 ) определяется как | х 1 - х 2 | + | у 1 - у 2 |. Однако особых оснований для использования этого определения нет. Для расчета расстояний вы можете использовать любой метод, который лучше всего подходит для вашей задачи. Или вы можете получить матрицу расстояний для любого набора мест в мире, используя API матрицы расстояний Google. См. API-интерфейс Distance Matrix для примера того, как это сделать.
Определить дистанционный обратный вызов
Как и в примере TSP , следующая функция создает обратный вызов расстояния, который возвращает расстояния между местоположениями, и передает их решателю. Он также устанавливает стоимость дуги, которая определяет стоимость перемещения, как расстояние между дугами.
Питон
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)С++
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);Джава
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);С#
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);Добавить размер расстояния
Чтобы решить эту задачу VRP, вам необходимо создать измерение расстояния, которое вычисляет совокупное расстояние, пройденное каждым транспортным средством по его маршруту. Затем вы можете установить стоимость, пропорциональную максимальному общему расстоянию по каждому маршруту. Программы маршрутизации используют измерения для отслеживания количеств, которые накапливаются на маршруте транспортного средства. См. «Размеры» для получения более подробной информации.
Следующий код создает измерение расстояния с помощью метода AddDimension решателя. transit_callback_index является индексом distance_callback .
Питон
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)С++
routing.AddDimension(transit_callback_index, 0, 3000,
true, // start cumul to zero
"Distance");
routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100);Джава
routing.addDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);С#
routing.AddDimension(transitCallbackIndex, 0, 3000,
true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
distanceDimension.SetGlobalSpanCostCoefficient(100); Метод SetGlobalSpanCostCoefficient устанавливает большой коэффициент ( 100 ) для глобального диапазона маршрутов, который в этом примере является максимальным из расстояний маршрутов. Это делает глобальный интервал преобладающим фактором в целевой функции, поэтому программа минимизирует длину самого длинного маршрута.
Добавьте принтер решения
Функция, которая печатает решение, показана ниже.
Питон
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")
С++
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";
}Джава
/// @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");
}С#
/// <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);
}Функция отображает маршруты движения транспортных средств и общие расстояния маршрутов.
Альтернативно, вы можете сначала сохранить маршруты в список или массив, а затем распечатать их.
Основная функция
Большая часть кода основной функции программы VRP такая же, как и в предыдущем примере TSP. См. раздел TSP для описания этого кода. Новым является измерение расстояния , описанное выше.
Запуск программ
Полные программы показаны в следующем разделе . Когда вы запускаете программы, они отображают следующий вывод:
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
Локации в маршрутах обозначаются их индексами в списке локаций . Все маршруты начинаются и заканчиваются в депо ( 0 ).
На диаграмме ниже показаны назначенные маршруты, в которых индексы местоположения были преобразованы в соответствующие координаты x - y .
Полные программы
Ниже показаны полные программы, минимизирующие самый длинный одиночный маршрут.
Питон
"""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()С++
#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;
}Джава
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);
}
}С#
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);
}
}Использование Google Distance Matrix API
В этом разделе показано, как использовать API матрицы расстояний Google для создания матрицы расстояний для любого набора местоположений, определяемых адресами или широтой и долготой. Вы можете использовать API для расчета матрицы расстояний для многих типов задач маршрутизации.
Чтобы использовать API, вам понадобится ключ API. Вот как его получить .
Пример
В качестве примера мы рассмотрим программу Python, которая создает матрицу расстояний для набора из 16 местоположений в городе Мемфис, штат Теннесси. Матрица расстояний представляет собой матрицу размером 16 x 16, чьи элементы i , j — это расстояние между местоположениями i и j . Вот адреса локаций.
data['addresses'] = ['3610+Hacks+Cross+Rd+Memphis+TN', # depot
'1921+Elvis+Presley+Blvd+Memphis+TN',
'149+Union+Avenue+Memphis+TN',
'1034+Audubon+Drive+Memphis+TN',
'1532+Madison+Ave+Memphis+TN',
'706+Union+Ave+Memphis+TN',
'3641+Central+Ave+Memphis+TN',
'926+E+McLemore+Ave+Memphis+TN',
'4339+Park+Ave+Memphis+TN',
'600+Goodwyn+St+Memphis+TN',
'2000+North+Pkwy+Memphis+TN',
'262+Danny+Thomas+Pl+Memphis+TN',
'125+N+Front+St+Memphis+TN',
'5959+Park+Ave+Memphis+TN',
'814+Scott+St+Memphis+TN',
'1005+Tillman+St+Memphis+TN'
]API-запросы
Запрос Distance Matrix API представляет собой длинную строку, содержащую следующее:
- Адрес API:
https://maps.googleapis.com/maps/api/distancematrix/json?. Конец запроса,json, запрашивает ответ в формате JSON. - Варианты запроса. В этом примере
units=imperialустанавливает английский язык ответа. - Адреса отправления: отправные точки путешествия. Например
&origins=3610+Hacks+Cross+Rd+Memphis+TN.
Пробелы в адресе заменяются знаком+. Несколько адресов разделяются|. - Адреса назначения: Конечные пункты путешествия. Например
&destinations=3734+Elvis+Presley+Blvd+Memphis+TN - Ключ API: учетные данные для запроса в форме
&key=YOUR_API_KEY.
Вот полный запрос для одного источника и одного пункта назначения, показанный выше после «Адреса источника» и «Адреса назначения».
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
Вот ответ на запрос.
{
"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"
}
Ответ содержит расстояние поездки (в милях и метрах) и продолжительность поездки (в минутах и секундах) между двумя адресами.
Подробную информацию о запросах и ответах см. в документации по API Distance Matrix .
Вычислить матрицу расстояний
Чтобы вычислить матрицу расстояний, мы хотели бы отправить один запрос, содержащий все 16 адресов как адреса отправления и назначения. Однако мы не можем этого сделать, потому что для этого потребуется 16x16=256 пар источник-назначение, а API ограничен 100 такими парами на запрос. Поэтому нам нужно сделать несколько запросов.
Поскольку каждая строка матрицы содержит 16 записей, мы можем вычислить не более шести строк за запрос (требуется 6x16=96 пар). Мы можем вычислить всю матрицу за три запроса, которые возвращают 6 строк, 6 строк и 4 строки.
Следующий код вычисляет матрицу расстояний следующим образом:
- Разделите 16 адресов на две группы по шесть адресов и одну группу из четырех адресов.
- Для каждой группы создайте и отправьте запрос на адреса происхождения в группе и все адреса назначения. См. раздел Сборка и отправка запроса .
- Используйте ответ, чтобы построить соответствующие строки матрицы и объединить строки (которые представляют собой просто списки Python). См. Построение строк матрицы расстояний .
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 Подфункция build_address_string объединяет адреса, разделенные символом вертикальной черты | .
Оставшийся код функции собирает части запроса, описанного выше, и отправляет запрос. Линия
response = json.loads(jsonResult)
преобразует необработанный результат в объект Python.
Построить строки матрицы
Следующая функция строит строки матрицы расстояний, используя ответ, возвращаемый функцией 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Линия
row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
извлекает расстояния между местоположениями для строки ответа. Вы можете сравнить это с частью ответа (преобразованной с помощью json.loads ) для одного источника и пункта назначения, как показано ниже.
{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']}
Если вы хотите создать матрицу времени, содержащую время в пути между местоположениями, замените 'distance' на 'duration' в функции build_distance_matrix .
Запустите программу
Следующий код в основной функции запускает программу
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)
Когда вы запускаете программу, она печатает матрицу расстояний, как показано ниже.
[[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]]
Матрица времени в пути
Как упоминалось выше , если вы хотите создать матрицу времени в пути между местоположениями (вместо расстояний), просто замените 'distance' на 'duration' в функции build_distance_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]]
Использование матрицы расстояний в программе VRP
Чтобы увидеть, как использовать матрицу расстояний, показанную выше, в программе VRP, замените матрицу расстояний из предыдущего примера VRP на приведенную выше. Также измените значение параметра maximum_distance в измерении расстояния на 70000 . Когда вы запускаете измененную программу, она возвращает следующий вывод.
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
Вся программа
Вся программа показана ниже.
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()