Podróżne dylematy

Przed długim weekendem czerwcowym wiele rodzin/osób zastanawiało się jak spędzić ten czas. Czy spędzić go w domu czy wyjechać? Spędzić go w jednym miejscu czy w kilku? Przedłużyć weekend czy skorzystać tylko z 4 dni? Odwiedzić rodzinę? Kogo i kiedy? Gdzie nocować? Którędy jechać? Co zabrać? Wziąć urlop czy nie? Co załatwić? Co zrobić? Z czego zrezygnować? Gdzie będą korki na drodze? Gdzie są utrudnienia w ruchu? Jaki jest koszt przejazdu? I wiele innych pytań.

Jednym z elementów jest kwestia przemieszczania się, czyli jakie miejscowości oraz w jakiej kolejności odwiedzić. Załóżmy, że mamy do odwiedzenia kilka miejsc (lokalizację, z której startujemy oraz 4 inne lokalizacje, tak jak na poniższym diagramie) i chcemy każde z nich odwiedzić tylko raz i wrócić do domu. Przejazd między miastami jest związany z kosztem przejazdu, odległością oraz czasem potrzebnym na przejazd (przykładowe elementy zostały wskazane na dostępnych połączeniach na diagramie).

Jest to związane z tzw. problemem komiwojażera (ang. travelling salesman problem). Chodzi o wybór najszybszej, najkrótszej lub najtańszej ścieżki (w zależności od zastosowanych wag na przejściach) przejścia po takim diagramie (dokładnie grafie), w ramach której wyruszamy z danego punktu początkowego, odwiedzamy wszystkie lokalizacje i wracamy do punktu początkowego, odwiedzając każdą lokalizację (poza początkową) tylko raz.

Myślę, że z takim problemem spotkało się wiele osób mających w planach odwiedzenie kilku lokalizacji (nie wnikam z jakiego powodu) – nie istotne czy są to punkty na obszarze danego kraju, kilku krajów, kontynentów czy danego regionu lub miasta. Można wykorzystać różne środki komunikacji lub skorzystać z własnego. Można poruszać się też pieszo. Mogą wystąpić roboty drogowe, objazdy, zwiększone natężenie ruchu czy może konieczne jest wykorzystanie przeprawy promowej. Elementy te wpływają na koszty i czas przejazdu. Z kolei ukształtowanie terenu może spowodować, że trasa blisko położonych lokalizacji w linii prostej, może się znacznie wydłużyć. Niektórzy oferują także przewóz dodatkowych osób, zmniejszając koszt przejazdu po swojej stronie. Atrybuty na połączeniach powinny uwzględniać wszystkie te elementy w zakresie czasu, kosztu przejazdu czy też fizycznej odległości.

komiwojazer_584px

Na diagramie wskazałem przykładowe odległości, ceny i czas przejazdu między 5 lokalizacjami, zakładając, że jedna z nich jest traktowana jako startowa. Atrybuty te na pierwszy rzut oka mogą się wydawać nielogiczne, ale starałem się uwzględnić, nie wskazując tego wprost, niektóre z powyższych elementów. Bez problemu można znaleźć na nim ścieżkę, która odwiedza wszystkie wierzchołki (lokalizacje) i wraca do początkowego punktu. Przykładem jest ścieżka START->4->2->1->3->START lub START->1->2->3->4->START. Oznacza to, że powyższe połączenia między lokalizacjami tworzą tzw. cykl Hamiltona. Znalezienie takiej ścieżki o najmniejszej wartości atrybutu branego pod uwagę jest rozwiązaniem problemu komiwojażera.

Dla podanego grafu (połączenia między lokalizacjami go tworzą) mamy takie cykle (wydaje mi się, że to wszystkie i że się nie pomyliłem podczas zliczania):

Przykładowy cykl Odległość
(km)
Koszt
(zł)
Czas
(h)
Śr. 
prędkość
km/h
Liczba 
km/zł
START>4>2>1>3>START i odwrotnie 470 41 6 78,33 11,46
START>1>2>3>4>START  i odwrotnie 660 33 11 60,00 20,00
START>3>4>2>1>START  i odwrotnie 430 36 8 53,75 11,94
START>1>3>2>4>START  i odwrotnie 670 48 9,5 70,53 13,96

Wśród wskazanych powyżej cykli widać, że pierwszy ma najmniejszy czas przejazdu, drugi najniższą cenę a trzeci najkrótszą odległość. Osobiście wybrałbym pierwszą ścieżkę.

Przy większej liczbie lokalizacji i połączeń, proces wyszukiwania „najlepszego” rozwiązania komplikuje się obliczeniowo. Można jednak powiedzieć, że wyznaczenie optymalnej trasy jest częścią większego procesu składającego się z określenia lokalizacji do odwiedzenia, oszacowania kosztów, czasu oraz odległości wymaganych do pokonania, czyli atrybutów połączeń, zaplanowania sposobu postępowania (wybór całej ścieżki lub pierwszych kroków, a potem dostosowywanie), realizacji planu, a na koniec oceny planu (np. wybrana droga nie nadaje się do użytkowania) i dostosowanie na przyszłość. Na diagramie został wskazany taki proces – kolorem zostały zaznaczone kroki odnoszące się do diagramu połączeń.

Atrybuty na powyższym diagramie można zmieniać podczas następnego podejścia lub na przykład likwidować określone krawędzie/połączenia jako nieakceptowalne z perspektywy kolejnej realizacji takiej „podróży”. Można także dodawać i odejmować lokalizacje i połączenia. Istotne jest to, że przy każdej takiej zmianie może nastąpić zmiana optymalnego rozwiązania, a także może zmienić się liczba cykli.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google

Komentujesz korzystając z konta Google. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s