More Web Proxy on the site http://driver.im/

article

A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling

Authors:

M. Fuchsberger,

R. ZenklusenAuthors Info & Claims

Transportation Science, Volume 45, Issue 2

Pages 212 - 227

https://doi.org/10.1287/trsc.1100.0349

Published: 01 May 2011 Publication History

Abstract

This paper addresses the problem of generating conflict-free train schedules on a microscopic model of the railway infrastructure. Conflicts arise if two or more trains are scheduled to block the same track section at the same time. A standard model for this problem is the so-called conflict graph, where each considered train path corresponds to a vertex, and edges represent pairwise conflicts so that a conflict-free schedule corresponds to a maximum independent set. Because the linear programming relaxation of the conflict graph formulation is typically very weak, we develop an alternative model using the sequence of resources that each train path passes, encoded in a resource tree. For each resource, we can efficiently determine the maximal conflict cliques by scanning through the blocking times of all train paths and use these cliques as strong cutting planes in an integer linear programming formulation. We show that the number of maximal conflict cliques is linear in the number of train paths, so the ILP formulation uses much fewer but stronger constraints compared to the conflict graph model. In tests with real-world data from the Swiss Federal Railways, the new Resource Tree Conflict Graph model generates for major stations within seconds, even though the underlying model contains about half a million binary variables. This corresponds to a reduction of the computation time of roughly two orders of magnitude when compared to previous approaches and thus allows us to tackle considerable larger problem instances.

References

[1]

Burkolter, D., "Capacity of railways in station areas using Petri nets," 2005.

[2]

Caimi, G., Burkolter, D., Herrmann, T. M., Fleuren, H., den Hertog, D. and Kort, P., "Finding delay-tolerant train routing through stations," Operations Research Proceedings 2004, GOR, Springer, Berlin, pp. 136-143, 2005.

[3]

Caimi, G., Fuchsberger, M., Laumanns, M. and Schüpbach, K., "Periodic railway timetabling with event flexibility," Networks, v57, pp. 3-18, 2011.

Digital Library

[4]

Caimi, G., Fuchsberger, M., Burkolter, D., Herrmann, T., Wüst, R., Roos, S. and Hansen, I., "Conflict-free train scheduling in a compensation zone exploiting the speed profile," Proc. 3rd Internat. Seminar Railway Oper. Modelling Anal. (RailZurich 2009), ETH, Zurich, Switzerland, 2009a.

[5]

Caimi, G., Herrmann, T. M., Burkolter, D., Chudak, F. and Laumanns, M., "Design of a railway scheduling model for dense services," Networks Spatial Econom., v9, pp. 25-46, 2009c.

[6]

Caprara, A., Galli, L., Toth, P., Liebchen, C., Ahuja, R. and Mesa, J., "Solution of the train platforming problem," ATMOS 2007, IBFI, Schloss Dagstuhl, Dagstuhl, Germany, 2007.

[7]

Caprara, A., Galli, L., Stiller, S. and Toth, P., "Recovery-robust platforming by network buffering," Proc. 3rd Internat. Seminar Railway Oper. Modelling Anal. (RailZurich 2009), I. Hansen, Zurich, Switzerland, 2009.

[8]

Carey, M., "A model and strategy for train pathing with choice of lines, platforms, and routes," Transportation Res. Part B, v28, pp. 333-353, 1994.

[9]

Carey, M. and Carville, S., "Scheduling and platforming trains at busy complex stations," Transportation Res. Part A, v37, pp. 195-224, 2003.

[10]

Chvátal, V., "On certain polytopes associated with graphs," J. Combin. Theory (B), v18, pp. 138-154, 1975.

[11]

Corman, F., Goverde, R. M. and D'Ariano, A., "Rescheduling dense train traffic over complex station interlocking areas," Robust and Online Large-Scale Optimization, v5868, Springer-Verlarg, Berlin, pp. 369-386, 2009.

[12]

Corman, F., D'Ariano, A., Pacciarelli, D. and Pranzo, M., "A tabu search algorithm for rerouting trains during rail operations," Transportation Res. Part B: Methodological, v44, pp. 175-192, 2010.

[13]

D'Ariano, A., Pacciarelli, A. and Pranzo, M., "A branch and bound algorithm for scheduling trains in a railway network," Eur. J. Oper. Res., v183, pp. 643-657, 2007.

[14]

Fischetti, M., Salvagnin, D. and Zanette, A., "Fast approaches to improve the robustness of a railway timetable," Transportation Sci., v43, pp. 321-335, 2009.

Digital Library

[15]

Gély, L., Dessagne, G., Pesneau, P. and Vanderbeck, F., A MultiScalable Model Based on a Connexity Graph Representation, WIT Press, Southampton, 2010.

[16]

Golumbic, M., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

[17]

