面向正常性的飛機排班優化算法

呂宗磊，王 舳

(1.中國民航大學 計算機科學與技術學院，天津 300300；2.中國民航大學 中國民航信息技術科研基地，天津 300300)

0 引 言

飛機排班是依據一定業務規則為飛機分配航班任務的過程，是航空公司運輸活動開展的核心。在建模方面，旅行商問題模型、多商品網絡流模型[1,2]、整數規劃[3]、0-1整數規劃模型、時空網絡模型[4]等都可以作為飛機排班問題的基礎模型，M Lindner等[5]考慮飛機老化對燃油消耗的影響擬定航班計劃，最大限度降低運營成本。在求解策略方面，朱星輝等[1]采用了列生成法對飛機排班模型進行求解。針對飛機使用均衡的飛機排班問題，范永俊等[6]提出了基于分支定界法的求解方案，劉婧、賈寶惠[7]用啟發式構造可行的解決方案，D’Ariano A等[8]嘗試使用調度規則、啟發式算法和分支定界法進行問題的求解并且進行了對比。文獻[9]嘗試使用貪婪隨機自適應搜索過程生成新的鄰域解以解決不正常航班的恢復問題。它將飛機的執行過程當作一個整體，將飛機的獨立延誤時間看作正態分布進行正常性的計算，做出了一些探索性的嘗試。但實際上，航班的飛行時間很難準確表示成典型性分布。

現有的研究主要以成本、收益、飛機利用率等作為優化目標，航班正常性是民航局關注的焦點問題之一，現有的研究很少著眼于這個方面。考慮加入到飛機執行航班的過程中，由同一架飛機執行的航班，前序航班的延誤影響到后續航班的運行，所以面向正常性的飛機排班較之其它目標更為復雜。因此，本文在飛機排班模型基礎上，以航班計劃正常性作為優化目標，設計了基于關聯規則挖掘的多階段混合求解策略。

1 問題描述

廣義的航班計劃一般指和航空生產活動相關的生產計劃，包括飛機維修計劃、機組排班、飛行路徑規劃以及狹義的航班計劃。狹義的航班計劃是指制定航班時刻，按照一定約束為每個飛機分配航班任務，也就是保證每個航班任務有且只有一個飛機執行的飛機分配過程。這一過程可以看作依據飛機等其它約束下對航班任務集合進行劃分的過程。

飛機執行航班任務的過程可以分為飛機推出、飛行、滑入和保障4個階段，這4個部分時間的總和為該航班任務完成、可以執行下一航班任務的總時間。由于這4個部分均可能會因特定事件的影響而對執行時長造成波動，且對造成波動的這些事件是否會發生、對時間影響程度有多強烈是不確定的，因此可以用不確定事件刻畫上述各部分的時間。因此想要準確描述飛機執行航班的具體過程，可以將每個航班的各部分的時長分布根據歷史數據分別計算得到，進而通過對每個部分依據歷史數據進行疊加得到整個航線延誤的概率。

延誤可以分為獨立延誤及波及延誤。獨立延誤是由航班自身原因引起的延誤，與其飛行路徑無關；即上文所述的推出時間、飛行時間、滑入時間過長導致的航班未按計劃準時起降；而波及延誤是由同一飛機順序執行的兩個航班，由于前序航班的晚到而導致后續航班無法按時起降而引起的延誤。在航班獨立延誤分布被計算出來的情況下，波及延誤同樣可以通過分布的疊加計算得到。當航班計劃內所有航班延誤概率都通過分布表達后，整個航班計劃的正常性就能通過簡單的數學計算得到。

2 相關工作

求解飛機排班問題，為飛機分配航班任務的過程中，必須滿足一定的約束條件。時空銜接約束是飛機排班問題中的重要約束條件。時空銜接約束是時間銜接約束和空間銜接約束的總稱。時間銜接約束是指在航班執行的過程中，由同一飛機連續執行的兩個航班，時間間隔必須大于局方標準過站時間，它是影響航班運行正常性的關鍵因素；空間銜接約束是指飛機連續執行兩個航班時，前序航班的降落機場為后序航班的起飛機場，保證航班能夠按計劃執行。

關聯規則挖掘是基于給定的規則，搜索得到數據之間關系的算法，其核心是基于兩階段頻集思想的遞推算法。關聯規則挖掘研究課題中的一個重要研究基礎是頻繁項集挖掘，頻繁項集挖掘算法的研究方向一般包括遍歷方向上的研究、搜索策略上的研究、候選項集產生上的研究和數據庫分布上的研究。Apriori算法是其中最經典頻繁項集挖掘方法之一，其基本思想為通過單遍掃描數據集得到頻繁1-項集，之后逐層迭代，由頻繁k項集產生候選k+1項集，直到無法產生新的頻繁項集時結束。定理1、定理2是Apriori算法的基礎：

定理1 如果一個集合是頻繁項集，則它的所有非空子集都是頻繁項集。

定理2 如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。

