Integrating train service route design with passenger flow allocation for an urban rail transit line

Train service design problem considers many operating strategies, i.e., multiple service routes, multiple train compositions, and express/local modes. Incorporating multiple operating strategies, this study first formulates an integer linear programming model for integrating train service route design with the passenger flow allocation problem. Consistency between the two components is enforced by a set of linking constraints that consider the relationship between the number of transit trips assigned to a route and the capacity of a single train. To solve the proposed model on real-life instances, we develop an approach that utilizes the Alternating Direction Method of Multipliers (ADMM). This dualizes the linking constraints and decomposes the problem into two subproblems: a train service route design subproblem and a passenger flow allocation subproblem. The latter can be subdivided into a set of passenger group-specific subproblems and is solved by a label correcting algorithm. Through Lagrangian multipliers, the interplay between the train service route design and passenger flow allocation subproblems is explored. To address the nonlinearities that arise in ADMM, we describe a new linearization technique for the quadratic penalty terms in the two subproblems by exploiting the rolling update mechanism of ADMM. The proposed approach is tested on synthetic and real-life instances from an urban rail company in China. The numerical results show that the proposed ADMM approach provides objective values that are on average 7.63% better than the conventional sequential approach. We also demonstrate that ADMM provides smaller optimality gaps in general when compared to a Lagrangian relaxation approach.