Problem komiwojażera

Algorytm udoskonalono o możliwość „rozwiązywania pętli”. Oznacza to, że droga komiwojażera jest bez przecięć. Dokonano tego poprzez możliwość zamiany kolejności miast w danym, zadeklarowanym wcześniej sąsiedztwie. Oznacza to, że przykładowo: przy sąsiedztwie równym 3, zostaje wylosowane dowolne miasto X oraz ustalony segment dla tego miasta składający się z X, X+1 i X+2.

Dodatkowo, przed zastosowaniem tej metody przeznaczono pewną część iteracji na standardowe symulowane wyżarzanie. Nie losowano natomiast dwóch miast, które zamieniano miejscami. Losowano miasto oraz miejsce, w które należy je przesunąć. Pozostałe miasta zostawały wtedy przesuwane w odpowiednią stronę o odpowiednią liczbę miejsc. Temperatura tego wstępnego wyżarzania zmieniała się schematem geometrycznym z c=0.99. Wolniejsze chłodzenie nie było potrzebne, gdyż główna część algorytmu skupiała się na przestawianiu miast w sektorach.

Takie modyfikacje pozwoliły na uzyskanie optymalnych wyników przy w miarę dobrym czasie trwania algorytmu.

Przedstawiono wyniki dla losowego rozłożenia miast:

N= 20 miast

T = 0.001

D= 375,83

Czas: 45 sekund

N= 30 miast

T = 0.001

D= 468,89

Czas: 1’ 50 sek.

N= 50 miast

T = 0.001

D= 621,12

Czas: 5’45 sek.

Niestety, dla większych ilości miast, szybkość działania algorytmu drastycznie rośnie. Wiąże się to z większą liczbą potrzebnych iteracji do rozplątania wszystkich „supełków”.

Dla n=100

Dla n=100 wyniki również są satysfakcjonujące, choć mogą zdarzyć się niewielkie przecięcia. Ma to związek z niewystarczającą liczbą iteracji i możliwością nie wylosowania danego sektora, by sprawdzić przetasowanie miast w sektorze. Zwiększenie liczby iteracji spowoduje natomiast znaczne przedłużenie czasu trwania algorytmu (obecnie wynosi ok. 15 minut).