Planowanie wycieczki, czyli problem komiwojażera

Właśnie zaczęło się lato więc i pogoda i długość dnia stały się sprzyjające dla wycieczek wyjazdowych w Polskę. Czynniki te nie mają niestety wpływu na znalezienie odpowiedzi na pytanie — dokąd pojechać? Każdy, kto choć trochę liznął programowania, chciałby pewnie mieć ten problem rozwiązany za pomocą programu. Albo przynajmniej ja. Klikam „Restart and run all…” i dostaję plan wycieczki. Oczywiście wcześniej muszę określić jakieś kryterium wyboru miejsc (np. znaczki turystyczne) i sposób, w jaki mają być ułożone (np. mają rozwiązywać problem komiwojażera). Czyli po prostu, gdy moja żona mówi do mnie „Pojedźmy na jakąś wycieczkę!”, to ja od razu uruchamiam interpreter Pythona.

Wybór miejsc — znaczki turystyczne

Pewnie już samemu chcesz wyruszyć na taką zaprogramowaną wycieczkę, przejdźmy więc do konkretów. Zacznijmy więc od zdefiniowania puli miejsc, które są dla nas potencjalnie interesujące. Jak pewnie zauważyłeś, we wcześniejszych moich wpisach (Analiza skupień na przykładzie algorytmu k-średnich i
Silhouette Coefficient – czy dobrze pogrupowałem obserwacje?) korzystałem ze zbioru miejsc ze strony znaczki-turystyczne.pl. Znaczki turystyczne to całkiem fajna inicjatywa, której jestem fanem (i nie jestem w żaden inny sposób powiązany). Polega ona na stworzeniu spisu ciekawych miejsc turystycznych w danym kraju i stworzeniu dla każdego takiego miejsca drewnianego znaczka (wielkości przypinki do plecaka) z wypaloną ryciną przedstawiającą dane miejsce. Później znaczki takie są do kupienia w danym miejscu lub jego okolicach. Jeśli więc ktoś podróżuje całkiem sporo turystycznie po Polsce, to w ten sposób może sobie zorganizować całkiem ładną (ech. te ryciny) i jednorodną kolekcję pamiątek. Nam ten pomysł spodobał się na tyle, że nieco odwróciliśmy kota ogonem i przede wszystkim jeździmy do miejsc, które mają znaczki.

Dodatkowe kryterium — gra kolekcjonerska

Żeby było zabawniej, każdy znaczek turystyczny posiada załączony kupon, który dodatkowo potwierdza zdobycie znaczka. Jeśli uzbieramy kupony o 10 kolejnych numerach, to po wysłaniu ich do organizatora otrzymamy specjalny (jeden z wielu) znaczek kolekcjonerski z ryciną ze zwierzęciem zagrożonym wyginięciem w Polsce albo z podobizną osoby z Pocztu królów i książąt polskich. Edukacja mocno!

Żeby więc zoptymalizować proces, będę wybierał krainy turystyczne względem kolejnej numeracji znaczków. Pierwsza kraina to będzie miejsce, gdzie są znaczki z numerami 1, 2, …, 9, 10. Druga kraina to 11, 12, …, 19,20. I tak aż nie wyczerpią się znaczki. Czyli, że za jednym strzałem będzie można zdobyć wszystkie znaczki turystyczne odpowiadające danemu znaczkowi kolekcjonerskiemu. Fajnie, nie?

Dodatkowe kryterium — baza wypadowa

Kto podróżował z dziećmi, ten się nad mapą nie śmieje. Że tak sparafrazuję krążące po internecie powiedzonko. Podróżowanie z małymi dziećmi prawie zawsze jest satysfakcjonujące i jednocześnie super męczące. Kryzysy są tak częste, że przestaje się je nazywać kryzysami i po prostu się je wlicza w scenariusz realistyczny. Podróże znaczkowe nie powinny być więc za długie. Może się tak zdarzyć, że jest gdzieś kraina, która ma kolejne znaczki bardzo blisko siebie. Jest też bardzo daleka od domu. Cała wyprawa więc będzie bardzo długa. Taka wycieczka nie powinna być wynikiem mojego skryptu, chyba że faktycznie nie ma nic sensowniejszego bliżej. Żeby więc dodać to kryterium do obliczeń, do potencjalnych krain dorzucam zawsze punkt bazowy. Zaraz się przekonasz dlaczego.

Długość trasy — problem komiwojażera

Okej, mamy więc około 80 krain turystycznych. W każdej krainie mamy przeważnie 10 miejsc. Chcemy wyznaczyć trasę tak, żeby odwiedzić każde miejsce raz i jednocześnie, żeby trasa, którą przebędziemy, była jak najkrótsza. Dodatkowo chcemy, aby nasza podróż zaczynała się i kończyła w bazie wypadowej. Mamy więc jedenaście punktów i chęć przejechania przez nie wszystkie jak najkrótszą trasą. Witajcie w problemie komiwojażera!

Nie będę się tutaj rozpisywał nad tym problemem, wskażę natomiast moją próbę uporania się z nim. Otóż wpadł mi w ręce moduł Pythonowy mlrose, który bazuje na algorytmach ewolucyjnych. Przykład rozwiązania problemu komiwojażera, na którym bazowałem w 100%, znajdziesz tutaj.

Idea jest więc taka, żeby sprawdzić każdą krainę z uwzględnieniem bazy wypadowej i wybrać taką, której objechanie będzie najkrótsze.

I do tej pory skrypt działa tak sobie :-). Tzn. widziałem ładny wynik, ale nie zadbałem wtedy o odpowiednią odtwarzalność i aktualny wynik to:

