Problem z wyznaczaniem trasy przez pojazd z przedziałami czasu

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,&nbsp;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);
    }
}