Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: Mixed-integer linear programming approaches. (March 2017)

• Record Type: Journal Article
• Authors: Yin, Jiateng; Yang, Lixing; Tang, Tao; Gao, Ziyou; Ran, Bin
• Is Part Of: Transportation research. Volume 97(2017)
• Page Start: 182
• Page End: 213
• Publication Date: 2017-03
• Subjects: Metro train scheduling -- Energy efficiency -- Dynamic passenger demands -- Space-time network -- Regenerative energy; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2017.01.001
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: Two linear programming models are formulated for the metro train scheduling problem. The first model minimizes the train traction energy consumption and passenger waiting time. The second model further considers the utilization of regenerative braking energy. A Lagrangian relaxation-based algorithm is developed for solving large-scale cases. Abstract: In the daily operation of metro systems, the train scheduling problem aims to find a set of space-time paths for multiple trains that determine their departure and arrival times at metro stations, while train operations are in charge of selecting the best operational speed to satisfy the punctuality and operation costs. Different from the most existing researches that treat these two problems separately, this paper proposes an integrated approach for the train scheduling problem on a bi-direction urban metro line in order to minimize the operational costs (i.e., energy consumption) and passenger waiting time. More specifically, we simultaneously consider (1) the train operational velocity choices that correspond to the energy consumption of trains on each travelling arc, and (2) the dynamic passenger demands at each station for the calculation of total passenger waiting time in the planning horizon. By employing a space-time network representation in the formulations, this complex train scheduling and control problem with dynamic passenger demands is rigorously formulated into two optimization models with linear forms. The first model is an integer programming model that jointly minimizes train traction energy consumption and passenger waiting time. The second model, which is formulated as a mixed-integer programming model, further considers the utilization of regenerative braking energy on the basis of the first model. Due to the computational complexity of these two models, especially for large-scale real-world instances, we develop a Lagrangian relaxation (LR)-based heuristic algorithm that decomposes the primal problem into two sets of subproblems and thus enables to find a good solution in short computational time. Finally, two sets of numerical experiments, involving a relatively small-scale case and a real-world instance based on the operation data of Beijing metro are implemented to verify the effectiveness of the proposed approaches.