Bi-objective conflict detection and resolution: Minimizing train delays and maximizing passenger connections

Railway timetables define routes, orders and timings for all trains running in the network. Usually, timetables provide good connectivity between different train services for a number of origins and destinations. For each pair of connected train services, the waiting train is scheduled to depart sufficiently later with respect to its feeder train in order to allow the movement of passengers from one train to the other. During operations, train traffic can be seriously disturbed by delays, accidents or technical problems. Major disturbances cause primary delays that propagate as consecutive delays to other trains in the network, thus requiring short-term adjustments to the timetable in order to limit delay propagation. This real-time problem is known as Conflict Detection and Resolution (CDR). Keeping transfer connections when solving the CDR problem increases delay propagation (Vromans, 2005), therefore one of the possible dispatching countermeasures to handle disturbances is the cancellation of some scheduled connections. This action reduces the overall train delays but has a negative impact on passenger satisfaction for the transferring passengers affected by missed connections. Train operating companies are therefore interested in keeping as many connections as possible even in the presence of disturbed traffic conditions, while infrastructure managers are mainly interested in limiting train delays. In fact, infrastructure managers discuss with train operating companies on which connections must be kept when regulating railway traffic. To support this negotiation process, this paper deals with a Bi-objective Conflict Detection and Resolution (BCDR) problem (Corman et al, 2010), i.e., the problem of finding a set of feasible schedules with a good trade-off between the minimization of train delays and the maximization of respected transfer connections. The BCDR problem is closely related to the Delay Management (DM) problem introduced by Schobel (2001). The latter problem adopts a passenger point of view, and aims at the minimization of the sum of all delays over all passengers at their final destination. In this paper we choose a train point of view, i.e., the minimization of train delays at all relevant