Algebraic connectivity maximization of an air transportation network: The flight routes’ addition/deletion problem

• Algebraic connectivity is introduced to measure the robustness of air transportation networks.
• The flight routes addition/deletion problem is formulated to maximize algebraic connectivity.
• The Modified Greedy Perturbation and Weighted Tabu Search methods have been developed.
• The air transportation network robustness of Virgin America is investigated and optimized.

A common metric to measure the robustness of a network is its algebraic connectivity. This paper introduces the flight routes addition/deletion problem and compares three different methods to analyze and optimize the algebraic connectivity of the air transportation network. The Modified Greedy Perturbation algorithm (MGP) provides a local optimum in an efficient iterative manner. The Weighted Tabu Search (WTS) is developed for the flight routes addition/deletion problem to offer a better optimal solution with longer computation time. The relaxed semidefinite programming (SDP) is used to set a performance upper bound and then three rounding techniques are applied to obtain feasible solutions. The simulation results show the trade-off among the Modified Greedy Perturbation, Weighted Tabu Search and relaxed SDP, with which we can decide the appropriate algorithm to adopt for maximizing the algebraic connectivity of the air transportation networks of different sizes. Finally a real air transportation network of Virgin America is investigated.