Nowe podejście do problemu komiwojażera

Abstract

Artykuł ten dotyczy problemu komiwojażera (ang. Travelling Salesman Problem - TSP), czyli znalezienia najkrótszej możliwej trasy poprzez zbiór węzłów (miast). Jesteśmy zainteresowani sytuacją, gdy powracamy do punktu początkowego na końcu naszej wędrówki. W pracy został zaprojektowany Algorytm Promienia (ang. Radius Algorithm - TSPAR) oraz dwa modyfikatory – Szybki oraz Najlepszy Modyfikator (ang. Fast and Best Modifiers - FM and BM). Podstawowym celem prezento-wanego podejścia było zapobieżenie przecinaniu się dróg i uzyskaniu możliwie jak najkrótszej trasy w omawianym problemie. Zaprojektowane środowisko badawcze doprowadziło do uzyskania wyników, wskazujących na potrzebę dalszej modyfikacji algorytmu.
Autor: Tomasz WILK

1. WSTĘP

Problem Komiwojażera (TSP) ma doniosłe znaczenie w: wyznaczaniu tras pojazdów, produkcji operacji komputerowych, wyznaczaniu wszelkich rozkładów, w biologii (np. badanie próbek pod mikroskopem), oraz w badaniu układów scalonych [1-6]. Jest to jeden z najbardziej znanych problemów kombinatoryki w dziedzinie informatyki [7]. Problem Komiwojażera jest przedstawicielem klasy "trudnych" problemów optymalizacyjnych, które to intrygowały matematyków i informatyków od lat. Artykuł ten opisuje doświadczenia w problemie Komiwojażera, który może być zdefiniowany jak następuje [7]: mając dane n miast oraz macierz odległości między każdą parą miast, problem Komiwojażera ma na celu stwierdzenie, czy jest możliwe odwiedzenie wszystkich n miast i powrót do początkowego miasta trasą długości l lub krótszą. B. Bixby (Rice University) i jego współpracownicy [8], używając sieci złożonej z SPARC 2, stacji DEC 5000, stacji roboczej SGI i innych (w sumie 50 stacji roboczych), wyznaczyli optymalną trasę dla 3038 miast. Był to znaczny postęp w stosunku do starego rekordu 2392 miast, wyznaczonego przez Padberga i Rinaldiego. Stworzony algorytm bazował na technice nazywanej "branch and cut" (gałąź i cięcie), która stabilnie poprawia zbiór liniowych nierówności opisując zbiór wykonalnych rozwiązań. Wiele innych grup opracowało algorytmy, które mogą osiągnąć przybliżony wynik (w granicach 2%) rozwiązań dla tego problemu, obliczając zbliżone do optymalnego rozwiązanie dla 1000 miast w kilka minut. Ulepszone wersje tych technik zostały wykorzystane, do wyznaczenia górnej granicy rozwiązania. Dużo trudniejsze było wyznaczenie granicy dolnej oraz udowodnienie optymalności. Obliczenia dla 3038 miast wymagały półtorej roku przetwarzania na wymienionym wcześniej sprzęcie. Interesujące są także inne, powszechnie stosowane algorytmy. Jednym z nich jest algorytm symulowanego wyżarzania (ang. Stimulated Annealing Algorithm) [9] W programie dostępne są dwa typy siatki – prostokątna i losowa.

Głównym celem tej pracy jest próba stworzenia i rozwinięcia nowego algorytmu dla TSP, łączącego węzły, takie jak miasta czy punkty dostaw, w sposób promienia. Ponadto, zostało zaprojektowane środowisko doświadczalne w celu testowania rozważanego podejścia. Artykuł ten jest zorganizowany w następujące sekcje: opis środowiska badawczego w sekcji 2; proponowane algorytmy – sekcja 3; sekcja 4 zawiera przykładowe wyniki badań; wnioski i propozycje usprawnień są tematem sekcji 5.