Wymiary

Rozwiązanie wyznaczania tras używa obiektu o nazwie wymiar, by śledzić ilości kumulowane na trasie pojazdu, takie jak czas podróży lub całkowita waga, jeśli pojazd dokonuje odbioru i dostawy; , Jeśli problem z trasą dotyczy takiej liczby, w ograniczeniach lub funkcji celu, musisz zdefiniować wymiar, by je określić.

Z tej sekcji dowiesz się, jak definiować i używać wymiarów.

Przykłady wymiarów

Oto kilka przykładów wymiarów z poprzednich sekcji.

  • Przykład VRPTW pozwala utworzyć wymiar do śledzenia. łączny czas podróży dla każdego pojazdu. Rozwiązanie używa wymiaru do egzekwowania ograniczenie, dzięki któremu pojazd może odwiedzać wyłącznie lokalizacje znajdujące się w okresu.

  • Przykład CVRP pozwala utworzyć wymiar dla: żądania (np. waga lub objętość przesyłek do odbioru), która śledzi łączne obciążenie pojazdu. Rozwiązanie używa wymiaru, aby egzekwować ograniczenie obciążenia pojazdu nie może przekroczyć jego pojemności.

Poniższe przykłady określają wymiar VRPTW za pomocą parametru AddDimension .

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

Metoda AddDimension zawiera te dane wejściowe:

  • callback_index: indeks wywołania zwrotnego, które zwraca ilość. indeks, który jest wewnętrznym odniesieniem rozwiązania do wywołania zwrotnego, jest tworzony przez takimi jak RegisterTransitCallback lub RegisterUnitaryTransitCallback.
  • slack_max: wartość maksymalna dla slack, zmiennej reprezentującej czas oczekiwania w różnych lokalizacjach. Zobacz zmienne Slacka poniżej. . Jeśli problem nie wiąże się z czasem oczekiwania, zazwyczaj możesz ustawić slack_max do 0.
  • capacity: maksymalna łączna ilość zgromadzonych na każdej trasie. Za pomocą capacity możesz tworzyć ograniczenia, takie jak te w CVRP. Jeśli Twój problem nie ma takiego możesz ustawić capacity na wartość wystarczająco dużą, nie nakładać żadnych ograniczeń na trasy – na przykład sumy wszystkich wpisy macierzy lub tablicy używane do zdefiniowania wywołania zwrotnego.
  • fix_start_cumulative_to_zero: wartość logiczna. Jeśli ma wartość prawda, skumulowana wartość liczby zaczyna się od 0. W większości przypadków należy ustawić wartość True. Jednak w przypadku VRPTW lub problemów z ograniczenia dotyczące zasobów, niektóre pojazdy może się rozpocząć po czasie 0 ze względu na ograniczenia czasowe, dlatego ustaw fix_start_cumulative_to_zero na False w przypadku tych problemów.
  • dimension_name: ciąg znaków nazwy wymiaru, np. 'Distance', który pozwala uzyskać dostęp do tych zmiennych w innym miejscu w programie.

Program CVRP tworzy nieco inny typ wymiaru za pomocą funkcji AddDimensionWithVehicleCapacity . Ta metoda wykorzystuje tablice pojemności, z 1 wjazdem dla każdego pojazdu. (W przeciwieństwie do tego funkcja AddDimension przyjmuje jedną wartość dla parametru capacity, więc wszystkie przyjmuje się, że mają taką samą pojemność).

Zobacz RoutingModel strony referencyjnej, gdzie znajdziesz inne metody tworzenia wymiarów.

Sekcja Zapisywanie przedziałów czasowych rozwiązania w formie listy lub tablicy przedstawia funkcje zapisujące skumulowane dane w wymiarze na liście lub w tablicy.

Zmienne Slack

Oto przykład ilustrujący zmienne slack dla zadania z czas podróży. Załóżmy, że pojazd jedziesz z lokalizacji i do lokalizacji j na jednym z etapów trasy, oraz że:

  • Łączny czas podróży pojazdu w miejscu i wynosi 100 minut.
  • Łączny czas podróży pojazdu w miejscu J to 200 minut.
  • Podróż z i do J wynosi 75 minut.

Pojazd nie może opuścić lokalizacji od razu po dotarciu do celu lub jego łączne czas w lokalizacji j będzie 175. Pojazd musi czekać 25 minut na lokalizacja i przed odjazdem; Innymi słowy, zapas w miejscu i to 25.

Musisz zezwolić na zaległości w VRPTW, ponieważ pojazdy mogą czekać przed w danej lokalizacji ze względu na ograniczenia czasowe. W takim zadaniu ustaw slack_max do maksymalnej dozwolonej długości czasu oczekiwania pojazdów lokalizację przed przejściem do następnej. Jeśli nie ma znaczenia, jak długo ustaw slack_max na bardzo dużą liczbę.

W przypadku CVRP zmiana skumulowanego obciążenia z i na j zawsze jest równy popytowi w wysokości i, więc nie ma spadków. Gdy występują problemy takie jak w tym przypadku ustaw wartość slack_max na 0.

Następnie podamy formalną definicję „slajdu”. Wymiar przechowuje wewnętrznie dane dwóch typów zmiennych powiązanych z ilościami, które kumulują się na trasach:

  • Zmienne transportu publicznego: wzrost lub spadek ilości na każdym etapie trasę. Jeśli parametr i -> j to jeden krok trasy, zmienna transportu publicznego to i, wpis j tablicy tranzytowej (w przypadku wywołania zwrotnego dla transportu publicznego) lub po prostu wartość wywołania zwrotnego w lokalizacji i (jeśli wywołanie zwrotne zależy tylko od jednej lokalizacji).
  • Zmienne skumulowane: łączna ilość danych w każdej lokalizacji. Ty może uzyskać dostęp do zmiennej skumulowanej w lokalizacji i przez dimension_name.CumulVar(i) Na przykład zobacz ograniczenia przedziałów czasowych w przykładzie VRPTW.

Zakładając, że pojazd przechodzi w jednym kroku z lokalizacji i do j, jest powiązany z tymi zmiennymi w następujący sposób: 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Więcej informacji o wymiarach: RoutingDimension .