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 jakRegisterTransitCallback
czyRegisterUnitaryTransitCallback
.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ć naTrue
. 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
naFalse
.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 tabelii
,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
.