現階段研究中固定支持度約束下進行頻繁項集的搜索依舊是以頻繁項集挖掘為核心的關聯規則挖掘算法的研究重心。目前，許多關聯規則挖掘實踐中，支持度和置信度的取值方法仍舊依據先驗知識進行人為制定，文獻[10]提出的自適應關聯規則挖掘算法使用統計擬合技術，對支持度和置信度進行自動化調整，降低算法對先驗知識的依賴。

集覆蓋問題是在一個集合中，滿足覆蓋集合中所有個體條件的情況下，所選擇的總的子集個數最小或費用最小的問題。

集覆蓋問題最早由Roth和Toregas等為解決消防中心和救護車等的應急服務設施選址問題而提出，使用整數規劃模型進行建模求解。整數規劃是一種特殊的線性規劃，在線性模型中，變量受限制為整數，整數規劃最典型的解法是逐步生成原問題的衍生問題，通過對每個衍生問題進行松弛求解確定原問題是否被舍棄，重復上述步驟直到問題不能產生新的未解決的衍生問題，此時衍生問題的解即為原問題的解。目前比較常用的整數規劃求解方法是分支定界和割平面法。

3 兩階段航班排班優化模型

由于作為優化目標的正常性是一個分布，所以相應的目標函數是一個期望值，該問題不是一個線性問題，直接求解比較困難。為此，本文建立了兩階段航班排班優化模型。模型的第一個階段先產生候選航班串，在滿足航班銜接約束的前提下，保留其中滿足正常性要求的航班串，作為航班計劃制定的基礎，航班串正常性的計算方式在第一章中已經有所提及，所以在此不做過多的描述。第二階段是在候選航班串的基礎上，選擇構成航班計劃的航班串，被選擇的航班串應該滿足航班串中包含的待分配航班都在被選擇的航班串中至少出現并且只出現一次的要求。如果產生的排班結果不能滿足飛機數量要求，則松弛正常性的要求，重新計算產生航班計劃。盡量選擇正常性較高的航班構成航班計劃。

求解候選航班串是兩階段算法的基礎，研究如何快速求解一個好的候選航班串可以減小集合覆蓋的困難程度，有效提高問題求解的效率。航班正常性的統計存在以下特點，若某個航班串符合正常性要求，那么其所有子航班串也必定符合正常性要求；若航班串不符合正常性要求，則所有包含它的航班串也不符合正常性要求。基于此，本文使用的候選航班串構建算法參考關聯規則挖掘的思想，以航班串的正常性作為支持度和置信度，待排航班作為初始數據集進行頻繁項的挖掘，其中得到的頻繁項即為所求候選航班串。

相應的數學模型如下

(1)

(2)

xk=0,1

(3)

4 閾值動態調整策略

在前述算法流程中僅僅考慮在符合正常性約束情況下使用最少飛機數量執行航班計劃，但是由于航空公司實際可執行任務的飛機數量有限，很難設置一個合適的閾值，使得得到的結果恰好滿足飛機數量需求，所以為了滿足航空公司實際運行需求，往往需要對正常性閾值進行動態調整。在前述兩階段混合求解算法中，由于產生的候選集合中包含航班串數量很大，且每一次計算所花費的時間遠遠超過候選集覆蓋所需的時間，動態調整策略做如下設計：

首先，依據第一階段產生的候選航班串數據，得到不同正常性航班串數量分布關系，得到飛機使用數量被滿足的情況下，正常性閾值的估計值；使用該估計值替代原先設置的初始值，得到新的候選航班串集合，再使用集覆蓋問題模型進行建模求解，產生飛機數量約束的解。再用梯度下降的方式提升正常性閾值，迭代多次，直到產生的解不再符合飛機數量的約束，此時上一代解是該算法求得的最優解。

圖1 正常性閾值與最小飛機數量散點趨勢

正常性閾值動態調整過程中一共涉及到兩種閾值變化情況：

(1)s′>s，原有的一些候選航班集合不滿足新的最小正常性閾值的情況，從而由頻繁項集變成非頻繁項集；

(2)s′

第一種情況下，只需要在原有的頻繁項集合中去除正常性小于閾值的個體和它們的超集，得到新的頻繁項集；在這個過程中不需要重新計算集合中每個個體的正常性，需要花費的時間代價不高，計算較為簡單。第二種情況下，當正常性閾值變小時，為了避免對已計算過頻繁項集進行重復計算，在候選航班串集合Lk生成的過程中，保存每一次計算得到的候選集合，對正常性低于閾值的個體并不是簡單的刪除，而是保留下來，存儲在航班串集合Nk中，Nk+Lk=Ck，Ck為所有被計算過的候選K-項集；當s′

候選航班集合更新算法流程如下：

輸入：航班任務集合F，飛機數量m，初始正常性閾值s，新閾值s′

L={L1,L2,L3,…}，N={N1,N2,N3,…}

輸出：L={L′1,L′2,L′3,…}，N={N′1,N′2,N′3,…}

(1)比較新閾值s′和初始閾值s的大小，若s′

(2)依次掃描L中的各集合，將正常性小于新閾值的項及其超集加入到對應的Nk中，得到更新后的L、N；

