Opcje routingu

W tej sekcji opisano niektóre opcje rozwiązania problemów z routingiem.

Limity wyszukiwania

Limity wyszukiwania kończą działanie po osiągnięciu określonego limitu, takiego jak maksymalny czas trwania lub liczba znalezionych rozwiązań. Limit wyszukiwania możesz ustawić za pomocą parametrów wyszukiwania do rozwiązania. Przykład znajdziesz w sekcji Limity czasu.

W poniższej tabeli opisano najczęstsze limity wyszukiwania.

Nazwa	Typ	Domyślna	Opis
solution_limit	int64	kint64max,	Ogranicz liczbę rozwiązań wygenerowanych podczas wyszukiwania.
time_limit.seconds	int64	kint64max,	Ogranicz czas w wyszukiwania do sekund:
lns_time_limit.seconds	int64	100	Ogranicz czas w sekundach do czasu: przekończenia wyszukiwania w przypadku każdego sąsiada.

Pierwsza strategia rozwiązania

Pierwsza strategia rozwiązania to metoda, której używa rozstrzygnięcie, aby znaleźć początkowe rozwiązanie. W tabeli poniżej znajdziesz opcje dotyczące narzędzia first_solution_strategy.

Option	Opis
AUTOMATIC	Umożliwia on znalezienie strategii, którą należy zastosować w przypadku danego modelu.
PATH_CHEAPEST_ARC	Zaczynając od węzła „start” na trasie, połącz go z węzłem, który powoduje utworzenie najtańszego segmentu trasy, a następnie rozszerz trasę, powtarzając ostatni węzeł dodany do trasy.
PATH_MOST_CONSTRAINED_ARC	Podobnie jak w przypadku typu PATH_CHEAPEST_ARC, ale łuki są oceniane za pomocą selektora opartego na porównaniu, który będzie preferować najbardziej ograniczony łuk najpierw. Aby przypisać selektor do modelu routingu, użyj metody ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Podobnie jak w przypadku funkcji PATH_CHEAPEST_ARC, ale koszty łuku są oceniane za pomocą funkcji przekazanej do SetFirstSolutionEvaluator().
SAVINGS	Algorytm oszczędzania (Clarke i Wright). Odwołanie: Clarke, G. i Wright, J.W. „Scheduling Vehicles from Central Central Depot to a Delivery Points”, Operations Operations, str. 12, 1964, s. 568-581.
SWEEP	Algorytm przesuwania (Wren i Holliday). Więcej informacji: Anthony Wren i Alan Holliday, komputerowe określanie harmonogramu pojazdów z jednej lub kilku stowarzyszeń do liczby obsługiwanych punktów dostawy (kwartał 1970–1977), nr 3, nr 3 (wrzesień, 1972), str. 333–344).
CHRISTOFIDES	algorytm Christofides (w rzeczywistości jest to odmiana algorytmu Christofides określana za pomocą dopasowania maksymalnego, a nie maksymalnego dopasowania, co nie gwarantuje 3/2 przybliżenia dla danego metrycznego sprzedawcy). Działa w przypadku ogólnych modeli routingu pojazdów przez poszerzenie trasy do momentu, aż nie będzie można w niej umieścić węzłów. Patrz: Nicos Christofides, najgorsza analiza nowego heurystyki dla podróżnych sprzedawców, raport 388, Graduate School of Industrial Admin, CMU, 1976 r.
ALL_UNPERFORMED	Dezaktywuj wszystkie węzły. Znajduje rozwiązanie tylko wtedy, gdy węzły są opcjonalne (jest to element ograniczenia połączenia z ostatecznym kosztem kary).
BEST_INSERTION	Rusztowo utwórz rozwiązanie, wstawiając najtańszy węzeł na najniższą pozycję. Koszt wstawiania jest oparty na globalnej funkcji kosztu modelu routingu. Od 2022 r. działa tylko w modelach z opcjonalnymi węzłami (z kosztami skończonej kary).
PARALLEL_CHEAPEST_INSERTION	Rutynowo utwórz rozwiązanie, wstawiając najtańszy węzeł na najniższą pozycję. Koszt wstawienia jest oparty na funkcji kosztów arc. Jest szybsze niż BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Rusztowo utwórz rozwiązanie, wstawiając każdy węzeł w najtańszą pozycję. Koszt wstawiania jest oparty na funkcji kosztów arcus . Różni się od węzła PARALLEL_CHEAPEST_INSERTION wybranego do wstawienia. Węzły są brane pod uwagę w kolejności utworzenia. Jest szybsze niż PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Powtarzaj połączenie 2 węzłów, które zapewniają najtańszy segment trasy.
LOCAL_CHEAPEST_ARC	Wybierz pierwszy węzeł z niezastąpionym następcą i połącz go z węzłem, który tworzy najtańszy segment trasy.
FIRST_UNBOUND_MIN_VALUE	Wybierz pierwszy węzeł z niezastąpionym następcą i połącz go z pierwszym dostępnym węzłem. To odpowiednik strategii CHOOSE_FIRST_UNBOUND połączonej z zasadą ASSIGN_MIN_VALUE (por. constraint_solver.h).

Stan wyszukiwania

Możesz zwrócić stan wyszukiwania za pomocą metody status modelu routingu. Oto kod Pythona do wydrukowania stanu wyszukiwania:

print("Solver status: ", solver.status())

Spowoduje to wydrukowanie liczby całkowitej w tym znaczeniu:

Wartość	Opis
0	ROUTING_NOT_SOLVED: nie udało się jeszcze rozwiązać problemu.
1	ROUTING_SUCCESS: udało się rozwiązać problem.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: po wywołaniu funkcji RoutingModel.Solve() problem został rozwiązany, ale lokalna optymalizacja nie została osiągnięta. Pozostawienie większej ilości czasu umożliwiłoby lepsze rozwiązanie.
3	ROUTING_FAIL: nie znaleziono rozwiązania problemu.
4	ROUTING_FAIL_TIMEOUT: osiągnięto limit czasu przed znalezieniem rozwiązania.
5	ROUTING_INVALID: model, parametry modelu lub flagi są nieprawidłowe.
6	ROUTING_INFEASIBLE: problem okazał się niemożliwy.

Opcje wyszukiwania lokalnego

W tabeli poniżej znajdziesz opcje lokalnych strategii wyszukiwania (nazywane też metaheurystyką). Przykłady ustawienia tych opcji znajdziesz w sekcji Zmiana strategii wyszukiwania.

Option	Opis
AUTOMATIC	Umożliwia rozstrzygniecie metabolizmu.
GREEDY_DESCENT	Akceptuje ulepszanie sąsiednich wyszukiwań (zmniejszających koszty), dopóki nie zostanie osiągnięta lokalna wartość minimalna.
GUIDED_LOCAL_SEARCH	Wykorzystuje funkcję wyszukiwania lokalnego w celu zmiany znaczenia. (por. Wyszukiwanie lokalne z przewodnikiem) to najbardziej wydajna metoda metapozycji wyznaczania trasy.
SIMULATED_ANNEALING	Używa symulowanej oddłużenia, aby unikać lokalnych miniatur. (por. Symulowana animacja).
TABU_SEARCH	Używa znaczenia wyszukiwania Tabu, by unikać lokalnych znaków minimalnych (por. Wyszukiwanie Tabu).
GENERIC_TABU_SEARCH	Korzysta z wyszukiwania Tabu na podstawie wartości celu rozwiązania, aby unikać lokalnych wartości minimalnych.

Rozpowszechnianie

Nazwa	Typ	Domyślna	Opis
use_full_propagation	wartość logiczna	prawda	Stosuj ograniczenia z pełną propagacją w modelu routingu (zamiast tylko prostsza). Pełna rozpowszechnienie jest potrzebna tylko w przypadku wyszukiwania z pierwszej głębiej lub w modelach, które wymagają silnej propagacji w celu wykończenia wartości zmiennych dodatkowych. Zmiana tego ustawienia na „true” (prawda) w większości przypadków spowalnia wyszukiwanie i zwiększa wykorzystanie pamięci.