基于受限位移約束的蟻群算法在航班著陸調(diào)度問題中的應(yīng)用研究

馬衛(wèi)民，楊文娟，徐 博

?

基于受限位移約束的蟻群算法在航班著陸調(diào)度問題中的應(yīng)用研究

馬衛(wèi)民1,2，楊文娟1，徐 博2

(1.西安工業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院，陜西西安710021；2.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092)

航班著陸調(diào)度問題是機(jī)場(chǎng)跑道調(diào)度中的重要問題，合理的調(diào)度策略將極大的減少航班延誤。本文提出基于受限位移約束的蟻群算法(CPS-AC)，該算法利用了蟻群算法高效的全局搜索能力，同時(shí)結(jié)合CPS確保調(diào)度的可操作性和公平性，能夠?yàn)閷?shí)際的空中交通流量管理提供理論方法和依據(jù)。數(shù)值模擬實(shí)驗(yàn)結(jié)果表明，CPS-AC算法明顯優(yōu)于經(jīng)典的先到先服務(wù)(FCFS)的調(diào)度方法和標(biāo)準(zhǔn)的蟻群算法(AC)，能在較短時(shí)間內(nèi)有效減少著陸航班的總延遲時(shí)間，且具有較好的收斂性。這些對(duì)于減少航班延誤，提高著陸容量具有推動(dòng)作用。

受限位移約束(CPS) ; 蟻群算法；航班著陸調(diào)度

0 引言

近年來，隨著我國(guó)民航產(chǎn)業(yè)的迅速發(fā)展，空域擁堵問題也越來越嚴(yán)重，由此引起的航班延誤問題不僅給航空公司造成巨大的經(jīng)濟(jì)損失，而且嚴(yán)重威脅到機(jī)場(chǎng)及空域的安全。合理調(diào)度到達(dá)航班對(duì)于保障飛行安全、降低延誤損失以及提高顧客滿意度等具有重大意義。

傳統(tǒng)的對(duì)到達(dá)航班流的調(diào)度方式通常采用先到先服務(wù)(FCFS)策略。它基于管制員的工作經(jīng)驗(yàn)，在滿足各種限制條件下按照先到先下降的策略為到達(dá)航班制定著陸次序和著陸時(shí)間，使隊(duì)列中航班的總延誤時(shí)間最小。在交通繁忙時(shí)，F(xiàn)CFS策略往往導(dǎo)致跑道利用效率低下，空中滯留航班過多而危及飛行安全。為解決這些問題，國(guó)內(nèi)外學(xué)者提出了許多優(yōu)化方法[1-5]。

比較突出的兩種方法是受限位移約束(CPS)和蟻群算法。Dear等人首次提出受限位移約束的思想[6]，即在調(diào)度時(shí)，相對(duì)于飛機(jī)初始在FCFS中的位置，只允許其向前或者向后移動(dòng)個(gè)位置(為最大受限位移)。這一做法可以大大縮小搜索空間，同時(shí)使可操作性更強(qiáng)。隨后大量的學(xué)者在CPS的框架下設(shè)計(jì)新的算法[7-12]。其中，最新的研究成果是Balakrishnan和 Chandran用動(dòng)態(tài)規(guī)劃方法求出了航班著陸調(diào)度問題的最優(yōu)解[13]。但該求解算法僅適用于的取值較小的情形。蟻群算法是首先由意大利學(xué)者Dorigo[14]提出的一種新型的啟發(fā)式搜索方法。它具有分布式、正反饋機(jī)制和貪婪式搜索的優(yōu)點(diǎn)，具有很強(qiáng)的全局搜索能力，首先應(yīng)用于TSP問題，并取得較好的結(jié)果。此后，該算法被普遍應(yīng)用于各種領(lǐng)域，如單機(jī)調(diào)度問題、車輛調(diào)度等。Randall第一次將蟻群算法應(yīng)用于跑道調(diào)度問題[15]。隨后Bencheikh等多次利用蟻群算法去生成最初的解來處理單跑道和多跑道的調(diào)度問題[16,17]。Zhan 等結(jié)合滾動(dòng)時(shí)域控制原理(Receding Horizon Control)對(duì)機(jī)場(chǎng)實(shí)時(shí)跑道調(diào)度問題進(jìn)行了研究[18]。在國(guó)內(nèi)，胡祥培等[19]對(duì)蟻群算法的相關(guān)領(lǐng)域進(jìn)行了評(píng)述。此外，許多學(xué)者也將蟻群算法應(yīng)用到航班著陸調(diào)度問題中[20-22]。

