Wymiary

Narzędzie do wyznaczania tras wykorzystuje obiekt o nazwie wymiar, aby śledzić ilości, które gromadzą się na trasie pojazdu, takie jak czas podróży, lub, jeśli pojazd przyjmuje i dostarcza, całkowitą wagę. Jeśli problem z routingiem obejmuje taką ilość (w ramach ograniczeń lub funkcji celu), musisz zdefiniować wymiar, aby je podać.

Z tej sekcji dowiesz się, jak definiować i wykorzystywać wymiary.

Przykłady wymiarów

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

  • Przykład VRPTW tworzy wymiar, który pozwala śledzić łączny czas podróży każdego pojazdu. Narzędzie do rozwiązywania problemów używa wymiaru, aby egzekwować ograniczenie, dzięki któremu pojazd może odwiedzić lokalizację tylko w oknie czasowym lokalizacji.

  • Przykład platformy CVRP tworzy wymiar dla żądań (np. waga lub ilość przesyłek do pobrania), który śledzi łączne ładowanie ciężarówek na trasie. Rozwiązanie korzysta z tego wymiaru, aby wymuszać ograniczenie, które powoduje, że obciążenie pojazdu nie może przekroczyć jego pojemności.

Poniższe przykłady definiują wymiar VRPTW, korzystając z metody 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 następujące dane wejściowe:

  • callback_index: indeks wywołania zwrotnego, które zwraca liczbę. Indeks, który jest wewnętrznym odniesieniem do wywołania zwrotnego, jest tworzony za pomocą takich metod jak RegisterTransitCallback czy RegisterUnitaryTransitCallback.
  • slack_max: maksymalna wartość slack, która odpowiada czasom oczekiwania w lokalizacjach. Szczegółowe informacje znajdziesz poniżej w sekcji Zmienne SSL. Jeśli problem nie wiąże się z czasem oczekiwania, zwykle możesz ustawić slack_max na 0.
  • capacity: maksymalna łączna ilość nagromadzona na każdej trasie. Za pomocą capacity możesz tworzyć ograniczenia podobne do tych w CVRP. Jeśli Twój problem nie ma takiego ograniczenia, możesz ustawić na tyle dużą wartość capacity, by nie nakładać żadnych ograniczeń na trasy. Może to być na przykład suma wszystkich elementów macierzy lub tablicy użytej do zdefiniowania wywołania zwrotnego.
  • fix_start_cumulative_to_zero: wartość logiczna. Jeśli wartość to prawda, łączna wartość ilościowa zaczyna się od 0. W większości przypadków należy go ustawić na True. W przypadku VRPTW lub problemów z ograniczeniami zasobów niektóre pojazdy mogą jednak być uruchamiane po czasie 0 z powodu ograniczeń czasowych, więc w przypadku tych problemów należy ustawić fix_start_cumulative_to_zero na False.
  • dimension_name: ciąg nazwy wymiaru, np. 'Distance', za pomocą którego możesz uzyskać dostęp do zmiennych w innym miejscu programu.

Program CVRP tworzy nieco inny typ wymiaru za pomocą metody AddDimensionWithVehicleCapacity. Ta metoda wykorzystuje szereg pojemności, po jednym wpisie na każdy pojazd. Natomiast dla porównania AddDimension przyjmuje jedną wartość dla capacity, dlatego wszystkie pojazdy są uznawane za takie same.

Informacje o innych metodach tworzenia wymiarów znajdziesz na stronie referencyjnej RoutingModel.

Sekcja Zapisywanie okresów czasu rozwiązania na liście lub w tablicy zawiera funkcje, które zapisują skumulowane dane w wymiarze na liście lub w tablicy.

Zmienne Slacka

Oto przykład, który ilustruje zmienne związane ze słodkim problemem z czasem podróży. Załóżmy, że pojazd znajduje się w jednym kroku od lokalizacji i do lokalizacji j oraz że:

  • Łączny czas podróży pojazdu wynosi i 100 minut.
  • Łączny czas podróży pojazdu wynosi 200 minut.
  • Czas podróży od i do 75 minut.

Pojazd nie może opuścić lokalizacji i od razu po przyjeździe lub jego łączny czas w miejscu j wynosi 175. Zamiast tego pojazd musi odczekać 25 minut w miejscu i, zanim wyruszy, czyli w miejscu, w którym został 25 minut.

Musisz zezwolić na ślizgnięcie się w rzeczywistości wirtualnej VRPT, ponieważ pojazd może być czekany przed wizytą w danym miejscu ze względu na ograniczenia czasowe. W przypadku tego typu problemu ustaw slack_max w maksymalnym czasie, przez jaki pojazd ma czekać w danej lokalizacji, zanim będzie można przejść do następnej. Jeśli nie ma ważnego czasu oczekiwania, ustaw slack_max na bardzo dużą liczbę.

Z drugiej strony, w przypadku platformy CVRP zmiana skumulowanego obciążenia z i na j zawsze równa się popytowi w i, dzięki czemu nie ma błędów. W przypadku problemów takich jak to można ustawić slack_max na 0.

Następnie należy podać formalną definicję słowa Slack. Wymiar przechowuje wewnętrznie 2 typy zmiennych związanych z ilościami, które gromadzą się na trasie:

  • Zmienne transportu publicznego: wzrost lub spadek ilości na każdym etapie trasy. Jeśli jednym z kroków na trasie jest i -> j, zmienna transportu publicznego to wpis w tabeli i, j (w przypadku wywołania zwrotnego 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 skumulowana ilość w każdej lokalizacji. Skumulowaną zmienną możesz otworzyć w lokalizacji i do dimension_name.CumulVar(i). Przykład znajdziesz w sekcji Ograniczenia czasowe w przykładzie VRPTW.

Zakładamy, że pojazd może w jednym kroku przejść z lokalizacji i do lokalizacji j, a Spad jest powiązany z tymi zmiennymi:

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

Więcej informacji o wymiarach znajdziesz w sekcji z informacjami w sekcji RoutingDimension.