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. repec:hal:journl:hal-04689665 is not listed on IDEAS
    4. 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.
    5. Сластников С.А., 2014. "Применение Метаэвристических Алгоритмов Для Задачи Маршрутизации Транспорта," Журнал Экономика и математические методы (ЭММ), Центральный Экономико-Математический Институт (ЦЭМИ), vol. 50(1), pages 117-126, январь.
    6. 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.
    7. 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.
    8. 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.
    9. Pirlot, Marc, 1996. "General local search methods," European Journal of Operational Research, Elsevier, vol. 92(3), pages 493-511, August.
    10. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    11. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    12. Dusan Ku & Tiru S. Arthanari, 2016. "On double cycling for container port productivity improvement," Annals of Operations Research, Springer, vol. 243(1), pages 55-70, August.
    13. Ghosh, Diptesh, 2016. "Exploring Lin Kernighan neighborhoods for the indexing problem," IIMA Working Papers WP2016-02-13, Indian Institute of Management Ahmedabad, Research and Publication Department.
    14. Yazdani Sabouni, M.T. & Logendran, Rasaratnam, 2013. "Carryover sequence-dependent group scheduling with the integration of internal and external setup times," European Journal of Operational Research, Elsevier, vol. 224(1), pages 8-22.
    15. Kadri Sylejmani & Jürgen Dorn & Nysret Musliu, 2017. "Planning the trip itinerary for tourist groups," Information Technology & Tourism, Springer, vol. 17(3), pages 275-314, September.
    16. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    17. B Dengiz & C Alabas-Uslu & O Dengiz, 2009. "Optimization of manufacturing systems using a neural network metamodel with a new training approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1191-1197, September.
    18. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    19. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    20. Ko, Young Dae, 2019. "The airfare pricing and seat allocation problem in full-service carriers and subsidiary low-cost carriers," Journal of Air Transport Management, Elsevier, vol. 75(C), pages 92-102.
    21. Kadri Sylejmani & Jürgen Dorn & Nysret Musliu, 0. "Planning the trip itinerary for tourist groups," Information Technology & Tourism, Springer, vol. 0, pages 1-40.

    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.