Algorytmy wyznaczania optymalnej trasy przejazdu

• Autorzy: Kozieł G.

Warianty tytułu

EN

Algorithms for optimal route determine

• Języki publikacji: PL

Abstrakty

PL

Wyznaczenie optymalnej trasy przejazdu ma coraz większe znaczenie w logistyce. Ważne są przede wszystkim koszty transportu oraz jego czas. Istotne jest więc zaplanowanie trasy w taki sposób by zoptymalizować żądane czynniki. Możliwe jest to dzięki zastosowaniu algorytmu pozwalającego uwzględnić koszt trasy. Należy jednak zwrócić uwagę na fakt, że na koszt przebycia trasy może składać się wiele czynników takich jak odległość, czas przejazdu, opłaty za przejazd określonymi drogami oraz inne. Konieczne jest więc stosowanie algorytmów pozwalających na znalezienie optymalnej trasy, przy uwzględnieniu wszystkich wymaganych czynników. Zaproponowana w artykule modyfikacja algorytmu Dijkstry pozwala na uwzględnianie dowolnej liczby parametrów podczas wyboru drogi, dzięki przypisaniu wielu niezależnych wag do każdej z krawędzi grafu reprezentującego sieć połączeń drogowych. Umożliwia to elastyczne przeliczanie tras, dowolny wybór parametrów uwzględnianych przy wyborze drogi oraz określanie w jakim stopniu będą miały one wpływ na ostateczny wynik. Osiągane jest to poprzez uwzględnienie każdej z wag przypisanych do krawędzi grafu a następnie przemnożenie ich przez przypisane do nich wagi określające wpływ jaki poszczególne współczynniki powinny mieć na ostateczny wybór trasy. Dzięki takiemu podejściu każdy użytkownik może samodzielnie zdefiniować optymalne dla niego czynniki wpływające na wybór trasy i określić ich stopień istotności.

EN

The importance of optimal route determination is very high today, especially in logistics. The most important aspects are the transport costs and its time. It is therefore essential to plan a route in such a way that allows to optimize the desired factors. It is possible by usage of an algorithm allowing for taking into account the route cost. It should be noted that the cost of traveling the route may consist of a number of factors such as distance, travel time, road fees and other. It is necessary to use algorithms that allow for finding optimal route by taking into account all the demanded factors. The proposed modification of Dijkstra's algorithm allows for taking into account any number of parameters when selecting the route. It is possible thanks to assigning a number of independent weights to each edge of the graph representing the network of roads. This allows for flexible route calculation and gives a possibility of each necessary parameter choice to take it into account when calculating a path and determining their impact on the final result. This is achieved by considering all weights assigned to the edges of the graph and then multiplying them by weights assigned to them. This operation makes it possible to determine the impact that each factor should have on the final choice of route. This approach allows user for defining the optimal factors influencing the choice of routes and determine their significance.

Słowa kluczowe

PL

nawigacja; trasa przejazdu; optymalna trasa; wybór trasy

EN

navigation; transit route; optimal route; route selection

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 3
• Strony: 3206--3212
• Opis fizyczny: Bibliogr. 7 poz., rys., wykr., pełen tekst na CD

Twórcy

autor

Kozieł G.

• Instytut Informatyki, Wydział Elektrotechniki i Informatyki, Politechnika Lubelska, Nadbystrzycka 36b, 20-618 Lublin

Bibliografia

• 1. Chabini I., Discrete Dynamic Shortest Path Problems In Transportation Applications: Complexity And Algorithms With Optimal Run Time. Transportation Research Records , 1645:170–175, 1998
• 2. Colombo R. M., P. Goatin, and M. Rosini. On the modeling and management of traffic. Quaderni del Seminario Matematico di Brescia , 14, 2010
• 3. DongKai Fan ; Ping Shi , Improvement of Dijkstra's algorithm and its application in route planning , Fuzzy Systems and Knowledge Discovery (FSKD), 2010 Seventh International Conference, s. 1901 - 1904
• 4. Jasika N., et. al.,Dijkstra's shortest path algorithm serial and parallel execution performance analysis, MIPRO, 2012 Proceedings of the 35th International Convention , s. 1811 - 1815
• 5. Nikos Anastopoulos, Konstantinos Nikas, Georgios Goumas and Nectarios Koziris, „Employing Transactional Memory and Helper Threads to Speedup Dijkstra’s Algorithm“ ,2009
• 6. Shu Yang ; Chunhua Li, An enhanced routing method with Dijkstra algorithm and AHP analysis in GIS-based emergency plan , Geoinformatics, 2010 18th International Conference, s. 1-6
• 7. Wilson R.J., Wprowadzenie do teorii grafów, PWN, Warszawa 2000