Parallel hierarchies for solving single source shortest path problem

• Autorzy: Chomątek Ł.
• Języki publikacji: EN

Abstrakty

EN

The problem of route optimization is significant due to the fact of the high availablity of private transport as well as the need of efficient utilization of the corporate fleet. Optimal route can have different meaning for different users. In the existing algorithms designed for finding optimal route between two points on the map, hardly any preferences are reflected. In this article we present efficient algorithm for finding optimal route between points on the map which is designed to conforms Users’ needs.

Słowa kluczowe

EN

single-source shortest path; parallel hierarchies; drivers' preferences

PL

wyszukiwanie najkrótszej ścieżki; hierarchie równoległe; preferencje kierowcy

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2013
• Tom: Vol. 21, nr 1
• Strony: 25--38
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Chomątek Ł.

• Lodz University of Technology, Institute of Information Technology, Wólczańska 215, 90-924 Lodz, Poland

Bibliografia

• [1] Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
• [2] Jacob, R., Marathe, M., and Nagel, K., A computational study of routing algorithms for realistic transportation networks, J. Exp. Algorithmics, Vol. 4, Dec. 1999.
• [3] Fu, L., Sun, D., and Rilett, L., Heuristic shortest path algorithms for transportation applications. State of the art, Computers and Operations Research, Vol. 33, No. 11, 2006, pp. 3324–3343.
• [4] Karimi, H., Real-time optimal route computation: A heuristic approach, ITS Journal, 1996.
• [5] Dantzig, G., On the shortest route through a network, Management Science, Vol. 6, 1960, pp. 187–90.
• [6] Goldberg, A. V. and Harrelson, C., Computing the shortest path: A search meets graph theory, In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’05, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2005, pp. 156–165.
• [7] Sanders, P. and Schultes, D., Engineering Highway Hierarchies. In: ESA, edited by Y. Azar and T. Erlebach, Vol. 4168 of Lecture Notes in Computer Science, Springer, 2006, pp. 804–816.
• [8] Delling, D., Sanders, P., Schultes, D., and Wagner, D., Engineering Route Planning Algorithms, In: ALGORITHMICS OF LARGE AND COMPLEX NETWORKS. LECTURE NOTES IN COMPUTER SCIENCE, Springer, 2009.
• [9] Chomatek, L. and Poniszewska-Maranda, A., Multi-agent System for Parallel Road Network Hierarchization, In: ICAISC (2), 2012, pp. 424–432.