Grötschel, M., Lovász, L. and Schrijver, A., Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1993.

[18]

Hansen, I. and Pachl, J., Railway Timetable and Traffic: Analysis, Modelling and Simulation, Eurailpress, Hamburg, Germany, 2008.

[19]

Herrmann, T. M., "Stability of timetables and train routings through station regions," 2005.

[20]

Kroon, L. G., "Fahrplanoptimierung mit mathematischen Modellen bei den Niederländischen Eisenbahnen," Eisenbahntechnische Rundschau, v6, pp. 359-362, 2008.

[21]

Kroon, L. G. and Maróti, G., "Robust train routing," 2008.

[22]

Kroon, L. G., Dekker, R., Vromans, M. J. C. M., Geraets, F., Kroon, L., Schoebel, A., Wagner, D. and Zaroliagis, C., "Cyclic railway timetabling: A stochastic optimization approach," Algorithmic Methods for Railway Optimization, Springer, Berlin, pp. 41-66, 2007.

[23]

Kroon, L. G., Romeijn, H. E. and Zwaneveld, P. J., "Routing trains through railway stations: Complexity issues," Eur. J. Oper. Res., v98, pp. 485-498, 1997.

[24]

Liebchen, C., "Periodic timetable optimization in public transport," 2006.

[25]

Liebchen, C. and Stiller, S., "Delay resistant timetabling," Public Transport, v1, pp. 55-72, 2009.

[26]

Liebchen, C., Lübbecke, M., Möhring, R. H. and Stiller, S., "The concept of recoverable robustness, linear programming recovery, and railway applications," Robust and Online Large-Scale Optimization, Springer, Berlin, pp. 1-27, 2009a.

[27]

Liebchen, C., Schachtebeck, M., Schöbel, A., Stiller, S. and Prigge, A., "Computing delay resistant railway timetables," Comput. Oper. Res., v37, pp. 857-868, 2010.

Digital Library

[28]

Lusby, R., "Routing trains through railway stations---A new set packing approach," Proc. 41th Annual Conf. Oper. Res. Soc., pp. 49-59, 2006.

[29]

Lusby, R., Larsen, J., Ryan, D. and Ehrgott, M., "Routing trains through railway junctions: A new set packing approach," 2006.

[30]

Lüthi, M., Medeossi, G. and Nash, A., "Structure and simulation evaluation of an integrated real-time rescheduling system for railway networks," Networks Spatial Econom., v9, pp. 103-121, 2008.

[31]

Odijk, M., Van den Berg, I., Murthy, T., Brebbia, C., Mellitt, B., Sciutto, G. and Sone, S., "DONS: Computer aided design of regular service timetables," Computers in Railways IV, Vol. 2, Railway Operations, WIT Press, Southampton, UK, pp. 109-116, 1994.

[32]

Pachl, J., Railway Operation and Control, VTD Rail Publishing, Mountlake Terrace, WA, 2002.

[33]

Pachl, J., Hansen, I. A. and Pachl, J., "Timetable design principles," Railway, Timetable and Traffic. Analysis, Modelling, Simulation, Eurailpress, Hamburg, Germany, pp. 9-42, 2008.

[34]

Radtke, A., Hansen, I. A. and Pachl, J., "Infrastructure Modeling," Railway Timetable and Traffic. Analysis, Modelling, Simulation, Eurailpress, Hamburg, Germany, pp. 43-57, 2008.

[35]

Radtke, A., Hauptmann, D., Allan, J., Hill, R., Brebbia, C., Sciutto, G. and Sone, S., "Automated planning of timetables in large railway networks using a microscopic data basis and railway simulation techniques," Computers in Railways IX, WIT Press, Southampton, UK, pp. 615-625, 2004.

[36]

Rodriguez, J., "A constraint programming model for real-time train scheduling at junctions," Transportation Res. Part B, v41, pp. 231-245, 2007.

[37]

"Geschäftsbericht 2008," 2008.

[38]

Schrijver, A., Combinatorial Optimization, Springer, Berlin, 2003.

[39]

Sewcyk, B., Radtke, A. and Wilfinger, G., "Combining microscopic and macroscopic infrastructure planning models," Proc. 2nd Internat. Seminar Railway Oper. Modeling Anal., International Association of Railway Operations Research, Hannover, Germany, 2007.

[40]

Tucker, A. C., "An efficient test for circular-arc graphs," SIAM J. Comput., v9, pp. 1-24, 1980.

Digital Library

[41]

"Prognosen für den Schienenverkehr," 2006.

[42]

Velasquez, R., Ehrgott, M., Ryan, D. and Schöbel, A., "A set-packing approach to routing trains through railway stations," Proc. 40th Annual Conf. Oper. Res. Soc., pp. 305-314, 2005.

[43]

Zwaneveld, P. J. and Kroon, L. G., "Stations: Final report of phase 1," 1995.

