IDEAS home Printed from https://ideas.repec.org/a/eee/jaitra/v71y2018icp73-87.html
   My bibliography  Save this article

An efficient hybrid approach for resolving the aircraft routing and rescheduling problem

Author

Listed:
  • Kammoun, Mohamed Ali
  • Rezg, Nidhal

Abstract

In this paper, we address the aircraft routing and rescheduling problem under airspace capacities uncertainty due to unplanned weather conditions, which occurs before the take-off of scheduled flights. For this problem, we propose a hybrid approach that is based on Time Petri Net (TPN) tool. Furthermore, as a second step, a genetic algorithm is introduced in which a possible solution for ARRP is represented by a new encoding. Additionally, we integrate a post-step, which verifies the feasibility of the flight plans based on an improved Time Reduced Ordered Binary Decision Diagrams (TROBDDs). The conducted experiments on a collection of instances show that the TROBDDs can represent a large number of rescheduling flights locations with compact structure and reduce computation time. In addition, the genetic algorithm illustrates a good compromise between the obtained solutions and computation times.

Suggested Citation

  • Kammoun, Mohamed Ali & Rezg, Nidhal, 2018. "An efficient hybrid approach for resolving the aircraft routing and rescheduling problem," Journal of Air Transport Management, Elsevier, vol. 71(C), pages 73-87.
    • Handle: RePEc:eee:jaitra:v:71:y:2018:i:c:p:73-87
    DOI: 10.1016/j.jairtraman.2018.06.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0969699718300139
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jairtraman.2018.06.005?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. Peter B. M. Vranas & Dimitris Bertsimas & Amedeo R. Odoni, 1994. "Dynamic Ground-Holding Policies for a Network of Airports," Transportation Science, INFORMS, vol. 28(4), pages 275-291, November.
    2. Agustı´n, A. & Alonso-Ayuso, A. & Escudero, L.F. & Pizarro, C., 2012. "On air traffic flow management with rerouting. Part II: Stochastic case," European Journal of Operational Research, Elsevier, vol. 219(1), pages 167-177.
    3. Richetta, Octavio & Odoni, Amedeo R., 1994. "Dynamic solution to the ground-holding problem in air traffic control," Transportation Research Part A: Policy and Practice, Elsevier, vol. 28(3), pages 167-185, May.
    4. G. Andreatta & G. Romanin-Jacur, 1987. "Aircraft Flow Management under Congestion," Transportation Science, INFORMS, vol. 21(4), pages 249-253, November.
    5. Octavio Richetta & Amedeo R. Odoni, 1993. "Solving Optimally the Static Ground-Holding Policy Problem in Air Traffic Control," Transportation Science, INFORMS, vol. 27(3), pages 228-238, August.
    6. Mostafa Terrab & Amedeo R. Odoni, 1993. "Strategic Flow Management for Air Traffic Control," Operations Research, INFORMS, vol. 41(1), pages 138-152, February.
    7. Agustı´n, A. & Alonso-Ayuso, A. & Escudero, L.F. & Pizarro, C., 2012. "On air traffic flow management with rerouting. Part I: Deterministic case," European Journal of Operational Research, Elsevier, vol. 219(1), pages 156-166.
    8. Dimitris Bertsimas & Sarah Stock Patterson, 1998. "The Air Traffic Flow Management Problem with Enroute Capacities," Operations Research, INFORMS, vol. 46(3), pages 406-422, June.
    9. Peter B. Vranas & Dimitris J. Bertsimas & Amedeo R. Odoni, 1994. "The Multi-Airport Ground-Holding Problem in Air Traffic Control," Operations Research, INFORMS, vol. 42(2), pages 249-261, April.
    10. Guglielmo Lulli & Amedeo Odoni, 2007. "The European Air Traffic Flow Management Problem," Transportation Science, INFORMS, vol. 41(4), pages 431-443, November.
    11. Michael Thorwarth & Wael Rashwan & Amr Arisha, 2016. "An analytical representation of flexible resource allocation in hospitals," Flexible Services and Manufacturing Journal, Springer, vol. 28(1), pages 148-165, June.
    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. Mohamed Ali Kammoun & Sadok Turki & Nidhal Rezg, 2020. "Optimization of Flight Rescheduling Problem under Carbon Tax," Sustainability, MDPI, vol. 12(14), pages 1-19, July.
    2. Ma, Hoi-Lam & Sun, Yige & Chung, Sai-Ho & Chan, Hing Kai, 2022. "Tackling uncertainties in aircraft maintenance routing: A review of emerging technologies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    3. Vieira, Thiago & De La Vega, Jonathan & Tavares, Roberto & Munari, Pedro & Morabito, Reinaldo & Bastos, Yan & Ribas, Paulo César, 2021. "Exact and heuristic approaches to reschedule helicopter flights for personnel transportation in the oil industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 151(C).
    4. Wen, Xin & Sun, Xuting & Ma, Hoi-Lam & Sun, Yige, 2022. "A column generation approach for operational flight scheduling and aircraft maintenance routing," Journal of Air Transport Management, Elsevier, vol. 105(C).

    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. Diao, Xudong & Chen, Chun-Hsien, 2018. "A sequence model for air traffic flow management rerouting problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 15-30.
    2. Mohamed Ali Kammoun & Sadok Turki & Nidhal Rezg, 2020. "Optimization of Flight Rescheduling Problem under Carbon Tax," Sustainability, MDPI, vol. 12(14), pages 1-19, July.
    3. Guo, Yechenfeng & Hu, Minghua & Zou, Bo & Hansen, Mark & Zhang, Ying & Xie, Hua, 2022. "Air Traffic Flow Management Integrating Separation Management and Ground Holding: An Efficiency-Equity Bi-objective Perspective," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 394-423.
    4. Thomas W. M. Vossen & Michael O. Ball, 2006. "Slot Trading Opportunities in Collaborative Ground Delay Programs," Transportation Science, INFORMS, vol. 40(1), pages 29-43, February.
    5. Andreatta, Giovanni & Dell'Olmo, Paolo & Lulli, Guglielmo, 2011. "An aggregate stochastic programming model for air traffic flow management," European Journal of Operational Research, Elsevier, vol. 215(3), pages 697-704, December.
    6. Bard, Jonathan F. & Mohan, Dinesh Natarajan, 2008. "Reallocating arrival slots during a ground delay program," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 113-134, February.
    7. Churchill, Andrew M. & Lovell, David J., 2012. "Coordinated aviation network resource allocation under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 19-33.
    8. Cynthia Barnhart & Dimitris Bertsimas & Constantine Caramanis & Douglas Fearing, 2012. "Equitable and Efficient Coordination in Traffic Flow Management," Transportation Science, INFORMS, vol. 46(2), pages 262-280, May.
    9. Brunner, Jens O., 2014. "Rescheduling of flights during ground delay programs with consideration of passenger and crew connections," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 236-252.
    10. Ivanov, Nikola & Netjasov, Fedja & Jovanović, Radosav & Starita, Stefano & Strauss, Arne, 2017. "Air Traffic Flow Management slot allocation to minimize propagated delay and improve airport slot adherence," Transportation Research Part A: Policy and Practice, Elsevier, vol. 95(C), pages 183-197.
    11. Ghoneim, Ayman & Abbass, Hussein A., 2016. "A multiobjective distance separation methodology to determine sector-level minimum separation for safe air traffic scenarios," European Journal of Operational Research, Elsevier, vol. 253(1), pages 226-240.
    12. Leal de Matos, Paula & Ormerod, Richard, 2000. "The application of operational research to European air traffic flow management - understanding the context," European Journal of Operational Research, Elsevier, vol. 123(1), pages 125-144, May.
    13. Dimitris Bertsimas & Sarah Stock Patterson, 2000. "The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach," Transportation Science, INFORMS, vol. 34(3), pages 239-255, August.
    14. Pellegrini, Paola & Rodriguez, Joaquin, 2013. "Single European Sky and Single European Railway Area: A system level analysis of air and rail transportation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 57(C), pages 64-86.
    15. Robert Hoffman & Michael O. Ball, 2000. "A Comparison of Formulations for the Single-Airport Ground-Holding Problem with Banking Constraints," Operations Research, INFORMS, vol. 48(4), pages 578-590, August.
    16. Murça, Mayara Condé Rocha, 2018. "Collaborative air traffic flow management: Incorporating airline preferences in rerouting decisions," Journal of Air Transport Management, Elsevier, vol. 71(C), pages 97-107.
    17. Dixit, Aasheesh & Jakhar, Suresh Kumar, 2021. "Airport capacity management: A review and bibliometric analysis," Journal of Air Transport Management, Elsevier, vol. 91(C).
    18. Mukherjee, Avijit, 2004. "Dynamic Stochastic Optimization Models for Air Traffic Flow Management," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt2vk8w6nc, Institute of Transportation Studies, UC Berkeley.
    19. Wei, P. & Cao, Y. & Sun, D., 2013. "Total unimodularity and decomposition method for large-scale air traffic cell transmission model," Transportation Research Part B: Methodological, Elsevier, vol. 53(C), pages 1-16.
    20. Dimitris Bertsimas & Shubham Gupta, 2016. "Fairness and Collaboration in Network Air Traffic Flow Management: An Optimization Approach," Transportation Science, INFORMS, vol. 50(1), pages 57-76, February.

    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:jaitra:v:71:y:2018:i:c:p:73-87. 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.journals.elsevier.com/journal-of-air-transport-management/ .

    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.