Abstract
Every human likes choices. But today’s fast route planning algorithms usually compute just a single route between source and target. There are beginnings to compute alternative routes, but there is a gap between the intuition of humans what makes a good alternative and mathematical definitions needed for grasping these concepts algorithmically. In this paper we make several steps towards closing this gap: Based on the concept of an alternative graph that can compactly encode many alternatives, we define and motivate several attributes quantifying the quality of the alternative graph. We show that it is already NP-hard to optimize a simple objective function combining two of these attributes and therefore turn to heuristics. The combination of the refined penalty based iterative shortest path routine and the previously proposed Plateau heuristics yields best results. A user study confirms these results.
Partially supported by DFG grant SA 933/5-1, and the ‘Concept for the Future’ of Karlsruhe Institute of Technology within the framework of the German Excellence Initiative.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dijkstra, E.: A note on two problems in connexion with graphs. Numerische mathematik 1(1), 269–271 (1959)
Dees, J.: Computing Alternative Routes in Road Networks. Master’s thesis, Karlsruhe Institut für Technologie, Fakultät für Informatik (April 2010)
Dees, J., Geisberger, R., Sanders, P., Bader, R.: Defining and Computing Alternative Routes in Road Networks. Technical report, ITI Sanders, Faculty of Informatics, Karlsruhe Institute of Technology (2010)
Eppstein, D.: Finding the k shortest paths. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1994), pp. 154–165 (1994)
Yen, J.Y.: Finding the K Shortest Loopless Paths in a Network. Management Science 17(11), 712–716 (1971)
Scott, K.: Finding alternatives to the best path (1997)
Hansen, P.: Bricriteria Path Problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making – Theory and Application, pp. 109–127. Springer, Heidelberg (1979)
Martins, E.Q.: On a Multicriteria Shortest Path Problem. European Journal of Operational Research 26(3), 236–245 (1984)
Delling, D., Wagner, D.: Pareto Paths with SHARC. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 125–136. Springer, Heidelberg (2009)
Chen, Y., Bell, M.G.H., Bogenberger, K.: Reliable pre-trip multi-path planning and dynamic adaptation for a centralized road navigation system. In: ITSC 2005 - 8th International IEEE Conference on Intelligent Transportation Systems, Vienna, pp. 14–20. IEEE, Los Alamitos (2007)
Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 66–79. Springer, Heidelberg (2007)
CAMVIT: Choice routing (2009), http://www.camvit.com
Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Alternative routes in road networks. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 23–34. Springer, Heidelberg (2010)
de Queiros Vieira Martins, E., Queir, E., Martins, V., Margarida, M., Pascoal, M.M.B.: A new implementation of yen’s ranking loopless paths algorithm (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bader, R., Dees, J., Geisberger, R., Sanders, P. (2011). Alternative Route Graphs in Road Networks. In: Marchetti-Spaccamela, A., Segal, M. (eds) Theory and Practice of Algorithms in (Computer) Systems. TAPAS 2011. Lecture Notes in Computer Science, vol 6595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19754-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-19754-3_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19753-6
Online ISBN: 978-3-642-19754-3
eBook Packages: Computer ScienceComputer Science (R0)