Problem komiwojażera

Problem komiwojażera (ang. TSP — Travelling Salesperson Problem) jest jednym z najstarszych problemów optymalizacyjnych w sieciach. Jest to zagadnienie, dla którego dotychczas nie znaleziono rozwiązania optymalnego w czasie wielomianowym, tzn. w czasie będącym wielomianem zmiennej n, czyli ilości danych. Problem ten można sformułować następująco.

Komiwojażer ma odwiedzić określoną ilość miejscowości. Wiadomo, że ma odwiedzić tylko raz każdą z nich i powrócić do miejscowości, z której rozpoczął podróż. Znane są koszty przejazdu pomiędzy każdą parą miast. Należy zaplanować komiwojażerowi drogę przejazdu tak, aby całkowity koszt podróży był jak najmniejszy.

Problem komiwojażera jest klasycznym problemem optymalizacji kombinatorycznej pojawiającym się w wielu zastosowaniach. Rozważmy na przykład sytuację, w której ramię maszyny nitującej porusza się na skrzydle samolotu od punktu do punktu i po umocowaniu n nitów wraca do punktu wyjścia. Wybór optymalnej drogi poruszania się ramienia jest rozwiązaniem odpowiedniego problemu komiwojażera.

W języku teorii sieci, problem polega na znalezieniu najkrótszego cyklu długości n (zwanego cyklem Hamiltona) w n-wierzchołkowej sieci pełnej. Ilość wierzchołków tej sieci odpowiada ilości miast pomiędzy, którymi porusza się komiwojażer, natomiast zwrot „sieć pełna” oznacza, że między każdą parą wierzchołków (miast) istnieje połączenie. Dla sieci niepełnych problem komiwojażera nie ma rozwiązania. Szczególnym przypadkiem problemu komiwojażera jest sytuacja kiedy koszty przejazdu pomiędzy poszczególnymi miejscowościami są takie same. Zajmiemy się przypadkiem ogólnym, tzn. kiedy koszty te są różne.

Rozwiązanie

Teoretycznie problem komiwojażera może być rozwiązany poprzez wygenerowanie (n-1)! cykli Hamiltona i wybraniu spośród nich optymalnego. Ilość (n-1)! bierze się stąd, że dla grafu o n wierzchołkach mamy n! permutacji pomiędzy tymi wierzchołkami i (n-1)! z nich odpowiada różnym cyklom Hamiltona wychodzącym z jednego z wierzchołków. Dodatkowo, jeśli koszty przejazdu pomiędzy miejscowościami są takie same, to ilość cykli ograniczamy o połowę. Takie podejście jest jednak ciągle bardzo nieefektywne gdyż, np. dla grafu o 20 wierzchołkach mamy do przeanalizowania 60 822 550 204 416 000 (ponad 60 biliardów) kombinacji (1 × 19!). Algorytm pełnego przeglądu liczyłby w tym przypadku nieprzerwanie latami.

Mając do rozwiązania tak trudny obliczeniowo problem, możemy zastosować udoskonaloną technikę, która gwarantuje, że otrzymamy rozwiązanie optymalne bez konieczności przeglądu wszystkich możliwych kombinacji. Jedną z tych technik jest algorytm podziału i ograniczeń.

Algorytm ten polega na podziale bieżącego zbioru rozwiązań na dwa lub więcej podzbiorów. Podział ten ma na celu zredukowanie ilości kombinacji potrzebnej do znalezienia rozwiązania optymalnego. Po każdym podziale liczone są dolne ograniczenia (ang. LB — Lower Bound) wag rozwiązań w obu podzbiorach i do dalszych podziałów wybierany jest ten podzbiór, który ma mniejsze dolne ograniczenie. Algorytm podziału i ograniczeń dla konkretnego problemu wygląda następująco:

Mamy sześciowierzchołkowy graf pełny, w którym poszczególne liczby odpowiadają kosztom przejazdu pomiędzy miastami.

Graf kosztów przejazdu między miastami

Graf kosztów przejazdu między miastami

