Integrated bus bridging service design and vehicle scheduling considering passenger flow control strategy in an oversaturated metro network: A Lagrangian heuristic based on column generation

Due to the operational advantages of the metro system, an increasing number of passengers choose to travel by metro. However, since the system has limited capacity, it often becomes oversaturated during peak hours with heavy passenger flow. To alleviate the operational pressure on the metro system, we introduce flexible bus bridging services to supplement and enhance capacity based on the existing metro network. In this study, we propose an approach for the integrated optimization of bus transit planning and metro passenger flow control to recommend suitable travel routes for passengers. This approach primarily includes the following aspects: (1) Bus service design problem considering timetable optimization with uneven headways, (2) Multi-depot vehicle scheduling problem considering multi-route operations, and (3) Multi-commodity flow problem considering optimal passenger assignment in a multimodal transportation system with coordinated bus bridging services and train operations. The integrated optimization problem is constructed as an integer linear programming (ILP) model based on a space-time-mode network representation. To solve the model efficiently, we decompose it into three tractable subproblems with integer properties, and then develop a Lagrangian relaxation and column generation based heuristic (LR&CG-H) algorithm, in which the pricing problem for timetabling is constructed to iteratively generate promising bus service plans using a dynamic programming algorithm. Additionally, a series of numerical experiments are conducted on a small-scale artificial network and the real-world Beijing metro network to validate the effectiveness of the LR&CG-H algorithm and the superiority of the proposed integrated optimization model. The results demonstrate that: (1) compared with the GUROBI solver, the two-stage modeling framework, and the Lagrangian relaxation method, the proposed approach outperforms them in terms of computational efficiency, solution quality, and applicability to large-scale instances; and (2) through comparisons with different operational strategies, the proposed approach is shown to significantly alleviate metro system oversaturation while effectively balancing bus service levels with operating costs.