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

P. Wei, L. Chen and D. Sun

Transportation Research Part E: Logistics and Transportation Review, 2014, vol. 61, issue C, 13-27

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.

Keywords: Air transportation network; Algebraic connectivity; Optimization (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554513001750
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:61:y:2014:i:c:p:13-27

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2013.10.008

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().