[44]

Zwaneveld, P. J., Kroon, L. G. and Van Hoesel, S. P. M., "Routing trains through a railway station based on a node packing model," Eur. J. Oper. Res., v128, pp. 14-33, 2001.

[45]

Zwaneveld, P. J., Kroon, L. G., Romeijn, H. E., Salomon, M., Dauzère-Pérès, S., van Hoesel, S. P. M. and Ambergen, H. W., "Routing trains through railway stations: Model formulation and algorithms," Transportation Sci., v30, pp. 181-194, 1996.

Digital Library

Cited By

Zhang JMagnouche YBauguion PMartin SBeck J(2024)Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-CutINFORMS Journal on Computing10.1287/ijoc.2023.012836:6(1634-1653)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1287/ijoc.2023.0128
Yin JYang LD’Ariano ATang TGao Z(2022)Integrated Backup Rolling Stock Allocation and Timetable Rescheduling with Uncertain Time-Variant Passenger Demand Under Disruptive EventsINFORMS Journal on Computing10.1287/ijoc.2022.123334:6(3234-3258)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1233
Pascariu BSamà MPellegrini PD’Ariano ARodriguez JPacciarelli D(2022)Performance Evaluation of a Parallel Ant Colony Optimization for the Real-Time Train Routing Selection Problem in Large InstancesEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-04148-8_4(46-61)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-04148-8_4
Show More Cited By

A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
      2. Mixed discrete-continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

A Mixed-Integer Linear Program for Routing and Scheduling Trains through a Railway Station
ICORES 2014: Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems

This paper studies a train routing and scheduling problem faced by railway station infrastructure managers to generate a conflict-free timetable which consists of two parts, commercial movements and technical movements. Firstly, we present the problem ...
Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph

In this paper a mixed integer set resulting from the intersection of a single constrained mixed 0-1 set with the vertex packing set is investigated. This set arises as a subproblem of more general mixed integer problems such as inventory routing and ...
A compact linear programming formulation of the maximum concurrent flow problem

We present an alternative linear programming formulation of the maximum concurrent flow problem MCFP termed the triples formulation. The standard formulations in the literature are the edge-path and node-edge formulations, which are known to be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Transportation Science

Transportation Science Volume 45, Issue 2

May 2011

138 pages

ISSN:1526-5447

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2011

Accepted: 01 August 2010

Received: 01 March 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang JMagnouche YBauguion PMartin SBeck J(2024)Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-CutINFORMS Journal on Computing10.1287/ijoc.2023.012836:6(1634-1653)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1287/ijoc.2023.0128
Yin JYang LD’Ariano ATang TGao Z(2022)Integrated Backup Rolling Stock Allocation and Timetable Rescheduling with Uncertain Time-Variant Passenger Demand Under Disruptive EventsINFORMS Journal on Computing10.1287/ijoc.2022.123334:6(3234-3258)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1233
Pascariu BSamà MPellegrini PD’Ariano ARodriguez JPacciarelli D(2022)Performance Evaluation of a Parallel Ant Colony Optimization for the Real-Time Train Routing Selection Problem in Large InstancesEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-04148-8_4(46-61)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-04148-8_4
Garg ARanade A(2021)Scheduling Trains with Small Stretch on a Unidirectional LineAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-67899-9_2(16-31)Online publication date: 11-Feb-2021
https://dl.acm.org/doi/10.1007/978-3-030-67899-9_2
Barah MSeifi AOstrowski J(2019)Decomposing the Train-Scheduling Problem into Integer-Optimal PolytopesTransportation Science10.1287/trsc.2018.084853:3(763-772)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1287/trsc.2018.0848
Kumar RSen GKar STiwari M(2018)Station Dispatching Problem for a Large TerminalInterfaces10.1287/inte.2018.095048:6(510-528)Online publication date: 5-Dec-2018
https://dl.acm.org/doi/10.1287/inte.2018.0950
Lamorgese LMannino CPiacentini M(2016)Optimal Train Dispatching by Benders'-Like ReformulationTransportation Science10.1287/trsc.2015.060550:3(910-925)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1287/trsc.2015.0605
Dollevoet THuisman DKroon LSchmidt MSchöbel A(2015)Delay Management Including Capacities of StationsTransportation Science10.1287/trsc.2013.050649:2(185-203)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1287/trsc.2013.0506
Huimin Niu Xiaopeng Tian Xuesong Zhou (2015)Demand-Driven Train Schedule Synchronization for High-Speed Rail LinesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2015.241551316:5(2642-2652)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TITS.2015.2415513
Pellegrini PMarliere GPesenti RRodriguez J(2015)RECIFE-MILP: An Effective MILP-Based Heuristic for the Real-Time Railway Traffic Management ProblemIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2015.241429416:5(2609-2619)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TITS.2015.2414294

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents