A Benders decomposition algorithm for demand-driven metro scheduling

Metro timetables are usually planned with a top-down approach. After dividing the day into different periods, the trains are scheduled between the terminals of the line with a fixed frequency per period. In this paper we adopt an alternative paradigm where trains are scheduled individually. The schedule is developed so as to best match the passenger demand, and trains may short-turn at intermediate stations, thus reversing their direction before reaching the line terminal. This type of approach is particularly suited for automated metro lines, since it has a limited impact on personnel management. Considering the objective of minimizing the passenger waiting times on a two-directional metro corridor, we make two operating assumptions when designing the train schedule. Specifically, we assume the presence of a root station, which cannot be skipped by short-turning, and we assume that idling is only allowed immediately after a short-turn, and for a maximum amount of time. We present a path-based formulation for the problem and develop an efficient exact algorithm for it using a Benders-based branch-and-cut algorithm. We evaluate the proposed formulation and algorithm on a number of test instances. Through our computational experiments, we demonstrate the effectiveness of the developed formulation and algorithm.