A Benders decomposition algorithm for demand-driven metro scheduling. (February 2022)

• Record Type: Journal Article
• Authors: Schettini, Tommaso; Jabali, Ola; Malucelli, Federico
• Is Part Of: Computers & operations research. Volume 138(2022)
• Publication Date: 2022-02
• Subjects: Metro scheduling -- Short-turning -- Demand-driven -- Benders decomposition; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105598
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: We introduce a demand-driven scheduling strategy for metro lines. We develop an efficient Benders-based branch-and-cut algorithm for the problem. We derive closed-form solutions to the sub-problems. We propose an effective method to reduce the size of the instances. We demonstrate the effectiveness of the proposed algorithm.