Abstract
This paper describes an algorithm that determines routes using three graphs: the railway graph, the train timetable graph and the summary timetable graph. The search in the timetable graphs is guided by a subgraph of the railway graph, which is defined by the nodes that form an ellipse around the minimum distance path from departure to arrival. We also present some performance evaluations of our proposed algorithm. Finally we describe an extension of this algorithm that can be used in conjunction with block agents to find routes in large timetable graphs, and some applications for medical domain.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bauer, R., Delling, D.: SHARC: Fast and Robust Unidirectional Routing. In: Proceedings of 10th Workshop of Algorithms and Engineering Experiments (ALENEX 2008), pp. 13–26. SIAM (April 2008)
Bauer, R., Delling, D., Wagner, D.: Experimental Study of Speed-up Techniques for Timetable Information Systems. Journal Networks 57, 38–52 (2011)
Dijkstra, E.W.: A Note on Two Problems Ion Connection with Graphs. Numerische Mathematic 1, 269–271 (1959)
Frede, L., Müller-Hannemann, M., Schnee, M.: Efficient On-trip Timetable Information in the Presence of Delays. In: ATMOS 2008, 8th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization and Systems, pp. 1–16 (2008)
Müller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.D.: Timetable Information: Models and Algorithms. In: Geraets, F., Kroon, L.G., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Railway Optimization 2004. LNCS, vol. 4359, pp. 67–90. Springer, Heidelberg (2007)
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Toward Realistic Modeling of Time-table Information Through the Time-dependent Approach. In: Proc. of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2003). ENTCS, vol. 92, pp. 85–103. Elsevier (2004)
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient Models for Timetable Information in Public Transportation Systems. ACM Journal of Experimental Algorithms 12, Article 2.4 (2007)
Salido, M.A., Abril, M., Barber, F., Ingolotti, L., Tormos, P., Lova, A.: Domain-Dependent Distributed Models for Railway Scheduling. Journal Knowledge Based Systems (Elsevier) 20, 186–194 (2007)
Schulz, F., Wagner, D., Zaroliagis, C.D.: Using Multi-level Graphs for Timetable Information in Railway Systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 43–59. Springer, Heidelberg (2002)
Tarjan, R.E.: A Note on Finding the Bridges of a Graph. Information Processing Letters 2(6), 160–161 (1974)
Wooldridge, M., Jennings, R.: Agent Theories, Architectures, and Languages: A Survey. Intelligent Agents, 1–22 (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Cozac, I. (2013). Route Search Algorithm in Timetable Graphs and Extension for Block Agents. In: Kountchev, R., Iantovics, B. (eds) Advances in Intelligent Analysis of Medical Data and Decision Support Systems. Studies in Computational Intelligence, vol 473. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-00029-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-00029-9_17
Publisher Name: Springer, Heidelberg
Print ISBN: 978-3-319-00028-2
Online ISBN: 978-3-319-00029-9
eBook Packages: EngineeringEngineering (R0)