A Demand-based Methodology for Urban Rail Transit Express Line Problem using Metaheuristic

Express line planning is an emerging area of transport planning that significantly reduces passenger travel time and minimizes transfer activities. This paper proposes an improved solution methodology for the Station Location Problem (SLP) and the Urban Rail Transit Routing Problem (URTRP). The methodology consists of two models for core station search and express line generation, considering existing Urban Rail Transit (URT) facilities. The approach incorporates enhanced initial solution generation procedures, novel perturbation operators, and iterative optimization processes in both trajectory-based and population-based concepts. The SLP model uses discretized population and employment distributions as demand sources while accounting for a non-fixed number of stations. It simulates user behaviour by incorporating demand attraction decay and facility selection preferences. After demand estimation, station locations are determined by maximizing the demand-to-cost ratio. Clustering algorithms are then applied to compress the station selection, retaining only the core stations for express line generation in the URTRP model. A modified Artificial Bee Colony algorithm is proposed to solve the SLP model, integrating batch mutation operations, random disturbances, and repair strategies to preserve higher-quality solutions and avoid stagnation. The URTRP model aims to minimize the expected average passenger travel time or total route length with consideration of the number of routes during optimization iterations. This model uses outputs from the SLP model, an origin–destination demand matrix, and existing URT routes as inputs to generate optimized transit route sets. The principle of Tabu Search is employed to solve the URTRP model, with improvements in three stages: initial feasible solution generation, neighbourhood generation, and sub-optimal solution reservation and filtering. Novel gradient perturbation operations are introduced to adaptively search the feasible solutions with the best trade-off between average travel time and total route time. Dynamic selection probabilities are updated in each iteration to choose perturbation operations that contribute significantly to solution improvement during neighborhood generation. Both models incorporate existing URT facilities and introduce related constraints to protect existing stations and routes from modification. The benchmark tests and comparisons with the traditional versions indicate that the improved Artificial Bee Colony and Tabu Search outperform the existing studies and increase passenger benefits with less cost. Real-world case studies are implemented to prove the adaptability of the proposed methods for practical express line planning applications.