Opcje routingu

W tej sekcji opisano niektóre opcje rozwiązania routingu.

Limity wyszukiwania

Limity wyszukiwania wyłączają rozwiązanie po osiągnięciu określonego limitu, np. maksymalnej długości czasu lub liczby znalezionych rozwiązań. Możesz ustawić wyszukiwanie za pomocą parametrów wyszukiwania rozwiązania. Zobacz Przykład: Limity czasu.

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

Nazwa	Typ	Domyślny	Opis
solution_limit	int64	kint64max	Ogranicz liczbę roztworów wygenerowane podczas wyszukiwania.
time_limit.seconds	int64	kint64max	Ogranicz czas (w sekundach): do wyników wyszukiwania.
lns_time_limit.seconds	int64	100	Ogranicz czas (w sekundach) do czasu w : z wyszukaniem zakończenia dla każdego lokalnego sąsiada wyszukiwania.

Pierwsza strategia rozwiązania

Pierwszą strategią jest metoda, której używa do znalezienia punktu początkowego rozwiązanie. W poniższej tabeli znajdziesz opcje dostępne w przypadku first_solution_strategy.

Opcja	Opis
AUTOMATIC	Pozwala rozwiązania określić, którą strategię zastosować zgodnie z rozwiązywanym modelu.
PATH_CHEAPEST_ARC	Początek trasy „start” należy połączyć z który generuje najtańszy segment trasy, a następnie wydłuży trasę o na ostatnim węźle dodanym do trasy.
PATH_MOST_CONSTRAINED_ARC	Podobne do PATH_CHEAPEST_ARC, ale łuki są oceniane za pomocą selektora opartego na porównaniach, który będzie faworyzował: najpierw ograniczone łuki. Aby przypisać selektor do modelu routingu, użyj funkcji metoda ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Podobny do PATH_CHEAPEST_ARC, oprócz kosztów są oceniane za pomocą funkcji przekazywanej do SetFirstSolutionEvaluator()
SAVINGS	Algorytm oszczędzania (Clarke i Wright). Odniesienie do: Clarke, G. & Wright, J.W. „Harmonogramy pojazdów z centrum Depot do określonej liczby punktów dostawy” , Operations Research, Vol. 12, 1964, s. 568-581.
SWEEP	Algorytm Sweep (Wren i Holliday). Materiały referencyjne Anthony Wren & Alan Holliday – komputerowe planowanie jazdy pojazdów od jednego lub kilku magazynów do liczby punktów dostawy Kwartalnik Research (1970–1977), nr 23, nr 3 (wrzesień, 1972), s. 333-344.
CHRISTOFIDES	algorytm Christofides (właściwie wariant funkcji Algorytm Christofides wykorzystujący dopasowanie maksymalne zamiast wartości maksymalnej które nie gwarantuje uzyskania 3/2 współczynnika sprzedawcy ds. podróży). Działa w ogólnych modelach kierowania pojazdów przez przedłuża trasę, dopóki nie będzie można wstawić do niej żadnych węzłów. Zobacz Nicosa Christofidesa, najgorszą analizę nowej heurystyki dla problem z podróżnym sprzedawcą, Report 388, Graduate School of Industrial Administracja, CMU, 1976 r.
ALL_UNPERFORMED	Ustaw wszystkie węzły jako nieaktywne. Znajduje rozwiązanie tylko wtedy, gdy węzły są opcjonalne (są elementem ograniczenia rozdzielenia z skończonym kosztem kary).
BEST_INSERTION	Opracuj rozwiązanie iteracyjne, wstawiając najtańszy element węzeł w najtańszej pozycji; koszt wstawienia reklamy jest obliczany na podstawie funkcja kosztowa modelu routingu. Od 2012 r. działa tylko w przypadku modeli węzłów opcjonalnych (z ograniczonymi kosztami kar).
PARALLEL_CHEAPEST_INSERTION	Iteracyjne opracowanie rozwiązania przez wstawienie pary klucz-wartość najtańszy węzeł w najtańszej pozycji; koszt wstawienia reklamy zależy od i kosztu łuku. Szybsza niż BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Opracuj rozwiązanie iteracyjne, wstawiając każdy z nich węzeł w najtańszej pozycji; koszt wstawienia zależy od łuku funkcji kosztu. Różni się od PARALLEL_CHEAPEST_INSERTION według węzła wybrane do wstawienia; tutaj węzły są uwzględniane w kolejności proces tworzenia. Szybsza niż PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Łącz iteracyjnie 2 węzły, które generują najtańszy fragment trasy.
LOCAL_CHEAPEST_ARC	Wybierz pierwszy węzeł z niepowiązanym następcą i połączyć go z węzłem, który tworzy najtańszy segment trasy.
FIRST_UNBOUND_MIN_VALUE	Wybierz pierwszy węzeł z niepowiązanym następcą i połącz go z pierwszym dostępnym węzłem. Jest to odpowiednik Strategia CHOOSE_FIRST_UNBOUND połączona z kontem ASSIGN_MIN_VALUE (por. ograniczenie_solver.h).

