×
Castillo, Enrique; Gallego, Inmaculada; Ureña, José María; Coronado, José María

Timetabling optimization of a mixed double- and single-tracked railway network. (English) Zbl 1205.90118

Appl. Math. Modelling 35, No. 2, 859-878 (2011).
Summary: The paper deals with the timetabling problem of a mixed multiple- and single-tracked railway network. Out of all the solutions minimizing the maximum relative travel time, the one minimizing the sum of the relative travel times is selected. User preferences are taken into account in the optimization problems, that is, the desired departure times of travellers are used instead of artificially planned departure times. To find the global optimum of the optimization problem, an algorithm based on the bisection rule is used to provide sharp upper bounds of the objective function together with one trick that allows us to drastically reduce the number of binary variables to be evaluated by considering only those which really matter. These two strategies together permit the memory requirements and the computation time to be reduced, the latter exponentially with the number of trains (several orders of magnitude for existing networks), when compared with other methods. Several examples of applications are presented to illustrate the possibilities and excellences of the proposed method. The model is applied to the case of the existing Madrid-Sevilla high-speed line (double track), together with several extensions to Toledo, Valencia, Albacete, and Málaga, which are contemplated in the future plans of the high-speed train Spanish network. The results show that the computation time is reduced drastically, and that in some corridors single-tracked lines would suffice instead of double-tracked lines.

Cited in 11 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90B10 Deterministic network models in operations research
90B06 Transportation, logistics and supply chain management
90C26 Nonconvex programming, global optimization

Keywords:

train timetabling; bisection method; global optimum; objective function upper bound
PDF BibTeX XML Cite
\textit{E. Castillo} et al., Appl. Math. Modelling 35, No. 2, 859--878 (2011; Zbl 1205.90118)
Full Text: DOI

References:

