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.
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.
Modelowanie procesów biznesowych 