Routing trains through railway stations: Complexity issues

DOI10.1016/S0377-2217(95)00342-8zbMath0930.90010OpenAlexW2125320823MaRDI QIDQ1278725

Peter J. Zwaneveld, H. Edwin Romeijn, Leo G. Kroon

Publication date: 22 February 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(95)00342-8

zbMATH Keywords

timetablingrailway transportationrouting trains

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06)

Related Items

Stability evaluation of a railway timetable at station level ⋮ A disjunctive graph model and framework for constructing new train schedules ⋮ Effective train routing selection for real-time traffic management: improved model and ACO parallel computing ⋮ Discrete optimization in public rail transport ⋮ Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances ⋮ Graph coloring-based approach for railway station design analysis and capacity determination ⋮ FREIGHT TRAIN ROUTING AND SCHEDULING IN A PASSENGER RAIL NETWORK: COMPUTATIONAL COMPLEXITY AND THE STEPWISE DISPATCHING HEURISTIC ⋮ A multiobjective optimization for train routing at the high-speed railway station based on tabu search algorithm ⋮ Railway track allocation: Models and methods ⋮ Real time management of a metro rail terminus ⋮ A sequencing approach for creating new train timetables ⋮ An adaptive memory programming method for risk logistics operations ⋮ Strategic timetable scheduling for last trains in urban railway transit networks ⋮ Sensitivity analysis of a railway station track layout with respect to a given timetable ⋮ Routing trains through a railway station based on a node packing model

Cites Work

• Unnamed Item
• On the computational complexity of (maximum) shift class scheduling
• Scheduling jobs with fixed start and end times
• On the computational complexity of (maximum) class scheduling
• License class design: Complexity and algorithms
• Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
• An analysis of shift class design problems
• The Fixed Job Schedule Problem with Spread-Time Constraints
• The Fixed Job Schedule Problem with Working-Time Constraints
• An Optimal Solution for the Channel-Assignment Problem
• Games of Boldness, Where the Player Performing the Hardest Task Wins
• Approximation Algorithms for Fixed Job Schedule Problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Minimal Resources for Fixed and Variable Job Schedules
• Routing Trains Through Railway Stations: Model Formulation and Algorithms
• On the facial structure of set packing polyhedra
• Depth-First Search and Linear Graph Algorithms