基于改進(jìn)遺傳算法的最小油耗機場飛行區(qū)布局優(yōu)化

李汝寧，馮 興

(1. 天津職業(yè)技術(shù)師范大學(xué) 汽車與交通學(xué)院，天津 300222； 2. 中國民航大學(xué) 交通科學(xué)與工程學(xué)院，天津 300300)

0 引 言

民航業(yè)是高能耗的產(chǎn)業(yè)，不斷推動民航業(yè)節(jié)能減排，實現(xiàn)社會經(jīng)濟可持續(xù)發(fā)展的目標(biāo)顯得尤為關(guān)鍵。隨著民航業(yè)高速發(fā)展，作為民航業(yè)三大支柱之一的機場，其數(shù)量和容量也在不斷擴大，能源消耗比重日益增長[1]。除降低機場建筑能耗的措施外[2]，通過對機場飛行區(qū)進(jìn)行合理布局，減小飛機著陸→滑行→等待→滑行→起飛的整體油耗，也是降低機場能源消耗的有效手段之一。

機場飛行區(qū)包括跑道、滑行道和停機坪等，其布局問題屬于優(yōu)化范疇[3-9]。國內(nèi)外學(xué)者根據(jù)不同的優(yōu)化目標(biāo)和約束條件，建立了飛行區(qū)布局優(yōu)化模型，并用優(yōu)化算法進(jìn)行了求解。YU Chuhang等[10-12]以提高機場跑道和滑行道容量為研究目標(biāo)，建立一種帶邊約束的劃分模型，運用綜合算法進(jìn)行了求解；種小雷等[13]以提高快速出口滑行道利用率為研究目標(biāo)，建立了基于綜合利用率的快速出口位置優(yōu)化模型，總結(jié)了基于利用率的快速出口位置確定步驟；O.E.GUCLU等[14]和C.CETEK等[15]分別以減小飛機滑行時間和滑行延誤為優(yōu)化目標(biāo)，均提出了一種混合動態(tài)的滑行路徑和登機口分配方法；ZHANG Tianci等[16-17]提出了一種基于區(qū)域控制的動態(tài)滑行路徑和時刻算法，用于求解飛機最短滑行時間的滑行路徑和時刻。綜上，現(xiàn)有機場飛行區(qū)布局研究主要針對已建設(shè)完成的飛行區(qū)布局構(gòu)型，通過合理的運行組織，以達(dá)到提高運行性能的目的；以降低飛行區(qū)飛機燃油消耗為目的的飛行區(qū)規(guī)劃研究則鮮有相關(guān)文獻(xiàn)。

筆者從新建和改建機場飛行區(qū)布局規(guī)劃出發(fā)，以減小飛機燃油消耗為研究目的，以跑道、滑行道和停機坪相對位置及停機坪、停機位分配為研究對象，建立了飛機從著陸到起飛的全過程飛行區(qū)燃油消耗仿真模型；設(shè)計完成了可兼顧停機位分配和跑道、滑行道及停機坪相對位置優(yōu)化的一種改進(jìn)混合編碼遺傳算法；在此基礎(chǔ)上，應(yīng)用燃油消耗仿真模型完成了滿足改進(jìn)混合編碼遺傳算法優(yōu)化的適應(yīng)度函數(shù)設(shè)計；完成了包含停機位分配在內(nèi)的飛行區(qū)布局優(yōu)化。

1 機場飛行區(qū)燃油消耗仿真模型

根據(jù)《2019年民航行業(yè)發(fā)展統(tǒng)計公報》[1]的統(tǒng)計數(shù)據(jù)，截至2019年底，我國共有頒證運輸機場238個，全行業(yè)運輸機場共有跑道261條，單跑道機場占全部機場的92%以上。2019年新增了4個機場，除北京大興國際機場外，其余3個機場均為單跑道機場[1]。從機場運量及需求出發(fā)，未來各地機場的修建基本也會以單跑道機場為主。故筆者以單跑道機場飛行區(qū)布局和停機位分配為研究對象，建立了考慮停機位分配的單跑道飛行區(qū)燃油消耗仿真模型。

圖1為單跑道機場飛行區(qū)布局示意。

圖1 單跑道機場飛行區(qū)布局Fig. 1 Single runway airport airfield layout

以跑道中線為X軸，跑道左端為零點，建立平面直角坐標(biāo)系，飛機降落點、飛機起飛點及快速滑行道進(jìn)出口位置等關(guān)鍵點及其坐標(biāo)如圖1。機場停機坪根據(jù)所能停靠飛機的類型，將停機位分為小型機、中型機和大型機這3種類型。停機坪數(shù)字代表停機位序號，停機坪相對跑道滑行道位置由停機坪與滑行道交口位置來確定。

