Zagadnienie podróżnika

Jeśli zagadnienie optymalnej marszruty zamierzamy rozwikłać na drodze formalnej, to najważniejszym krokiem jest ograniczenie liczby rozwiązań, pośród których szukamy najlepszego.

Wprowadzenie

Powyższe zdanie oznacza, że w ogólnym przypadku nie możemy spodziewać się znalezienia jednego najlepszego rozwiązania w rozsądnym czasie, nawet jeśli zaangażujemy do tego najbardziej wydajne komputery. Dlaczego – oto wyjaśnienie w terminach kombinatoryki.

Zagadnienie podróżnika albo problem podróżującego sprzedawcy (komiwojażera)

Sprzedawca wyrusza z miasta A i musi dokładnie raz odwiedzić każde z miast B, C, D, E, F,... (itd.) oraz wrócić do miasta A. Znamy wszystkie odległości między wszystkimi miastami. Zadanie: która marszruta jest najkrótsza? Zadanie to nosi nazwę: problem komiwojażera (Traveling Salesman Problem, TSP).

Dokładne rozwiązanie wymagałoby obliczenia długości wszystkich możliwych marszrut, aby je potem porównać i znaleźć najkrótszą. Ale wszystkich możliwych marszrut pomiędzy n miastami jest aż (n-1)!/2. Na przykład dla 10 miast mamy 181.440 możliwych marszrut, a dla 12 miast już prawie 20 milionów marszrut. W przypadku problemu niesymetrycznego (patrz niżej) jest ich 2 razy więcej. W praktyce więc taka bezpośrednia metoda rozwiązania zagadnienia jest do przyjęcia tylko dla bardzo małych liczb n.

Zagadnienie dla obu logistyk

Marszruta występuje zarówno w dystrybucji, jak i w procesach wytwarzania wyrobów i usług. Ponadto „optymalna marszruta” to niekoniecznie marszruta najkrótsza, gdyż w praktyce chodzi często o inne kryteria. Może to być marszruta najtańsza (angażująca najmniej – wartościowo – zasobów) bądź zabierająca najmniej czasu, najmniej narażona na zdarzenia niekorzystne itp. Co więcej, nawet w procesie produkcyjnym niekoniecznie musi to być marszruta materiału, lecz np. sekwencja produktów albo sekwencja różnych operacji wykonywanych przez jedno stanowisko robocze. W takich przypadkach często wchodzi w grę niesymetryczny problemem komiwojażera, ponieważ przezbrojenie stanowiska z operacji – powiedzmy – F na operację K pochłania inną ilość czasu i kosztów, niż przezbrojenie odwrotne.

Podejście formalne i praktyka

W podejściu, które tu nazywam formalnym poszukuje się takich „automatycznych” (komputerowych) sposobów rozwiązania zagadnienia podróżnika i zagadnień bardziej szczegółowych (np. zagadnień marszrut pojazdów), aby czas rozwiązania (idealnym komputerem, którego modelem jest niedeterministyczna maszyna Turinga) był proporcjonalny nie do n!, lecz – w najlepszym wypadku – do wielomianu zmiennej n. Na drodze matematycznej można udowodnić, że taki sposób rozwiązania istnieje i w związku z tym mówi się, że zagadnienie podróżnika jest niedeterministyczne wielomianowo zupełne (ang. NP-complete). Jednak do tej pory nie znaleziono tak dobrego sposobu rozwiązania.

Najlepsze obecnie metody dokładne (algorytmy), oparte na programowaniu dynamicznym, dają rozwiązanie w czasie proporcjonalnym do 2ⁿ . To dużo krócej, niż ~n!, ale nadal o wiele za długo, aby stosować to podejście w praktyce. Na przykład obliczenia metodą opartą na programowaniu liniowym zastosowaną do przypadku 15.112 miast zajęły ponad 22 i pół roku pracy komputerów w przeliczeniu na pracę pojedynczego standardowego procesora 500 MHz. Powstało więc kilka sposobów „automatycznego” otrzymywania rozwiązań niedokładnych, tzn bliskich optymalnemu, ale w ogólnym przypadku nie wiadomo dokładnie jak bliskich. W przypadkach konkretnych niekiedy da się to określić i typowa „dobroć” takiego rozwiązania to marszruta o ok 2-15% gorsza od najlepszej, gdy stosowane są heurystyki, a 100-150% gorsza od najlepszej, gdy stosowane są algorytmy. Najbardziej wydajne sposoby formalne to metaheurystyki, których konstrukcja opiera się na pewnym MODELU ujmującym sytuacje praktyczne określonej kategorii.

