Two-phase decomposition method for the last train departure time choice in subway networks

An urban subway network with a number of service lines forms the backbone of the public transport system for a large city of high population, such as Singapore, Hong Kong and Beijing. Passengers in these large cities heavily rely on urban subway networks for their daily life. The departure times of the last trains running on different lines of an urban subway network should be well coordinated in order to serve more passengers who can successfully transfer from one line to another, which is referred to as the last train departure time choice problem. This study aims to develop a global optimization method that can solve the last train departure time choice problem for large-scale urban subway networks. To do so, it first formulates a mixed-integer linear programming (MILP) model by introducing auxiliary binary and integer decision variables. For the real-life and large-scale instances, however, the formulated MILP model cannot be solved directly by the global optimization methods such as branch-and-bound algorithm invoked by CPLEX – one of the powerful optimization solvers because of the instance sizes. An effective two-phase decomposition method is thus proposed to globally solve the large-scale problems by decomposing the original MILP into two MILP models with small sizes. Finally, a real case study from the Beijing subway network is conducted to assess the efficiency and applicability of the two-phase decomposition method and perform the necessary sensitivity analysis of the operational parameters involved in the last train departure time choice problem.