本文結(jié)合上述的受限位移約束和蟻群算法，提出基于受限位移約束的蟻群算法(CPS-AC)來解決航班著陸調(diào)度問題。這樣一方面利用蟻群算法強(qiáng)大的全局搜索能力，另一方面結(jié)合CPS確保了調(diào)度的可操作性和公平性，能夠較好的應(yīng)用于實(shí)際的交通管理系統(tǒng)中。更重要的是，蟻群算法結(jié)合CPS進(jìn)行研究，可以彌補(bǔ)以往對(duì)CPS研究的不足。這是因?yàn)?，用?jīng)典的動(dòng)態(tài)規(guī)劃方法求解CPS模型，只能解決當(dāng)飛機(jī)的最大受限位移較小時(shí)的情形。隨著求解問題的規(guī)模的增大(飛機(jī)允許前后移動(dòng)的最大位置變大)，動(dòng)態(tài)規(guī)劃方法求解的算法復(fù)雜度將呈指數(shù)增加[13]，從而不能得到一個(gè)較好的解。而CPS-AC算法能夠在這種情況下給出一個(gè)不錯(cuò)的可行解，從而拓展了經(jīng)典CPS模型的求解適用范圍。

1 航班著陸調(diào)度問題模型和CPS策略

1.1航班著陸調(diào)度模型

航班著陸調(diào)度問題是為了盡可能的減少航班延誤，即對(duì)于一些給定的需要下降的航班，怎樣使它們?cè)诳罩械目傃舆t時(shí)間最小。對(duì)于需要下降的架航班，假設(shè)調(diào)度后的航班著陸序列為，令為序列中的第架航班(位于位置),則航班著陸調(diào)度問題需要優(yōu)化的目標(biāo)函數(shù)為

(2)

1.2CPS策略

CPS策略是指某架飛機(jī)在調(diào)度后的位置與其初始在FCFS中的位置之差要控制在一定范圍內(nèi)，即某飛機(jī)在調(diào)度過程中，相對(duì)于初始位置，其最多向前或者向后移動(dòng)個(gè)位置。如有架航班，航班在FCFS隊(duì)列中的位置為，則調(diào)度后其位置必須在和之間，其中為受限偏移半徑，表示調(diào)度后位置的偏移量的最大值。表1給出了=6，=1時(shí)各個(gè)航班的可能位置。

表1=6，=1時(shí)航班的可分配位置[13]

1.3 最小時(shí)間間隔(MST)

為飛機(jī)制定最小時(shí)間間隔是為了避免飛機(jī)產(chǎn)生的尾渦流對(duì)后機(jī)的影響，對(duì)于不同類型的航班，其產(chǎn)生和抵抗尾渦流的能力也不相同，因此要根據(jù)飛機(jī)類型及著陸次序制定不同的最小時(shí)間間隔(MST)。如表2所示，一架波音727在一架波音 747 之后降落需要的MST為200s，而一架波音747在一架波音 727之后降落需要的MST僅為72s。

表2 飛機(jī)尾渦流間隔標(biāo)準(zhǔn)(s)[23]

尾流間隔后機(jī) 1234 前機(jī)196200181228 2728070110 37210070130 472807090

注：1=Boeing 747, 2=Boeing 727, 3=Boeing 707, 4=DC9

2 基于CPS的蟻群算法設(shè)計(jì)

本文結(jié)合CPS與蟻群算法的優(yōu)勢(shì)，提出CPS-AC算法。這主要是為彌補(bǔ)當(dāng)最大受限位移較大時(shí)經(jīng)典動(dòng)態(tài)規(guī)劃算法無(wú)法求解CPS的不足，同時(shí)確保了調(diào)度的公平性，使該算法能夠更好的運(yùn)用于現(xiàn)實(shí)的交通管理系統(tǒng)中。CPS-AC算法的設(shè)計(jì)思路如下：

(4)

(2)信息素更新策略

(6)

3 航班著陸調(diào)度的CPS-AC算法描述