Macierz opisująca graf ma postać:
$$
\begin{array}{cc}
~ & \begin{matrix} 1 &\;\;\; 2 &\;\;\; 3 &\;\;\;\; 4 &\;\;\;\; 5 &\;\; 6 \end{matrix} \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{matrix} & \begin{bmatrix}
\infty \;&\; 3 \;&\; 93 \;&\; 13 \;&\; 33 \;&\; 9 \\
4 & \infty & 77 &42 & 21 & 16 \\
45 & 17 & \infty & 36 & 16 & 28 \\
39 & 90 & 80 & \infty& 56 & 7 \\
28 & 46 & 88 & 33 & \infty & 25 \\
3 & 88 & 18 & 46 &92 & \infty \end{bmatrix}
\end{array}
$$

W przypadku jednakowych kosztów podróży pomiędzy miastami, graf posiadałby tylko jedną wartość na każdym ramieniu, natomiast macierz opisująca graf byłaby macierzą diagonalną.

W pierwszym kroku odejmujemy od każdego wiersza najmniejszą wartość jaka w nim występuje. W ten sposób każdy wiersz będzie posiadał wartość 0.
$$
\begin{array}{ccc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\;\; 3 &\;\;\;\; 4 &\;\;\;\; 5 &\;\; 6 \end{matrix} & ~ \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{matrix} &
\begin{bmatrix} \infty \;&\; 3 \;&\; 93 \;&\; 13 \;&\; 33 \;&\; 9 \\
4 & \infty & 77 &42 & 21 & 16 \\
45 & 17 & \infty & 36 & 16 & 28 \\
39 & 90 & 80 & \infty & 56 & 7 \\
28 & 46 & 88 & 33 & \infty & 25 \\
3 & 88 & 18 & 46 & 92 & \infty \end{bmatrix} &
\begin{matrix} -3 \\ -4 \\ -16 \\ -7 \\ -25 \\ -3 \end{matrix} \\
\end{array}
$$

Jeżeli po tym kroku w jakiejś kolumnie nie ma zera, to również od niej odejmujemy jej najmniejszą wartość.

$$
\begin{array}{cc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\;\; 3 &\;\;\;\; 4 &\;\;\;\; 5 &\;\; 6 \end{matrix} \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{matrix} &
\begin{bmatrix} \infty \;&\; 0 \;&\; 90 \;&\; 10 \;&\; 30 \;&\; 6 \\
0 & \infty & 73 & 38 & 17 & 12 \\
29 & 1 & \infty & 20 & 0 & 12 \\
32 & 83 & 73 & \infty & 49 & 0 \\
3 & 21 & 63 & 8 & \infty & 0 \\
0 & 85 & 15 & 43 & 89 & \infty \end{bmatrix}
\end{array}
$$

W ten sposób otrzymujemy zredukowaną macierz kosztów, w której każdy wiersz i kolumna zawiera przynajmniej jedno zero.

$$
\begin{array}{cc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\;\; 3 &\;\;\; 4 &\;\;\; 5 &\;\; 6 \end{matrix} \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{matrix} &
\begin{bmatrix} \infty \;&\; 0 \;&\; 75 \;&\; 2 \;&\; 30 \;&\; 6 \\
0 & \infty & 58 & 30 & 17 & 12 \\
29 & 1 & \infty & 12 & 0 & 12 \\
32 & 83 & 58 & \infty & 49 & 0 \\
3 & 21 & 48 & 0 & \infty & 0 \\
0 & 85 & 0 & 35 & 89 & \infty \end{bmatrix} \\
\end{array}
$$

W obu krokach odjęliśmy w sumie 81, a więc 81 jest dolnym ograniczeniem rozwiązania optymalnego.

$$
\begin{array}{cc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\;\; 3 &\;\;\; 4 &\;\;\; 5 &\;\; 6 \end{matrix} \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{matrix} &
\begin{bmatrix} \infty \;&\; 0 \;&\; 75 \;&\; 2 \;&\; 30 \;&\; 6 \\
0 & \infty & 58 & 30 & 17 & 12 \\
29 & 1 & \infty & 12 & 0 & 12 \\
32 & 83 & 58 & \infty & 49 & 0 \\
3 & 21 & 48 & 0 & \infty & 0 \\
0 & 85 & 0 & 35 & 89 & \infty \end{bmatrix} \\
\end{array}
$$
$$ \text{LB = 3 + 4 + 16 + 7 + 25 + 3 + 25 + 8 = 81} $$

Krok 1A

Następnie wykonywać będziemy kolejne redukcje rozmiaru macierzy. Dla każdej wartości macierzy równej zero określamy jaką liczbę możemy odjąć od danego wiersza oraz kolumny. Przykładowo dla zera na pozycji [1,2] w wierszu możemy odjąć 6, a w kolumnie 0. Dla zera na pozycji [2,1] w wierszu możemy odjąć 12, natomiast w kolumnie 0. Odejmowane wartości zapisujemy obok odpowiednich kolumn i wierszy:

$$
\begin{array}{cc}
~ & \begin{matrix} \; 1 &\;\;\; 2 &\;\;\; 3 &\;\;\; 4 &\;\;\; 5 &\;\; 6 \end{matrix} \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{matrix} &
\begin{bmatrix} \infty \;&\; 0 \;&\; 75 \;&\; 2 \;&\; 30 \;&\; 6 \\
0 & \infty & 58 & 30 & 17 & 12 \\
29 & 1 & \infty & 12 & 0 & 12 \\
32 & 83 & 58 & \infty & 49 & 0 \\
3 & 21 & 48 & 0 & \infty & 0 \\
0 & 85 & 0 & 35 & 89 & \infty \end{bmatrix} \\
~ & \begin{matrix} \;\;\; -0 & -1 & -48 & -2 & -17 & -0 \end{matrix}
\end{array}
$$
$$ \text{LB = 81 + 48 + 0 = 129} ~~~~~~~~~~ \text{[6,3]} $$

Krok 2A

Po określeniu liczb jakie możemy odjąć od wierszy i kolumn wybieramy takie dwie, które dodane do wartości dolnego ograniczenia najbardziej je zwiększą. Kolejnym ograniczeniem w wyborze jest to, że musimy go dokonać względem zer macierzy. Nie możemy np. wybrać liczb 48 oraz 32 ponieważ na przecięciu wiersza 4 i kolumny 3 mamy wartość 58. Parą liczb najbardziej zwiększającą LB jest w tym przypadku 48 i 0. W kolejnym kroku macierz nie będzie zatem zawierała wiersza szóstego i kolumny trzeciej, a łuk grafu z punktu 6 do 3 jest już jedną z dróg ostatecznego rozwiązania. Ponieważ komiwojażer każdą drogę ma przebyć tylko raz, możemy od razu wykluczyć podróż w kierunku przeciwnym (3›6). Dokonujemy tego wstawiając symbol \(\infty\) na pozycji [3,6].
$$
\begin{array}{ccc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\; 4 &\;\;\; 5 &\;\;\; 6 \end{matrix} & ~ \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{matrix} &
\begin{bmatrix} \infty \;&\; 0 \;&\; 2 \;&\; 30 \;&\; 6 \\
0 & \infty & 30 & 17 & 12 \\
29 & 1 & 12 & 0 & \infty \\
32 & 83 & \infty & 49 & 0 \\
3 & 21 & 0 & \infty & 0 \end{bmatrix} & \begin{matrix} -2 \\ -17 \\ -1 \\ \mathbf{-32} \\ -0 \end{matrix} & \\
~ & \begin{matrix} -3 & -1 & -2 & -17 & \mathbf{-0} \end{matrix} & ~ \\
\end{array}
$$
$$ \text{LB = 81 + 0 + 32 = 113} ~~~~~~~~~~ \text{[4,6]} $$

Krok 3A

Postępując jak poprzednio wykreślamy z macierzy wiersz czwarty i kolumnę szóstą. Kolejną drogą komiwojażera będzie zatem łuk z punktu 4 do 6. Nie musimy już zajmować się drogą przeciwną [6,4] ponieważ kolumna 6 została wykreślona w poprzednim kroku. Procedurę tą będziemy przeprowadzać aż do całkowitego zredukowania wymiaru macierzy lub pozbycia się zer. Przy okazji możliwe jest wykluczenie kolejnych dróg z macierzy. W rozwiązaniu mamy już drogi [4,6] i [6,3]. Oznacza to, że komiwojażer z punktu 4 uda się do punktu 6, a następnie do 3. Możemy więc uznać, że nigdy nie przebędzie on drogi z 3 do 4, bo oznaczałoby to dwukrotne przebywanie w punkcie 4. W następnej macierzy od razu wstawiamy \(\infty\) na pozycji [3,4] i dokonujemy kolejnej redukcji.
$$
\begin{array}{ccc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\; 4 &\;\;\; 5 \end{matrix} & ~ \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 5 \end{matrix} & \begin{bmatrix} \infty \;&\; 0 \;&\; 2 \;&\; 30 \\
0 & \infty & 30 & 17 \\
29 & 1 & \infty & 0 \\
3 & 21 & 0 & \infty \end{bmatrix} & \begin{matrix} -2 \\ \mathbf{-17} \\ -1 \\ -3 \end{matrix} \\
~ & \begin{matrix} \mathbf{-3} & -1 & -2 & -17 \end{matrix} & ~ \
\end{array}
$$
$$ \text{LB = 81 + 17 + 3 = 101} ~~~~~~~~~~ \text{[2,2]}$$

Krok 4A

W następnym kroku pamiętać należy o wprowadzeniu symbolu \(\infty\) na pozycji [1,2].
$$
\begin{array}{ccc}
~ & \begin{matrix} \;\;\; 2 &\;\; 4 &\;\;\; 5 \end{matrix} & ~ \\
\begin{matrix} 1 \\ 3 \\ 5 \end{matrix} & \begin{bmatrix} \infty \;&\; 2 \;&\; 30 \\
1 & \infty & 0 \\
21 & 0 & \infty \end{bmatrix} & \begin{matrix} ~ \\ ~ \\ \mathbf{-1} \\ -21 \end{matrix} \\
~ & \begin{matrix} ~ & \;\;\;\;\; -2 & \mathbf{-30} \end{matrix} & ~
\end{array}
$$
$$ \text{LB = 81 + 1 + 30 = 112} ~~~~~~~~~~ \text{[3,5]} $$

Krok 5A

W tym momencie wiemy już, że komiwojażer będzie poruszał się po trasie: 4, 6, 3, 5. Dzięki temu możliwe są dodatkowe redukcje w macierzy. Jeśli komiwojażer znajdzie się w punkcie 5, to analogicznie do poprzedniego rozumowania, nie może już udać się do punktu 4, możemy zatem na pozycji [5,4] wstawić \(\infty\). Otrzymujemy macierz, w której nie występują już zera, nie możemy więc wykonywać kolejnych redukcji. W takiej sytuacji sumujemy wszystkie elementy różne od nieskończoności i dodajemy je do dolnego ograniczenia. Drogi jakie w tej chwili nam pozostały ([1,4] oraz [5,2]) są kolejnymi trasami rozwiązania optymalnego.
$$
\begin{array}{cc}
~ & \begin{matrix} \; 2 &\;\; 4 \end{matrix} \\
\begin{matrix} 1 \\ 5 \end{matrix} & \begin{bmatrix} \infty & 2 \\
21 & \infty \end{bmatrix}
\end{array}
$$
$$ \text{LB = 81 + 21 + 2 = 104} ~~~~~~~~~~ \text{[1,4] [5,2]} $$

Krok 6A

Przeprowadzając kolejne kroki algorytmu otrzymaliśmy drogi: [6,3], [4,6], [2,1], [3,5], [1,4], [5,2]. Po uporządkowaniu: [1,4], [4,6], [6,3], [3,5], [5,2], [2,1]

Graf kosztów przejazdu między miastami z zaznaczeniem optymalnej drogi przejazdu

Graf kosztów przejazdu między miastami z zaznaczeniem optymalnej drogi przejazdu

Jest to optymalna droga poruszania się komiwojażera między miastami, a koszt podróży jest równy wartości LB otrzymanej w ostatnim kroku, czyli 104.

Znając optymalną trasę i jej koszt musimy jeszcze sprawdzić, czy jest to jedyne takie rozwiązanie. W tym celu szukamy czy w czasie kolejnych redukcji rozmiaru macierzy nie otrzymaliśmy wartość LB mniejszej niż 104. Rzeczywiście przy kroku 4A mamy LB = 101. Oznacza to, że zadanie ma więcej niż jedno rozwiązanie i musimy przeanalizować macierz z punktu 4A.

Aby nie dokonywać redukcji tej samej macierzy musimy ją przekształcić. Dotychczas wybieraliśmy wiersz i kolumnę, dla których możliwe było największe zwiększenie wartość LB, a następnie usuwaliśmy ten wiersz i kolumnę z dalszych rozważań. Teraz natomiast dokonamy odjęcia tych liczb otrzymując nową macierz, ale o tym samym rozmiarze. Dodatkowo zero, na pozycji względem której dokonujemy przekształcenia ([2,1]), zamieniamy na \(\infty\).

$$
\begin{array}{ccc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\; 4 &\;\;\; 5 \end{matrix} \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 5 \end{matrix} & \begin{bmatrix} \infty \;&\; 0 \;&\; 2 \;&\; 30 \\
0 & \infty & 30 & 17 \\
29 & 1 & \infty & 0 \\
3 & 21 & 0 & \infty \end{bmatrix} & \begin{matrix} -2 \\ \mathbf{-17} \\ -1 \\ -3 \end{matrix} \\
~ & \begin{matrix} \mathbf{-3} & -1 & -2 & -17 \end{matrix} & ~
\end{array}
$$
\(\Longrightarrow\) $$
\begin{array}{ccc}
~ & \begin{matrix} \;\; 1 &\;\;\; 2 &\;\; 4 &\;\;\; 5 \end{matrix} & ~ \\
\begin{matrix} 1 \\ 2 \\ 3 \\ 5 \end{matrix} & \begin{bmatrix} \infty \;&\; 0 \;&\; 2 \;&\; 30 \\
\infty & \infty & 13 & 0 \\
26 & 1 & \infty & 0 \\
0 & 21 & 0 & \infty \end{bmatrix} & \begin{matrix} -2 \\ -13 \\ -1 \\ \mathbf{-0} \end{matrix} \\
~ & \begin{matrix} \mathbf{-26} & -1 & -2 & -0 \end{matrix} & ~
\end{array}
$$

$$ \text{LB = 101 + 0 + 26 = 127} ~~~~~ \text{[5,1]} $$

Krok 4B

Dla nowej macierzy dokonujemy wyboru wiersza i kolumny, które będziemy redukować oraz liczymy wartość LB dodając 0 i 26 już nie do 81, ale do 101. Kolejne kroki wykonujemy według tego samego schematu co poprzednio.

$$
\begin{array}{ccc}
~ & \begin{matrix} \;\;\; 2 &\;\; 4 &\;\;\; 5 \end{matrix} & ~ \\
\begin{matrix} 1 \\ 2 \\ 3 \end{matrix} & \begin{bmatrix} 0 \;&\; 2 \;&\; \infty \\
\infty & 13 & 0 \\
1 & \infty & 0 \end{bmatrix} & \begin{matrix} -2 \\ \mathbf{-13} \\ -1 \end{matrix} \\
~ & \begin{matrix} -1 & ~~~~ & \mathbf{-0} \end{matrix} \\
\end{array}
$$
$$ \text{LB = 101 + 13 + 0 = 114} ~~~~~~~~~~ \text{[2,5]} $$

Krok 5B

Po otrzymaniu dróg [5,1] i [2,5] możemy wstawić \(\infty\) na pozycji [1,2].

$$
\begin{array}{cc}
~ & \begin{matrix} \; 2 &\;\; 4 \end{matrix} \\
\begin{matrix} 1 \\ 3 \end{matrix} & \begin{bmatrix} \infty & 2 \\
1 & \infty \end{bmatrix} \\
\end{array}
$$
$$ \text{LB = 101 + 2 + 1 = 104} ~~~~~~~~~~ \text{[2,5] [3,2]} $$

Krok 6B

Tak jak poprzednio dalsza redukcja wymiaru macierzy nie jest możliwa. W drugiej części rozwiązania otrzymaliśmy drogi: [5,1], [2,5], [1,4] i [3,2]. Po dodaniu ich do poprzednich i uporządkowaniu dostajemy drugą drogę optymalną komiwojażera: [1,4], [4,6], [6,3], [3,2], [2,5], [5,1]. Możemy również sprawdzić, że nie ma dodatkowych rozwiązań, gdyż żadna z wartości LB obliczona w drugim etapie nie jest większa od 101. Koszt podróży jest taki sam jak poprzednio: 104. Optymalnym drogami dla komiwojażera są zatem dwie trasy:

1 › 4 › 6 › 3 › 5 › 2 › 1
1 › 4 › 6 › 3 › 2 › 5 › 1

W ten sposób wykonując około 10 przekształceń macierzy i kilkanaście prostych operacji arytmetycznych otrzymujemy rozwiązanie problemu. W przypadku przeglądu wszystkich kombinacji dla grafu o wymiarze 6 mielibyśmy 5!, czyli 120 możliwych dróg.


Rysunki grafów wykonane zostały przy użyciu programu Grafos v. 1.2.9

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *