A Benders decomposition algorithm for demand-driven metro scheduling. (February 2022)
- Record Type:
- Journal Article
- Title:
- A Benders decomposition algorithm for demand-driven metro scheduling. (February 2022)
- Main Title:
- A Benders decomposition algorithm for demand-driven metro scheduling
- Authors:
- Schettini, Tommaso
Jabali, Ola
Malucelli, Federico - 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.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. … (more)
- Is Part Of:
- Computers & operations research. Volume 138(2022)
- Journal:
- Computers & operations research
- Issue:
- Volume 138(2022)
- Issue Display:
- Volume 138, Issue 2022 (2022)
- Year:
- 2022
- Volume:
- 138
- Issue:
- 2022
- Issue Sort Value:
- 2022-0138-2022-0000
- Page Start:
- Page End:
- Publication Date:
- 2022-02
- Subjects:
- Metro scheduling -- Short-turning -- Demand-driven -- Benders decomposition
Operations research -- Periodicals
Electronic digital computers -- Periodicals
004.05 - Journal URLs:
- http://www.sciencedirect.com/science/journal/03050548 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.cor.2021.105598 ↗
- Languages:
- English
- ISSNs:
- 0305-0548
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.770000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 20075.xml