CPS-AC算法結(jié)合CPS策略改進(jìn)了經(jīng)典的蟻群算法，一方面提高了運(yùn)行速度，另一方面給出的調(diào)度策略更加貼近實(shí)際。下面給出CPS-AC算法求解航班著陸調(diào)度問題的具體步驟：

Step2: 結(jié)合在CPS約束中每個(gè)位置可能的航班分配和狀態(tài)轉(zhuǎn)移概率公式選擇下一個(gè)位置的待著陸航班。

Step3: 檢查每只螞蟻的禁忌表，即為一個(gè)航班排序組合，并按公式(2)計(jì)算該組合中每架航班的著陸時(shí)間，從而得出每只螞蟻所選擇序列的總延遲時(shí)間。找出本次循環(huán)中最小的總延遲時(shí)間，記為，對(duì)應(yīng)的飛機(jī)排序組合為。若，則，否則不變。

Step4：按公式(5)和公式(6)更新信息素。

4 數(shù)值試驗(yàn)與仿真

為檢驗(yàn)CPS-AC算法的模型求解的可行性和求解效果，本文在最大受限位移取值較小()和較大時(shí)(=5,10),分別將CPS-AC算法與FCFS算法和傳統(tǒng)的蟻群算法(AC)進(jìn)行比較,并對(duì)算法的穩(wěn)定性進(jìn)行了分析(如圖1)。其中CPS-AC算法選取的參數(shù)分別為：=1；=5；=0.1；=100；=150；=100。

在MATLAB2013a環(huán)境下實(shí)現(xiàn)了CPS-AC算法與AC算法。

此外，為進(jìn)一步檢查該測(cè)試結(jié)果的穩(wěn)定性，更好的對(duì)AC-CPS和AC以及FCFS進(jìn)行比較，分別對(duì)于表3中的數(shù)據(jù)進(jìn)行50次仿真計(jì)算，得出的結(jié)果如表4所示?？梢姡罅康臄?shù)值統(tǒng)計(jì)結(jié)果仍然證實(shí)了上述結(jié)論的正確性。

表3 FCFS、AC算法、CPS-AC算法得到的航班排序結(jié)果

由表5可以看出，標(biāo)準(zhǔn)的蟻群算法(AC)在航班數(shù)量較少時(shí)()能取得一定的優(yōu)化結(jié)果(延誤時(shí)間比FCFS調(diào)度方法減少了10%～14%)，當(dāng)航班數(shù)量較多時(shí)(),AC算法很難進(jìn)行優(yōu)化，且運(yùn)行時(shí)間較長(zhǎng)。對(duì)于CPS-AC算法，當(dāng)=5時(shí)，CPS-AC算法得到的航班著陸隊(duì)列的總延遲時(shí)間比FCFS調(diào)度方法減少了26%～38%；當(dāng)=10時(shí)，CPS-AC算法得到的航班著陸隊(duì)列的總延遲時(shí)間減少了17%～36%。隨著航班數(shù)量和最大受限位移增大(求解問題規(guī)模變大)，算法的效率會(huì)有一定程度的降低。但是，這個(gè)趨勢(shì)是可控的，即使在求解問題規(guī)模較大()時(shí)，該算法仍能較為有效的減少航班延誤。

表4 AC算法、CPS-AC算法的比較

表5 FCFS、AC算法、CPS-AC算法的總延遲時(shí)間的比較（k=5,10）

(3)算法的穩(wěn)定性

圖1CPS-AC算法的收斂性

5 結(jié)論

本文為解決航班著陸調(diào)度問題，提出了一種新的解決框架，即將CPS與蟻群算法相結(jié)合。這樣既利用蟻群算法強(qiáng)大的全局搜索能力和較好的收斂性，又加入CPS約束，避免了由于著陸隊(duì)列次序的調(diào)整幅度較大而引起的某些航班過于靠后的情況，在一定程度上體現(xiàn)了航班降落的公平性，同時(shí)也減小了管制人員的工作負(fù)荷。更為重要的是，CPS-AC算法拓展了經(jīng)典CPS模型的求解適用范圍，給出CPS中當(dāng)最大受限位移較大情況下的可行解。文章最后通過仿真將CPS-AC算法與FCFS調(diào)度方法和標(biāo)準(zhǔn)蟻群算法(AC)分別進(jìn)行比較，結(jié)果表明，該算法明顯優(yōu)于FCFS調(diào)度方法和標(biāo)準(zhǔn)的蟻群算法，在值較大及航班數(shù)量較多的情況仍能有效減少著陸航班的總延誤時(shí)間，從而在一定程度上降低航班延誤成本并減少航空公司的經(jīng)濟(jì)損失。此外，在算法中更有效的設(shè)置約束條件以滿足現(xiàn)實(shí)復(fù)雜空管約束，以及將該算法擴(kuò)展到多跑道航班著陸調(diào)度問題中是我們今后進(jìn)一步的研究方向。

[1] Briskorn D, Stolletz R. Aircraft landing problems with aircraft classes[J]. Journal of Scheduling, 2014, 17: 31-45.

[2] Tavakkoli-Moghaddam R, Yaghoubi-Panah M, Radmehr F. Scheduling the sequence of aircraft landings for a single runway using a fuzzy programming approach[J]. Journal of Air Transport Management, 2012, 25: 15-18.

[3] Beasley JE, Krishnamoorthy M, Sharaiha YM, et al. Scheduling aircraft landings-the static case[J]. Transportation Science, 2000, 34(2): 180-197.

[4] 余江，蒲云. 飛機(jī)著陸調(diào)度優(yōu)化——帶移動(dòng)時(shí)間窗的隱枚舉算法[J]. 系統(tǒng)工程理論方法應(yīng)用，2004, 13(2): 182-186.

[5] 應(yīng)圣鋼，孫富春, 胡來紅，等. 基于多目標(biāo)動(dòng)態(tài)規(guī)劃的多跑道進(jìn)港排序[J]. 控制理論與應(yīng)用，2010, 27(7): 828-835.

[6] Dear RG. The dynamic scheduling of aircraft in the near terminal area[R]. MIT Flight Transportation Report R76-9, Massachusetts Institute of Technology, Cambridge, 1976.

[7] Psaraftis HN. A dynamic programming approach for sequencing groups of identical jobs[J]. Operations Research, 1980, 28(6): 1347-1359.

[8] Dear RG, Sherif YS. An algorithm for computer assisted sequencing and scheduling of terminal area operations[J]. Transportation Research, Part A, Policy Practice 1991, 25(2-3): 129-139.

[9] Neuman F, Erzberger H. Analysis of delay reducing and fuel saving sequencing and spacing algorithms for arrival spacing[R]. NASA technical report A-91203; NAS 1.15:103880; NASA-TM-103880. Retrieved August 2008, NASA Technical Reports Server (NTRS), 1991.

[10] Trivizas DA. Optimal scheduling with maximum position shift (MPS)constraints: A runway scheduling application[J]. Journal of Navigation 1998, 51(2): 250-266.

[11] de Neufville R, Odoni AR. Airport Systems: Planning, Design and Management[J]. McGraw-Hill, New York, 2003.

[12] Carr FR. Robust decision-support tools for airport surface traffic[D]. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2004.

[13] Balakrishnan H, Chandran BG. Algorithms for scheduling runway operations under constrained position shifting[J]. Operations Research, 2010,58(6):1650-1665.

[14] Dorigo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-56.

[15] Randall MC. Scheduling aircraft landings using ant colony optimisation[C]. In: Proceedings of The IASTED international conference artificial intelligence and soft computing, Banff, Canada, 2002.

[16] Bencheikh G, Boukachour J, Alaoui AEH, et al. Hybrid method for aircraft landing scheduling based on a job shop formulation[J]. Int J Comput Sci Netw Secur 2009, 9: 78-88.

[17] Bencheikh G, Boukachour J, Elhilali Alaoui A. Improved Ant Colony Algorithm to Solve the Aircraft Landing Problem[J]. International Journal of Computer Theory and Engineering 2011, 3(2): 224-233.

