Algorytmy wyznaczania optymalnej trasy przejazdu

Najczęściej optymalizacja sprowadza się do możliwości wyboru jednego z parametrów jako głównego kryterium. Wśród nich możemy spotkać takie wielkości jak odległość, czas przejazdu czy zużyte paliwo. Jednak coraz częściej istotne jest określenie optymalnej trasy przy uwzględnieniu zupełnie innych parametrów. Dodatkowo ważne jest jednoczesne uwzględnienie wszystkich wymaganych parametrów przy zapewnieniu, że będzie istniała możliwość określenia ich "ważności". Tak zdefiniowane parametry pozwolą na elastyczne planowanie tras przejazdu i optymalizację działania transportu. Jest to szczególnie istotne w przypadku przedsiębiorstw spedycyjnych lub producentów czy hurtowni zaopatrujących swoich klientów w towary. W warunkach rzeczywistych coraz częściej spotykamy się z planowaniem dostaw towarów do klientów. Samochód z towarem ma za zadanie dostarczenie towaru do określonej liczby klientów. Istotne są tu przede wszystkim koszty transportu oraz jego czas. Ważne jest więc zaplanowanie trasy w taki sposób by zoptymalizować żądane czynniki. Konieczne jest zastosowanie algorytmu pozwalającego uwzględnić koszt trasy. Należy jednak zwrócić uwagę na to, że koszt trasy jest sumą kosztów pokonania poszczególnych odcinków. A koszt pokonania każdego z odcinków może być zupełnie inny w każdym z rozpatrywanych wariantów trasy. Może na to wpłynąć chociażby kierunek przejazdu danego odcinka, zwłaszcza jeżeli występują różnice wysokości pomiędzy jego końcowymi punktami. Dodatkowo planując łańcuch dostaw musimy uwzględnić zwiększony koszt transportu na początku trasy, wynikający z większej masy ładunku. Parametr ten jest istotny zwłaszcza przy planowaniu transportu towarów posiadających dużą masę. Konieczne jest więc używanie algorytmów, które pozwalają na określenie kosztu przebycia każdego odcinka niezależnie w dwie strony. Ponadto algorytmy te muszą pozwalać na elastyczne wprowadzanie modyfikacji swojej metody działania w celu dostosowania ich działania do specjalnych potrzeb użytkowników. Według opinii autora, możliwe jest wprowadzenie takiej modyfikacji istniejących algorytmów wyznaczania drogi, by możliwe było uwzględnienie wielu parametrów podczas jej wyboru.

Algorytmy wyznaczania drogi
Wyznaczenie drogi możliwe jest za pomocą różnego rodzaju algorytmów przeszukiwania. Zasada działania tych algorytmów opiera się na przeszukiwaniu grafu. Mapa drogowa przekształcana jest w graf skierowany. Jego węzły odpowiadają punktom na mapie - najczęściej skrzyżowaniom lub miejscowościom (w zależności od skali rozpatrywanego problemu i jego szczegółowości), a krawędzie reprezentują drogi łączące poszczególne punkty. Najprostsze techniki opierają się o budowanie drzewa przeszukiwań, przeszukując je wszerz, w głąb lub przy pomocy innej techniki. W rzeczywistych warunkach nie są one jednak wystarczające, ze względu na brak możliwości uwzględnienia kosztu przejścia pomiędzy węzłami drzewa. Odpowiada to sytuacji w której koszt przejazdu pomiędzy dwoma dowolnymi punktami jest jednakowy. W rzeczywistości sytuacje takie nie występują.

Artykuł zawiera 20260 znaków.

Źródło: Czasopismo Logistyka