[2] Carey, M., A model and strategy for train pathing with choice of lines, platforms and routes, Transp. Res. Part B, 28, 5, 333-353 (1994)
[3] Carey, M.; Lockwood, D., A model, algorithms and strategy for train pathing, J. Oper. Res. Soc., 46, 8, 988-1005 (1995) · Zbl 0832.90068
[4] Higgins, A.; Kozan, E.; Ferreira, L., Optimal scheduling of trains on a single line track, Transp. Res. Part B, 30, 2, 147-161 (1996)
[5] Cordeau, J. F.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transp. Sci., 32, 4, 380-404 (1998) · Zbl 0987.90507
[6] Zhou, X.; Zhong, M., Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds, Transp. Res. B, 41, 3, 320-341 (2007)
[7] Sahin, I., Railway traffic control and train scheduling based on inter-train conflict management, Transp. Res. Part B, 33, 7, 511-534 (1999)
[8] Jia, L-M.; Zhang, X-D., Distributed intelligent railway traffic control based on fuzzy decision making, Fuzzy Sets Syst., 62, 3, 255-265 (1993)
[9] Kraay, D. R.; Harker, P. T., Real-time scheduling of freight railroads, Transp. Res. Part B, 29, 3, 213-229 (1995)
[11] D’Ariano, A.; Pranzo, M.; Hansen, I. A., Conflict resolution and train speed coordination for solving real-time timetable perturbations, IEEE Trans. Intell.Transp. Syst., 8, 2 (2007)
[13] Törnquist, J.; Persson, J. A., N-tracked railway traffic re-scheduling during disturbances, Transp. Res. B, 41, 3, 342-362 (2007)
[14] Petersen, E. R.; Taylor, A. J.; Martland, C. D., An introduction to computer aided train dispatching, J. Adv. Transp., 20, 63-72 (1986)
[15] Ghoseiri, K.; Szidarovszky, F.; Asgharpour, M. J., A multi-objective train scheduling model and solution, Transp. Res. Part B, 38, 10, 927-952 (2004)
[17] Amit, I.; Goldfarb, D., The timetable problem for railways, Dev. Oper. Res., 2, 379-387 (1971)
[18] Assad, A., Models for rail transportation, Transp. Res. Part A, 14, 3, 205-220 (1980)
[19] Haghani, A. E., Rail freight transportation: a review of recent optimization models for train routing and empty car distribution, J. Adv. Transp., 21, 147-172 (1987)
[20] Frank, O., Two-way traffic on a single line of railway, Oper. Res., 14, 801-811 (1965) · Zbl 0149.38201
[22] Petersen, E. R.; Taylor, A. J., A structured model for rail line simulation and optimization, Transp. Sci., 16, 2, 192-206 (1982)
[24] Komaya, K.; Fukuda, T., ESTRAC-III: An expert system for train track control in disturbed situations, (Perrin, J. P., IFAC Control, Computers, Communications in Transportation, IFAC/IFIP/IFORS Symposium, Paris, France, 19-21 September, 1989 (1989), Published for the International Federation of Automatic Control by Pergamon Press: Published for the International Federation of Automatic Control by Pergamon Press Paris, France), 147-153
[25] Komaya, K.; Fukuda, T., A knowledge-based approach for railway scheduling, (Proceedings of the Seventh IEEE Conference on Artificial Intelligence for Applications (1991), IEEE Computer Society Press), 404-411
[26] Komaya, K., An integrated framework of simulation and scheduling in railway systems, (Murthy, T. K.S.; Allan, J.; Hill, R. J.; Sciutto, G.; Sone, S., Computers in Railways III. Computers in Railways III, Management, vol. 1 (1992), Computational Mechanics Publications: Computational Mechanics Publications Southampton, Boston), 611-622
[29] Szpigel, B., Optimal train scheduling on a single track railway, (Operations Research’72 (1973), North-Holland: North-Holland Amsterdam, Netherlands), 343-352
[30] Jovanovic, D.; Harker, P. T., Tactical scheduling of rail operations: The SCAN I system, Transp. Sci., 25, 1, 46-64 (1991)
[31] Kraay, D.; Harker, P. T.; Chen, B., Optimal pacing of trains in freight railroads: model formulation and solution, Oper. Res., 39, 82-99 (1991)
[32] Carey, M., Extending a train pathing model from one-way to two-way track, Transp. Res. Part B, 28, 5, 395-400 (1994)
[33] Brannlund, U.; Lindberg, P. O.; Nou, A.; Nilsson, J. E., Railway timetabling using Lagrangian relaxation, Transp. Sci., 32, 4, 358-369 (1998) · Zbl 1004.90035
[34] Castillo, E.; Gallego, I.; Ureña, J. M.; Coronado, J. M., Timetabling optimization of a single railways track line with sensitivity analysis, TOP, 17, 2, 256-287 (2009) · Zbl 1181.90063
[36] Zhou, X.; Zhong, M., Bi-criteria train scheduling for high-speed passenger railroad planning applications, Eur. J. Oper. Res., 167, 3, 752-771 (2005) · Zbl 1077.90033
[37] Törnquist, J., Railway traffic disturbance management, Transp. Res. Part A: Policy Pract., 41, 3, 249-266 (2007)
[38] D’Ariano, A.; Pacciarelli, D.; Pranzo, M., A branch and bound algorithm for scheduling trains in a railway network, Eur. J. Oper. Res., 183, 2, 643-657 (2007) · Zbl 1179.90135
[39] Cai, X.; Goh, C. J.; Mees, A. I., Greedy heuristics for rapid scheduling of trains on a single track, IIE Trans., 30, 5, 481-493 (1998)
[40] Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Oper. Res., 50, 5, 851-861 (2002) · Zbl 1163.90482
[41] Greenberg, H. H., A branch-and-bound solution to the general scheduling problem, Oper. Res., 16, 2, 352-361 (1968) · Zbl 0155.28704
[42] Adenso-Diaz, B.; González, M. O.; González-Torre, P., On-line timetable re-scheduling in regional train services, Transp. Res. Part B, 33, 6, 387-398 (1999)
[43] Higgins, A.; Kozan, E., Modeling train delays in urban networks, Transp. Sci., 32, 4, 346-357 (1998) · Zbl 0987.90518
[45] Dorfman, M. J.; Medanic, J., Scheduling trains on a railway network using a discrete event model of railway traffic, Transp. Res. Part B, 38, 1, 81-98 (2004)
[46] Vansteenwegen, P.; Van Oudheusden, D., Decreasing the passenger waiting time for an intercity rail network, Transp. Res. Part B, 41, 4, 478-492 (2007)
[47] Carey, M.; Crawford, I., Scheduling trains on a network of busy complex stations, Transp. Res. Part B, 41, 1, 159-178 (2007)
[48] Castillo, E.; Hadi, A. S.; Conejo, A.; Fernández-Canteli, A., A General Method for local sensitivity analysis with application to regression models and other optimization problems, Technometrics, 46, 430-444 (2004)
[49] Castillo, E.; Conejo, A. J.; Mı´nguez, R.; Castillo, C., A closed formula for local sensitivity analysis in mathematical programming, Eng. Optim., 38, 1, 93-112 (2006)
[50] Castillo, E.; Conejo, A. J.; Castillo, C.; Mínguez, R., Closed formulas in local sensitivity analysis for some classes of linear and non-linear problems, TOP, 15, 2, 355-371 (2007) · Zbl 1145.90087
[51] Castillo, E.; Conejo, A. J.; Pedregal, P.; García, R.; Alguacil, N., Building and Solving Mathematical Programming Models in Engineering and Science. Building and Solving Mathematical Programming Models in Engineering and Science, Pure and Applied Mathematics (2001), Wiley: Wiley New York · Zbl 1029.90001
[52] Conejo, A.; Castillo, E.; Mínguez, R.; García-Bertrand, R., Decomposition Techniques in Mathematical Programming. Decomposition Techniques in Mathematical Programming, Engineering and Science Applications (2006), Springer: Springer Berlin, Heildelberg · Zbl 1186.90002
[53] Castillo, E.; Conejo, A.; Castillo, C.; Mínguez, R.; Ortigosa, D. A., Perturbation approach to sensitivity analysis in nonlinear programming, Journal of Optimization Theory and Applications, 128, 1, 49-74 (2006) · Zbl 1130.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.