IDEAS home Printed from https://ideas.repec.org/a/eee/jaitra/v127y2025ics0969699725000705.html

An improved multi-objective restart variable neighborhood search algorithm for aircraft sequencing problem with complex interdependent runways

Author

Listed:
  • Chen, Kejia
  • Situ, Tengkuan
  • Fang, Yunfei

Abstract

The Aircraft Sequencing Problem (ASP) is a problem that seeks to minimize adverse impacts such as flight delays by adjusting flight sequencing schemes. With the increase in aviation demand, ASP has been garnered more attention in recent years. However, existing ASPs typically assume that the relationships between runways are either entirely independent or entirely interdependent, without considering the complex scenarios where runways have both dependent and independent relationships. Moreover, existing ASP research focusing on multi-objective aspects is relatively scarce, while it is essential to consider multifaceted needs in reality. Therefore, we have established a multi-objective mathematical model for the Aircraft Sequencing Problem with Complex Interdependent Runways (ASP-CIR), aiming to minimize the total delays and makespan. Different from the common lack of problem-specific structural design in existing ASP algorithms, or the need to improve structural strategies, we propose an Improved Multi-Objective Restart Variable Neighborhood Search (IMORVNS) algorithm based on the characteristic of the studied ASP-CIR. In the IMORVNS, we have designed several problem-specific structures guided by constraints, such as initialization and neighborhood search. We tested our new method on 30 different problem instances of three sizes and found it worked better than other recent algorithms. Moreover, a sensitivity analysis on the scenario featuring both interdependent and independent runway relationships was conducted, reaffirming the importance of considering the ASP-CIR scenario.