[18] Zhan ZH, Zhang J, Liu O, et al. An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem [J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11(2): 399-412.

[19] 胡祥培，丁秋雷，李永先. 蟻群算法研究評(píng)述[J]. 管理工程學(xué)報(bào)，2008,22(2): 74-79.

[20] 張濤, 胡佳研, 李福娟, 等. 基于ASRank和MMAS的蟻群算法求解飛機(jī)指派問題[J]. 管理工程學(xué)報(bào)，2012,26(2): 148-155.

[21] 陳欣, 楊文東, 陸訊, 等. 一種終端區(qū)飛機(jī)排序問題的蟻群算法研究[J]. 山東大學(xué)學(xué)報(bào)(工學(xué)版)，2007, 37(6): 111-117.

[22] 李志榮, 張兆寧. 基于蟻群算法的航班著陸排序[J]. 交通運(yùn)輸工程與信息學(xué)報(bào)，2006, 4(6): 66-69.

[23] Bianco L, Dell’Olmo P, Giordani S. “Scheduling models and algorithms for TMA traffic management,” in Modelling and Simulation in Air Traffic Management[J]. New York: Springer-Verlag, 1997: 139-167.

[24] Willemain TR, Fan H, Ma H. Statistical analysis of intervals between projected airport arrivals[R]. DSES Technical Report 38-04-510, Rensselaer Polytechnic Institute, Troy, NY, 2004.

Ant Colony Algorithm Based on Constraint Position Shifting for Aircraft Landing Problem

MA Wei-min1,2, YANG Wen-juan1, XU Bo2

(1.School of Economics and Management, Xi’an Technological University, Xi’an 710021, China;2.School of Economics and Management, Tongji University, Shanghai 200092, China)

Aircraft landing scheduling problems are salient in the airport runway system. A reasonable scheduling method can greatly reduce the total delay time of aircrafts. Thus, an increasing number of scholars focus on developing various optimization methods to tackle these problems. Two prominent approaches are Constraint Position Shifting (CPS) and Ant Colony (AC) algorithm.

CPS stipulates that all aircrafts are only allowed to move at mostpositions forward or backward from their FCFS (First-Come-First-Served) order, whereis the maximum position shift. It reduces the search space for large scale problems and maintains some level of fairness among different airlines. AC algorithm, another widely used method, is a highly efficient heuristic algorithm, which is firstly developed by Dorigo in travelling salesman problems (TSP). It has many important advantages, such as positive feedback mechanism, greedy search mode and strong global searching ability.

By combining the advantages of AC and CPS mentioned above, we propose the resultant CPS-AC strategy. This new strategy is effective to tackle aircraft landing scheduling problems. It has strong global-search ability and ensures the maneuverability of scheduling and fairness among airlines. At the same time, it reduces controllers’ workload to a certain extent. More importantly, in the course of solving CPS model, a reasonable solution can be obtained when the value ofis not small. This is an important achievement since the classical Dynamic Programming, which is widely used to solve CPS model, only presents effective solutions whenis typically small. AC is an important supplement of problem-solving technology for CPS when k is large.

To test the efficiency of the CPS-AC algorithm, we present some experimental tests where FCFS strategy (First Come First Served) and traditional ant colony algorithm (AC) are used to compare with CPS-AC. First, we test a case whereis set to be 2 and the number of aircrafts () is 30. The results show that CPS-AC algorithm reduces 53.27% of the total delay time more than FCFS strategy, whereas AC reduces 30.70% of the total delay time. The runtime of CPS-AC algorithm is also smaller than that of AC algorithm. That is to say, CPS-AC algorithm is more efficient in reducing the total delay time whenis small. To verify the performance of CPS-AC algorithm when the scale of problem is large, we conduct a series of tests whereis set from 40 to 200 andis set to be 5 and 10, respectively. Similarly, the results also reveal that CPS-AC algorithm is still very promising. CPS-AC algorithm not only outperforms FCFS but also AC algorithm. At last, we analyze the convergence of the CPS-AC algorithm, which has a good convergence.

The paper is concluded with a summary of our research findings, implications and future research directions.

constrained position shifting (CPS); ant colony algorithm; aircraft landing scheduling

中文編輯：杜 ??；英文編輯：Charlie C. Chen

V351.11

A

1004-6062(2016)01-0191-06

10.13587/j.cnki.jieem.2016.01.024

2014-04-26

2014-10-31

國(guó)家自然科學(xué)基金(71071113, 71161016)；全國(guó)優(yōu)秀博士論文作者專項(xiàng)資金資助項(xiàng)目(200782)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20100072110011)；上海市哲學(xué)社會(huì)科學(xué)規(guī)劃課題(2010BZH003)

馬衛(wèi)民(1971—), 男，陜西合陽(yáng)人。西安工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院、陜西省百人計(jì)劃特聘教授，同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院教授(博導(dǎo))，研究方向：運(yùn)籌與運(yùn)作管理、優(yōu)化理論與方法。