Two-Phase Modeling of Metro Network Layouts Based on a Hybrid Path Searching Algorithm

Abstract

The planning of a metro network layout is important in alleviating traffic congestion, guiding land exploitation, and promoting urban development. This paper proposes a hybrid model of two-phase formulation based on path searching to determine the structure layout of a metro network. A selection of origin–destination (O–D) pairs is first performed to filter out ineffective O–D pairs outside of the major distance range of metro trips, where the distance is calculated under p-norm. To further reduce the searching space, a K-shortest paths (KSP) algorithm is devised to generate the subnetwork for each O–D pair. As a rapid transit network design problem (RTNDP), the model is formulated in two phases by integer programming. The optimal path of each O–D pair is determined in phase 1 considering objectives of construction cost and nodes demand capture, and a constraint of the path length control is specially constructed to avoid bad solutions with meandering paths. In phase 2, a model is developed to integrate optimal links into a network depending on the aggregate transit demand under constraints such as link capacity and graph connectivity. Meanwhile, the procedures of the model and algorithm are comprehensively designed, with interactions between the geographic information system (GIS) database and mathematical programming solvers. Finally, applications of the two-phase model are illustrated with a real example. The evaluation results indicate that the proposed model can enhance the network connectivity and line capacity usage, and fit better with the transit demand inside the urban area.