IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v284y2020i1p135-151.html
   My bibliography  Save this article

Modeling and solving a bi-objective airport slot scheduling problem

Author

Listed:
  • Androutsopoulos, Konstantinos N.
  • Manousakis, Eleftherios G.
  • Madas, Michael A.

Abstract

The strategic airport slot allocation problem concerns the scheduling of airlines’ requests for landings and take-offs at congested airports for a series of days within a given scheduling season. Relevant scheduling models dealing with the strategic airport slot allocation problem have employed various combinations of the total schedule displacement criterion with several variations of acceptability metrics. However, most variations of schedule displacement pursued in existing literature do not thoroughly capture the real-world scheduling practice, and, most importantly, do not guarantee the allocation of acceptable/tolerable or viable displacement among competing airlines’ slot requests. In this paper, we propose the formulation of the strategic airport slot allocation problem as a bi-objective resource constrained project scheduling problem with partially renewable resources and non-regular objective functions. We employ two non-regular performance criteria: (i) the total earliness-tardiness and (ii) a dispersion measure aiming to alleviate over-displaced requests. Α novel hybrid heuristic algorithm integrating the Objective Feasibility Pump (FP) algorithm with the Large Neighborhood Search technique (LNS) is proposed. We generate a set of new problem instances originating from the patterns of a data set of actual slot requests for a Greek Regional Airport (GRA) to assess the performance of the algorithm. The computational results indicate that the proposed algorithm is reasonably accurate, and it has the capability to approximate the entire efficient frontier of the problem.

