Optimal dispatching under uncertainty: With application to railroad scheduling

Improving the reliability of train operations is of major concern to the North American freight rail industry. Plausibly, a cost-effective strategy towards that goal is to adopt operating policies and decision support technology aimed at the production of achievable strategic/tactical train schedules and at reliable real-time execution of those schedules (e.g., train dispatching). We develop a novel simulation model to analyze an optimizing train dispatching process in scheduled rail operations under uncertainty, and an improved analytical line delay model (LDM). We then perform computational experiments to test certain operating policies and properties of the models. Initially, we review the larger research effort of developing a system-wide rail scheduling methodology. Emphasis is given to the changes in the dispatching process which are occurring from emerging technologies and market-oriented operating policies. We then develop a detailed stochastic discrete-event (rolling time horizon) simulation of the process which includes a minimum tardiness cost meet/pass algorithm and a replanning/rescheduling feature. We then develop the LDM formulated as a system of nonlinear equations of fixed point form, and the target time generator (TTG) as a calibration procedure for the LDM. In a series of simulation-based tests which assume optimal dispatching, we analyze the effect of departure time uncertainty inherent in dispatching environments on on-time performance, train delay, and the accuracy of LDM\u27s predictions. The problems are based on data collected by a major railroad. Our analysis indicates there may be opportunities to significantly increase both the reliability and productivity of train operations through improved train scheduling and schedule execution. For the problems we considered, LDM-derived target arrival times, when used in conjunction with an optimal dispatching algorithm, could achieve a substantial reduction in train transit times (tighter schedules) with no increase in tardiness. Our tests also indicate that, with more refined calibration, the LDM may for some applications provide a practical, rough cut alternative to simulation