航班着陆调度的实时优化方法研究
|
摘要
航班着陆调度(Aircraft Landing Scheduling, ALS)是机场终端区空中流量管理(Air Traffic Flow Management, ATFM)的核心,它旨在为待着陆的航班给出有效的着陆调度方案,保证这些航班能够安全且经济地着陆。研究终端区航班调度问题对确保飞行安全和提高飞行效益具有重大的意义。
航班着陆调度是一个典型的组合优化问题,其存在的多约束等复杂性使得这一问题成为公认的一个难解问题;同时,应用时的调度实时性要求进一步增加了这一问题的求解难度。目前,业内实际采用的先来先服务调度方案简单快速,但它无法进一步提高飞行效率,而且在航班较密集的情况下该算法可能无法给出合理的调度方案;研究界提出的线性规划算法具有高效性和正确性,但缺乏全局搜索能力,在很多情况下很难找到最优解;计算智能算法是近年来解决航班着陆调度问题的一个研究热点,但计算代价过大,特别是在较为繁忙的机场终端区,所以它需要结合有效的启发式方法才能更好的解决航班着陆调度问题。
本文提出了一种新型的优化调度方法来解决航班着陆调度问题。与以往侧重于寻找最优解的方法不同,本文将重点放在达到航班着陆调度的实时性要求上。提出了一种航班着陆调度的实时优化方法。它由两个部分组成:首先,建立基于元胞自动机(Cellular Automate,CA)模拟的虚拟航班着陆过程,得到一个相对较好的航班着陆序列;然后,提出了一种简单但有效的针对性的航班着陆优化调度算法,进一步优化航班着陆序列。
在标准的数据集OR-library上的对比实验表明,该方法不仅可以得到高质量的解,而且其速度要快得多,可以满足实际航班着陆调度的性能要求。
As one of the core contents of Air Traffic Flow Management (ATFM) in terminal area, Aircraft Landing Scheduling (ALS) determines an efficient landing scheduling scheme for a given set of aircrafts in order to insure the safety of aircrafts. Researches about ALS problem have great significance for flight safety and improving flight benefit.
ALS is a typical combinatorial optimization problem, the existence of such complex multi-constraint makes this problem an intractable problem; and the real-time requirement increases the difficulty of the solving this problem. When there are too many planes waiting for landing, FCFS may not provide a feasible solution. Until now, there have been two kinds of scheduling algorithms for addressing ALS problem, one is Linear Programming (LP) algorithm, and the other is Computational Intelligence (CI) algorithm. LP shows high effectiveness and correctness, however it can hardly find the global optimal solution owing to lack of the ability for global search. Nevertheless CI not only has the powerful ability for global search, but also is able to handle nonlinear constraint and goal function. Therefore it has become a hot topic to resolve ALS using CI. However CI likely produces large computational cost especially at busy airports. Thereby CI needs to combine some heuristic methods to address ALS better.
In this paper, we propose a novel approach to address the ALS problem. Compared to previous studies, we put more emphasis in meeting the requirement of real-time scheduling rather than securing a global optimal solution. Our approach, named Cellular-Automata-based Optimization (CAO) consists of two main steps. First, we aim to seek a considerably good aircraft landing sequence via a fast heuristic search base on a Cellular Automata (CA) model. Second, the landing sequence obtained by the CA model is further fine-tuned by a simple yet effective local search procedure.
Experimental study on the standard database was conducted to compare the CAO method and several popular approaches in the literature. It was observed that the CAO method not only managed to attain solutions of higher quality, but also was much faster (in CPU time) than the compared methods. The latter property is of significant importance to applying our method in real-world.
航班着陆调度是一个典型的组合优化问题,其存在的多约束等复杂性使得这一问题成为公认的一个难解问题;同时,应用时的调度实时性要求进一步增加了这一问题的求解难度。目前,业内实际采用的先来先服务调度方案简单快速,但它无法进一步提高飞行效率,而且在航班较密集的情况下该算法可能无法给出合理的调度方案;研究界提出的线性规划算法具有高效性和正确性,但缺乏全局搜索能力,在很多情况下很难找到最优解;计算智能算法是近年来解决航班着陆调度问题的一个研究热点,但计算代价过大,特别是在较为繁忙的机场终端区,所以它需要结合有效的启发式方法才能更好的解决航班着陆调度问题。
本文提出了一种新型的优化调度方法来解决航班着陆调度问题。与以往侧重于寻找最优解的方法不同,本文将重点放在达到航班着陆调度的实时性要求上。提出了一种航班着陆调度的实时优化方法。它由两个部分组成:首先,建立基于元胞自动机(Cellular Automate,CA)模拟的虚拟航班着陆过程,得到一个相对较好的航班着陆序列;然后,提出了一种简单但有效的针对性的航班着陆优化调度算法,进一步优化航班着陆序列。
在标准的数据集OR-library上的对比实验表明,该方法不仅可以得到高质量的解,而且其速度要快得多,可以满足实际航班着陆调度的性能要求。
As one of the core contents of Air Traffic Flow Management (ATFM) in terminal area, Aircraft Landing Scheduling (ALS) determines an efficient landing scheduling scheme for a given set of aircrafts in order to insure the safety of aircrafts. Researches about ALS problem have great significance for flight safety and improving flight benefit.
ALS is a typical combinatorial optimization problem, the existence of such complex multi-constraint makes this problem an intractable problem; and the real-time requirement increases the difficulty of the solving this problem. When there are too many planes waiting for landing, FCFS may not provide a feasible solution. Until now, there have been two kinds of scheduling algorithms for addressing ALS problem, one is Linear Programming (LP) algorithm, and the other is Computational Intelligence (CI) algorithm. LP shows high effectiveness and correctness, however it can hardly find the global optimal solution owing to lack of the ability for global search. Nevertheless CI not only has the powerful ability for global search, but also is able to handle nonlinear constraint and goal function. Therefore it has become a hot topic to resolve ALS using CI. However CI likely produces large computational cost especially at busy airports. Thereby CI needs to combine some heuristic methods to address ALS better.
In this paper, we propose a novel approach to address the ALS problem. Compared to previous studies, we put more emphasis in meeting the requirement of real-time scheduling rather than securing a global optimal solution. Our approach, named Cellular-Automata-based Optimization (CAO) consists of two main steps. First, we aim to seek a considerably good aircraft landing sequence via a fast heuristic search base on a Cellular Automata (CA) model. Second, the landing sequence obtained by the CA model is further fine-tuned by a simple yet effective local search procedure.
Experimental study on the standard database was conducted to compare the CAO method and several popular approaches in the literature. It was observed that the CAO method not only managed to attain solutions of higher quality, but also was much faster (in CPU time) than the compared methods. The latter property is of significant importance to applying our method in real-world.
引文
高海军,王健,陈龙等. 2003.空中交通流量管理研究综述[J].控制工程, 10(6):484-487.
马正平,崔德光,谢玉兰. 2003.机场终端区流量分配及优化调度[J].清华大学学报:自然科学版, 43(7).
余江. 2005.机场扩展终端区的运行优化策略研究[D]: [博士].成都:西南交通大学.
赵嶷飞,王健. 2003.空中交通流量管理仿真系统方案研究[J].中国民航学院学报. 21(3):27-29.
Neuman F, Erzberger H. 1990. Analysis of sequencing and scheduling methods for arrival traffic[R]. Moffett Field, California: NASA, Ames Research Center.
Atkin J.A.D, Burke E.K. Greenwood J.S. 2007. Reeson D., Hybrid Meta-heuristics to Aid Runway Scheduling at London Heathrow[J], in: Transportation Science Vol.41,No. 1, pp. 90-106.
Balakrishnan H, Chandran B. 2006. Scheduling aircraft landings under constrained position shifting[C]. AIAA Guidance, Navigation, and Control Conference and Exhibit. Keystone, Colorado: AIAA.
Bianco L, Rinaldi G, Sassano A. 1987. A combinatorial optimization approach to aircraft sequencing problem[J]. Flow Control of Congested Networks, pp. 323–339
Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al. 2000. Scheduling aircraft landings - the static case[J]. Transportation Science, 34(2):180–197.
Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al. 2004. Displacement problem and dynamically scheduling aircraft landings[J]. Journal of Operational Research Society, 55(1):54–64.
Beasley J E, Sonander J, Havelock P. 2001. Scheduling aircraft landings at London Heathrow using a population heuristic[J]. Journal of Operational Research Society, 52(5):483–493.
Ciesielski V, Scerri P. 1998. Real time genetic scheduling of aircraft landing times[C].Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, 360–364.
Ciesielski V., Scerri P. 1997. An Anytime Algorithm for Scheduling of Aircraft Landing Times Using Genetic Algorithms[J]. in: Aust J Intell Inf Process Systems 4 , pp.206–213.
Chellapilla K. 1998. Combining mutation operators in evolutionary programming[J]. IEEE Transactions on Evolutionary Computation, 2(3): 91–96.
Cheng V H L, Crawford L S, Menon P K. 1999. Air traffic control using genetic search techniques[C]. Proceedings of the 1999 IEEE International Conference on Control Applications, 1:249-254.
Ernst A T, Krishnamoorthy M, Storer R H. 1999. Heuristic and exact algorithms for scheduling aircraft landings[J]. Networks, 34(3):229–241.
Grefenstette J J, Gopal R, Rosmaita B J, et al. 1985. Genetic algorithms for the traveling salesman problem[C]. Proc. 1st Int. Conf. Genetic Algorithms, 160–168.
Gregory C C, Erzberger H, Neuman F. 1999. Delay exchanges in arrival sequencing and scheduling[J]. Journal of Aircraft, 36(5):785–791.
Gregory C C, Erzberger H, Neuman F. 2000. Fast-time study of airline-in?uenced arrival sequencing and scheduling[J]. Journal of Guidance, Control and Dynamics, 23(3):526–531.
Ho P Y, Shimizu K. 2007. Evolutionary constrained optimization using an addition of ranking method and a percentage-based tolerance value adjustment scheme[J]. Information Sciences, 177(14):2985-3004.
Hu X B, Chen W H. 2005. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling[J]. Engineering Applications of Artificial Intelligence, 18(5):633–642.
Hu X B, Paolo E.A.D. 2008. Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 9(2): 301-310.
Hu X B, Chen W H, Paolo E.A.D. 2007. Multiairport Capacity Management Genetic Algorithm With Receding Horizon[J]. Intelligent Transportation Systems, IEEE Transactions on Volume 8, Issue 2, pp. 254– 263
Jia B, Jiang R, Wu Q S, Hu M B. 2005. Honk effect in the two-lane cellular automaton model for traffic flow[J]. Physica A 348, pp. 544-552.
Li X B, Wu Q S, Jiang R. 2001. Cellular automaton model considering the velocity effect of a car on the successive car[J], PHYSICAL REVIEW E, VOLUME 64, 066128.
Liu F R, Wang Q L, Gao X Z. 2006. Survey of artificial immune system[C]. 1st International Symposium on Systems and Control in Aerospace and Astronautics, 985-989.
Mcgovern L K, Feron E. 1999. Closed-loop stability of systems driven by real-time, dynamic optimization algorithms[C]. Proceedings of the 38th IEEE Conference on Decision and Contro, 4:3690–3696.
Michalewicz Z, Schoenauer M. 1996. Evolutionary algorithms for constrained parameter optimization problems[J]. Evolutionary Computation, 4(1):1-32.
Moser I, Hendtlass T. 2007. Solving Dynamic Single-Runway Aircraft Landing Problems with Extremal Optimisation[C]. Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Scheduling (CI-Sched 2007)
Mu S J, Su H Y, Chu J, et al. 2003. An infeasibility degree selection based genetic algorithms for constrained optimization problems[C]. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2:1950-1954.
Mullins J, 1996. Trails of destruction[J]. New Scientist 2056, 28-31.
Nagel K, Schreckenberg M. 1992. cellular automaton model for freeway traffic[J]. Phys. I France 2, pp. 2221-2229.
Park J H, Yoo H W, Han S, et al. 2007. Receding horizon control for input-delayed systems[C]. 46th IEEE Conference on Decision and Control, 1368–1373.
Pinol H, Beasley J.E, 2006. Scatter Search and Bionomic Algorithms for the aircraft landing problem[J]. in: European Journal of Operational Research 171 439–462
Randall M, 2002. Scheduling Aircraft Landings with Ant Colony Optimisation[C]. Proceedings of the International Conference Artificial Intelligence and Soft Computing, , pp. 129-133.
Sarkar P, 2000. A Brief History of Cellular Automata[J]. ACM Computing Surveys (CSUR), 32, 1, pp. 80-107.
Simons R. 1997. Making best use of the world’s favourite runways[J]. OR Newsletter 19-21.
Zhang X, Zhang X J, Zhang J, et al. 2007. Optimization of sequencing for aircraft arrival based on approach routes, 10th International IEEE Conference on Intelligent Transportation Systems, 592-596.
马正平,崔德光,谢玉兰. 2003.机场终端区流量分配及优化调度[J].清华大学学报:自然科学版, 43(7).
余江. 2005.机场扩展终端区的运行优化策略研究[D]: [博士].成都:西南交通大学.
赵嶷飞,王健. 2003.空中交通流量管理仿真系统方案研究[J].中国民航学院学报. 21(3):27-29.
Neuman F, Erzberger H. 1990. Analysis of sequencing and scheduling methods for arrival traffic[R]. Moffett Field, California: NASA, Ames Research Center.
Atkin J.A.D, Burke E.K. Greenwood J.S. 2007. Reeson D., Hybrid Meta-heuristics to Aid Runway Scheduling at London Heathrow[J], in: Transportation Science Vol.41,No. 1, pp. 90-106.
Balakrishnan H, Chandran B. 2006. Scheduling aircraft landings under constrained position shifting[C]. AIAA Guidance, Navigation, and Control Conference and Exhibit. Keystone, Colorado: AIAA.
Bianco L, Rinaldi G, Sassano A. 1987. A combinatorial optimization approach to aircraft sequencing problem[J]. Flow Control of Congested Networks, pp. 323–339
Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al. 2000. Scheduling aircraft landings - the static case[J]. Transportation Science, 34(2):180–197.
Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al. 2004. Displacement problem and dynamically scheduling aircraft landings[J]. Journal of Operational Research Society, 55(1):54–64.
Beasley J E, Sonander J, Havelock P. 2001. Scheduling aircraft landings at London Heathrow using a population heuristic[J]. Journal of Operational Research Society, 52(5):483–493.
Ciesielski V, Scerri P. 1998. Real time genetic scheduling of aircraft landing times[C].Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, 360–364.
Ciesielski V., Scerri P. 1997. An Anytime Algorithm for Scheduling of Aircraft Landing Times Using Genetic Algorithms[J]. in: Aust J Intell Inf Process Systems 4 , pp.206–213.
Chellapilla K. 1998. Combining mutation operators in evolutionary programming[J]. IEEE Transactions on Evolutionary Computation, 2(3): 91–96.
Cheng V H L, Crawford L S, Menon P K. 1999. Air traffic control using genetic search techniques[C]. Proceedings of the 1999 IEEE International Conference on Control Applications, 1:249-254.
Ernst A T, Krishnamoorthy M, Storer R H. 1999. Heuristic and exact algorithms for scheduling aircraft landings[J]. Networks, 34(3):229–241.
Grefenstette J J, Gopal R, Rosmaita B J, et al. 1985. Genetic algorithms for the traveling salesman problem[C]. Proc. 1st Int. Conf. Genetic Algorithms, 160–168.
Gregory C C, Erzberger H, Neuman F. 1999. Delay exchanges in arrival sequencing and scheduling[J]. Journal of Aircraft, 36(5):785–791.
Gregory C C, Erzberger H, Neuman F. 2000. Fast-time study of airline-in?uenced arrival sequencing and scheduling[J]. Journal of Guidance, Control and Dynamics, 23(3):526–531.
Ho P Y, Shimizu K. 2007. Evolutionary constrained optimization using an addition of ranking method and a percentage-based tolerance value adjustment scheme[J]. Information Sciences, 177(14):2985-3004.
Hu X B, Chen W H. 2005. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling[J]. Engineering Applications of Artificial Intelligence, 18(5):633–642.
Hu X B, Paolo E.A.D. 2008. Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 9(2): 301-310.
Hu X B, Chen W H, Paolo E.A.D. 2007. Multiairport Capacity Management Genetic Algorithm With Receding Horizon[J]. Intelligent Transportation Systems, IEEE Transactions on Volume 8, Issue 2, pp. 254– 263
Jia B, Jiang R, Wu Q S, Hu M B. 2005. Honk effect in the two-lane cellular automaton model for traffic flow[J]. Physica A 348, pp. 544-552.
Li X B, Wu Q S, Jiang R. 2001. Cellular automaton model considering the velocity effect of a car on the successive car[J], PHYSICAL REVIEW E, VOLUME 64, 066128.
Liu F R, Wang Q L, Gao X Z. 2006. Survey of artificial immune system[C]. 1st International Symposium on Systems and Control in Aerospace and Astronautics, 985-989.
Mcgovern L K, Feron E. 1999. Closed-loop stability of systems driven by real-time, dynamic optimization algorithms[C]. Proceedings of the 38th IEEE Conference on Decision and Contro, 4:3690–3696.
Michalewicz Z, Schoenauer M. 1996. Evolutionary algorithms for constrained parameter optimization problems[J]. Evolutionary Computation, 4(1):1-32.
Moser I, Hendtlass T. 2007. Solving Dynamic Single-Runway Aircraft Landing Problems with Extremal Optimisation[C]. Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Scheduling (CI-Sched 2007)
Mu S J, Su H Y, Chu J, et al. 2003. An infeasibility degree selection based genetic algorithms for constrained optimization problems[C]. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2:1950-1954.
Mullins J, 1996. Trails of destruction[J]. New Scientist 2056, 28-31.
Nagel K, Schreckenberg M. 1992. cellular automaton model for freeway traffic[J]. Phys. I France 2, pp. 2221-2229.
Park J H, Yoo H W, Han S, et al. 2007. Receding horizon control for input-delayed systems[C]. 46th IEEE Conference on Decision and Control, 1368–1373.
Pinol H, Beasley J.E, 2006. Scatter Search and Bionomic Algorithms for the aircraft landing problem[J]. in: European Journal of Operational Research 171 439–462
Randall M, 2002. Scheduling Aircraft Landings with Ant Colony Optimisation[C]. Proceedings of the International Conference Artificial Intelligence and Soft Computing, , pp. 129-133.
Sarkar P, 2000. A Brief History of Cellular Automata[J]. ACM Computing Surveys (CSUR), 32, 1, pp. 80-107.
Simons R. 1997. Making best use of the world’s favourite runways[J]. OR Newsletter 19-21.
Zhang X, Zhang X J, Zhang J, et al. 2007. Optimization of sequencing for aircraft arrival based on approach routes, 10th International IEEE Conference on Intelligent Transportation Systems, 592-596.