根據(jù)不同類型的飛機著陸和起飛過程，分別考慮飛機著陸過程和起飛過程的油耗。因此，飛行區(qū)燃油消耗仿真模型如式(1)：

(1)

式中：i代表飛機類型，i=1為小型機，i=2為中型機，i=3為大型機；Qi,著陸為i類型飛機著陸過程油耗；Qi,起飛為i類型飛機起飛過程油耗；Ki為i類型飛機日架次。

1.1 飛機著陸燃油消耗仿真模型

由于風(fēng)向等氣候原因，飛機可以選擇在跑道右端著陸，即著陸點為圖1中的關(guān)鍵點6；也可選擇在跑道左端著陸，即著陸點為圖1中的關(guān)鍵點6′。因此，i類型飛機著陸燃油消耗仿真模型如式(2)：

Qi,著陸=Qi,著陸左×Pi,著陸+Qi,著陸右× (1-Pi,著陸)

(2)

式中：Pi,著陸為i類型飛機在跑道左端著陸的概率；Qi,著陸左為i類型飛機在跑道左端著陸的燃油消耗。

Qi,著陸左的計算如式(3)：

(3)

式中：vi,1為i類型飛機自飛機著陸點6′到快速滑行道入口5的平均速度；qi,1為此過程飛機的單位時間平均油耗；vi,2為i類型飛機自快速滑行道入口5到快速滑行道出口4的平均速度；qi,2為此過程飛機的單位時間平均油耗；vi,3為i類型飛機自快速滑行道出口4到達(dá)序號n停機位的平均速度；qi,3為此過程飛機的單位時間平均油耗；d1為停機位與平行滑行道間距；d2為停機位間距；N為總停機位數(shù)。

Qi,著陸右為i類型飛機在跑道右端著陸的燃油消耗。飛機在跑道右端著陸過程與在左端著陸過程類似，故其燃油消耗如式(4)：

(4)

1.2 飛機起飛燃油消耗仿真模型

飛機起飛的方向和飛機著陸類似，可根據(jù)風(fēng)向等氣候原因選擇在跑道左端起飛，即起飛點為圖1中的關(guān)鍵點8；也可選擇在跑道右端起飛，即起飛點為圖1中的關(guān)鍵點8′。故i類型飛機起飛燃油消耗仿真模型如式(5)：

Qi,起飛=Qi,起飛左×Pi,起飛+Qi,起飛右×(1-Pi,起飛)

(5)

式中：Pi,起飛為i類型飛機在跑道左端起飛的概率；Qi,起飛左、Qi,起飛右分別為i類型飛機在跑道左、右端起飛的燃油消耗。

Qi,起飛左的計算如式(6)：

(6)

式中：vi,4為i類型飛機自序號為n的停機位，經(jīng)滑行道左端所在的位置2到達(dá)跑道左端所在位置1的平均速度；qi,4為此過程中飛機單位時間的平均油耗；vi,5為i類型飛機從跑道左端所在位置1到飛機起飛所在位置8的平均速度；qi,5為此過程中飛機單位時間的平均油耗；ti為i類型飛機在跑道左端位置1所等待的時間；qi,6為此過程中飛機單位時間的油耗。

飛機在跑道右端起飛過程與左端類似。因此，Qi,起飛右的計算如式(7)：

(7)

2 改進(jìn)遺傳算法設(shè)計

停機位的分配和飛行區(qū)的布局優(yōu)化涉及到兩個不同類型的優(yōu)化對象，常規(guī)基因編碼及基因的選擇、變異和交叉等操作方式難以對該問題進(jìn)行有效表達(dá)和求解?；诖藛栴}，筆者從基因編碼方式及相對應(yīng)的遺傳操作和解的映射等方面出發(fā)，對遺傳算法進(jìn)行了針對性的改進(jìn)。

2.1 適應(yīng)度函數(shù)設(shè)計

對機場停機位分配和飛行區(qū)布局優(yōu)化的目標(biāo)是為了使得飛行區(qū)的飛機燃油消耗最低。通過改進(jìn)遺傳算法優(yōu)化目標(biāo)為搜索適應(yīng)度的最大值，通過變換，確定機場停機位分配和飛行區(qū)布局優(yōu)化的適應(yīng)度函數(shù)Fit如式(8)：

(8)

式中：Pu為懲罰因子。

Pu值小于1，其作用是在選擇操作中減小不可行解被選中的概率。

