Multimodal Hub-and-Spoke Network Design Problems to Integrate Urban Air Mobility and High-Speed Rail Services: A Semi-Quadratic Assignment Formulation and its Linearization

Abstract

Urban air mobility (UAM) leverages advanced air transportation systems to facilitate efficient and reliable air travel within and around urban areas. It involves the use of electric aircraft capable of vertical take-off and landing (VTOL), such as air taxis, which navigate urban airspace to transport passengers quickly between locations. High-speed rail (HSR) service, on the other hand, is a rail transport system that utilizes trains operating at higher speeds than traditional rail services, providing rapid connectivity between major metropolitan areas. In this study, we aim to develop a hub-and-spoke network design (HSND) problem that integrates UAM and HSR (UAMHSR–HSND) to improve the efficiency of multimodal transportation systems. The hub-and-spoke model captures the interfacility interactions between passenger flows and vertiport–station assignments via a semi-quadratic assignment model, which poses significant computational challenges. To address this challenge, we compare different linearization models that leverage the special network configuration of UAMHSR–HSND and allow the problem to be solved using off-the-shelf solvers. We further propose a hybrid solving strategy that uses NET-QAP to generate warm-start solutions and then refine them with stronger linearization models, thereby enhancing scalability for large instances. Numerical results show that the NET-QAP model consistently solves large-scale cases with reasonable optimality gaps, and that integrating it with the multicommodity-flow linearization can obtain optimality (GAP = 0%) within reasonable time limit on large-scale instances. Case studies conducted along the Beijing–Shanghai high-speed rail corridor, with spoke vertiports scattered throughout both Beijing and the Changjiang Delta, demonstrate the practicality of the proposed method.

Keywords

Urban air mobility / High-speed railway / Hub location problem / Semi-quadratic assignment / Linearization / Hybrid approach

References

[1] Aykin T. Networking policies for hub-and-spoke systems with application to the air transportation system. Transp Sci, 1995, 29(3): 201-221

[2] An Y, Zhang Y, Zeng B. The reliable hub-and-spoke design problem: models and algorithms. Transp Res B Methodol, 2015, 77: 103-122

[3] Bryan DL, O'Kelly ME. Hub-and-spoke networks in air transportation: an analytical review. J Reg Sci, 1999, 39(2): 275-295

[4] Campbell JF. Integer programming formulations of discrete hub location problems. Eur J Oper Res, 1994, 72: 387-405

[5] Chae M, Kim SH, Kim M, Park HT, Kim SH. Potential market-based policy considerations for urban air mobility. J Air Transp Manag, 2024, 119 Article ID: 102654

[6] Coto-Millán P, Inglada V, Rey B. Effects of network economies in high-speed rail: the Spanish case. Ann Reg Sci, 2007, 41: 911-925

[7] Cohen AP, Shaheen SA, Farrar EM. Urban air mobility: history, ecosystem, market potential, and challenges. IEEE Trans Intell Transp Syst, 2021, 22(9): 6074-6087

[8] Domschke W. Schedule synchronization for public transit networks. OR Spektrum, 1989, 11(1): 17-24

[9] Frieze AM, Yadegar J. On the quadratic assignment problem. Discrete Appl Math, 1983, 5(1): 89-98

[10] Fu J, Huang X, Tong L. Urban layout optimization in a city network under an extended quadratic assignment problem framework. Transportmetrica A Transp Sci, 2022, 18(2): 221-247

[11] Heffley DR. The quadratic assignment problem: a note. Econometrica, 1972

[12] Hwang JH, Hong S. A study on the factors influencing the adoption of urban air mobility and the future demand: using the stated preference survey for three UAM operational scenarios in South Korea. J Air Transp Manag, 2023, 112 Article ID: 102467

[13] Ge D, Wang C, Xiong Z, Ye Y. From an interior point to a corner point: smart crossover. INFORMS J Comput, 2025

[14] Koopmans TC, Beckmann M. Assignment problems and the location of economic activities. Econometrica, 1957

[15] Lawler EL. The quadratic assignment problem. Manage Sci, 1963, 9(4): 586-599

[16] Lu K, Han B, Lu F, Wang Z. Urban rail transit in China: progress report and analysis (2008–2015). Urban Rail Transit, 2016, 2: 93-105

[17] Martí-Henneberg J. European integration and national models for railway networks (1840–2010). J Transp Geogr, 2013, 26: 126-138