Suggested Citation

  • Chen, Kejia & Situ, Tengkuan & Fang, Yunfei, 2025. "An improved multi-objective restart variable neighborhood search algorithm for aircraft sequencing problem with complex interdependent runways," Journal of Air Transport Management, Elsevier, vol. 127(C).
    • Handle: RePEc:eee:jaitra:v:127:y:2025:i:c:s0969699725000705
    DOI: 10.1016/j.jairtraman.2025.102807
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0969699725000705
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jairtraman.2025.102807?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

    for a different version of it.

    References listed on IDEAS

    as
    1. L. Bianco & P. Dell'Olmo & S. Giordani, 1999. "Minimizing total completion time subject to release dates and sequence‐dependentprocessing times," Annals of Operations Research, Springer, vol. 86(0), pages 393-415, January.
    2. Lieder, Alexander & Stolletz, Raik, 2016. "Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 167-188.
    3. Marie-Sklaerder Vié & Nicolas Zufferey & Roel Leus, 2022. "Aircraft landing planning under uncertain conditions," Journal of Scheduling, Springer, vol. 25(2), pages 203-228, April.
    4. Bennell, Julia A. & Mesgarpour, Mohammad & Potts, Chris N., 2017. "Dynamic scheduling of aircraft landings," European Journal of Operational Research, Elsevier, vol. 258(1), pages 315-327.
    5. Geert De Maere & Jason A. D. Atkin & Edmund K. Burke, 2018. "Pruning Rules for Optimal Runway Sequencing," Transportation Science, INFORMS, vol. 52(4), pages 898-916, August.
    6. Song, Cen & Ma, Xiaoqian & Ardizzone, Catherine & Zhuang, Jun, 2024. "The adverse impact of flight delays on passenger satisfaction: An innovative prediction model utilizing wide & deep learning," Journal of Air Transport Management, Elsevier, vol. 114(C).
    7. Hancerliogullari, Gulsah & Rabadi, Ghaith & Al-Salem, Ameer H. & Kharbeche, Mohamed, 2013. "Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem," Journal of Air Transport Management, Elsevier, vol. 32(C), pages 39-48.
    8. Faye, Alain, 2015. "Solving the Aircraft Landing Problem with time discretization approach," European Journal of Operational Research, Elsevier, vol. 242(3), pages 1028-1038.
    9. Sabar, Nasser R. & Kendall, Graham, 2015. "An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem," Omega, Elsevier, vol. 56(C), pages 88-98.
    10. J. E. Beasley & M. Krishnamoorthy & Y. M. Sharaiha & D. Abramson, 2000. "Scheduling Aircraft Landings—The Static Case," Transportation Science, INFORMS, vol. 34(2), pages 180-197, May.
    11. Pinol, H. & Beasley, J.E., 2006. "Scatter Search and Bionomic Algorithms for the aircraft landing problem," European Journal of Operational Research, Elsevier, vol. 171(2), pages 439-462, June.
    12. Faye, Alain, 2018. "A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes," European Journal of Operational Research, Elsevier, vol. 270(3), pages 1148-1157.
    13. Liu, Yulin & Yin, Mogeng & Hansen, Mark, 2019. "Economic costs of air cargo flight delays related to late package deliveries," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 388-401.
    14. Marcella Samà & Andrea D’Ariano & Konstantin Palagachev & Matthias Gerdts, 2019. "Integration methods for aircraft scheduling and trajectory optimization at a busy terminal manoeuvring area," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(3), pages 641-681, September.
    15. Salehipour, Amir, 2020. "An algorithm for single- and multiple-runway aircraft landing problem," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 175(C), pages 179-191.
    16. Olivares, Felipe & Sun, Xiaoqian & Wandelt, Sebastian & Zanin, Massimiliano, 2023. "Measuring landing independence and interactions using statistical physics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 170(C).
    Full references (including those not matched with items on IDEAS)

    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. Pohl, Maximilian & Artigues, Christian & Kolisch, Rainer, 2022. "Solving the time-discrete winter runway scheduling problem: A column generation and constraint programming approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 674-689.
    2. Pohl, Maximilian & Kolisch, Rainer & Schiffer, Maximilian, 2021. "Runway scheduling during winter operations," Omega, Elsevier, vol. 102(C).
    3. Bin Cao & Chao Xu, 2025. "A near-linear time algorithm and a min-cost flow approach for determining the optimal landing times of a fixed sequence of planes," Annals of Operations Research, Springer, vol. 344(1), pages 479-498, January.
    4. Gao, Jinmin & Le, Meilong & Wu, Xiansheng, 2026. "Improved discrete Harris Hawks optimization with heuristic approximation and rolling horizon control strategy for aircraft landing problem," Journal of Air Transport Management, Elsevier, vol. 131(C).
    5. Ng, K.K.H. & Lee, C.K.M. & Chan, Felix T.S. & Qin, Yichen, 2017. "Robust aircraft sequencing and scheduling problem with arrival/departure delay using the min-max regret approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 115-136.
    6. Lieder, Alexander & Stolletz, Raik, 2016. "Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 167-188.
    7. Zhang, Junfeng & Zhao, Pengli & Zhang, Yu & Dai, Ximei & Sui, Dong, 2020. "Criteria selection and multi-objective optimization of aircraft landing problem," Journal of Air Transport Management, Elsevier, vol. 82(C).
    8. Chen, Shuiwang & Wu, Lingxiao & Ng, Kam K.H. & Liu, Wei & Wang, Kun, 2024. "How airports enhance the environmental sustainability of operations: A critical review from the perspective of Operations Research," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 183(C).
    9. Bo Xu & Weimin Ma & Hui Huang & Lei Yue, 2016. "Weighted Constrained Position Shift Model for Aircraft Arrival Sequencing and Scheduling Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(04), pages 1-22, August.
    10. Salehipour, Amir, 2020. "An algorithm for single- and multiple-runway aircraft landing problem," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 175(C), pages 179-191.
    11. Marie-Sklaerder Vié & Nicolas Zufferey & Roel Leus, 2022. "Aircraft landing planning under uncertain conditions," Journal of Scheduling, Springer, vol. 25(2), pages 203-228, April.
    12. Marcella Samà & Andrea D’Ariano & Konstantin Palagachev & Matthias Gerdts, 2019. "Integration methods for aircraft scheduling and trajectory optimization at a busy terminal manoeuvring area," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(3), pages 641-681, September.
    13. Choi, Hong-Cheol & Deng, Chuhao & Park, Hyunsang & Ryu, Jaeyoung & Lee, Hak-Tae & Hwang, Inseok, 2025. "Multi-agent Estimated Time of Arrival prediction and dynamic arrival sequencing by Emulating Air Traffic Controllers," Journal of Air Transport Management, Elsevier, vol. 128(C).
    14. Jianan Yin & Yuanyuan Ma & Yuxin Hu & Ke Han & Suwan Yin & Hua Xie, 2021. "Delay, Throughput and Emission Tradeoffs in Airport Runway Scheduling with Uncertainty Considerations," Networks and Spatial Economics, Springer, vol. 21(1), pages 85-122, March.
    15. Huo, Ying & Delahaye, Daniel & Yang, Huijuan & Wang, Maolin, 2026. "An improved optimization algorithm for solving arrival aircraft scheduling problem in the Terminal Maneuvering Area," Journal of Air Transport Management, Elsevier, vol. 133(C).
    16. Dönmez, Kadir & Çetek, Cem & Kaya, Onur, 2022. "Air traffic management in parallel-point merge systems under wind uncertainties," Journal of Air Transport Management, Elsevier, vol. 104(C).
    17. Samà, Marcella & D’Ariano, Andrea & D’Ariano, Paolo & Pacciarelli, Dario, 2017. "Scheduling models for optimal aircraft traffic control at busy airports: Tardiness, priorities, equity and violations considerations," Omega, Elsevier, vol. 67(C), pages 81-98.
    18. Ahmed Khassiba & Fabian Bastin & Sonia Cafieri & Bernard Gendron & Marcel Mongeau, 2020. "Two-Stage Stochastic Mixed-Integer Programming with Chance Constraints for Extended Aircraft Arrival Management," Transportation Science, INFORMS, vol. 54(4), pages 897-919, July.
    19. Julia Bennell & Mohammad Mesgarpour & Chris Potts, 2013. "Airport runway scheduling," Annals of Operations Research, Springer, vol. 204(1), pages 249-270, April.
    20. Zheng, Shuang & Li, Zhaojin & Zheng, Weibo & Zhang, Rui & Yang, Zhen & He, Zhengwen, 2025. "A novel scaling-based landing first constructive heuristic algorithm for aircraft scheduling and parking problem in multi-runway airports," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:127:y:2025:i:c:s0969699725000705. 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.