×

Exact formulations and algorithm for the train timetabling problem with dynamic demand. (English) Zbl 1307.90067

Summary: In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

PESPLib
Full Text: DOI

References:

[1] Bussieck, M. R.; Winter, T.; Zimmermann, U. T., Discrete optimization in public rail transport, Math Programming, 79, 1-3, 415-444 (1997) · Zbl 0887.90055
[2] Cacchiani, V.; Toth, P., Nominal and robust train timetabling problems, Eur J Oper Res, 219, 3, 727-737 (2012) · Zbl 1253.90108
[3] Cacchiani, V.; Caprara, A.; Toth, P., A column generation approach to train timetabling on a corridor, Q J Oper Res, 6, 2, 125-142 (2008) · Zbl 1151.90323
[4] Cacchiani, V.; Caprara, A.; Toth, P., Non-cyclic train timetabling and comparability graphs, Oper Res Lett, 38, 3, 179-184 (2010) · Zbl 1187.90092
[5] Cacchiani, V.; Caprara, A.; Toth, P., Scheduling extra freight trains on railway networks, Transp Res Part BMethodol, 44, 2, 215-231 (2010)
[6] Cai, X.; Goh, C. J.; Mees, A. I., Greedy heuristics for rapid scheduling of trains on a single track, IIE Trans, 30, 481-493 (1998)
[7] Caimi, G.; Fuchsberger, M.; Laumanns, M.; Schüpbach, K., Periodic railway timetabling with event flexibility, Networks, 57, 1, 3-18 (2011) · Zbl 1205.90117
[8] Caimi, G.; Laumanns, M.; Schüpbach, K.; Wörner, S.; Fuchsberger, M., The periodic service intention as a conceptual framework for generating timetables with partial periodicity, Transp Plann Technol, 34, 4, 323-339 (2011)
[9] Canca, D.; Zarzo, A.; Algaba, E.; Barrena, E., Confrontation of different objectives in the determination of train scheduling, Proc Soc Behav Sci, 20, 302-312 (2011)
[11] Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Oper Res, 50, 5, 851-861 (2002) · Zbl 1163.90482
[12] Caprara, A.; Monaci, M.; Toth, P.; Guida, P. L., A Lagrangian heuristic algorithm for a real-world train timetabling problem, Discrete Appl Math, 154, 5, 738-753 (2006) · Zbl 1120.90324
[13] Caprara, A.; Monaci, M.; Toth, P.; Guida, P. L., A Lagrangian heuristic approach to real-world train timetabling problems, Discrete Appl Math, 154, 738-753 (2006) · Zbl 1120.90324
[14] Chierici, A.; Cordone, R.; Maja, R., The demand-dependent optimization of regular train timetables, Electron Notes Discrete Math, 17, 99-104 (2004) · Zbl 1152.90435
[15] 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
[16] Cordone, R.; Redaelli, F., Optimizing the demand captured by a railway system with a regular timetable, Transp Res Part BMethodol, 45, 2, 430-446 (2011)
[17] Guihaire, V.; Hao, J. K., Transit network design and schedulinga global review, Transp Res Part APolicy Pract, 42, 1251-1273 (2008)
[18] Huisman, D.; Kroon, L. G.; Lentink, R. M.; Vromans, M. J.C. M., Operations research in passenger railway transportation, Stat Neerl, 59, 7, 467-497 (2005) · Zbl 1149.90435
[19] Ingolotti, L.; Lova, A.; Barber, F.; Tormos, P.; Salido, M. A.; Abril, M., New heuristics to solve the CSOP railway timetabling problem, (Ali, M.; Dapoigny, R., Advances in applied artificial intelligence. Lecture notes in artificial intelligence, vol. 4031 (2006), Springer: Springer Berlin, Heidelberg), 400-409
[20] Kroon, L. G.; Dekker, R.; Vromans, M. J.C. M., Cyclic railway timetablinga stochastic optimization approach, (Geraets, F.; Kroon, L. G.; Schoebel, A.; Wagner, D.; Zaroliagis, C. D., Algorithmic methods for railway optimization. Lecture notes on computer science, vol. 4359 (2007), Springer: Springer Berlin, Heidelberg), 41-66
[21] Kroon, L. G.; Marti, G.; Helmrich, M. R.; Vromans, M. J.C. M.; Dekker, R., Stochastic improvement of cyclic railway timetables, Transp Res Part BMethodol, 42, 6, 553-570 (2008)
[22] Kroon, L. G.; Huisman, D.; Abbink, E.; Fioole, P.-J.; Fischetti, M.; Maróti, G., The new Dutch timetablethe OR revolution, Interfaces, 39, 1, 6-17 (2009)
[23] Larson, R. C.; Odoni, A. R., Urban operations research (1981), Prentice-Hall: Prentice-Hall New York
[24] Liebchen, C.; Möhring, R., A case study in periodic timetabling, Electron Notes Theor Comput Sci, 66, 6, 1-14 (2002)
[25] Liebchen, C.; Peeters, L., Integral cycle bases for cyclic timetabling, Discrete Optim, 6, 1, 89-109 (2009) · Zbl 1160.90640
[27] Nachtigall, K.; Voget, S., A genetic algorithm approach to periodic railway synchronization, Electron Notes Theor Comput Sci, 23, 5, 453-463 (1996) · Zbl 0847.90098
[28] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM J Discrete Math, 2, 4, 550-581 (1989) · Zbl 0676.90030
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.