[18] Matthews L (2019) I took Uber Copter from Manhattan to JFK–Here’s what it’s like. AFAR, [online] 3 October. Available at: https://www.afar.com/magazine/what-its-like-to-fly-uber-copter-from-manhattan-to-jfk-airport [Accessed 5 Apr. 2025]

[19] Meng Q, Wang X. Intermodal hub-and-spoke network design: incorporating multiple stakeholders and multi-type containers. Transp Res B Methodol, 2011, 45(4): 724-742

[20] Morelli AC, Hofmann C, Topputo F. Warm start of interior-point methods applied to sequential convex programming. IEEE Trans Aerosp Electron Syst, 2024, 60(4): 3837-3846

[21] Mahmoudi M, Zhou X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state–space–time network representations. Transp Res B Methodol, 2016, 89: 19-42

[22] Jin M, Lin KC, Shi W, Lee PT, Li KX. Impacts of high-speed railways on economic growth and disparity in China. Transp Res A Policy Pract, 2020, 138: 158-171

[23] O'Kelly ME. A geographer’s analysis of hub-and-spoke networks. J Transp Geogr, 1998, 6(3): 171-186

[24] Potra FA, Wright SJ. Interior-point methods. J Comput Appl Math, 2000, 124(1-2): 281-302

[25] Reis V, Meier JF, Pace G, Palacin R. Rail and multi-modal transport. Res Transp Econ, 2013, 41(1): 17-30

[26] Rimjha M, Hotle S, Trani A, Hinze N. Commuter demand estimation and feasibility assessment for urban air mobility in Northern California. Transp Res A Policy Pract, 2021, 148: 506-524

[27] Sakti S, Zhang L, Thompson RG. Synchronization in synchromodality. Transp Res E Logist Transp Rev, 2023, 179 Article ID: 103321

[28] Shin H, Lee T, Lee HR. Skyport location problem for urban air mobility system. Comput Oper Res, 2022, 138 Article ID: 105611

[29] Takatsu T. The history and future of high-speed railways in Japan. Japan Railw Transp Rev, 2007, 48: 6-21

[30] Thipphavong DP, Apaza R, Barmore B, Battiste V, Burian B, Dao Q, Feary M, Go S, Goodrich, KH, Homola J, Idris HR (2018) Urban air mobility airspace integration concepts and considerations. In: 2018 Aviation technology, integration, and operations conference, p 3676

[31] Tong L, Zhou X, Miller HJ. Transportation network design for maximizing space–time accessibility. Transp Res B Methodol, 2015, 81: 555-576

[32] Vuchic VRUrban public transportation systems, 20025PhiladelphiaUniversity of Pennsylvania2532-2558

[33] Willey LC, Salmon JL. A method for urban air mobility network design using hub location and subgraph isomorphism. Transp Res C Emerg Technol, 2021, 125 Article ID: 102997

[34] Wright M. The interior-point revolution in optimization: history, recent developments, and lasting consequences. Bull Am Math Soc, 2005, 42(1): 39-56

[35] Wu X, Nie L, Xu M. Designing an integrated distribution system for catering services for high-speed railways: a three-echelon location routing model with tight time windows and time deadlines. Transp Res C Emerg Technol, 2017, 74: 212-244

[36] Wu X, Nie L, Xu M, Zhao L. Distribution planning problem for a high-speed rail catering service considering time-varying demands and pedestrian congestion: a lot-sizing-based model and decomposition algorithm. Transp Res E Logist Transp Rev, 2019, 123: 61-89

[37] Wu XB, Lu J, Wu S, Zhou XS. Synchronizing time-dependent transportation services: reformulation and solution algorithm using quadratic assignment problem. Transp Res Part B: Methodol, 2021, 152: 140-179

[38] Xia Y. Gilmore-Lawler bound of quadratic assignment problem. Front Math China, 2008, 3: 109-118

[39] Yildirim EA, Wright SJ. Warm-start strategies in interior-point methods for linear programming. SIAM J Optim, 2002, 12(3): 782-810

[40] Zhang P, Zhao Y, Zhu X, Cai Z, Xu J, Shi S. Spatial structure of urban agglomeration under the impact of high-speed railway construction: based on the social network analysis. Sustain Cities Soc, 2020, 62 Article ID: 102404

[41] Zheng J, Meng Q, Sun Z. Liner hub-and-spoke shipping network design. Transp Res Part E: Logist Transp Rev, 2015, 75: 32-48

[42] Zhou J, Yang L, Li L. The implications of high-speed rail for Chinese cities: connectivity and accessibility. Transp Res Part A: Policy Pract, 2018, 116: 308-326

RIGHTS & PERMISSIONS

The Author(s)