RAILWAY JOURNEY PLANNER

Railway Journey Planner



Abstract

We consider the problem of train planning or scheduling for large, busy, complex train stations, which are common in Europe and elsewhere, though not in North America. We develop the constraints and objectives for this problem, but these are too computationally complex to solve by standard combinatorial search or integer programming methods. Also, the problem is somewhat political in nature, that is, it does not have a clear objective function because it involves multiple train operators with conflicting interests. We therefore develop scheduling heuristics analogous to those successfully adopted by train planners using “manual” methods. We tested the model and algorithms by applying to a typical large station that exhibits most of the complexities found in practice. The results compare well with those found by traditional methods, and take account of cost and preference trade-offs not handled by those methods. With successive refinements, the algorithm eventually took only a few seconds to run, the time depending on the version of the algorithm and the scheduling problem. The scheduling models and algorithms developed and tested here can be used on their own, or as key components for a more general system for train scheduling for a rail line or network.

Train scheduling for a busy station includes ensuring that there are no conflicts between several hundred trains per day going in and out of the station on intersecting paths from multiple in-lines and out-lines to multiple platforms, while ensuring that each train is allowed at least its minimum required headways, dwell time, turnaround time and trip time. This has to be done while minimizing (costs of) deviations from desired times, platforms or lines, allowing for conflicts due to through-platforms, dead-end platforms, multiple sub-platforms, and possible constraints due to infrastructure, safety or business policy.

Railway Journey Planner

Introduction

Most research on train planning and timetabling is concerned with scheduling trains on lines, usually single lines, and is not concerned with busy multi-platform stations with multiple in-lines and out-lines, or assumes these have unlimited capacity (Assad, 1980; Crainic, 1988; Petersen et al., 1986. E.R. Petersen, A.J. Taylor and C.D. Martland , An introduction to computer aided train dispatching. Journal of Advanced Transportation 20 (1986), pp. 63-72. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (19)Petersen et al., 1986; Jovanovic, 1989; Jovanovic and Harker, 1991; Kraay et al., 1991; Carey and Carey; Carey and Lockwood, 1995; Odijk, 1996 and a recent survey Cordeau et al., 1998). This is also true of unpublished work done by or for train or rail operators. However, in Europe busy complex rail stations are key components of the busy passenger rail networks, and are the location of most train conflicts. Since these are the most complex and parts of the network to schedule, we focus on them in the present paper.

Stations with several hundred, or over a thousand, trains per day are common throughout Europe and elsewhere. Such stations typically have multiple intersecting in-lines and out-lines, connected to multiple parallel or sequential ...