LAUSR

Designing a robust air transportation network is an ongoing research effort that seeks to improve the extent of a network being connected against failures and attacks. The total effective resistance can be a promising measure for network robustness as demonstrated by case studies conducted in this paper. To enhance the robustness of air transportation networks, we consider to solve a flight route selection problem in which a set of routes is chosen from a candidate route set to minimize the utility function defined by the total effective resistance. Since it is an integer nonlinear programming problem, to balance the tradeoff between optimality performance and computational efficiency, two methods that implement the total effective resistance are developed to suit different network scales. For small/medium-scale networks, we develop an interior-point method based on convex relaxation and duality gap, which achieves a near optimality performance within acceptable time. For large-scale networks, we develop an accelerated greedy algorithm based on proved monotone submodularity, which can substantially reduce the computation time in deriving a good solution with a guaranteed optimality gap. Their optimality performance and computational efficiency are verified and compared through numerical results. Moreover, three case studies from real-world examples are also performed to demonstrate the application of the proposed methods for different network scales.