Najbardziej znane oraz najciekawsze sposoby rozwiązania zagadnienia podróżnika zostaną omówione niżej, ale w tym miejscu trzeba powiedzieć, że te wydajne mają wbudowany jakiś mechanizm ograniczający liczbę rozpatrywanych marszrut, np. eliminujący część marszrut z pewnością nieoptymalnych.

A praktyka? W praktyce logistycy – dyspozytorzy środków transportu, planiści i szefowie produkcji, organizatorzy prac zespołowych itd. – postępują podobnie, z góry eliminując większość marszrut, o których z doświadczenia wiadomo, że są nieoptymalne.

Zagadnienia marszruty pojazdów

W logistyce dystrybucji pojedyncze kryterium optymalizacji jest niewystarczające, gdyż jej zadanie to dostarczyć wymaganą ilość w wymaganym czasie przy jak najpełniejszym wykorzystaniu ładowności pojazdów. Toteż od strony formalnej zagadnienie marszruty pojazdów to nałożone na siebie co najmniej dwa zagadnienia: zagadnienie podróżnika oraz zagadnienie optymalnego pakowania.

Problem marszruty pojazdów (Vehicle Routing Problem, VRP) w postaci ogólnej i w sformułowaniu potocznym to zadanie: jaka jest optymalna marszruta dla floty pojazdów rozwożących towar z jednego albo wielu magazynów, jeśli każdy pojazd wyrusza z magazynu, odwiedza jeden raz każdego klienta dostarczając mu wymaganą ilość towaru i wraca do magazynu. W naturalny sposób jest to centralne zagadnienie logistyki. Typową postać marszruty dla jednego magazynu przedstawia Rys. 1.

Rys. 1. Typowa postać marszruty floty pojazdów dla 1 magazynu

Od strony matematycznej VRP jest to problem NP-trudny (NP-hard), czyli taki, który jest NP-zupełny (patrz wyżej) albo trudniejszy. W praktyce oznacza to, że nie da się w ogóle rozwiązać ściśle w czasie proporcjonalnym do wielomianu zmiennej n.

Gdyby pojazdy miały nieograniczoną ładowność, byłby to problem wielu komiwojażerów (Multiple Traveling Salesman Problem, MTSP). Gdyby zaś każdy odcinek marszruty miał zerowy koszt, byłby to problem optymalnego pakowania pojemników (Bin Packing Problem, BPP). Żaden z tych przypadków nie zachodzi, więc można powiedzieć, że w zagadnieniu marszruty pojazdów oba problemy narzucają ograniczenia nawzajem na siebie.

W praktyce mamy do czynienia z wieloma dodatkowymi ograniczeniami, a zatem z wieloma odmianami zagadnienia marszruty pojazdów. Do najbardziej typowych należą:

• VRP przy określonej (jednakowej) ładowności pojazdów: Capacitated VRP – CVRP,
• VRP z wieloma magazynami: Multiple Depot VRP – MDVRP,
• VRP z możliwością obsługi niektórych klientów przez kilka różnych pojazdów: Split Delivery VRP – SDVRP,
• VRP ze zwrotem niektórych towarów do magazynu: VRP with Pick-Up and Delivering – VRPPD,
• VRP z dostawą w wymaganych oknach czasowych: VRP with time windows – VRPTW,
• VRP z dostawami cyklicznymi (np. w określonych dniach tygodnia): Periodic VRP – PVRP,

Oczywiście w konkretnych przypadkach ograniczenia często łączą się i np. w większych firmach logistycznych występuje zagadnienie VRP z wieloma magazynami i z oknami czasowymi (Multiple Depot VRP with Time Windows, MDVRPTW). Ponadto matematyczne sformułowania pomijają szereg występujących w praktyce sytuacji, np. częściowego uzupełniania ładunku pojazdu w trasie.

Rozwiązania

c. d. n.