(3)依次掃描N中的各集合，正常性大于新閾值的項使用前文所述算法得到新的集合L′，N′，更新后的L、N為初始L、N與L′、N′的并集。

所以加入閾值動態調整策略后的整體算法流程如下：

輸入:F為航班任務集合，初始正常性閾值為s，飛機數量m，梯度值ε

輸出:飛機排班方x={x1,x2,x3,…,xm}

(1)使用前文所述候選航班串生成算法，構建初始候選航班串集合，L={L1,L2,L3,…}，N={N1,N2,N3,…}；

(2)基于L={L1,L2,L3,…}，求解集覆蓋模型，最小飛機數量m′，解為x′={x1,x2,x3,…,xm}；

(3)若m′>m，將計算得到的正常性閾值-最小飛機數量數據加入已知數據中，使用前文所述公式重新計算得到新閾值s′，更新候選航班集合，得到L′，N′，返回(2)；

(4)s′=s+ε求解集覆蓋模型，最小飛機數量m″，解為x″={x1,x2,x3,…,xm}；

(5)若m″>m，上一步的x′為所求最優解，否則返回(4)。

5 實驗及結果分析

實驗使用航空公司2016至2017歷史運行數據對吉祥航空2018年冬春航班計劃進行正常性的優化。選取其中一天的總計326個航班任務，分配給65架飛機執行。表1為所有待排航班信息。

5.1 生成初始航班計劃表

使用前文所述方法，選取民航局規定的處罰標準70%作為初始正常性閾值，構建候選航班串集合，并以此為基礎，以所需飛機數量最少為目標構建航班覆蓋模型，基于分支定界法對構建的航班覆蓋模型求解，得到的結果見表2，這個結果為在符合航班覆蓋條件約束和正常約束條件下，所需要的飛機最少情況下的航班計劃表。

表1 航班信息

表2 初始計劃

由得到的初始航班計劃表可知，若要所有航班都符合正常性要求，至少需要105架飛機執行該航班任務，大于航空公司現有的飛機數量，若要保證所有航班實際運行符合正常性要求，計劃執行過程中需要依據實際運行情況進行實時調整。

初始正常性閾值改變，若計算得到的結果依舊不滿足飛機數量條件，依舊需要進入下一步動態調整中，最終結果不會變化。若初始正常性閾值變小到初始最優結果能夠滿足實際運行需求，那么初始最優方案就為最終結果。

5.2 閾值的動態調整

正常性閾值是算法中的一項重要指標，當得到的結果無法滿足航空公司實際運行條件時，使用動態調整策略，在有限的飛機數量下，盡可能保證航班計劃整體正常性，得到的結果見表3。

表3 改進的計劃

我們對算法迭代過程中得到的中間結果與最終得到航班計劃依據歷史數據進行仿真實驗，對得到的正常性評估結果進行對比，得到的對比結果見表4。其中迭代梯度值ε的選取影響著迭代次數與實驗結果的精度。ε越小，迭代次數越多，計算精度越高，反之則反。在實際運行中，當選取的梯度值小到一定程度時梯度的變化很難影響到實驗結果的變化，綜合考慮以上因素，實驗選取的迭代梯度值ε=0.005。

表4 仿真結果

從仿真結果我們可以看出，優化后的航班計劃正常性有了一定的提升，其中原計劃中存在共66個正常率小于70%的航班，平均正常率為84.76%，即在該航班計劃在實際運行過程中，若不對航班的運行進行實時調整，有66個航班有較大概率因運行正常率小于70%被民航局處罰。而使用兩階段優化算法得到的航班計劃結果，被處罰的航班數量被減少到了48，其中涉及到的航線數量由31下降到了26，航班計劃總正常率維持在84.7%左右。雖然鄰域搜索經過大量的計算之后也能取得較好的效果，但是由于算法選擇領域解方面有較強的隨機性，計算復雜度遠大于兩階段優化算法。所以可以驗證，在控制延誤，保證航空公司航班正常運行方面，該兩階段優化算法有著較好的效果。

6 結束語

傳統飛機排班方法針對飛機延誤問題考慮不到位，在航班運行過程中無法預先在計劃編排的過程中對航班延誤進行有效控制與預防。在飛機排班的過程中考慮航班延誤時，對延誤產生的原因以及其后續影響方式進行分析。本文將航班延誤分為獨立延誤以及波及延誤，且利用歷史運行數據對獨立延誤的產生和后續的波及延誤進行預估，基于此建立了面向航班正常的排班優化模型。航空公司依靠預先對航班計劃進行優化減少波及延誤，即獨立延誤對后續航班產生的影響。模型求解方面使用兩階段啟發式算法對模型進行優化求解并且創新性的使用動態調整策略對正常性閾值進行有效的控制和調整以快速求得有效的航班計劃。通過實例分析，本模型在減少航班計劃性延誤方面有著較好的效果，對于航空公司預防航班延誤，編排一個計劃正常性較高的航班計劃有一定的參考價值。