2.2 混合編碼設(shè)計

停機位分配和飛行區(qū)結(jié)構(gòu)參數(shù)若采取同一種基因編碼的方式，則在解的映射過程中會產(chǎn)生大量的不可行解，從而增加了不必要的計算量，并最終影響優(yōu)化效果。

針對該問題，筆者設(shè)計了一種混合編碼方式。其中：停機位分配采用實數(shù)編碼方式，基因與解之間為直接映射關(guān)系，通過懲罰函數(shù)約束不可行解；飛行區(qū)結(jié)構(gòu)參數(shù)采取二進(jìn)制編碼方式，基因與解之間通過解的取值范圍進(jìn)行映射。圖2為一條混合編碼基因的結(jié)構(gòu)示意。

圖2 混合編碼基因的結(jié)構(gòu)示意Fig. 2 Schematic diagram of the structure of mixed coding gene

圖2中：Pop(c)為基因序號為c的基因，該基因的前N位為實數(shù)編碼，表示停機位分配；N為總停機位數(shù)，其中1代表小型機，2代表中型機，3代表大型機；該基因的后L×M位為二進(jìn)制編碼，表示飛行區(qū)結(jié)構(gòu)參數(shù)編碼，M代表飛行區(qū)結(jié)構(gòu)參數(shù)的數(shù)量，L代表一個結(jié)構(gòu)參數(shù)的二進(jìn)制基因串長度。

飛行區(qū)結(jié)構(gòu)參數(shù)編碼與解(飛行區(qū)結(jié)構(gòu)參數(shù))的映射關(guān)系如式(9)：

(9)

式中：A為參數(shù)x對應(yīng)長度為L的二進(jìn)制字符串；Rangemax為參數(shù)x的最大值；Rangemin為參數(shù)x的最小值。

2.3 遺傳操作設(shè)計

改進(jìn)遺傳的操作與基本遺傳算法的選擇一致，采取比例選擇方式，依據(jù)個體的適應(yīng)度，確定其被選中的概率，適應(yīng)度越大，被選中的概率就會越大[18-23]。

基因編碼采取實數(shù)和二進(jìn)制混合編碼的方式，且不同編碼方式代表的含義不同。為避免產(chǎn)生大量不可行解，同時又要保證基因之間染色體交流，故交叉和變異操作均采取分部的方式進(jìn)行。

圖3為交叉操作的示意。圖3中：Pop(c)和Pop(c+1)為兩條相鄰基因?；蚋鶕?jù)編碼方式不同，將交叉操作分為兩部分進(jìn)行，其中實數(shù)編碼采取自身交叉方式；二進(jìn)制編碼采取相互基因之間隨機相互交叉方式，該交叉操作不會產(chǎn)生不可行解。圖4為變異操作的示意。圖4中：Pop′(c)為Pop(c)經(jīng)變異操作后，產(chǎn)生了新的基因。與交叉操作類似，變異操作也分為兩部分，其中實數(shù)編碼部分為隨機位的1或2或3的變異；二進(jìn)制編碼部分為隨機位的0或1變異。變異操作中容易產(chǎn)生不可行解，通過適應(yīng)度函數(shù)的設(shè)計、懲罰因子的設(shè)置，能降低不可行解的影響。

圖3 交叉操作示意Fig. 3 Schematic diagram of cross operation

圖4 變異操作示意Fig. 4 Schematic diagram of mutation operation

為避免最優(yōu)基因在選擇、交叉和變異的遺傳操作中被破壞，降低適應(yīng)度較低的基因(或不可行解的基因)對其他優(yōu)良基因的影響，筆者采用“最優(yōu)保存”策略，即最優(yōu)基因不參與選擇、交叉和變異操作，同時對適應(yīng)度較低的基因進(jìn)行替換。

綜上，改進(jìn)遺傳算法對停機位分配和飛行區(qū)布局優(yōu)化的基本流程如圖5。

圖5 優(yōu)化流程Fig. 5 The flow chart of optimization

步驟①：以停機位分配、停機坪位置參數(shù)x3和快速滑行道與跑道的銳角α為優(yōu)化參數(shù)，隨機生成初始化種群，種群中每個基因采取實數(shù)(停機位分配)和二進(jìn)制(停機坪位置參數(shù)x3和快速滑行道與跑道的銳角α)混合編碼(圖2)；

步驟②：根據(jù)飛行區(qū)結(jié)構(gòu)參數(shù)編碼與解(飛行區(qū)結(jié)構(gòu)參數(shù))的映射關(guān)系〔式(9)〕進(jìn)行參數(shù)編碼與解的映射，并完成可行解的判斷；

