Abstract
Train scheduling plays an important role in the operation of railways systems. This work focuses on a model of scheduling in which one minimizes the total travel time of trains in a single track railways network. The model can be written in the form of a mixed 0–1 linear program which has the worst case exponential complexity to calculate the optimal solution. In this paper, we propose a computationally efficient approach to solve the train scheduling problem. Our approach is based on a so-called Difference of Convex functions Algorithm (DCA) to provide good feasible solutions with finite convergence. The algorithm is tested on three different railway network topologies including one topology introduced in [18] and two practical topologies in Northern Vietnam. The numerical results are encouraging and demonstrate the efficiency of the approach.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adenso-Diaz, B., Gonzalez, M.O., Gonzalez-Torre, P.: On-line timetable re-scheduling in regional train services. Transp. Res. Part B 33(6), 387–398 (1999)
Bussieck, M.R., Kreuzer, P., Zimmermann, U.T.: Optimal lines for railway systems. Eur. J. Oper. Res. 96(1), 54–63 (1997)
Cacchiani, V., Caprara, A., Toth, P.: A column generation approach to train timetabling on a corridor. 4OR 6(2), 125–142 (2008)
Cacchiani, V., Caprara, A., Toth, P.: Non-cyclic train timetabling and comparability graphs. Oper. Res. Lett. 38(3), 179–184 (2010)
Caimi, G., Fuchsberger, M., Laumanns, M., Luthi, M.: A model predictive control approach for discrete time rescheduling in complex central railway station areas. Comput. Oper. Res. 39(11), 2578–2593 (2012)
Caprara, A., Fischetti, M., Toth, P.: Modeling and solving the train timetabling problem. Oper. Res. 50(5), 851–861 (2002)
Castillo, E., Gallego, I., Urena, J.M., Coronado, J.M.: Timetabling optimization of a mixed double and single track rail network. Appl. Math. Model. 35(2), 859–878 (2011)
Chang, Y.H., Yeh, C.H., Shen, C.C.: A multiobjective model for passenger train services planning: application to Taiwan’s high-speed rail line. Transp. Res. Part B 34, 91–106 (2000)
Chen, B., Harker, P.T.: Two moments estimation of the delay on single-track rail lines with scheduled traffic. Transp. Sci. 24(4), 261–275 (1990)
Corman, F., D’Ariano, A., Pacciarelli, D., Pranzo, M.: A tabu search algorithm for rerouting trains during rail operations. Transp. Res. B 44(1), 175–192 (2010)
Corman, F., D’Ariano, A., Hansen, I.A., Pacciarelli, D.: Optimal multi-class rescheduling of railway traffic. J. Rail. Transp. Plan Manage. 1(1), 14–24 (2011)
D’Ariano, A., Pacciarelli, D., Pranzo, M.: A branch and bound algorithm for scheduling trains in a railway network. Eur. J. Oper. Res. 183, 643–657 (2007)
D’Ariano, A., Corman, F., Pacciarelli, D., Pranzo, M.: Reordering and local rerouting strategies to manage train traffic in real time. Transp. Sci. 42(4), 405–419 (2008)
Higgins, A., Kozan, E., Ferreira, L.: Optimal scheduling of trains on a single-line track. Transp. Res. Part B: Methodol. 30(2), 147–161 (1996)
Higgins, A., Kozan, E., Ferreira, L.: Heuristic techniques for single-line train scheduling. J. Heuristics 3, 43–62 (1997)
Jovanovic, D., Harker, P.T.: Tactical scheduling of rail operations: the SCAN I system. Transp. Sci. 25(1), 46–64 (1991)
Jong, J.-C., Chang, S., Lai, Y.-C.: Development of a two-stage hybrid method for solving high speed rail train scheduling problem. In: Proceedings of the Transportation Research Board 92nd Annual Meeting, Washington D.C., 13–17 January 2013
Karoonsoontawong, A., Taptana, A.: Branch-and-bound-based local search heuristics for train timetabling on single-track railway network. Netw. Spat. Econ. 17(1), 1–39 (2017)
Kraay, D.R., Harker, P.T.: Real-time scheduling of freight railroads. Transp. Res. Part B 29, 213–229 (1995)
Le Thi, H.A., Nguyen, Q.T., Tran, P.K., Pham Dinh, T.: DC programming and DCA based cross-layer optimization in multi-hop TDMA networks. In: ACIIDS 2013, LNCS, vol. 7803, pp. 398–408 (2013)
Le Thi, H.A., Nguyen, Q.T.: A robust approach for nonlinear UAV task assignment problem under uncertainty. Trans. Comput. Collective Intell. 2, 147–159 (2010)
Le Thi, H.A., Nguyen, Q.T., Huynh, T.N., Pham, D.T.: Solving the earliness tardiness scheduling problem by DC programming and DCA. Math. Balkanica (N.S.) 23(3-4), 271–288 (2009)
Le Thi, H.A., Pham, D.T.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world non convex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)
Le Thi, H.A., Pham, D.T., Le, D.M.: Exact penalty in DC programming. Vietnam J. Math. 27(2), 169–178 (1999)
Lee, Y., Chen, C.: A heuristic for the train pathing and timetabling problem. Transp. Res. Part B 43(8–9), 837–851 (2009)
Mu, S., Dessouky, M.: Scheduling freight trains traveling on complex networks. Transp. Res. Part B 45, 1103–1123 (2011)
Nguyen, Q.T., Le Thi, H.A.: Solving an inventory routing problem in supply chain by DC programming and DCA. In: ACIIDS 2011, LNCS, vol. 6592, pp. 432–441 (2011)
Petersen, E.R., Taylor, A.J., Martland, C.D.: An introduction to computer aided train dispatching. J. Adv. Transp. 20, 63–72 (1986)
Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnamica 22, 289–355 (1997). Dedicated to Professor Hoang Tuy on the occasion of his 70th birthday
Sahin, I.: Railway traffic control and train scheduling based on inter-train conflict management. Transp. Res. Part B 33(7), 511–534 (1999)
Szpigel, B.: Optimal train scheduling on a single track railway. Oper. Res. 72, 343–352 (1973). North-Holland, Amsterdam, Netherlands
Zhou, X., Zhong, M.: Single-track train timetabling with guaranteed optimality, branch-and-bound algorithms with enhanced lower bounds. Transp. Res. Part B 41, 320–341 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Thuan, N.Q., Anh, N.D. (2020). A Novel Approach for Travel Time Optimization in Single-Track Railway Networks. In: Le Thi, H., Le, H., Pham Dinh, T., Nguyen, N. (eds) Advanced Computational Methods for Knowledge Engineering. ICCSAMA 2019. Advances in Intelligent Systems and Computing, vol 1121. Springer, Cham. https://doi.org/10.1007/978-3-030-38364-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-38364-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-38363-3
Online ISBN: 978-3-030-38364-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)