Abstract
In this paper, we consider the problem of finding itineraries in bus networks under multiple independent optimization criteria, namely arrival time at destination and number of transfers. It is also allowed to walk from one stop to another if the two stops are located within a small distance. A time–dependent model is proposed to solve this problem. While focusing on the network where the size of the Pareto set in the multi–criteria shortest path problem might grow exponentially, we develop an efficient algorithm with its speed–up techniques. An evaluation on the qualities of found paths and the empirical results of different implementations are given. The results show that the allowance of walking shortcuts between nearby stops gives a better route planning.
Chapter PDF
Similar content being viewed by others
Keywords
References
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)
Schulz, F., Wagner, D., Weihe, K.: Dijkstra’s Algorithm On-Line: An Empirical Case Study from Public Railroad Transport. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 110–123. Springer, Heidelberg (1999)
Müller-Hannemann, M., Schnee, M.: Finding All Attractive Train Connections by Multi-criteria Pareto Search. In: Geraets, F., Kroon, L.G., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Railway Optimization 2004. LNCS, vol. 4359, pp. 246–263. Springer, Heidelberg (2007)
Brodal, G.S., Jacob, R.: Time–dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theoretical Computer Science 92, 3–15 (2004)
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Towards Realistic Modeling of Timetable Information through the Time–Dependent Approach. Electronic Notes in Theoretical Computer Science 92, 85–103 (2004)
Disser, Y., Müller–Hannemann, M., Schnee, M.: Multi-criteria Shortest Paths in Time-Dependent Train Networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 347–361. Springer, Heidelberg (2008)
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Experimental comparison of shortest path approaches for timetable information. In: 6th Workshop on Algorithm Engineering and Experiments (ALENEX04), pp. 88–99. SIAM (2004)
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient Models for Timetable Information in Public Transportation Systems. Journal of Experimental Algorithmics (JEA) 12, Article No. 2.4 (2008)
Skriver, A.J.V., Andersen, K.A.: A label correcting approach for solving bicriterion shortest path problems. Computers & Operations Research 27, 507–524 (2000)
Gandibleux, X., Beugnies, F., Randriamasy, S.: Martins’ algorithm revisited for multi–objective shortest path problems with a MaxMin cost function. In: 4OR, vol. 4, pp. 47–59 (2006)
Martins, E.Q.V., Santos, J.L.: The labeling algorithm for multicriteria shortest path problem. Departamento de Matematica, Universidade de Coimbra, Portugal (1999)
Brumbaugh, J., Smith: An empirical investigation of some bicriterion shortest path algorithms. European Journal of Operational Research 43, 216–224 (1989)
Mote, J., Murthy, I., Olson, D.L.: A parametric approach to solving bicriterion shortest path problems. European Journal of Operational Research 53, 81–92 (1991)
Paixao, J.M., Santos, J.L.: Labeling methods for the general case of the multiobjective shortest path problem–a computational study. Intelligent Systems, Control and Automation: Science and Engineering 61, 489–502 (2013)
Mali, G., Michail, P., Zaroliagis, C.: Faster multiobjective heuristic search in road maps. In: Proceedings ICT, vol. 3, pp. 67–72 (2012)
Dijkstra, E.W.: A note on two problems in connection with graphs. Numerische Mathematik 1, 269–271 (1959)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Khoa, V.D., Pham, T.V., Nguyen, H.T., Van Hoai, T. (2014). Multi–criteria Route Planning in Bus Network. In: Saeed, K., Snášel, V. (eds) Computer Information Systems and Industrial Management. CISIM 2015. Lecture Notes in Computer Science, vol 8838. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45237-0_49
Download citation
DOI: https://doi.org/10.1007/978-3-662-45237-0_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45236-3
Online ISBN: 978-3-662-45237-0
eBook Packages: Computer ScienceComputer Science (R0)