步驟③：可行解和不可行解可分別采用適應(yīng)度函數(shù)〔式(8)〕進(jìn)行計算，其中針對不可行解引入懲罰因子Pu，降低了不可行解的適應(yīng)度值；

步驟④：判斷是否滿足停止條件(達(dá)到最大進(jìn)化代數(shù))；若滿足，進(jìn)入步驟⑩，不滿足則進(jìn)入步驟⑤；

步驟⑤：采用“最優(yōu)保存”策略，即最優(yōu)基因不參與選擇、交叉和變異操作，直接進(jìn)入下一代種群，剩余基因進(jìn)入選擇、交叉和變異操作；

步驟⑥：采取比例選擇方式，依據(jù)其個體的適應(yīng)度，確定其被選中的概率，完成基因選擇操作；

步驟⑦：為避免大量的不可行解產(chǎn)生，同時實現(xiàn)基因中染色體交流，實數(shù)編碼采取自身交叉方式，二進(jìn)制編碼采取相互基因之間隨機相互交叉方式；

步驟⑧：變異操作分兩部分進(jìn)行，其中實數(shù)編碼部分為隨機位的1或2或3變異；二進(jìn)制編碼部位為隨機位的0或1變異(變異操作中易產(chǎn)生不可行解，通過適應(yīng)度函數(shù)的設(shè)計、懲罰因子的設(shè)置，降低不可行解的影響)；

步驟⑨：經(jīng)過選擇、交叉和變異后產(chǎn)生的新基因和上一代最優(yōu)基因組成新一代種群，并進(jìn)入步驟②；

步驟⑩：輸出包含最優(yōu)停機位分配方案在內(nèi)的飛行區(qū)布局參數(shù)和應(yīng)用改進(jìn)遺傳算法優(yōu)化的過程數(shù)據(jù)。

3 停機位分配和飛行區(qū)布局優(yōu)化

3.1 優(yōu)化參數(shù)描述

在飛行區(qū)燃油消耗模型中，i類型飛機在不同階段的滑行速度vi,1、vi,2、vi,3、vi,4和vi,5，相對應(yīng)的單位時間平均油耗qi,1、qi,2、qi,3、qi,4、qi,5和待機單位時間平均油耗qi,6，起飛場長和降落距離均為飛機工作參數(shù)，可通過該類型飛機的飛機手冊和發(fā)動機動力特性曲線確定[3,24-28]。筆者選取A320、B787、B747等機型分別代表小型機、中型機和大型機，這3種不同類型飛機的不同階段滑行速度如表1；不同階段平均油耗如表2；每種類型飛機起飛場長、日平均架次和左端起飛和降落概率如表3?？紤]不同類型飛機降落距離及降落速度等因素，確定快速滑行道入口位置距離跑道端部距離為2 km。

表1 飛機平均滑行速度Table 1 Average taxiing speed of aircraft (km·h-1)

表2 飛機平均油耗Table 2 Average fuel consumption of aircraft (kg·h-1)

表3 機場運行參數(shù)Table 3 Airport operating parameters

根據(jù)優(yōu)化機場等級為4E，確定跑道長度為3.6 km；考慮不同類型飛機翼展及升降帶寬度等因素，確定平行滑行道中線距離跑道中線的最小距離為0.2 km；停機位與平行滑行道最小間距為0.2 km，停機位間距為0.15 km，共設(shè)定停機位為10個，其中小型機停機位5個，中型機停機位3個，大型機停機位2個。

綜上，確定優(yōu)化參數(shù)為不同類型停機位的分配、停機坪位置參數(shù)x3和快速滑行道與跑道的銳角α。約束條件如式(10)：

(10)

3.2 優(yōu)化和結(jié)果分析

筆者應(yīng)用Python語言，編制了應(yīng)用改進(jìn)遺傳算法進(jìn)行停機位分配與飛行區(qū)布局優(yōu)化的程序，并在此基礎(chǔ)上進(jìn)行了優(yōu)化分析。根據(jù)優(yōu)化參數(shù)和優(yōu)化目標(biāo)，確定的改進(jìn)遺傳算法運行參數(shù)如表4。

表4 改進(jìn)遺傳算法運行參數(shù)Table 4 The operation parameters of improved genetic algorithm

圖6為每代種群中可行解與不可行解的個數(shù)和不可行解的比例。由圖6可知：第1代種群，由于是初次生成，故全部為可行解；隨著進(jìn)化進(jìn)行，變異操作中產(chǎn)生了不可行解，但不可行解個數(shù)控制在50左右，不可行解占全部種群的比例低于5.1%，因此不可行解對可行解的影響較小，同時還可通過懲罰函數(shù)進(jìn)一步降低不可行解的影響，以保證整體種群規(guī)模的健康狀況。

