×
Zwaneveld, Peter J.; Kroon, Leo G.; van Hoesel, Stan P. M.

Routing trains through a railway station based on a node packing model. (English) Zbl 0982.90004

Eur. J. Oper. Res. 128, No. 1, 14-33 (2001).
Summary: We describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into acount.
In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.

Cited in 17 Documents

MSC:

90B06 Transportation, logistics and supply chain management
90B20 Traffic problems in operations research
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

railway transportation; timetabling; routing trains; node packing problem; branch-and-cut

Software:

PESPLib; CPLEX
PDF BibTeX XML Cite
\textit{P. J. Zwaneveld} et al., Eur. J. Oper. Res. 128, No. 1, 14--33 (2001; Zbl 0982.90004)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Using the CPLEX callable Library, Version 3.0, CPLEX Optimization, 1994 (Manual)
[2] J. Bourachot, Computer-aided planning of traffic in large stations by means of the AFAIG model, Railway International May (1986) 2-18
[3] J. Bourachot, Conception assistée par ordinateur de l’exploitation et de l’aménagement des gares ferroviaires voyageurs: Modèle interactif graphique AFAIG, Ph.D. thesis, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, 1984
[4] A. Hertz, On a graph transformation that preserves the stability number, Working Paper OR 97/11, Ecole Polytechnique Fédérale de Lausanne, Switzerland, 1997
[5] Hoffman, K.L.; Padberg, M., Solving airline crew scheduling problems by branch-and-cut, Management science, 39, 6, 657-682, (1993) · Zbl 0783.90051
[6] Kroon, L.G.; Romeijn, H.E.; Zwaneveld, P.J., Routing trains through railway stations: complexity issues, European journal of operational research, 98, 485-498, (1997) · Zbl 0930.90010
[7] L.G. Kroon, P.J. Zwaneveld, STATIONS: Final report of phase 1, ERASM Management Report Series no. 201, Rotterdam School of Management, Erasmus University Rotterdam, Rotterdam, Netherlands, 1995
[8] C. Mannino, A. Sassano, Edge projection and the maximum stable set problem, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Università di Roma la Sapienza, Italy, 1995 · Zbl 0864.90122
[9] Nemhauser, G.L.; Sigismondi, G., A strong cutting plane branch-and-bound algorithm for node packing, Journal of operational research society, 43, 5, 443-457, (1992) · Zbl 0756.90067
[10] Padberg, M.W., On the facial structure of set packing polyhedra, Mathematical programming, 5, 199-215, (1973) · Zbl 0272.90041
[11] A. Schrijver, A. Steenbeek, Dienstregeling ontwikkeling voor Railned (Timetable development for Railned), Report Cadans 1.0, C.W.I., Amsterdam, Netherlands, 1994
[12] Serafini, P.; Ukovich, W., Mathematical model for periodic scheduling problems, SIAM journal on discrete mathematics, 2, 550-581, (1989) · Zbl 0676.90030
[13] P.J. Zwaneveld, Railway Planning – routing of trains and allocation of passenger lines, Ph.D. thesis, Erasmus University Rotterdam, Rotterdam, the Netherlands, 1997
[14] P.J. Zwaneveld, S. Dauzère-Peres, C.P.M van Hoesel, L.G. Kroon, H.E. Romeijn, M. Salomon, H.W. Ambergen, Routing trains through railway stations: Model formulation and algorithms, Transportation Science, 30 (3) (1996) 181-194 · Zbl 0884.90079
[15] P.J. Zwaneveld, L.G. Kroon, H.W. Ambergen, A decision support system for routing trains through railway stations, in: Proceedings of Comp Rail 96, Berlin, Computational Mechanics Publications, Southampton, 1996, pp. 217-226
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.