Wiele problemów z wyznaczaniem tras przez pojazdy wiąże się z planowaniem wizyt klientów, którzy są dostępni tylko w określonych przedziałach czasowych.
Takie problemy są nazywane problemami z wyznaczaniem tras pojazdów w przedziałach czasowych (VRPTW).
Przykład VRPTW
Na tej stronie zapoznamy się z przykładem rozwiązania problemu VRPTW. Problem obejmuje przedziały czasu, dlatego dane obejmują macierz czasu, która zawiera czasy podróży między lokalizacjami (a nie macierz odległości jak w poprzednich przykładach).
Na diagramie poniżej widać lokalizacje, które warto odwiedzić, na niebiesko i czarną budowę. Przedziały czasu są wyświetlane nad każdą lokalizacją. Więcej informacji o definiowaniu lokalizacji znajdziesz w sekcji Współrzędne lokalizacji w sekcji VRP.
Celem jest zminimalizowanie całkowitego czasu podróży pojazdami.
Rozwiązanie przykładu VRPTW za pomocą OR-Tools
W tych sekcjach opisaliśmy, jak rozwiązać przykład VRPTW za pomocą narzędzi LUB.
Tworzenie danych
Poniższa funkcja tworzy dane problemu.
Python
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["time_matrix"] = [
[0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
[6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
[9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
[8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
[7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
[3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
[6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
[2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
[3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
[2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
[6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
[6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
[4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
[4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
[5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
[9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
[7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
]
data["time_windows"] = [
(0, 5), # depot
(7, 12), # 1
(10, 15), # 2
(16, 18), # 3
(10, 13), # 4
(0, 5), # 5
(5, 10), # 6
(0, 4), # 7
(5, 10), # 8
(0, 3), # 9
(10, 16), # 10
(10, 15), # 11
(0, 5), # 12
(5, 10), # 13
(7, 8), # 14
(10, 15), # 15
(11, 15), # 16
]
data["num_vehicles"] = 4
data["depot"] = 0
return data
Te dane składają się z:
-
data['time_matrix']: tablica czasów podróży między lokalizacjami. Zwróć uwagę, że różni się to od poprzednich przykładów, w których zastosowano macierz odległości. Jeśli wszystkie pojazdy poruszają się z tą samą prędkością, otrzymasz to samo rozwiązanie, jeśli zastosujesz macierz odległości lub macierz czasu, ponieważ odległość jest stałą wielokrotnością czasu podróży. -
data['time_windows']: tablica przedziałów czasu dla lokalizacji, którą możesz sobie wyobrazić jako żądane godziny wizyty. Pojazdy muszą odwiedzić daną lokalizację w wyznaczonym czasie. -
data['num_vehicles']: liczba pojazdów we flocie. -
data['depot']: indeks magazynu.
C++
struct DataModel {
const std::vector<std::vector<int64_t>> time_matrix{
{0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
{6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
{9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
{8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
{7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
{3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
{6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
{2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
{3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
{2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
{6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
{6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
{4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
{4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
{5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
{9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
{7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
};
const std::vector<std::pair<int64_t, int64_t>> time_windows{
{0, 5}, // depot
{7, 12}, // 1
{10, 15}, // 2
{16, 18}, // 3
{10, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 4}, // 7
{5, 10}, // 8
{0, 3}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 8}, // 14
{10, 15}, // 15
{11, 15}, // 16
};
const int num_vehicles = 4;
const RoutingIndexManager::NodeIndex depot{0};
};
Te dane składają się z:
-
time_matrix: tablica czasów podróży między lokalizacjami. Zwróć uwagę, że różni się to od poprzednich przykładów, w których zastosowano macierz odległości. Jeśli wszystkie pojazdy poruszają się z tą samą prędkością, otrzymasz to samo rozwiązanie, jeśli zastosujesz macierz odległości lub macierz czasu, ponieważ odległość jest stałą wielokrotnością czasu podróży. -
time_windows: tablica przedziałów czasu dla lokalizacji, którą możesz sobie wyobrazić jako żądane godziny wizyty. Pojazdy muszą odwiedzić daną lokalizację w wyznaczonym czasie. -
num_vehicles: liczba pojazdów we flocie. -
depot: indeks magazynu.
Java
static class DataModel {
public final long[][] timeMatrix = {
{0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
{6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
{9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
{8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
{7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
{3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
{6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
{2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
{3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
{2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
{6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
{6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
{4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
{4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
{5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
{9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
{7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
};
public final long[][] timeWindows = {
{0, 5}, // depot
{7, 12}, // 1
{10, 15}, // 2
{16, 18}, // 3
{10, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 4}, // 7
{5, 10}, // 8
{0, 3}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 8}, // 14
{10, 15}, // 15
{11, 15}, // 16
};
public final int vehicleNumber = 4;
public final int depot = 0;
}
Te dane składają się z:
-
timeMatrix: tablica czasów podróży między lokalizacjami. Zwróć uwagę, że różni się to od poprzednich przykładów, w których zastosowano macierz odległości. Jeśli wszystkie pojazdy poruszają się z tą samą prędkością, otrzymasz to samo rozwiązanie, jeśli zastosujesz macierz odległości lub macierz czasu, ponieważ odległość jest stałą wielokrotnością czasu podróży. -
timeWindows: tablica przedziałów czasu dla lokalizacji, którą możesz sobie wyobrazić jako żądane godziny wizyty. Pojazdy muszą odwiedzić daną lokalizację w wyznaczonym czasie. -
vehicleNumber: liczba pojazdów we flocie. -
depot: indeks magazynu.
C#
class DataModel
{
public long[,] TimeMatrix = {
{ 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 },
{ 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 },
{ 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 },
{ 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 },
{ 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 },
{ 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 },
{ 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 },
{ 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 },
{ 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 },
{ 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 },
{ 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 },
{ 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 },
{ 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 },
{ 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 },
{ 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 },
{ 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 },
{ 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 },
};
public long[,] TimeWindows = {
{ 0, 5 }, // depot
{ 7, 12 }, // 1
{ 10, 15 }, // 2
{ 16, 18 }, // 3
{ 10, 13 }, // 4
{ 0, 5 }, // 5
{ 5, 10 }, // 6
{ 0, 4 }, // 7
{ 5, 10 }, // 8
{ 0, 3 }, // 9
{ 10, 16 }, // 10
{ 10, 15 }, // 11
{ 0, 5 }, // 12
{ 5, 10 }, // 13
{ 7, 8 }, // 14
{ 10, 15 }, // 15
{ 11, 15 }, // 16
};
public int VehicleNumber = 4;
public int Depot = 0;
};
Te dane składają się z:
-
TimeMatrix: tablica czasów podróży między lokalizacjami. Zwróć uwagę, że różni się to od poprzednich przykładów, w których zastosowano macierz odległości. Jeśli wszystkie pojazdy poruszają się z tą samą prędkością, otrzymasz to samo rozwiązanie, jeśli zastosujesz macierz odległości lub macierz czasu, ponieważ odległość jest stałą wielokrotnością czasu podróży. -
TimeWindows: tablica przedziałów czasu dla lokalizacji, którą możesz sobie wyobrazić jako żądane godziny wizyty. Pojazdy muszą odwiedzić daną lokalizację w wyznaczonym czasie. -
VehicleNumber: liczba pojazdów we flocie. -
Depot: indeks magazynu.
Godzina oddzwonienia
Poniższa funkcja tworzy wywołanie zwrotne czasu i przekazuje je do rozwiązania. Ustala też koszty podróży, które określają koszt podróży, jako czasy podróży między lokalizacjami.
Python
def time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_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 time matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return data.time_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.timeMatrix[fromNode][toNode];
});
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
C#
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to time
// matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.TimeMatrix[fromNode, toNode];
});
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
Dodaj ograniczenia przedziału czasu
Poniższy kod dodaje ograniczenia przedziałów czasu do wszystkich lokalizacji.
Python
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # allow waiting time
30, # maximum time per vehicle
False, # Don't force start cumul to zero.
time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
)
for i in range(data["num_vehicles"]):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i))
)
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
C++
const std::string time = "Time";
routing.AddDimension(transit_callback_index, // transit callback index
int64_t{30}, // allow waiting time
int64_t{30}, // maximum time per vehicle
false, // Don't force start cumul to zero
time);
const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);
// Add time window constraints for each location except depot.
for (int i = 1; i < data.time_windows.size(); ++i) {
const int64_t index =
manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
data.time_windows[i].second);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.num_vehicles; ++i) {
const int64_t index = routing.Start(i);
time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
data.time_windows[0].second);
}
for (int i = 0; i < data.num_vehicles; ++i) {
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)));
}
Java
routing.addDimension(transitCallbackIndex, // transit callback
30, // allow waiting time
30, // vehicle maximum capacities
false, // start cumul to zero
"Time");
RoutingDimension timeDimension = routing.getMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.timeWindows.length; ++i) {
long index = manager.nodeToIndex(i);
timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
}
for (int i = 0; i < data.vehicleNumber; ++i) {
routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
}
C#
routing.AddDimension(transitCallbackIndex, // transit callback
30, // allow waiting time
30, // vehicle maximum capacities
false, // start cumul to zero
"Time");
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
{
long index = manager.NodeToIndex(i);
timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.VehicleNumber; ++i)
{
long index = routing.Start(i);
timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);
}
for (int i = 0; i < data.VehicleNumber; ++i)
{
routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
}
Kod tworzy wymiar dotyczący czasu przejazdu pojazdów, podobny do wymiarów odległości i wymagań dotyczących podróży z poprzednich przykładów. Wymiary śledzą ilości gromadzone na trasie pojazdu. W powyższym kodzie time_dimension.CumulVar(index) to łączny czas podróży, w którym pojazd dotarł do lokalizacji o określonej wartości index.
Wymiar jest tworzony za pomocą metody AddDimension, która ma następujące argumenty:
- Indeks wywołania zwrotnego w czasie podróży:
transit_callback_index - Górna granica czasu oczekiwania (czasy oczekiwania w wybranych lokalizacjach):
30. Chociaż w przykładzie CVRP ta wartość była ustawiona na 0, VRPTW musi zezwolić na dodatni czas oczekiwania ze względu na ograniczenia przedziału czasu. - Górna granica łącznego czasu na trasie każdego pojazdu:
30 - Zmienna logiczna, która określa, czy na początku trasy każdego pojazdu zmienna skumulowana jest ustawiona na 0.
- Nazwa wymiaru.
Następne linie to
Python
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
C++
for (int i = 1; i < data.time_windows.size(); ++i) {
const int64_t index =
manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
data.time_windows[i].second);
}
Java
for (int i = 1; i < data.timeWindows.length; ++i) {
long index = manager.nodeToIndex(i);
timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
}
C#
for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
{
long index = manager.NodeToIndex(i);
timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
}
będzie wymagać, aby pojazd dotarł do lokalizacji w określonym przedziale czasu.
Ustawianie parametrów wyszukiwania
Ten kod ustawia domyślne parametry wyszukiwania i heurystyczną metodę znajdowania pierwszego rozwiązania:
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
Java
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
C#
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
Dodawanie drukarki rozwiązania
Funkcja, która wyświetla rozwiązanie, jest przedstawiona poniżej.
Python
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
time_dimension = routing.GetDimensionOrDie("Time")
total_time = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
" -> "
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
)
plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
print(plan_output)
total_time += solution.Min(time_var)
print(f"Total time of all routes: {total_time}min")
C++
//! @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) {
const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
int64_t total_time{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 << ":";
std::ostringstream route;
while (!routing.IsEnd(index)) {
auto time_var = time_dimension.CumulVar(index);
route << manager.IndexToNode(index).value() << " Time("
<< solution.Min(time_var) << ", " << solution.Max(time_var)
<< ") -> ";
index = solution.Value(routing.NextVar(index));
}
auto time_var = time_dimension.CumulVar(index);
LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
<< solution.Min(time_var) << ", " << solution.Max(time_var)
<< ")";
LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";
total_time += solution.Min(time_var);
}
LOG(INFO) << "Total time of all routes: " << total_time << "min";
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
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.
RoutingDimension timeDimension = routing.getMutableDimension("Time");
long totalTime = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
String route = "";
while (!routing.isEnd(index)) {
IntVar timeVar = timeDimension.cumulVar(index);
route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
+ solution.max(timeVar) + ") -> ";
index = solution.value(routing.nextVar(index));
}
IntVar timeVar = timeDimension.cumulVar(index);
route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
+ solution.max(timeVar) + ")";
logger.info(route);
logger.info("Time of the route: " + solution.min(timeVar) + "min");
totalTime += solution.min(timeVar);
}
logger.info("Total time of all routes: " + totalTime + "min");
}
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.
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
long totalTime = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
var timeVar = timeDimension.CumulVar(index);
Console.Write("{0} Time({1},{2}) -> ", manager.IndexToNode(index), solution.Min(timeVar),
solution.Max(timeVar));
index = solution.Value(routing.NextVar(index));
}
var endTimeVar = timeDimension.CumulVar(index);
Console.WriteLine("{0} Time({1},{2})", manager.IndexToNode(index), solution.Min(endTimeVar),
solution.Max(endTimeVar));
Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
totalTime += solution.Min(endTimeVar);
}
Console.WriteLine("Total time of all routes: {0}min", totalTime);
}
rozwiązanie wyświetla trasy pojazdów i okno rozwiązania w każdym miejscu, zgodnie z opisem w następnej sekcji.
Okna rozwiązań
Okno rozwiązania w danej lokalizacji to przedział czasu, w którym musi przyjechać pojazd, aby zachował on zgodność z harmonogramem.Okno rozwiązania zawiera się w danym miejscu w danym miejscu i zwykle jest mniejsze od przedziału czasu ograniczenia.
W powyższej funkcji drukarki rozwiązania okno rozwiązania jest zwracane przez (assignment.Min(time_var), assignment.Max(time_var), gdzie time_var = time_dimension.CumulVar(index) to łączny czas podróży pojazdu w danej lokalizacji.
Jeśli minimalne i maksymalne wartości time_var są takie same, okno rozwiązania wskazuje jeden punkt w czasie, co oznacza, że pojazd musi wyruszyć z lokalizacji zaraz po dotarciu na miejsce. Jeśli minimalna wartość jest mniejsza niż maksymalna, pojazd może zaczekać przed odjazdem.
W sekcji Uruchamianie programu opisano okna rozwiązań w tym przykładzie.
Oferowanie rozwiązań
Główna funkcja w tym przykładzie jest podobna do funkcji w przykładzie dostawcy usługi tokenów.
Python
solution = routing.SolveWithParameters(search_parameters)
C++
const Assignment* solution = routing.SolveWithParameters(searchParameters);
Java
Assignment solution = routing.solveWithParameters(searchParameters);
C#
Assignment solution = routing.SolveWithParameters(searchParameters);
Uruchamianie programu
Po uruchomieniu programu wyświetli się te dane wyjściowe:
Route for vehicle 0: 0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8) -> 16 Time(11,11) -> 0 Time(18,18) Time of the route: 18min Route for vehicle 1: 0 Time(0,0) -> 7 Time(2,4) -> 1 Time(7,11) -> 4 Time(10,13) -> 3 Time(16,16) -> 0 Time(24,24) Time of the route: 24min Route for vehicle 2: 0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 3: 0 Time(0,0) -> 5 Time(3,3) -> 8 Time(5,5) -> 6 Time(7,7) -> 2 Time(10,10) -> 10 Time(14,14) -> 0 Time(20,20) Time of the route: 20min Total time of all routes: 82min
W przypadku każdej lokalizacji na trasie Time(a,b) to okno rozwiązania: pojazd, który odwiedza daną lokalizację, musi zrobić to w tym przedziale czasu, aby zachować zgodność z harmonogramem.
Spójrzmy na przykład na poniższy fragment trasy dla pojazdu 0.
0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8)
W lokalizacji 9 okno rozwiązania wynosi Time(2,3), co oznacza, że pojazd musi tam dotrzeć w godzinach 2–3. Okno rozwiązania znajduje się w przedziale czasu ograniczenia w tej lokalizacji ((0, 3)) określonej w danych problemu. Okno rozwiązania rozpoczyna się w czasie 2, ponieważ dotarcie ze stacji do lokalizacji 9 zajmuje 2 jednostki czasu (wpis 0 i 9 w macierzu czasu).
Dlaczego pojazd może odjechać o 9 w dowolnym momencie między 2 a 3? Wynika to z tego, że czas podróży z lokalizacji 9 do 14 wynosi 3, więc jeśli pojazd wyjedzie w dowolnym momencie przed 3, to przyjedzie do miejsca 14 przed godziną 6, czyli za wcześnie na wizytę. W związku z tym pojazd musi gdzieś czekać, np. kierowca może poczekać w miejscu 9 do momentu 3, nie opóźniając końca trasy.
Jak widzisz, niektóre okna rozwiązań (np. w lokalizacjach 9 i 14) mają różne czasy rozpoczęcia i zakończenia, ale inne (np. na trasach 2 i 3) mają ten sam czas rozpoczęcia i zakończenia. W pierwszym przypadku pojazdy mogą odjechać do końca okna, a w drugim – jak najszybciej po dotarciu na miejsce.
Zapisz okna rozwiązań w postaci listy lub tablicy
Sekcja dostawcy usługi tokenów pokazuje, jak zapisywać trasy w rozwiązaniu w postaci listy lub tablicy. W przypadku VRPTW możesz też zapisać okna rozwiązań. Poniższe funkcje zapisują okna rozwiązań w postaci listy (Python) lub tablicy (C++).
Python
def get_cumul_data(solution, routing, dimension):
"""Get cumulative data from a dimension and store it in an array."""
# Returns an array cumul_data whose i,j entry contains the minimum and
# maximum of CumulVar for the dimension at the jth node on route :
# - cumul_data[i][j][0] is the minimum.
# - cumul_data[i][j][1] is the maximum.
cumul_data = []
for route_nbr in range(routing.vehicles()):
route_data = []
index = routing.Start(route_nbr)
dim_var = dimension.CumulVar(index)
route_data.append([solution.Min(dim_var), solution.Max(dim_var)])
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
dim_var = dimension.CumulVar(index)
route_data.append([solution.Min(dim_var), solution.Max(dim_var)])
cumul_data.append(route_data)
return cumul_data
C++
std::vector<std::vector<std::pair<int64_t, int64_t>>> GetCumulData(
const Assignment& solution, const RoutingModel& routing,
const RoutingDimension& dimension) {
// Returns an array cumul_data, whose i, j entry is a pair containing
// the minimum and maximum of CumulVar for the dimension.:
// - cumul_data[i][j].first is the minimum.
// - cumul_data[i][j].second is the maximum.
std::vector<std::vector<std::pair<int64_t, int64_t>>> cumul_data(
routing.vehicles());
for (int vehicle_id = 0; vehicle_id < routing.vehicles(); ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
IntVar* dim_var = dimension.CumulVar(index);
cumul_data[vehicle_id].emplace_back(solution.Min(dim_var),
solution.Max(dim_var));
while (!routing.IsEnd(index)) {
index = solution.Value(routing.NextVar(index));
IntVar* dim_var = dimension.CumulVar(index);
cumul_data[vehicle_id].emplace_back(solution.Min(dim_var),
solution.Max(dim_var));
}
}
return cumul_data;
}
Te funkcje zapisują minimalne i maksymalne wartości danych skumulowanych w przypadku dowolnego wymiaru (a nie tylko czasu).
W bieżącym przykładzie te wartości stanowią dolną i górną granicę okna rozwiązania, a wymiar przekazany do funkcji to time_dimension.
Poniższe funkcje wyświetlają rozwiązanie z tras i danych skumulowanych.
Python
def print_solution(routes, cumul_data):
"""Print the solution."""
total_time = 0
route_str = ""
for i, route in enumerate(routes):
route_str += "Route " + str(i) + ":\n"
start_time = cumul_data[i][0][0]
end_time = cumul_data[i][0][1]
route_str += (
" "
+ str(route[0])
+ " Time("
+ str(start_time)
+ ", "
+ str(end_time)
+ ")"
)
for j in range(1, len(route)):
start_time = cumul_data[i][j][0]
end_time = cumul_data[i][j][1]
route_str += (
" -> "
+ str(route[j])
+ " Time("
+ str(start_time)
+ ", "
+ str(end_time)
+ ")"
)
route_str += f"\n Route time: {start_time}min\n\n"
total_time += cumul_data[i][len(route) - 1][0]
route_str += f"Total time: {total_time}min"
print(route_str)
C++
void PrintSolution(
const std::vector<std::vector<int>> routes,
std::vector<std::vector<std::pair<int64_t, int64_t>>> cumul_data) {
int64_t total_time{0};
std::ostringstream route;
for (int vehicle_id = 0; vehicle_id < routes.size(); ++vehicle_id) {
route << "\nRoute " << vehicle_id << ": \n";
route << " " << routes[vehicle_id][0] << " Time("
<< cumul_data[vehicle_id][0].first << ", "
<< cumul_data[vehicle_id][0].second << ") ";
for (int j = 1; j < routes[vehicle_id].size(); ++j) {
route << "-> " << routes[vehicle_id][j] << " Time("
<< cumul_data[vehicle_id][j].first << ", "
<< cumul_data[vehicle_id][j].second << ") ";
}
route << "\n Route time: "
<< cumul_data[vehicle_id][routes[vehicle_id].size() - 1].first
<< " minutes\n";
total_time += cumul_data[vehicle_id][routes[vehicle_id].size() - 1].first;
}
route << "\nTotal travel time: " << total_time << " minutes";
LOG(INFO) << route.str();
}
Ukończ programy
Poniżej znajdziesz pełne programy rozwiązania problemu z wyznaczaniem tras pojazdów z przedziałami czasu.
Python
"""Vehicles Routing Problem (VRP) with Time Windows."""
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["time_matrix"] = [
[0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
[6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
[9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
[8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
[7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
[3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
[6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
[2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
[3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
[2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
[6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
[6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
[4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
[4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
[5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
[9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
[7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
]
data["time_windows"] = [
(0, 5), # depot
(7, 12), # 1
(10, 15), # 2
(16, 18), # 3
(10, 13), # 4
(0, 5), # 5
(5, 10), # 6
(0, 4), # 7
(5, 10), # 8
(0, 3), # 9
(10, 16), # 10
(10, 15), # 11
(0, 5), # 12
(5, 10), # 13
(7, 8), # 14
(10, 15), # 15
(11, 15), # 16
]
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()}")
time_dimension = routing.GetDimensionOrDie("Time")
total_time = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
" -> "
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
)
plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
print(plan_output)
total_time += solution.Min(time_var)
print(f"Total time of all routes: {total_time}min")
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["time_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # allow waiting time
30, # maximum time per vehicle
False, # Don't force start cumul to zero.
time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
)
# Instantiate route start and end times to produce feasible times.
for i in range(data["num_vehicles"]):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i))
)
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
if __name__ == "__main__":
main()
C++
#include <cstdint>
#include <sstream>
#include <string>
#include <utility>
#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>> time_matrix{
{0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
{6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
{9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
{8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
{7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
{3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
{6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
{2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
{3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
{2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
{6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
{6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
{4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
{4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
{5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
{9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
{7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
};
const std::vector<std::pair<int64_t, int64_t>> time_windows{
{0, 5}, // depot
{7, 12}, // 1
{10, 15}, // 2
{16, 18}, // 3
{10, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 4}, // 7
{5, 10}, // 8
{0, 3}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 8}, // 14
{10, 15}, // 15
{11, 15}, // 16
};
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) {
const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
int64_t total_time{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 << ":";
std::ostringstream route;
while (!routing.IsEnd(index)) {
auto time_var = time_dimension.CumulVar(index);
route << manager.IndexToNode(index).value() << " Time("
<< solution.Min(time_var) << ", " << solution.Max(time_var)
<< ") -> ";
index = solution.Value(routing.NextVar(index));
}
auto time_var = time_dimension.CumulVar(index);
LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
<< solution.Min(time_var) << ", " << solution.Max(time_var)
<< ")";
LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";
total_time += solution.Min(time_var);
}
LOG(INFO) << "Total time of all routes: " << total_time << "min";
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
void VrpTimeWindows() {
// Instantiate the data problem.
DataModel data;
// Create Routing Index Manager
RoutingIndexManager manager(data.time_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 time matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return data.time_matrix[from_node][to_node];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
// Add Time constraint.
const std::string time = "Time";
routing.AddDimension(transit_callback_index, // transit callback index
int64_t{30}, // allow waiting time
int64_t{30}, // maximum time per vehicle
false, // Don't force start cumul to zero
time);
const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);
// Add time window constraints for each location except depot.
for (int i = 1; i < data.time_windows.size(); ++i) {
const int64_t index =
manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
data.time_windows[i].second);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.num_vehicles; ++i) {
const int64_t index = routing.Start(i);
time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
data.time_windows[0].second);
}
// Instantiate route start and end times to produce feasible times.
for (int i = 0; i < data.num_vehicles; ++i) {
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)));
}
// Setting first solution heuristic.
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(data, manager, routing, *solution);
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::VrpTimeWindows();
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.IntVar;
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;
/** VRPTW. */
public class VrpTimeWindows {
private static final Logger logger = Logger.getLogger(VrpTimeWindows.class.getName());
static class DataModel {
public final long[][] timeMatrix = {
{0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
{6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
{9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
{8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
{7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
{3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
{6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
{2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
{3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
{2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
{6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
{6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
{4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
{4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
{5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
{9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
{7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
};
public final long[][] timeWindows = {
{0, 5}, // depot
{7, 12}, // 1
{10, 15}, // 2
{16, 18}, // 3
{10, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 4}, // 7
{5, 10}, // 8
{0, 3}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 8}, // 14
{10, 15}, // 15
{11, 15}, // 16
};
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.
RoutingDimension timeDimension = routing.getMutableDimension("Time");
long totalTime = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
String route = "";
while (!routing.isEnd(index)) {
IntVar timeVar = timeDimension.cumulVar(index);
route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
+ solution.max(timeVar) + ") -> ";
index = solution.value(routing.nextVar(index));
}
IntVar timeVar = timeDimension.cumulVar(index);
route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
+ solution.max(timeVar) + ")";
logger.info(route);
logger.info("Time of the route: " + solution.min(timeVar) + "min");
totalTime += solution.min(timeVar);
}
logger.info("Total time of all routes: " + totalTime + "min");
}
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.timeMatrix.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.timeMatrix[fromNode][toNode];
});
// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Add Time constraint.
routing.addDimension(transitCallbackIndex, // transit callback
30, // allow waiting time
30, // vehicle maximum capacities
false, // start cumul to zero
"Time");
RoutingDimension timeDimension = routing.getMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.timeWindows.length; ++i) {
long index = manager.nodeToIndex(i);
timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
}
// Instantiate route start and end times to produce feasible times.
for (int i = 0; i < data.vehicleNumber; ++i) {
routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
}
// 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);
}
}
// [END_program_part1]
C#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// Vehicles Routing Problem (VRP) with Time Windows.
/// </summary>
public class VrpTimeWindows
{
class DataModel
{
public long[,] TimeMatrix = {
{ 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 },
{ 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 },
{ 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 },
{ 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 },
{ 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 },
{ 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 },
{ 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 },
{ 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 },
{ 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 },
{ 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 },
{ 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 },
{ 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 },
{ 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 },
{ 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 },
{ 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 },
{ 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 },
{ 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 },
};
public long[,] TimeWindows = {
{ 0, 5 }, // depot
{ 7, 12 }, // 1
{ 10, 15 }, // 2
{ 16, 18 }, // 3
{ 10, 13 }, // 4
{ 0, 5 }, // 5
{ 5, 10 }, // 6
{ 0, 4 }, // 7
{ 5, 10 }, // 8
{ 0, 3 }, // 9
{ 10, 16 }, // 10
{ 10, 15 }, // 11
{ 0, 5 }, // 12
{ 5, 10 }, // 13
{ 7, 8 }, // 14
{ 10, 15 }, // 15
{ 11, 15 }, // 16
};
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.
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
long totalTime = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
var timeVar = timeDimension.CumulVar(index);
Console.Write("{0} Time({1},{2}) -> ", manager.IndexToNode(index), solution.Min(timeVar),
solution.Max(timeVar));
index = solution.Value(routing.NextVar(index));
}
var endTimeVar = timeDimension.CumulVar(index);
Console.WriteLine("{0} Time({1},{2})", manager.IndexToNode(index), solution.Min(endTimeVar),
solution.Max(endTimeVar));
Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
totalTime += solution.Min(endTimeVar);
}
Console.WriteLine("Total time of all routes: {0}min", totalTime);
}
public static void Main(String[] args)
{
// Instantiate the data problem.
DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.TimeMatrix.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 time
// matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.TimeMatrix[fromNode, toNode];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Add Time constraint.
routing.AddDimension(transitCallbackIndex, // transit callback
30, // allow waiting time
30, // vehicle maximum capacities
false, // start cumul to zero
"Time");
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
{
long index = manager.NodeToIndex(i);
timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.VehicleNumber; ++i)
{
long index = routing.Start(i);
timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);
}
// Instantiate route start and end times to produce feasible times.
for (int i = 0; i < data.VehicleNumber; ++i)
{
routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
}
// 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);
}
}