IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v61y2014icp13-27.html
   My bibliography  Save this article

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

Author

Listed:
  • Wei, P.
  • Chen, L.
  • Sun, D.

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.

Suggested Citation

  • Wei, P. & Chen, L. & Sun, D., 2014. "Algebraic connectivity maximization of an air transportation network: The flight routes’ addition/deletion problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 13-27.
    • Handle: RePEc:eee:transe:v:61:y:2014:i:c:p:13-27
    DOI: 10.1016/j.tre.2013.10.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554513001750
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2013.10.008?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Li, Siping & Zhou, Yaoming & Kundu, Tanmoy & Zhang, Fangni, 2021. "Impact of entry restriction policies on international air transport connectivity during COVID-19 pandemic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    2. Wandelt, Sebastian & Sun, Xiaoqian, 2015. "Evolution of the international air transportation country network from 2002 to 2013," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 55-78.
    3. Zhou, Yaoming & Wang, Junwei & Sheu, Jiuh-Biing, 2019. "On connectivity of post-earthquake road networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 1-16.
    4. Cheung, Kam-Fung & Bell, Michael G.H., 2021. "Improving connectivity of compromised digital networks via algebraic connectivity maximisation," European Journal of Operational Research, Elsevier, vol. 294(1), pages 353-364.
    5. Maria Sartzetaki & Dimitrios Dimitriou & Aristi Karagkouni, 2019. "Optimum Allocation of Time Resources For Transport Operation Enterprises," International Journal of Business Research and Management (IJBRM), Computer Science Journals (CSC Journals), vol. 10(3), pages 29-43, October.
    6. Li, Max Z. & Ryerson, Megan S., 2019. "Reviewing the DATAS of aviation research data: Diversity, availability, tractability, applicability, and sources," Journal of Air Transport Management, Elsevier, vol. 75(C), pages 111-130.
    7. Zhou, Yaoming & Kundu, Tanmoy & Qin, Wei & Goh, Mark & Sheu, Jiuh-Biing, 2021. "Vulnerability of the worldwide air transportation network to global catastrophes such as COVID-19," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    8. Sun, Xiaoqian & Wandelt, Sebastian, 2014. "Network similarity analysis of air navigation route systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 416-434.
    9. Cheung, Kam-Fung & Bell, Michael G.H. & Pan, Jing-Jing & Perera, Supun, 2020. "An eigenvector centrality analysis of world container shipping network connectivity," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    10. Li, Max Z. & Ryerson, Megan S. & Balakrishnan, Hamsa, 2019. "Topological data analysis for aviation applications," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 149-174.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marianov, Vladimir & Serra, Daniel & ReVelle, Charles, 1999. "Location of hubs in a competitive environment," European Journal of Operational Research, Elsevier, vol. 114(2), pages 363-371, April.
    2. Chiara Gruden & Irena Ištoka Otković & Matjaž Šraml, 2020. "Neural Networks Applied to Microsimulation: A Prediction Model for Pedestrian Crossing Time," Sustainability, MDPI, vol. 12(13), pages 1-22, July.
    3. Chou, Jui-Sheng & Truong, Dinh-Nhat, 2021. "A novel metaheuristic optimizer inspired by behavior of jellyfish in ocean," Applied Mathematics and Computation, Elsevier, vol. 389(C).
    4. Thibaud Deguilhem & Juliette Schlegel & Jean-Philippe Berrou & Ousmane Djibo & Alain Piveteau, 2024. "Too many options: How to identify coalitions in a policy network?," Post-Print hal-04689665, HAL.
    5. Anurag Agarwal, 2009. "Theoretical insights into the augmented-neural-network approach for combinatorial optimization," Annals of Operations Research, Springer, vol. 168(1), pages 101-117, April.
    6. Helena Ramalhinho-Lourenço & Olivier C. Martin & Thomas Stützle, 2000. "Iterated local search," Economics Working Papers 513, Department of Economics and Business, Universitat Pompeu Fabra.
    7. Marti, Rafael, 1998. "A tabu search algorithm for the bipartite drawing problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 558-569, April.
    8. Mohammad Javad Feizollahi & Igor Averbakh, 2014. "The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 321-335, May.
    9. Nha Vo‐Thanh & Hans‐Peter Piepho, 2023. "Generating designs for comparative experiments with two blocking factors," Biometrics, The International Biometric Society, vol. 79(4), pages 3574-3585, December.
    10. Сластников С.А., 2014. "Применение Метаэвристических Алгоритмов Для Задачи Маршрутизации Транспорта," Журнал Экономика и математические методы (ЭММ), Центральный Экономико-Математический Институт (ЦЭМИ), vol. 50(1), pages 117-126, январь.
    11. Hanafi, Said & Freville, Arnaud, 1998. "An efficient tabu search approach for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 659-675, April.
    12. Grolimund, Stephan & Ganascia, Jean-Gabriel, 1997. "Driving Tabu Search with case-based reasoning," European Journal of Operational Research, Elsevier, vol. 103(2), pages 326-338, December.
    13. repec:dar:wpaper:62383 is not listed on IDEAS
    14. Minghe Sun, 2007. "A Primogenitary Linked Quad Tree Approach for Solution Storage and Retrieval in Heuristic Binary Optimization," Working Papers 0009, College of Business, University of Texas at San Antonio.
    15. Bolte, Andreas & Thonemann, Ulrich Wilhelm, 1996. "Optimizing simulated annealing schedules with genetic programming," European Journal of Operational Research, Elsevier, vol. 92(2), pages 402-416, July.
    16. Jack Brimberg & Pierre Hansen & Nenad Mladenović & Eric D. Taillard, 2000. "Improvements and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem," Operations Research, INFORMS, vol. 48(3), pages 444-460, June.
    17. Deng, Ye & Wu, Jun & Tan, Yue-jin, 2016. "Optimal attack strategy of complex networks based on tabu search," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 442(C), pages 74-81.
    18. Drexl, Andreas & Haase, Knut, 1996. "Fast approximation methods for sales force deployment," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 411, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    19. Rego, Cesar & Roucairol, Catherine, 1995. "Using Tabu search for solving a dynamic multi-terminal truck dispatching problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 411-429, June.
    20. Chen, Lu & Langevin, André & Riopel, Diane, 2011. "A tabu search algorithm for the relocation problem in a warehousing system," International Journal of Production Economics, Elsevier, vol. 129(1), pages 147-156, January.
    21. H. A. J. Crauwels & C. N. Potts & L. N. Van Wassenhove, 1998. "Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 10(3), pages 341-350, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:61:y:2014:i:c:p:13-27. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.