Problem komiwojażera z n = 11
Problem komiwojażera z n = 11

Dodatkowe kryterium — znaczki turystyczne z innej grupy

Tak jak pisałem powyżej, żeby otrzymać znaczek kolekcjonerski, trzeba zebrać 10 kolejno numerowanych znaczków. Jako że baza znaczków turystycznych jest systematycznie powiększana, stwarza to ciekawą sytuację. Na przykład w mieście Bolków mamy znaczki 433 i 641. Będą więc one w dwóch różnych grupach, mimo iż są od siebie oddalone o około 1 KM. Pomyślałem więc o pewnym rozwiązaniu tego problemu, które całkiem fajnie się spisuje.

Wyznaczamy więc tak jak wyżej krainę, której objechanie będzie najkrótsze. Czyli po prostu sprawdzamy wszystkie i wybieramy tę, której rozwiązanie ma najniższą wartość. Na bazie punktów z tej krainy wyznaczam wielokąt wypukły. Jak już mam ten zbiór, to sprawdzam wszystkie znaczki, zadając jedno pytanie: czy dany znaczek jest w środku, czy na zewnątrz tego wielokąta. Jeśli jest w środku, to oznacza, że pewnie będziemy w którymś momencie blisko niego. Jeśli jest na zewnątrz, to przyjmuję, że nie będziemy blisko. To drugie założenie jest bardzo naiwne, ale nie można mieć wszystkiego :-).

Otrzymamy więc coś takiego:

Wielokąt wypukły
Wielokąt wypukły

Może więc się zdarzyć, że ilość znaczków w tym obszarze znacznie nam wzrośnie. I tak też niestety dzieje się w przygotowanym przeze mnie przykładzie:

Problem komiwojażera z n = 23
Problem komiwojażera z n = 23

Dlaczego się psuje?

Mignęła mi gdzieś publikacja z dowodem, że optymalna ścieżka rozwiązująca problem komiwojażera to wielokąt prosty. To znaczy, że żadne krawędzie się w nim nie przecinają. Jeśli widzimy więc rozwiązanie, które ma przecinające się krawędzie, to od razu wiemy, że jest nieoptymalne. Tutaj faktycznie tak jest. Dlaczego?

Otóż po dodaniu ostatniego kryterium otrzymujemy 23 punkty w naszej krainie. A taka liczba daje nam 23!/2 kombinacji do sprawdzenia. Czyli 12926008369442488320000 kombinacji. Jeśli zlecimy mlrose sprawdzenie 8192 pokoleń po 200 osobników w każdym, to sprawdzimy tylko 1638400 kombinacji. Czyli bardzo, bardzo mały ułamek wszystkich możliwych rozwiązań. A poświęcimy na to kilka godzin. Czyli lipa.

Konkluzja

Za dużo miejsc na raz!

Po obejrzeniu dotychczasowych wyników możemy zauważyć, że zdobycie 10 znaczków w czasie jednej wycieczki to nieco karkołomne wyzwanie. No bo w jednym przykładowym rozwiązaniu mamy takie miejsca: Waligóra — najwyższy szczyt Gór Kamiennych, Zamek Książ w Wałbrzychu, Schronisko górskie Orzeł, Nowa Ruda — Ratusz, Zespół Pałacowo-Hotelowy w Jedlince, Podziemne Miasto Osówka, Wieża Ratuszowa w Świdnicy, Zamek Grodno w Zagórzu Śląskim, Sztolnie Walimskie w Górach Sowich i Wielka Sowa — wieża widokowa. Czyli zdecydowanie kilka dni zwiedzania. Wychodzi więc, że pierwotne założenie już jest nierealistyczne. A co dopiero rozszerzenie tego rozwiązania o dodatkowe znaczki.

Nie będzie więc przeszkodą nieoptymalny pomysł na problem komiwojażera, tylko zwykła ludzka wydajność turystyczna. Jako że nie jesteśmy Japończykami na wyciecze (bez uprzedzeń), założenie to było niemożliwe do zrealizowania od samego początku.

Jest jednak łatwe uproszczenie tego problemu. Możemy, zamiast grupować znaczki turystyczne po 10, pogrupować je np. po 5. Wtedy wciąż będziemy systematycznie uzupełniać kolekcję, a złożoność będzie zdecydowanie mniejsza.

Problem komiwojażera z n = 6
Problem komiwojażera z n = 6
Problem komiwojażera z n = 10
Problem komiwojażera z n = 10

Lepszy algorytm rozwiązujący problem komiwojażera?

Gdy przeglądałem internet w poszukiwaniu innych ciekawych pomysłów na rozwiązanie problemu komiwojażera, trafiłem na wzmianki o pewnych heurystykach pozwalających go rozwiązać „dość dobrze i dość szybko”. Możliwe, że to byłoby kluczem do przyspieszenia i stworzenia sensowniejszych planów. Nie znalazłem jednak żadnego modułu, który by je implementował. Cóż, może następnym razem.

Kod użyty w tym przykładzie tym razem jest wyjątkowo okropny, więc nie polecam za bardzo jego zgłębiania. Jeśli jednak rozwiązujesz podobny problem i potrzebujesz inspiracji, to możesz go podejrzeć tutaj i zadać pytanie w komentarzu, na które z chęcią odpowiem :-).

Jeśli interesuje Cię jakiś temat – nie musi być związany z tym artykułem – to zostaw mi sygnał tutaj. Dzięki!

Dodaj komentarz

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