Multithreaded enhancements of the Dijkstra algorithm for route optimization in urban networks

• Autorzy: Bazan M. , Ciskowski P. , Dudek R. , Halawa K. , Janiczek T. , Kozaczewski P. , Rusiecki A.
• Języki publikacji: PL

Abstrakty

EN

In this paper, we present a case study, showing step by step, how to speed up Dijkstra’s method by parallelizing its computation and using different data structures. We compare basic algorithm with its bidirectional version and investigate two-and-multi-thread implementations based on Fibonacci heaps and regular priority queues. Experimental results obtained for artificially generated graphs as well as real-world road network data are presented and described.

Słowa kluczowe

PL

algorytm Dijkstry; najkrótsza ścieżka; najszybsza trasa; sieć miejska; optymalizacja trasy

EN

Dijkstra algorithm; shortest paths; fastest routes; urban networks; route optimization

• Wydawca: Polskie Stowarzyszenie Telematyki Transportu
• Czasopismo: Archives of Transport System Telematics
• Rocznik: 2016
• Tom: Vol. 9, iss. 2
• Strony: 3--7
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Bazan M.

• Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland

autor

Ciskowski P.

• Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland

autor

Dudek R.

• Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland

autor

Halawa K.

• Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland

autor

Janiczek T.

• Wrocław University of Technology, Faculty of Electronics, Department of Control Systems and Mechatronics, ul. Janiczewskiego 11/17, 50-372 Wrocław, Poland

autor

Kozaczewski P.

• Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland

autor

Rusiecki A.

• Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland

Bibliografia

• [1] BAST, H., et al.: Route Planning in Transportation Networks, Technical Report of Microsoft Research, January 2014.
• [2] CRAUSER, A., et al.: A Parallelization of Dijkstra’s Shortest Path Algorithm, in MFCS’98, LNCS 1450, pp. 722-731, Springer-Verlag 1998.
• [3] DELLING, D., WAGNER, D.: Time-dependent route planning, in Robust and Online Large-Scale Optimization, LNCS 5868, pp. 207–230, Springer 2009.
• [4] DELLING D., et al.: Engineering Route Planning Algorithms in: Algorithmics, LNCS 5515, pp. 117–139, Springer-Verlag 2009.
• [5] DUDEK, R.: Analysis and evaluation of a set of shortest paths of passing on traffic control system, Thesis, Wroclaw University of Technology 2014.
• [6] JASIKA, N., et al.: Dijkstra’s shortest path algorithm serial and parallel execution performance analysis, MIPRO 2012, May 21-25, Croatia 2012.
• [7] KARLSSON, B.: Beyond the C++ Standard Library: An Introduction to Boost, Addison-Wesley 2006.
• [8] LEDA Homepage: http://www.algorithmic-solutions.com/leda/index.htm, [date of access: 05.01.2016].
• [9] Open Street Map Homepage: https://www.openstreetmap.org, [date of access: 05.01.2016].