Suggested Citation

  • Androutsopoulos, Konstantinos N. & Manousakis, Eleftherios G. & Madas, Michael A., 2020. "Modeling and solving a bi-objective airport slot scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(1), pages 135-151.
    • Handle: RePEc:eee:ejores:v:284:y:2020:i:1:p:135-151
    DOI: 10.1016/j.ejor.2019.12.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719309920
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.12.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. Böttcher, Jan & Drexl, A. & Kolisch, R. & Salewski, F., 1999. "Project scheduling under partially renewable resource constraints," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 345, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. Ribeiro, Nuno Antunes & Jacquillat, Alexandre & Antunes, António Pais & Odoni, Amedeo R. & Pita, João P., 2018. "An optimization approach for airport slot allocation under IATA guidelines," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 132-156.
    3. Al-Fawzan, M. A. & Haouari, Mohamed, 2005. "A bi-objective model for robust resource-constrained project scheduling," International Journal of Production Economics, Elsevier, vol. 96(2), pages 175-187, May.
    4. Konstantinos G. Zografos & Michael A. Madas & Konstantinos N. Androutsopoulos, 2017. "Increasing airport capacity utilisation through optimum slot scheduling: review of current developments and identification of future needs," Journal of Scheduling, Springer, vol. 20(1), pages 3-24, February.
    5. Viana, Ana & Pinho de Sousa, Jorge, 2000. "Using metaheuristics in multiobjective resource constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 120(2), pages 359-374, January.
    6. Lorenzo Castelli & Paola Pellegrini & Raffaele Pesenti, 2012. "Airport slot allocation in Europe: economic efficiency and fairness," International Journal of Revenue Management, Inderscience Enterprises Ltd, vol. 6(1/2), pages 28-44.
    7. Mario Vanhoucke & Erik Demeulemeester & Willy Herroelen, 2001. "An Exact Procedure for the Resource-Constrained Weighted Earliness–Tardiness Project Scheduling Problem," Annals of Operations Research, Springer, vol. 102(1), pages 179-196, February.
    8. Jan Böttcher & Andreas Drexl & Rainer Kolisch & Frank Salewski, 1999. "Project Scheduling Under Partially Renewable Resource Constraints," Management Science, INFORMS, vol. 45(4), pages 543-559, April.
    9. Alexandre Jacquillat & Amedeo R. Odoni, 2015. "An Integrated Scheduling and Operations Approach to Airport Congestion Mitigation," Operations Research, INFORMS, vol. 63(6), pages 1390-1410, December.
    10. F. Brian Talbot & James H. Patterson, 1978. "An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems," Management Science, INFORMS, vol. 24(11), pages 1163-1174, July.
    11. Pellegrini, Paola & Bolić, Tatjana & Castelli, Lorenzo & Pesenti, Raffaele, 2017. "SOSTA: An effective model for the Simultaneous Optimisation of airport SloT Allocation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 99(C), pages 34-53.
    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. Bergantino, Angela Stefania & Intini, Mario & Volta, Nicola, 2021. "The spatial dimension of competition among airports at the worldwide level: a spatial stochastic frontier analysis," European Journal of Operational Research, Elsevier, vol. 295(1), pages 118-130.
    2. Jorge, Diana & Antunes Ribeiro, Nuno & Pais Antunes, António, 2021. "Towards a decision-support tool for airport slot allocation: Application to Guarulhos (Sao Paulo, Brazil)," Journal of Air Transport Management, Elsevier, vol. 93(C).
    3. Dixit, Aasheesh Kumar & Shakya, Garima & Jakhar, Suresh Kumar & Nath, Swaprava, 2023. "Algorithmic mechanism design for egalitarian and congestion-aware airport slot allocation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    4. Bergantino, Angela Stefania & Intini, Mario & Volta, Nicola, 2020. "Spatial competition and efficiency: an investigation in the airport sector," The Warwick Economics Research Paper Series (TWERPS) 1287, University of Warwick, Department of Economics.
    5. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    6. Kai Watermeyer & Jürgen Zimmermann, 2022. "A partition-based branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 575-602, June.

    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. Cavusoglu, Sabriye Sera & Macário, Rosário, 2021. "Minimum delay or maximum efficiency? Rising productivity of available capacity at airports: Review of current practice and future needs," Journal of Air Transport Management, Elsevier, vol. 90(C).
    2. Androutsopoulos, Konstantinos N. & Madas, Michael A., 2019. "Being fair or efficient? A fairness-driven modeling extension to the strategic airport slot scheduling problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 37-60.
    3. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    4. Zografos, Konstantinos G. & Androutsopoulos, Konstantinos N. & Madas, Michael A., 2018. "Minding the gap: Optimizing airport schedule displacement and acceptability," Transportation Research Part A: Policy and Practice, Elsevier, vol. 114(PA), pages 203-221.
    5. Nuno Antunes Ribeiro & Alexandre Jacquillat & António Pais Antunes, 2019. "A Large-Scale Neighborhood Search Approach to Airport Slot Allocation," Transportation Science, INFORMS, vol. 53(6), pages 1772-1797, November.
    6. Keskin, Merve & Zografos, Konstantinos G., 2023. "Optimal network-wide adjustments of initial airport slot allocations with connectivity and fairness objectives," Transportation Research Part B: Methodological, Elsevier, vol. 178(C).
    7. Jorge, Diana & Antunes Ribeiro, Nuno & Pais Antunes, António, 2021. "Towards a decision-support tool for airport slot allocation: Application to Guarulhos (Sao Paulo, Brazil)," Journal of Air Transport Management, Elsevier, vol. 93(C).
    8. Katsigiannis, Fotios A. & Zografos, Konstantinos G., 2021. "Optimising airport slot allocation considering flight-scheduling flexibility and total airport capacity constraints," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 50-87.
    9. Donghai Wang & Qiuhong Zhao, 2020. "A Simultaneous Optimization Model for Airport Network Slot Allocation under Uncertain Capacity," Sustainability, MDPI, vol. 12(14), pages 1-14, July.
    10. Lambelho, Miguel & Mitici, Mihaela & Pickup, Simon & Marsden, Alan, 2020. "Assessing strategic flight schedules at an airport using machine learning-based flight delay and cancellation predictions," Journal of Air Transport Management, Elsevier, vol. 82(C).
    11. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    12. Ribeiro, Nuno Antunes & Jacquillat, Alexandre & Antunes, António Pais & Odoni, Amedeo, 2019. "Improving slot allocation at Level 3 airports," Transportation Research Part A: Policy and Practice, Elsevier, vol. 127(C), pages 32-54.
    13. Sheng, Dian & Li, Zhi-Chun & Fu, Xiaowen, 2019. "Modeling the effects of airline slot hoarding behavior under the grandfather rights with use-it-or-lose-it rule," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 48-61.
    14. Dixit, Aasheesh Kumar & Shakya, Garima & Jakhar, Suresh Kumar & Nath, Swaprava, 2023. "Algorithmic mechanism design for egalitarian and congestion-aware airport slot allocation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    15. Ziming Wang & Chaohao Liao & Xu Hang & Lishuai Li & Daniel Delahaye & Mark Hansen, 2022. "Distribution Prediction of Strategic Flight Delays via Machine Learning Methods," Sustainability, MDPI, vol. 14(22), pages 1-14, November.
    16. Till Kösters & Marlena Meier & Gernot Sieg, 2023. "Effects of the use-it-or-lose-it rule on airline strategy and climate," Working Papers 36, Institute of Transport Economics, University of Muenster.
    17. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    18. Katsigiannis, Fotios A. & Zografos, Konstantinos G., 2023. "Incorporating slot valuation in making airport slot scheduling decisions," European Journal of Operational Research, Elsevier, vol. 308(1), pages 436-454.
    19. Hu, Rong & Feng, Huilin & Witlox, Frank & Zhang, Junfeng & Connor, Kevin O., 2022. "Airport capacity constraints and air traffic demand in China," Journal of Air Transport Management, Elsevier, vol. 103(C).
    20. Ribeiro, Nuno Antunes & Jacquillat, Alexandre & Antunes, António Pais & Odoni, Amedeo R. & Pita, João P., 2018. "An optimization approach for airport slot allocation under IATA guidelines," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 132-156.

    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:ejores:v:284:y:2020:i:1:p:135-151. 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/locate/eor .

    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.