×

Designing metro network expansion: deterministic and robust optimization models. (English) Zbl 07797532

Summary: The design and construction of metro networks are typically conducted in stages due to the ongoing growth of urbanization and investment in public transportation systems. Designing new metro lines within an existing metro network is challenging as passenger flow patterns will be significantly updated and change. This study investigates new line designing in an existing metro network, also known as the metro network expansion design problem, and develops two optimization models to maximize the origin-destination (OD) demand capture under a limited budget. The first is a deterministic binary integer linear programming model, while the second is a robust optimization model that considers the demand uncertainty. The paper proposes a section-based modeling strategy to make the issue tractable and consider mode competition with other transport modes to capture the attracted demand by new metro lines. The models are applied to a real-world case in Wuxi, China, to validate their applicability and computational efficiency. The results showed satisfactory metro network expansion patterns with good connections between new lines and existing networks. The deterministic model can identify corridors and sections with higher priorities under tight budget conditions. A sensitivity analysis indicates that passengers’ concerns about travel time and fares are conducive to constructing the metro network. Furthermore, the advantage of the robust solution becomes critical as the demand variation increases. The robust optimization model can provide a more reliable and competitive solution than the deterministic model under large demand variation scenarios.

MSC:

90Bxx Operations research and management science
90Cxx Mathematical programming
81Txx Quantum field theory; related classical field theories
Full Text: DOI

References:

