IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v33y2016i04ns0217595916500287.html
   My bibliography  Save this article

Weighted Constrained Position Shift Model for Aircraft Arrival Sequencing and Scheduling Problem

Author

Listed:
  • Bo Xu

    (Business School, University of Shanghai for Science and Technology, Shanghai 200093, P. R. China2School of Economics and Management, Tongji University, Shanghai 200092, P. R. China)

  • Weimin Ma

    (School of Economics and Management, Tongji University, Shanghai 200092, P. R. China)

  • Hui Huang

    (Jiangsu Migo Education and Technology Company Limited, Shanghai 200233, P. R. China)

  • Lei Yue

    (School of Economics and Management, Tongji University, Shanghai 200092, P. R. China)

Abstract

The constrained position shift (CPS) model is a famous model in the aircraft arrival sequencing and scheduling (ASS) problem, which allows each aircraft to shift forward or backward at most k (a given integer number) positions in the first come first serve (FCFS) sequence. However, CPS is insufficient to cope with the case that some aircraft requiring more than k positions shift. From this point, we modify it to be a more applicable model, named weighted constrained position shift (W-CPS) model. Three methods are developed to solve W-CPS, which are dynamic programming (DP), mixed integer programming (MIP) and ant colony (AC) algorithm. Numerical results validate the efficiency of these methods.

Suggested Citation

  • 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.
    • Handle: RePEc:wsi:apjorx:v:33:y:2016:i:04:n:s0217595916500287
    DOI: 10.1142/S0217595916500287
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595916500287
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595916500287?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. 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 & Briskorn, Dirk & Stolletz, Raik, 2015. "A dynamic programming approach for the aircraft landing problem with aircraft classes," European Journal of Operational Research, Elsevier, vol. 243(1), pages 61-69.
    3. Faye, Alain, 2015. "Solving the Aircraft Landing Problem with time discretization approach," European Journal of Operational Research, Elsevier, vol. 242(3), pages 1028-1038.
    4. Hamsa Balakrishnan & Bala G. Chandran, 2010. "Algorithms for Scheduling Runway Operations Under Constrained Position Shifting," Operations Research, INFORMS, vol. 58(6), pages 1650-1665, December.
    5. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Approach for Sequencing Groups of Identical Jobs," Operations Research, INFORMS, vol. 28(6), pages 1347-1359, December.
    6. Samà, Marcella & D’Ariano, Andrea & Pacciarelli, Dario, 2013. "Rolling horizon approach for aircraft scheduling in the terminal control area of busy airports," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 140-155.
    7. Soomer, M.J. & Franx, G.J., 2008. "Scheduling aircraft landings using airlines' preferences," European Journal of Operational Research, Elsevier, vol. 190(1), pages 277-291, October.
    8. 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.
    9. 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.
    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 & Kolisch, Rainer & Schiffer, Maximilian, 2021. "Runway scheduling during winter operations," Omega, Elsevier, vol. 102(C).
    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. 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.
    4. Rakesh Prakash & Jitamitra Desai & Rajesh Piplani, 2022. "An optimal data-splitting algorithm for aircraft sequencing on a single runway," Annals of Operations Research, Springer, vol. 309(2), pages 587-610, February.
    5. 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.
    6. 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.
    7. 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.
    8. Julia Bennell & Mohammad Mesgarpour & Chris Potts, 2013. "Airport runway scheduling," Annals of Operations Research, Springer, vol. 204(1), pages 249-270, April.
    9. Lieder, Alexander & Briskorn, Dirk & Stolletz, Raik, 2015. "A dynamic programming approach for the aircraft landing problem with aircraft classes," European Journal of Operational Research, Elsevier, vol. 243(1), pages 61-69.
    10. Jason A. D. Atkin & Geert De Maere & Edmund K. Burke & John S. Greenwood, 2013. "Addressing the Pushback Time Allocation Problem at Heathrow Airport," Transportation Science, INFORMS, vol. 47(4), pages 584-602, November.
    11. Senay Solak & Gustaf Solveling & John-Paul B. Clarke & Ellis L. Johnson, 2018. "Stochastic Runway Scheduling," Transportation Science, INFORMS, vol. 52(4), pages 917-940, August.
    12. Ahmed Ghoniem & Hanif D. Sherali & Hojong Baik, 2014. "Enhanced Models for a Mixed Arrival-Departure Aircraft Sequencing Problem," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 514-530, August.
    13. 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.
    14. 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).
    15. 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.
    16. 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.
    17. Pasquale Avella & Maurizio Boccia & Carlo Mannino & Igor Vasilyev, 2017. "Time-Indexed Formulations for the Runway Scheduling Problem," Transportation Science, INFORMS, vol. 51(4), pages 1196-1209, November.
    18. 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.
    19. A R Brentnall & R C H Cheng, 2009. "Some effects of aircraft arrival sequence algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 962-972, July.
    20. Guépet, Julien & Briant, Olivier & Gayon, Jean-Philippe & Acuna-Agost, Rodrigo, 2017. "Integration of aircraft ground movements and runway operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 104(C), pages 131-149.

    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:wsi:apjorx:v:33:y:2016:i:04:n:s0217595916500287. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    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.