Uçak çizelgeleme probleminin karınca kolonileri optimizasyonu ile çözümü

Havalimanına iniş yapmak üzere havada bulunan uçaklar için iniş sıra ve zamanlarının belirlenmesi özellikle trafiğin yoğun olduğu zaman periyotlarında önemli bir problemdir. Uçak çizelgeleme problemi olarak adlandırılan bu problem temel olarak iş çizelgeleme problemlerine benzemektedir. İşlem zamanları sıralamaya bağımlı olarak değişebilmektedir. Hedef zamanlarında yapılmayan işler için ek maliyet oluşmaktadır. Her uçak için önceden belirlenmiş olan ve iniş yapabileceği zaman aralığım belirleyen alt ve üst sınırlar vardır. Genelde, çizelgeleme sonucunda amaçlanan durum ise uçakların bir veya daha fazla pist için optimum iniş sıralama ve zamanlarının belirlenirken minimum takip mesafelerinin de korunmasıdır. Karınca Kolonileri Optimizasyonu (KKO) metasezgiseli kullanılarak genel amaçlı bir karar verme algoritması geliştirilmiştir. Geliştirilen algoritma tek veya çok pist kullanımında iniş ve kalkışların çizelgelenebilmesi için kullanılabilecektir. Test problemlerinin çözümü sonucunda elde edilen sonuçlar geçmiş çalışmalar ile karşılaştmlmıştır. Ayrıca KKO yönteminin çizelge problemleri için kullanılabilmesi için değişiklik ve yenilikler önerilmiştir.

Scheduling aircraft landings is a major problem in air traffic control area of congested airports. It is a special type of machine scheduling problem; processing times are sequence dependent, and there are penalties for jobs that are not completed on target time. Each plane has an allowable predetermined time window for landing. The objective is to optimally land a set of planes on one or several runways in such a way that separation criteria between all pairs of planes are satisfied. If efficient algorithms can be developed to assist the controller who is in charge of making scheduling decisions, then more effective use affixed runway capacity will result. We tried to solve the problem using Ant System metaheuristic, which is gained more popularity in recent years. Using Ant System metaheuristic, we present a generic decision making tool that can be used both for the single runway and the multiple runway landings and takeoffs. Computational results are presented for the standard test problems obtained from literature. Results are compared with the previous works and show that Ant System solutions can be effective in practice.

PDF

___

1.Mullins J., Trails of Destruction, New Scientist 2056,28-31,1996

2.Odoni A.R., Rousseau J.M., Wilson N.H.M., Models in Urban and Air Transportation, Handbooks in OR & MS, Vol.6, 107-150,1994.

3.Milan J., The Flow Management Problem in Air Traffic Control: A Model of Assigning Priorities for Landings at a Congested Airport, Transportation Planning and Technology 20, 131-162, 1997.

4.Beasley J.E., Krishnamoorthy M., Sharaiha Y.M., Abramson D., Scheduling Aircraft Landings-The Static Case, Transportation Science,Vol.34, No.2, Mayıs 2000.

5.Beasley J.E., Sonander J., Havelock P., Scheduling Aircraft Landings at London Heathrow Using a Population Heuristic, Journal of Operational Research Society 52, 483-493, 2001.

6.Beasley J.E., OR-Library : Distributing Test Problems by Electronic Mail, Journal of Operational Research Society 41, 1069-1072, 1990.

7.Andreussi A., Bianco L., Riciardelli S., A Simulation Model of Aircraft Sequencing in the Near Terminal Area, European Journal of Operations Research 8, 345-354,1981.

8.Dear R.G., The Dynamic Scheduling of Aircraft in the Near Terminal Area, Report R76-9, Flight Transportation Laboratory, MIT, Cambridge, MA, 1976

9.Dear R.G., Sherif Y.S., The Dynamic Scheduling of Aircraft Density Terminal Areas, Microelectronics and Reliability 29, 743-749, 1989.

lO.Dear R.G., Sherif Y.S., An Algorithm for Computer Assisted Sequencing and Scheduling of Terminal Area Operations, Transportation Research Part A, Policy and Practise, 25, 129-139,1991.

11.Abela J., Abramson D., Krishnamoorthy M., De Silva A., Mills G., Computing Optimal Schedules for Landing Aircraft, Proceedings of the 12th National ASOR Conference, Adelaide, Australia, 71-90, 1993.

12.Ernst A.T., Krishnamoorthy M., Storer H., Heuristic and Exact Algorithms for Scheduling Aircraft Landings, Networks 34, 229-241,1999.

13.Dorigo M., Optimization, Learning and Natural Algorithms, PhD thesis, Dipartimento di Elettoronica, Politecnico di Milano, IT, 1992.

14.Dorigo M., Maniezzo V., Colorni A., Positive Feedback as a Search Strategy, Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.

15.Deneubourg J.L., Aron S., Goss S., ve Pasteels J.M., The Self-organizing Exploratory Pattern of the Argentine Ant, Journal of Insect Behavior, 3:159-168, 1990.

16.Dorigo M., Caro G., Gambardella L., Ant Algorithms for Discrete Optimization, Artifical Life, Vol.5, No.3, 137-172,1999

17.Dorigo M., Maniezzo V., Colorni A., The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Tansactions on System, Man and Cybernetics, Part-B, Vol.26, No.l, 1996.