×

zbMATH — the first resource for mathematics

Non-cyclic train timetabling and comparability graphs. (English) Zbl 1187.90092
Summary: We consider the customary formulation of non-cyclic train timetabling, calling for a maximum-profit collection of compatible paths in a suitable graph. The associated ILP models look for a maximum-weight clique in a (n exponentially-large) compatibility graph. By taking a close look at the structure of this graph, we analyze the existing ILP models, propose some new stronger ones, all having the essential property that both the separation and the column generation can be carried out efficiently, and report the computational results on highly-congested instances.

MSC:
90B20 Traffic problems in operations research
90B10 Deterministic network models in operations research
PDF BibTeX Cite
Full Text: DOI
References:
[1] ARRIVAL. Research Project, 6th Framework Program, http://arrival.cti.gr/.
[2] Brännlund, U.; Lindberg, P.O.; Nöu, A.; Nilsson, J.E., Allocation of scarce track capacity using Lagrangian relaxation, Transportation science, 32, 358-369, (1998) · Zbl 1004.90035
[3] Cacchiani, V.; Caprara, A.; Toth, P., A column generation approach to train timetabling on a corridor, 4or, 6, 125-142, (2008) · Zbl 1151.90323
[4] Cacchiani, V.; Caprara, A.; Toth, P., Scheduling extra freight trains on railway networks, Transportation research B, 44B, 2, 215-231, (2010)
[5] V. Cacchiani, A. Caprara, P. Toth, Non-cyclic train timetabling and comparability graphs, Research Report OR/10/1 DEIS, 2010. Available at:http://www.or.deis.unibo.it/alberto/ttp_clique_web.pdf. · Zbl 1187.90092
[6] Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Operations research, 50, 851-861, (2002) · Zbl 1163.90482
[7] Caprara, A.; Kroon, L.; Monaci, M.; Peeters, M.; Toth, P., Passenger railway optimization, (), 129-187
[8] Caprara, A.; Lancia, G.; Ng, S.K., Sorting permutations by reversals through branch-and-price, INFORMS journal on computing, 13, 224-244, (2001) · Zbl 1238.90100
[9] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer-Verlag · Zbl 0634.05001
[10] Savelsbergh, Martin, A branch-and-price algorithm for the generalized assignment problem, Operations research, 45, 831-841, (1997) · Zbl 0895.90161
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.