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

A railroad infrastructure microscopic model for conflict-free train schedule generation is addressed in this paper. When more than one train is simultaneously scheduled to block the same track section, conflicts arise. The so-called conflict graph is a standard model for this issue, where edges represent pairwise conflicts and each considered train path corresponds to a vertex, allowing conflict-free schedules to correspond to a maximum independent set. The authors develop an alternative model since the conflict graphics formulation linear programming relaxation typically is very weak. The alternative model is developed by using, encoded in a resource tree, the sequence of resources each train path passes. By scanning through all train path blocking times and using these cliques as strong integer linear programming formulation cutting planes, the authors can determine efficiently the maximum conflict cliques for each resource. The authors show that in the number of train paths, the number of maximal conflict cliques is linear, so significantly fewer but stronger constraints are used by the ILP formulation in comparison with the conflict graph model. The new Resource Tree Conflict Graph model was generated, in tests using Swiss Federal Railway's real world data, for major stations within seconds, although about half a million binary variables are contained in the underlying model. When compared with previous approaches, the test findings correspond to reduced computation time of roughly two orders of magnitude. Thus, it allows the authors to tackle considerably larger problems.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Authors:
  • Caimi, G
  • Chudak, F
  • Fuchsberger, M
  • Laumanns, M
  • Zenklusen, R
• Publication Date: 2011-5

Language

• English

Media Info

• Media Type: Print
• Features: Bibliography; Figures; Tables;
• Pagination: pp 212-227
• Serial:
  • Transportation Science
  • Volume: 45
  • Issue Number: 2
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Linear programming; Mathematical models; Railroad facilities; Railroad traffic; Routes and routing; Schedules and scheduling
• Identifier Terms: Schweizerische Bundesbahnen
• Uncontrolled Terms: Blocking (Schedules); Computation time; Conflict analysis; Microscopic models; Multi-commodity network flow; Path analysis; Resource planning; Tree analysis; Tree classification
• Subject Areas: Operations and Traffic Management; Planning and Forecasting; Railroads; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01342346
• Record Type: Publication
• Files: TRIS
• Created Date: Jun 21 2011 12:00PM