Stan wyszukiwania

Stan wyszukiwania możesz zwrócić, używając metody status modelu routingu. Oto kod w Pythonie pozwalający wyświetlić stan wyszukiwania:

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

Powoduje to wydrukowanie liczby całkowitej o następującym znaczeniu:

Wartość	Opis
0	ROUTING_NOT_SOLVED: problem nie został jeszcze rozwiązany.
1	ROUTING_SUCCESS: problem został rozwiązany.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: problem rozwiązany po wywołaniu RoutingModel.Solve() z wyjątkiem tego, nie osiągnięto jeszcze optymalnej wartości. Większa ilość czasu pozwoliłaby poprawić rozwiązanie.
3	ROUTING_FAIL: nie znaleziono rozwiązania problemu.
4	ROUTING_FAIL_TIMEOUT: upłynęło limit czasu przed znalezieniem rozwiązania.
5	ROUTING_INVALID: model, parametry modelu lub flagi są nieprawidłowe.
6	ROUTING_INFEASIBLE: Okazało się, że problem jest niemożliwy do realizacji.

Opcje wyszukiwania lokalnego

W tabeli poniżej znajdziesz opcje dotyczące lokalnych strategii wyszukiwania (nazywanych też metaheurystyka). Przeczytaj artykuł Zmienianie strategii wyszukiwania. aby dowiedzieć się, jak skonfigurować te opcje.

Opcja	Opis
AUTOMATIC	Zezwala rozwiązanieowi na wybranie metaheurystyki.
GREEDY_DESCENT	Akceptuje poprawę (obniżenie kosztów) lokalnych sąsiadów z wyszukiwaniem aż do osiągnięto minimum.
GUIDED_LOCAL_SEARCH	Wykorzystuje wyszukiwanie lokalne z przewodnikiem, by uciec od lokalnego minima. (por. Wyszukiwanie lokalne z pomocą) jest to zwykle najskuteczniejsza metaheurystyka do wyznaczania tras pojazdów.
SIMULATED_ANNEALING	Wykorzystuje symulowane wydrążanie w celu uniknięcia lokalnych minima (por. Symulowane wygładzanie).
TABU_SEARCH	Wykorzystuje wyszukiwanie tabu, aby uciec od minima lokalnego (por. Wyszukiwanie w Tabu).
GENERIC_TABU_SEARCH	Wykorzystuje wyszukiwanie tabu w odniesieniu do obiektywnej wartości rozwiązania, aby uciec od wyników lokalnych i minimatyczne.

Kontrola rozmnażania

Nazwa	Typ	Domyślny	Opis
use_full_propagation	wartość logiczna	prawda	Użyj ograniczeń z pełną propagacją w modelu routingu (a nie tylko z propagacją lekką). W pełni naładowana propagacja jest konieczna tylko w przypadku korzystania z wyszukiwania opartego na głębi i modeli które wymagają silnego rozmnażania, aby sfinalizować wartość drugorzędnej zmiennych. Zmiana tego ustawienia na Prawda spowalnia wyszukiwanie w w większości przypadków i zwiększają wykorzystanie pamięci.