An analysis of constructive algorithms for the airport baggage sorting station assignment problem

详细信息    查看全文

• 作者：Amadeo Ascó (1)
  Jason A. D. Atkin (1)
  Edmund K. Burke (2)
  
• 关键词：Airport baggage sorting stations ; Scheduling ; Heuristics ; Constructive algorithms ; Greedy algorithms
• 刊名：Journal of Scheduling
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：17
• 期：6
• 页码：601-619
• 全文大小：3,498 KB
• 参考文献：1. Abdelghany, A., Abdelghany, K., & Narasimhan, R. (2006). Scheduling baggage-handling facilities in congested airports. / Journal of Air Transport Management, / 12(2), 76-1. doi:10.1016/j.jairtraman.2005.10.001 . CrossRef
  2. Air Transport Users Council (2009). / Annual report 2008/09. Tech. Rep., AUC.
  3. Ascó, A., Atkin, J. A. D., & Burke, E. K. (2011). The airport baggage sorting station allocation problem. In J. Fowler, G. Kendall, & B. McCollum (Eds.), / Proceedings of the 5th multidisciplinary international conference on scheduling : Theory and applications (MISTA 2011) (pp. 419-44). August 9-1 2011, Phoenix, AZ, USA. http://www.schedulingconference.org/previous/publications/displaypub.php?key=2011-419-444-P&filename=mista.bib.
  4. Ascó, A., Atkin, J. A. D., & Burke, E. K. (2012). An evolutionary algorithm for the over-constrained airport baggage sorting station assignment problem. In L. Bui, Y. Ong, N. Hoai, H. Ishibuchi, & P. Suganthan (Eds.), / 9th International conference on simulated evolution and learning, SEAL2012, Lecture Notes in Computer Science, Vol. 7673 (pp. 32-1). Berlin Heidelberg: Springer. doi:10.1007/978-3-642-34859-4_4 .
  5. Atkin, J. A. D., Burke, E. K., Greenwood, J. S., & Reeson, D. (2008). On-line decision support for take-off runway scheduling at London Heathrow airport. / Journal of Scheduling, / 11(5), 323-46. doi:10.1007/s10951-008-0065-9 . CrossRef
  6. Atkin, J. A. D., De Maere, G., Burke, E. K., & Greenwood, J. S. (2012). Addressing the pushback time allocation problem at heathrow airport. / Transportation Science. doi:10.1287/trsc.1120.0446 .
  7. Bolat, A. (2000). Procedures for providing robust gate assignments for arriving aircrafts. / European Journal of Operational Research, / 120(1), 63-0. http://www.sciencedirect.com/science/article/pii/S0377221798003750.
  8. Cormen, T. H., Leiserson, C.E., Rivest, R. L., & Stein, C. (Eds.) (2001). / Introduction to algorithms. Cambridge, MA: The Massachusetts Institute of Technology Press. http://www-2.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/shortestPaths.pdf.
  9. Diepen, G. (2008). Column generation algorithms for machine scheduling and integrated airport planning. PhD thesis, Utrecht University.
  10. Ding, H., Lim, A., Rodrigues, B., & Zhu, Y. (2004). Aircraft and gate scheduling optimization at airports. / System Sciences, 2004. Proceedings of the 37th annual Hawaii international conference (pp. 1530-605). doi:10.1109/HICSS.2004.1265219 .
  11. Ding, H., Rodrigues, A. L., & Zhu, Y. (2005). The over-constrained airport gate assignment problem. / Computers and Operations Research, / 32(7), 1867-880. CrossRef
  12. Federal Aviation Administration. (2010). / FAA aerospace forecast fiscal years 20102030—forecast highlights. Tech. Rep., Federal Aviation Administration. http://www.faa.gov/data_research/aviation/aerospace_forecasts/2010-2030/.
  13. Haralick, R. M., & Elliott, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. / Artificial Intelligence, / 14, 263-13. doi:10.1016/0004-3702(80)90051-X . CrossRef
  14. Hassounah, M. I., & Steuart, G. N. (1993). Demand for aircraft gates. / Transportation Research Record, / 1423(1423), 26-3. http://pubsindex.trb.org/view.aspx?id=390306.
  15. ICAO (2010). Icao news release—pio 06/10. / Tech. Rep., International Civil Aviation Organization. http://icaopressroom.files.wordpress.com/2010/07/pio-06-10-en.pdf.
  16. Mulvey, J. M., Vanderbei, R. J., & Zenios, S. A. (1995). Robust optimization of large-scale systems. / Operational
• 作者单位：Amadeo Ascó (1)
  Jason A. D. Atkin (1)
  Edmund K. Burke (2)
  
  1. School of Computer Science, University of Nottingham, Nottingham, Nottinghamshire, UK
  2. Department of Computing and Mathematics, University of Stirling, Stirling, Scotland, UK
  
• ISSN：1099-1425

文摘

The assignment of airport resources can significantly affect the quality of service provided by airlines and airports. High quality assignments can support airlines and airports in adhering to published schedules by minimising changes or delays while waiting for resources to become available. In this paper, we consider the problem of assigning available baggage sorting stations to flights which have already been scheduled and allocated to stands. A model for the problem is presented, and the different objectives which have to be considered are highlighted. A number of constructive algorithms for sorting station assignments are then presented and their effects are compared and analysed when different numbers of sorting stations are available. It can be observed that appropriate algorithm selection is highly dependent upon whether or not reductions in service time are permitted and upon the flight density in relation to the number of sorting stations. Finally, since these constructive approaches produce different solutions which are better for different trade-offs of the objectives, we utilise these as initial solutions for an evolutionary algorithm as well as for an Integer Linear Programming model in CPLEX. We show that in both cases they are helpful for improving the results which are obtainable within reasonable solution times.