A method for urban air mobility network design using hub location and subgraph isomorphism

• Published in: Transportation research. Part C, Emerging technologies Emerging technologies, 2021-04, Vol.125, p.102997, Article 102997
• Main Authors: Willey, Landon C., Salmon, John L.
• Format: Article
• Language: English
• ISSN: 0968-090X; 1879-2359
• DOI: 10.1016/j.trc.2021.102997

Rising concerns related to the effects of traffic congestion have led to the proposal of many alternative solutions, including the idea of Urban Air Mobility (UAM), which uses electric aircraft to service routes in dense urban areas. UAM networks rely on an infrastructure of vertiports, which are closely tied to the ability of the UAM service to operate effectively. This research addresses identifying desirable locations for vertiports while taking into account vehicle limitations, desired operational strategies, and the possibility of passenger trips involving more than two vertiports. The vertiport selection problem is presented as a modified single-allocation p-hub median location problem that incorporates elements of subgraph isomorphism to create structured networks to allow for public transit operations. Because the problem is NP-hard, five heuristic algorithms are developed to find potential solutions with acceptable computation times. The methods are compared to the optimal solution in three different areas of the United States. The most effective of these methods are found to be within 10% of the optimal solution on average, and results indicate that they scale well to larger networks. General trends from the three case study regions examined are also briefly discussed. •Presents a novel hub location problem objective function for vertiport selection.•The update-based heuristics introduced come within 91% of the optimum on average.•Solutions are found in 10% of the time using new greedy update algorithms.•Travel time saved increases logarithmically with vehicle speed; number of vertiports.