Route planning in dynamic graphs with linear changing and preprocessing for speed-up

• Autorzy: Szűcs G.

Warianty tytułu

PL

Planowanie podróży w dynamicznych grafach z uwzględnieniem wstępnie przetworzonego i zmieniającego się liniowo przyspieszenia

• Języki publikacji: EN

Abstrakty

EN

The goal of this paper is to work out a concept for route planning in a road network, where the costs of roads are not constant, but changing in a linear way. The solution developed is based on the classical Dijkstra's algorithm, which helps to find the route with minimal cost. The new algorithm takes the varying into account in order to find out the best route. This search refers not only to a moment of the departure but to the whole duration of the travel. A speed-up technique has been developed for preprocessing before run time. This preprocessing phase helps to give back the route with minimal cost for the user quickly in run time query. A numerical example has been presented to show the detailed steps of the algorithm and the speed-up technique.

PL

Celem artykułu jest wypracowanie koncepcji planowania tras (trasowania) w sieci drogowej, w której koszty połączeń nie są stałe, lecz zmieniają się w sposób liniowy. Zastosowane rozwiązanie opiera się na klasycznym algorytmie Dijkstra, który umożliwia znajdowanie tras po koszcie minimalnym. Proponowany algorytm uwzględnia dynamiczną różnorodność tras, w celu generowania najkorzystniejszej trasy. Jej poszukiwanie uwzględnia nie tylko momenty rozpoczęcia podróży, ale także czas trwania całej podróży. Technikę przyspieszania (speed-up) rozwinięto, w celu wstępnego przetwarzania przed fazą wykonania. Faza wstępnego przetwarzania pozwala szybciej pozyskać trasę, po koszcie minimalnym dla użytkownika. W artykule zostały zaprezentowane liczne przykłady, w których przedstawiono kolejne kroki algorytmu i techniki przyspieszania.

Słowa kluczowe

EN

route planning; road network; dynamic graph

PL

planowanie trasy; sieć drogowa; graf dynamiczny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Transport Problems
• Rocznik: 2010
• Tom: T. 5, z. 2
• Strony: 49--58
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Szűcs G.

• Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, 2nd Magyar Tudósok Krt. H-1117 Bld. I.B. Room 222, Budapest, Hungary,

Bibliografia

• 1. Cicerone S., Stefano G. D., Frigioni D., Nanni U.: A fully dynamic algorithm for distributed shortest paths, Theoretical Computer Science, Volume 297, Issues 1-3, 17 March, 2003, pp. 83-102.
• 2. Daunoras J., Bagdonas V., Gargasas V.: City transport monitoring and routes optimal management system, Transport. Vol. 23, No. 2, pp. 144-149.
• 3. Delling D., Wagner D.: Landmark-Based Routing in Dynamic Graphs. In: 6th Workshop on Experimental Algorithms (WEA), 2007, pp. 52-65.
• 4. Demetrescu C. Italiano G. F.: Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures, Journal of Discrete Algorithms, Volume 4, Issue 3, September, 2006, pp. 353-383.
• 5. Demetrescu C., Italiano G. F.: Fully dynamic all pairs shortest paths with real edge weights, Journal of Computer and System Sciences, Volume 72, Issue 5, August, 2006, pp. 813-837.
• 6. Dijkstra E. W.: A note on two problems in connexion with graphs. In Numerische Mathematik, Volume 1, Amsterdam, The Netherlands: Mathematisch Centrum. 1959, pp. 269-271.
• 7. Frigioni D., Marchetti-Spaccamela A., Nanni U.: Fully dynamic shortest paths in digraphs with arbitrary arc weights, Journal of Algorithms, Volume 49, Issue 1, October, 2003, pp. 86-113.
• 8. Goldberg A.V., Harrelson C.: Computing the shortest path: A* meets graph theory. In: 16th ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 156-165.
• 9. Goldberg A.V., Werneck R.F.: An efficient external memory shortest path algorithm. In: Algorithm Engineering and Experimentation (ALENEX), 2005, pp. 26-40.
• 10. Gutman R. J.: Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX) and the First Workshop on Analytic Algorithmics and Combinatorics (ANALCO), New Orleans, LA, USA, Philadelphia, PA, USA, SIAM, 2004, pp. 100-111.
• 11. Hart P.J., Nilsson N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4. 1968, pp. 100-107.
• 12. Kiisler. A.: Logistics in Estonian business companies, Transport. 2008, Vol. 23, No. 4, pp. 356-362.
• 13. Köhler E., Möhring R.H., Schilling H., Hilger, M.: Fast Point-to-Point Shortest Path Computation with Arc-Flags. In: 9th DIMACS Challenge on Shortest Paths, 2006.
• 14. Lauther, U.: Slow preprocessing of graphs for extremely fast shortest path calculations, Lecture at the Workshop on Computational Integer Programming at ZIB, 1997.
• 15. Lauther, U.: An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In: Geoinformation und Mobilitat - von der Forschung zur praktischen Anwendung, Volume 22., IfGI prints, Institut für Geoinformatik, Münster, 2004, pp. 219-230.
• 16. Likhachev M., Ferguson D., Gordon G., Stentz A., Thrun S.: Anytime search in dynamic graphs, Artificial Intelligence, Volume 172, Issue 14, September, 2008, pp. 1613-1643.
• 17. Matis P.: Decision support system for solving the street routing problem, Transport, 2008. Vol. 23, No. 3, pp. 230-235.
• 18. Möhring R. H., Schilling H., Schütz B., Wagner D., Willhalm T.: Partitioning graphs to speed up Dijkstra’s algorithm. In: 4th International Workshop on Efficient and Experimental Algorithms, 2005, pp. 189-202.
• 19. Sanders P., Schultes D.: Highway hierarchies hasten exact shortest path queries. In 13th European Symposium, on Algorithms (ESA), Volume 3669 of LNCS, Springer, 2005, pp 568-579.
• 20. Sanders P, Schultes D.: Engineering highway hierarchies. In: 14th European Symposium on Algorithms (ESA), Volume 4168 of LNCS, Springer, 2006. 804-816