Two-Phase Modeling of Metro Network Layouts Based on a Hybrid Path Searching Algorithm
Publication: Journal of Urban Planning and Development
Volume 146, Issue 3
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.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research work was supported by the National Key R&D Program of China under Grant Nos. 2018YFB1201403 and 2016YFB1200400. We deeply thank Yuan Li at Xi’an Municipal Engineering Institute for his assistance in data collection.
Notation
The following symbols are used in this paper:
- A
- link set;
- card()
- operator to get the number of elements in a set;
- Cm
- maximum capacity of a metro line during the peak hour;
- diag()
- diagonal matrix;
- G
- graph of adjacency network;
- link(i, j)
- link between node i and node j;
- N
- node set;
- p
- p-norm distance;
- Q
- total urban trips per day;
- s
- origin node;
- (s, t)
- O–D pair from s to t;
- TCi
- transit convenience of the ith zone;
- average transit convenience of the city;
- t
- destination node;
- U
- adjacency matrix;
- uij
- element of U;
- Vs,t
- desired transit demand from node s to node t;
- W
- impedance matrix;
- wij
- impedance of link(i, j);
- 0–1 variable in phase 1;
- Yij
- 0–1 variable in phase 2;
- α
- budget control coefficient;
- γ
- load intensity of a metro line;
- δ
- nonlinear coefficient;
- θ
- north or south latitude;
- ρm
- share rate of metro in residential trips; and
- φ
- the average transfer coefficient.
References
An, K., and K. L. Hong. 2016. “Two-phase stochastic program for transit network design under demand uncertainty.” Transp. Res. Part B: Meth. 84: 157–181. https://doi.org/10.1016/j.trb.2015.12.009.
Bruno, G., M. Gendreau, and G. Laporte. 2002. “A heuristic for the location of a rapid transit line.” Comput. Oper. Res. 29 (1): 1–12. https://doi.org/10.1016/S0305-0548(00)00051-4.
Bruno, G., G. Ghiani, and G. Improta. 1998. “A multi-modal approach to the location of a rapid transit line.” Eur. J. Oper. Res. 104 (2): 321–332. https://doi.org/10.1016/S0377-2217(97)00187-2.
Cadarso, L., and A. Marín. 2017. “Improved rapid transit network design model: Considering transfer effects.” Ann. Oper. Res. 258 (2): 547–567. https://doi.org/10.1007/s10479-015-1999-x.
Canca, D., A. De-Los-Santos, G. Laporte, and J. A. Mesa. 2016. “A general rapid network design, line planning and fleet investment integrated model.” Ann. Oper. Res. 246 (1–2): 1–18. https://doi.org/10.1007/s10479-014-1725-0.
Canca, D., A. De-Los-Santos, G. Laporte, and J. A. Mesa. 2017. “An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem.” Comput. Oper. Res. 78: 1–14. https://doi.org/10.1016/j.cor.2016.08.008.
Chakroborty, P. 2003. “Genetic algorithms for optimal urban transit network design.” Comput.-Aided Civ. Infrastruct. Eng. 18 (3): 184–200. https://doi.org/10.1111/1467-8667.00309.
Cipriani, E., S. Gori, and M. Petrelli. 2012. “Transit network design: A procedure and an application to a large urban area.” Transp. Res. Part C: Emerging Technol. 20 (1): 3–14. https://doi.org/10.1016/j.trc.2010.09.003.
Ding, R., N. Ujang, H. B. Hamid, M. S. A. Manan, R. Li, and J. Wu. 2017. “Heuristic urban transportation network design method, a multilayer coevolution approach.” Physica A 479: 71–83. https://doi.org/10.1016/j.physa.2017.02.051.
Ding, R., N. Ujang, H. B. Hamid, and J. Wu. 2015. “Complex network theory applied to the growth of Kuala Lumpur’s public urban rail transit network.” PLoS One 10 (10): e0139961. https://doi.org/10.1371/journal.pone.0139961.
Estrada, M., M. Roca-Riu, H. Badia, F. Robusté, and C. F. Daganzo. 2011. “Design and implementation of efficient transit networks: Procedure, case study and validity test.” Procedia 17: 113–135. https://doi.org/10.1016/j.sbspro.2011.04.510.
Gao, Z., J. Wu, and H. Sun. 2005. “Solution algorithm for the bi-level discrete network design problem.” Transp. Res. Part B: Meth. 39 (6): 479–495. https://doi.org/10.1016/j.trb.2004.06.004.
Gerçek, H., B. Karpak, and T. Kılınçaslan. 2004. “A multiple criteria approach for the evaluation of the rail transit networks in istanbul.” Transportation 31 (2): 203–228. https://doi.org/10.1023/B:PORT.0000016572.41816.d2.
Gutiérrez-Jarpa, G., C. Obreque, G. Laporte, and V. Marianov. 2013. “Rapid transit network design for optimal cost and origin-destination demand capture.” Comput. Oper. Res. 40 (12): 3000–3009. https://doi.org/10.1016/j.cor.2013.06.013.
Hasselgren, B. 2018. Transport infrastructure in time, scope and scale: Planning and coordination of transport infrastructure. Cham, Switzerland: Palgrave Macmillan.
Laporte, G., and M. M. B. Pascoal. 2015. “Path based algorithms for metro network design.” Comput. Oper. Res. 62: 78–94. https://doi.org/10.1016/j.cor.2015.04.007.
Li, P., Z. T. Zhu, J. Zhou, J. Y. Ding, H. W. Wang, and S. S. Wei. 2009. Complex sciences: Performance analysis of public transport systems in Nanjing based on network topology. Berlin: Springer.
Marín, A., and R. García-Ródenas. 2009. “Location of infrastructure in urban railway networks.” Comput. Oper. Res. 36 (5): 1461–1477. https://doi.org/10.1016/j.cor.2008.02.008.
Marín, A., and P. Jaramillo. 2009. “Urban rapid transit network design: Accelerated benders decomposition.” Ann. Oper. Res. 169 (1): 35–53. https://doi.org/10.1007/s10479-008-0388-0.
Nassir, N., M. Hickman, A. Malekzadeh, and E. Irannezhad. 2016. “A utility-based travel impedance measure for public transit network accessibility.” Transp. Res. Part A: Policy Pract. 88: 26–39. https://doi.org/10.1016/j.tra.2016.03.007.
Pradhan, A., and G. Mahinthakumar. 2013. “Finding all-pairs shortest path for a large-scale transportation network using parallel floyd-warshall and parallel dijkstra algorithms.” J. Comput. Civ. Eng. 27 (3): 263–273. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000220.
Samanta, S., and M. K. Jha. 2011. “Modeling a rail transit alignment considering different objectives.” Transp. Res. Part A: Policy Pract. 45 (1): 31–45. https://doi.org/10.1016/j.tra.2010.09.001.
Selvakumar, M., M. Abishek Reddy, V. Sathish, and R. Venkatesh. 2018. “Potential influence of metro on bus: A case study.” J. Inst. Eng. India Ser. A 99 (2): 379–384. https://doi.org/10.1007/s40030-018-0290-y.
Shaikh, A., and M. M. Ndiaye. 2013. “Mapping distance estimation functions by means of city parameter optimization.” Arab. J. Sci. Eng. 38 (5): 1281–1287. https://doi.org/10.1007/s13369-012-0359-2.
Song, L., F. Chen, K. Xian, and M. Sun. 2012. “Research on a scientific approach for bus and metro networks integration.” Procedia 43: 740–747. https://doi.org/10.1016/j.sbspro.2012.04.147.
Vira, C., and Y. Y. Haimes. 1983. Multiobjective decision making. theory and methodology. New York: North-Holland.
Watts, D. J., and S. H. Strogatz. 1998. “Collective dynamics of “small-world” networks.” Nature 393 (6684): 440–442. https://doi.org/10.1038/30918.
Information & Authors
Information
Published In
Journal of Urban Planning and Development
Volume 146 • Issue 3 • September 2020
Copyright
© 2020 American Society of Civil Engineers.
History
Received: Feb 1, 2019
Accepted: Apr 24, 2020
Published online: Jul 10, 2020
Published in print: Sep 1, 2020
Discussion open until: Dec 10, 2020
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.