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.

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.

Reklama

Optymalizacja zakupowa a reguły biznesowe

Przygotowywanie listy zakupów to czynność jak najbardziej codzienna. Żadna filozofia, tworzysz listę, zastanawiasz się gdzie możesz kupić poszczególne rzeczy, jak daleko, ile czasu potrzeba, co jest najbardziej potrzebne, co mogę kupić innym razem. Łatwiej jest gdy robimy listę zakupów do określonego sklepu – spożywczego czy marketu. Trudniej, gdy okazuje się, że lista zakupów jest na tyle różnorodna, że wymaga odwiedzenia różnego rodzaju sklepów i niekoniecznie mamy czas, aby udać się do marketu.

Załóżmy więc, że mamy do kupienia: kwiaty (ZAK3), chleb(ZAK2), gazety(ZAK1) i płytę CD (ZAK4). Rzeczy potrzebne i jak dostępne w różnych sklepach. Dodatkowo mapa obok wskazuje miejsca potencjalnego zakupu tych produktów oraz miejsce rozpoczęcie zakupów (START).

Poniższy diagram (w BPMN) prezentuje przebieg procesu realizowanego w powyższej sytuacji – od określenia zakupów do realizacji zakupów. Najważniejszą częścią procesu jest określenie priorytetów oraz kolejności wykonywanych zakupów. Jest to istotne, gdy na przykład mamy mniej czasu lub liczymy się z tym, że pewnych produktów możemy nie dostać lub może być kolejka. Może będzie trzeba zmienić sklep. Następnie, co prawda dynamicznie, określana jest droga po zakupy. Można ją zaplanować przed wyjściem z domu a można w trakcie. W podanym przykładzie nie zostały wskazane priorytety. Po połączeniu informacji o miejscach (gdy będą inne) oraz priorytetach droga może zostać określona w zupełnie inny sposób.

Taką optymalizację zakupową wykonujemy automatycznie w trakcie określania listy zakupów, nie zastanawiając się nad poszczególnymi krokami, ani kolejnością. Gdybyśmy chcieli przygotować aplikację, która dla podanej listy zakupów określa lokalizację, potencjalną kolejność zakupów w zależności od priorytetów, akceptowalną odległość od miejsca startu, miejsca, których chcemy uniknąć, należałoby zdefiniować odpowiednie reguły biznesowe, zaimplementować mechanizm rozwiązujący problem komiwojażera, włączyć mapę wraz z naniesioną listą sklepów.