圖6 種群健康狀況Fig. 6 Population health status

圖7為應(yīng)用改進(jìn)遺傳算法對停機位分配和飛行區(qū)布局進(jìn)行優(yōu)化過程中，最大適應(yīng)度、平均適應(yīng)度和飛行區(qū)燃油消耗的變化曲線。由圖7可知：隨著進(jìn)化進(jìn)行，最優(yōu)適應(yīng)度值逐漸升高，飛行區(qū)燃油消耗量逐漸減??；當(dāng)進(jìn)化到75代左右時，最優(yōu)適應(yīng)度達(dá)到最大值，此時飛行區(qū)燃油消耗量也降到最低值(32 754 kg)，并一直保持到進(jìn)化結(jié)束。平均適應(yīng)度也呈現(xiàn)逐漸上升并向最優(yōu)適應(yīng)度靠攏的趨勢，這說明種群中的每個個體通過選擇、交叉和變異等遺傳操作均在向最優(yōu)個體收斂。

圖7 適應(yīng)度和燃油消耗量變化曲線Fig. 7 The fitness and fuel consumption variation curve

圖8為飛行區(qū)布局優(yōu)化參數(shù)(停機坪位置參數(shù)x3和快速滑行道與跑道的銳角α)隨著進(jìn)化進(jìn)行，每一代種群中最優(yōu)個體的變化曲線。由圖8可知：當(dāng)進(jìn)化到75代左右后，優(yōu)化參數(shù)收斂，x3=2.2 km，α=44.4°。表5為每代種群中的最優(yōu)停機位分配方案。同其他參數(shù)優(yōu)化進(jìn)程類似，當(dāng)進(jìn)化到75代左右后，停機位分配方案確定。

圖8 飛行區(qū)布局優(yōu)化參數(shù)變化曲線Fig. 8 Variation curve of flight area layout optimization parameters

表5 停機位分配方案Table 5 The scheme of stand allocation

由本例可看出：采取實數(shù)和二進(jìn)制編碼的混合編碼方式可有效實現(xiàn)對優(yōu)化參數(shù)的描述；懲罰因子、分部交叉和變異操作和最優(yōu)保存策略等的設(shè)計也可保證在不產(chǎn)生大量不可行解及最優(yōu)基因不被破壞的前提下，實現(xiàn)基因中染色體的交流，有效地提高了優(yōu)化的收斂速度和收斂精度。因此，采用改進(jìn)后的遺傳算法可實現(xiàn)包含停機坪停機位分配在內(nèi)的飛行區(qū)布局優(yōu)化，達(dá)到飛行區(qū)飛機燃油消耗最低的目標(biāo)。

4 結(jié) 論

1)筆者以單跑道機場飛行區(qū)為研究對象，以飛行區(qū)燃油消耗為研究目標(biāo)，針對飛機的起飛和著陸過程，建立了飛行區(qū)燃油消耗數(shù)學(xué)仿真模型。該模型可直觀地反映出飛行區(qū)結(jié)構(gòu)參數(shù)及停機坪停機位分配對飛行區(qū)燃油消耗的影響，并為下一步采用改進(jìn)遺傳算法對停機位分配和飛行區(qū)布局優(yōu)化設(shè)計奠定基礎(chǔ)。

2)通過對停機位分配和飛行區(qū)布局結(jié)構(gòu)參數(shù)優(yōu)化的分析，建立了實數(shù)編碼和二進(jìn)制編碼相結(jié)合的混合編碼方式，并在此基礎(chǔ)上對選擇、交叉和變異等遺傳操作方式進(jìn)行了改進(jìn)；同時采用懲罰函數(shù)降低了在變異操作中對不可行解的影響；針對停機位分配和飛行區(qū)布局優(yōu)化問題所進(jìn)行的遺傳算法改進(jìn)，具有收斂速度快、優(yōu)化結(jié)果好、有助于飛行區(qū)飛機燃油消耗降低等特點，研究方法可為飛行區(qū)平面布局規(guī)劃提供一定參考。

3)影響停機位分配和飛行區(qū)布局的因素較多，后續(xù)可結(jié)合機場資源的利用效率及乘客的換乘體驗等因素進(jìn)一步開展研究；同時，還可將研究方法進(jìn)一步擴展至多跑道機場飛行區(qū)布局優(yōu)化中。