[1] Al-Najjar, Y.; Ben-Ameur, W.; Leguay, J., On the approximability of robust network design, Theor Comput Sci, 860, 41-50 (2021) · Zbl 1500.90007 · doi:10.1016/j.tcs.2021.01.026
[2] An, K.; Lo, HK, Robust transit network design with stochastic demand considering development density, Transp Res Pt B-Methodol, 81, 3, 737-754 (2015) · doi:10.1016/j.trb.2015.05.019
[3] Atamturk, A.; Zhang, M., Two-stage robust network flow and design under demand uncertainty, Oper Res, 55, 4, 662-673 (2007) · Zbl 1167.90409 · doi:10.1287/opre.1070.0428
[4] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math Oper Res, 23, 4, 769-805 (1998) · Zbl 0977.90052 · doi:10.1287/moor.23.4.769
[5] Bertsimas, D.; Sim, M., The price of robustness, Oper Res, 52, 1, 35-53 (2004) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065
[6] Bourbonnais, PL; Morency, C.; Trepanier, M.; Martel-Poliquin, E., Transit network design using a genetic algorithm with integrated road network and disaggregated o-d demand data, Transportation, 48, 1, 95-130 (2021) · doi:10.1007/s11116-019-10047-1
[7] Burggraeve, S.; Vansteenwegen, P., Robust routing and timetabling in complex railway stations, Transp Res Pt B-Methodol, 101, 228-244 (2017) · doi:10.1016/j.trb.2017.04.007
[8] Cacchiani, V.; Qi, J.; Yang, L., Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty, Transp Res Pt B-Methodol, 136, 1-29 (2020) · doi:10.1016/j.trb.2020.03.009
[9] Canca, D.; De-Los-Santos, A.; Laporte, G.; Mesa, JA, Integrated railway rapid transit network design and line planning problem with maximum profit, Transp Res Pt E-Logist Transp Rev, 127, 1-30 (2019) · doi:10.1016/j.tre.2019.04.007
[10] Canca D, De-Los-Santos A, Laporte G, Mesa JA (2019b) The railway rapid transit network construction scheduling problem. Comput Ind Eng 138 · Zbl 1391.90049
[11] Cats, O.; Krishnakumari, P., Metropolitan rail network robustness, Physica A, 549 (2020) · doi:10.1016/j.physa.2020.124317
[12] Ceder, A.; Wilson, NH, Bus network design, Transp Res Pt B-Methodol, 20, 4, 331-344 (1986) · doi:10.1016/0191-2615(86)90047-0
[13] Chakroborty, P., Genetic algorithms for optimal urban transit network design, Comput-Aided Civil Infrastruct Eng, 18, 3, 184-200 (2003) · doi:10.1111/1467-8667.00309
[14] Chen, J.; Liu, Z.; Wang, S.; Chen, X., Continuum approximation modeling of transit network design considering local route service and short-turn strategy, Transp Res Pt E-Logist Transp Rev, 119, 165-188 (2018) · doi:10.1016/j.tre.2018.10.001
[15] Escudero, LF; Monge, JF; Rodríguez-Chía, AM, On pricing-based equilibrium for network expansion planning. a multi-period bilevel approach under uncertainty, Eur J Oper Res, 287, 1, 262-279 (2020) · Zbl 1443.90262 · doi:10.1016/j.ejor.2020.03.048
[16] Fan, W.; Machemehl, RB, Tabu search strategies for the public transportation network optimizations with variable transit demand, Comput-Aided Civil Infrastruct Eng, 23, 7, 502-520 (2008) · doi:10.1111/j.1467-8667.2008.00556.x
[17] Farahani, R.; Miandoabchi, E.; Szeto, W.; Rashidi, H., A review of urban transportation network design problems, Eur J Oper Res, 229, 2, 281-302 (2013) · Zbl 1317.90047 · doi:10.1016/j.ejor.2013.01.001
[18] Fragkos, I.; Cordeau, JF; Jans, R., Decomposition methods for large-scale network expansion problems, Transp Res Pt B-Methodol, 144, 60-80 (2021) · doi:10.1016/j.trb.2020.12.002
[19] Guan, JF; Yang, H.; Wirasinghe, SC, Simultaneous optimization of transit line configuration and passenger line assignment, Transp Res Pt B-Methodol, 40, 10, 885-902 (2006) · doi:10.1016/j.trb.2005.12.003
[20] Gutiérrez-Jarpa, G.; Obreque, C.; Laporte, G.; Marianov, V., Rapid transit network design for optimal cost and origin-destination demand capture, Comput Oper Res, 40, 12, 3000-3009 (2013) · Zbl 1348.90664 · doi:10.1016/j.cor.2013.06.013
[21] Gutiérrez-Jarpa, G.; Laporte, G.; Marianov, V.; Moccia, L., Multi-objective rapid transit network design with modal competition: The case of concepción, chile, Comput Oper Res, 78, 27-43 (2017) · Zbl 1391.90400 · doi:10.1016/j.cor.2016.08.009
[22] Gutiérrez-Jarpa, G.; Laporte, G.; Marianov, V., Corridor-based metro network design with travel flow capture, Comput Oper Res, 89, 58-67 (2018) · Zbl 1391.90114 · doi:10.1016/j.cor.2017.08.007
[23] Jha, SB; Jha, J.; Tiwari, MK, A multi-objective meta-heuristic approach for transit network design and frequency setting problem in a bus transit system, Comput Ind Eng, 130, 166-186 (2019) · doi:10.1016/j.cie.2019.02.025
[24] Jin, JG; Nieto, H.; Lu, L., Robust bike-sharing stations allocation and path network design: a two-stage stochastic programming model, Transp Lett, 12, 10, 682-691 (2020) · doi:10.1080/19427867.2019.1691299
[25] Król A, Król M (2019) The design of a metro network using a genetic algorithm. Appl Sci 9(3) · Zbl 1442.81048
[26] Laporte, G.; Pascoal, MMB, Path based algorithms for metro network design, Comput Oper Res, 62, 78-94 (2015) · Zbl 1348.90157 · doi:10.1016/j.cor.2015.04.007
[27] Laporte, G.; Mesa, JA; Ortega, FA, Locating stations on rapid transit lines, Comput Oper Res, 29, 6, 741-759 (2002) · Zbl 0995.90062 · doi:10.1016/S0305-0548(00)00013-7
[28] Laporte G, Marín Á, Mesa JA, Ortega FA (2007) An integrated methodology for the Rapid Transit Network Design Problem. In: Geraets, F (ed) Algorithmic Methods for Railway Optimization, Springer, Heidelberg, Lecture Notes in Computer Science, vol 4359, pp 187-199
[29] Laporte, G.; Mesa, JA; Perea, F., A game theoretic framework for the robust railway transit network design problem, Transp Res Pt B-Methodol, 44, 4, 447-459 (2010) · doi:10.1016/j.trb.2009.08.004
[30] Laporte, G.; Mesa, JA; Ortega, FA; Perea, F., Planning rapid transit networks, Socio-Econ Plan Sci, 45, 3, 95-104 (2011) · doi:10.1016/j.seps.2011.02.001
[31] Lee JK, Yoo KE, Song KH (2016) A study on travelers’ transport mode choice behavior using the mixed logit model: A case study of the seoul-jeju route. J Air Transp Manag 56(pt.B):131-137
[32] Li, S.; Chen, L.; Zhao, P., The impact of metro services on housing prices: a case study from beijing, Transportation, 46, 1, 1291-1317 (2019) · doi:10.1007/s11116-017-9834-7
[33] Li, ZC; Lam, WH; Wong, S.; Sumalee, A., Design of a rail transit line for profit maximization in a linear transportation corridor, Transp Res Pt E-Logist Transp Rev, 48, 1, 50-70 (2012) · doi:10.1016/j.tre.2011.05.003
[34] Liang J, Wu J, Gao Z, Sun H, Yang X, Lo HK (2019a) Bus transit network design with uncertainties on the basis of a metro network: A two-step model framework. Transp Res Pt B-Methodol 126:115-138
[35] Liang J, Wu J, Qu Y, Yin H, Qu X, Gao Z (2019b) Robust bus bridging service design under rail transit system disruptions. Transp Res Pt E-Logist Transp Rev 132:97-116
[36] Marín, Á.; García-Ródenas, R., Location of infrastructure in urban railway networks, Comput Oper Res, 36, 5, 1461-1477 (2009) · Zbl 1179.90209 · doi:10.1016/j.cor.2008.02.008
[37] Marín, Á.; Jaramillo, P., Urban rapid transit network capacity expansion, Eur J Oper Res, 191, 1, 45-60 (2008) · Zbl 1146.90350 · doi:10.1016/j.ejor.2007.08.010
[38] Mesa JA, De-Los-Santos A, Canca D, Laporte G (2016) A mathematical model for the railway rapid transit network design problem. Paper presented at Congreso Latino-iberoamericano De Investigación Operativa(CLAIO 2016), 2 Oct. 2016
[39] Ouyang, Y.; Nourbakhsh, SM; Cassidy, MJ, Continuum approximation approach to bus network design under spatially heterogeneous demand, Transp Res Pt B-Methodol, 68, 333-344 (2014) · doi:10.1016/j.trb.2014.05.018
[40] Petit A, Yildirimoglu M, Geroliminis N, Ouyang Y (2021) Dedicated bus lane network design under demand diversion and dynamic traffic congestion: An aggregated network and continuous approximation model approach. Transp Res Pt C-Emerg Technol 128:103187
[41] Pu S, Zhan S (2021) Two-stage robust railway line-planning approach with passenger demand uncertainty. Transp Res Pt E-Logist Transp Rev 152
[42] Wang, X.; Koç, Y.; Derrible, S.; Ahmad, SN; Pino, WJ; Kooij, RE, Multi-criteria robustness analysis of metro networks, Physica A, 474, 19-31 (2017) · doi:10.1016/j.physa.2017.01.072
[43] Wei, Y.; Jin, JG; Yang, J.; Lu, L., Strategic network expansion of urban rapid transit systems: A bi-objective programming model, Comput-Aided Civil Infrastruct Eng, 34, 5, 431-443 (2019) · doi:10.1111/mice.12426
[44] Wei Y, Mao M, Zhao X, Zou J, An P (2020) City metro network expansion with reinforcement learning. Paper presented at the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 23 Aug. 2020
[45] Xu, X.; Li, CL; Xu, Z., Train timetabling with stop-skipping, passenger flow, and platform choice considerations, Transp Res Pt B-Methodol, 150, 52-74 (2021) · doi:10.1016/j.trb.2021.06.001
[46] Yang L (2010) The study of the line site of the urban subway choosing. Master thesis, Central South University, China, in Chinese
[47] Zhao S, Yang H, Wu Y (2021) An integrated approach of train scheduling and rolling stock circulation with skip-stopping pattern for urban rail transit lines. Transp Res Pt C-Emerg Technol 128:103170
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.