Algebraic Connectivity Maximization of an Air Transportation Network: The Flight Routes’ Addition/Deletion Problem

Document Type

Article

Publication Date

1-2014

Publication Source

Transportation Research Part E: Logistics and Transportation Review

Abstract

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.

Inclusive pages

13–27

ISBN/ISSN

1366-5545

Comments

Permission documentation is on file.

Publisher

Elsevier

Volume

61

Peer Reviewed

yes

Link to Full Text

Share

COinS