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

Document Type

Journal Article

Publication Date


Subject Area

place - asia, place - urban, mode - subway/metro, operations - scheduling, planning - integration


Urban subway networks, Last train departure time choice, Mixed-integer linear programming, Global optimization method, Two-phase decomposition method


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.


Permission to publish the abstract has been given by Elsevier, copyright remains with them.


Transportation Research Part B Home Page: