Improving railroad on-time performance: Models, algorithms and applications

Poor on-time performance and the resulting low level of service is one of the most important problems of railroads in many developed countries; in developing countries, inadequate capacity of mostly single-tracked railway lines and scarce funds for capital improvements are becoming the major problems. This dissertation addresses these issues by presenting a methodological framework and decision support tools aimed at the design of feasible and, ultimately, reliable train schedules at the tactical level, and at the better capacity utilization through optimal computer-aided train dispatching (CAD) in real-time.; The biggest obstacle to the successful implementation of an optimal CAD system is the combinatorial nature of the optimal train dispatching problem and the need for optimization algorithms that could provide good solutions in a real-time environment. We develop novel lower-bound based algorithms for the minimum tardiness cost train dispatching problem: an exact algorithm and a heuristic. It is shown by extensive numerical tests based on real-world data that the developed algorithms represent a dramatic improvement upon the current state-of-the-art enumeration-based algorithms. The new algorithms enable a single CAD system to handle larger traffic volumes and cover planning horizons and larger dispatching territories then currently possible, while providing for optimal or near-optimal ways to move the trains over the railroad line.; The optimal train dispatching framework proposed in this dissertation attempts to fill the void in the literature regarding the use of and the benefits from a CAD system. It is argued that the primary purpose of dispatching tools is to allow trains to arrive on-time rather than to minimize total train delays. The potential of optimal CAD to minimize train lateness is illustrated on examples.; The tactical scheduling decision support methodology was implemented and illustrated within the Schedule Analyzer (SCAN II) software package. SCAN focuses on schedules by removing bias introduced by historical and stochastic data used by simulation models. Use of SCAN by a large railroad and evaluation of a number of real-world train schedules has confirmed the hypothesis that the poor on-time performance is in part due to the inadequate scheduling. Creation of robust train schedules remains a challenge.