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

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.