面向正常性的飛機(jī)排班優(yōu)化算法

呂宗磊，王 舳

(1.中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300；2.中國(guó)民航大學(xué) 中國(guó)民航信息技術(shù)科研基地，天津 300300)

0 引 言

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

現(xiàn)有的研究主要以成本、收益、飛機(jī)利用率等作為優(yōu)化目標(biāo)，航班正常性是民航局關(guān)注的焦點(diǎn)問(wèn)題之一，現(xiàn)有的研究很少著眼于這個(gè)方面?？紤]加入到飛機(jī)執(zhí)行航班的過(guò)程中，由同一架飛機(jī)執(zhí)行的航班，前序航班的延誤影響到后續(xù)航班的運(yùn)行，所以面向正常性的飛機(jī)排班較之其它目標(biāo)更為復(fù)雜。因此，本文在飛機(jī)排班模型基礎(chǔ)上，以航班計(jì)劃正常性作為優(yōu)化目標(biāo)，設(shè)計(jì)了基于關(guān)聯(lián)規(guī)則挖掘的多階段混合求解策略。

1 問(wèn)題描述

廣義的航班計(jì)劃一般指和航空生產(chǎn)活動(dòng)相關(guān)的生產(chǎn)計(jì)劃，包括飛機(jī)維修計(jì)劃、機(jī)組排班、飛行路徑規(guī)劃以及狹義的航班計(jì)劃。狹義的航班計(jì)劃是指制定航班時(shí)刻，按照一定約束為每個(gè)飛機(jī)分配航班任務(wù)，也就是保證每個(gè)航班任務(wù)有且只有一個(gè)飛機(jī)執(zhí)行的飛機(jī)分配過(guò)程。這一過(guò)程可以看作依據(jù)飛機(jī)等其它約束下對(duì)航班任務(wù)集合進(jìn)行劃分的過(guò)程。

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

延誤可以分為獨(dú)立延誤及波及延誤。獨(dú)立延誤是由航班自身原因引起的延誤，與其飛行路徑無(wú)關(guān)；即上文所述的推出時(shí)間、飛行時(shí)間、滑入時(shí)間過(guò)長(zhǎng)導(dǎo)致的航班未按計(jì)劃準(zhǔn)時(shí)起降；而波及延誤是由同一飛機(jī)順序執(zhí)行的兩個(gè)航班，由于前序航班的晚到而導(dǎo)致后續(xù)航班無(wú)法按時(shí)起降而引起的延誤。在航班獨(dú)立延誤分布被計(jì)算出來(lái)的情況下，波及延誤同樣可以通過(guò)分布的疊加計(jì)算得到。當(dāng)航班計(jì)劃內(nèi)所有航班延誤概率都通過(guò)分布表達(dá)后，整個(gè)航班計(jì)劃的正常性就能通過(guò)簡(jiǎn)單的數(shù)學(xué)計(jì)算得到。

2 相關(guān)工作

求解飛機(jī)排班問(wèn)題，為飛機(jī)分配航班任務(wù)的過(guò)程中，必須滿足一定的約束條件。時(shí)空銜接約束是飛機(jī)排班問(wèn)題中的重要約束條件。時(shí)空銜接約束是時(shí)間銜接約束和空間銜接約束的總稱。時(shí)間銜接約束是指在航班執(zhí)行的過(guò)程中，由同一飛機(jī)連續(xù)執(zhí)行的兩個(gè)航班，時(shí)間間隔必須大于局方標(biāo)準(zhǔn)過(guò)站時(shí)間，它是影響航班運(yùn)行正常性的關(guān)鍵因素；空間銜接約束是指飛機(jī)連續(xù)執(zhí)行兩個(gè)航班時(shí)，前序航班的降落機(jī)場(chǎng)為后序航班的起飛機(jī)場(chǎng)，保證航班能夠按計(jì)劃執(zhí)行。

關(guān)聯(lián)規(guī)則挖掘是基于給定的規(guī)則，搜索得到數(shù)據(jù)之間關(guān)系的算法，其核心是基于兩階段頻集思想的遞推算法。關(guān)聯(lián)規(guī)則挖掘研究課題中的一個(gè)重要研究基礎(chǔ)是頻繁項(xiàng)集挖掘，頻繁項(xiàng)集挖掘算法的研究方向一般包括遍歷方向上的研究、搜索策略上的研究、候選項(xiàng)集產(chǎn)生上的研究和數(shù)據(jù)庫(kù)分布上的研究。Apriori算法是其中最經(jīng)典頻繁項(xiàng)集挖掘方法之一，其基本思想為通過(guò)單遍掃描數(shù)據(jù)集得到頻繁1-項(xiàng)集，之后逐層迭代，由頻繁k項(xiàng)集產(chǎn)生候選k+1項(xiàng)集，直到無(wú)法產(chǎn)生新的頻繁項(xiàng)集時(shí)結(jié)束。定理1、定理2是Apriori算法的基礎(chǔ)：

定理1 如果一個(gè)集合是頻繁項(xiàng)集，則它的所有非空子集都是頻繁項(xiàng)集。

定理2 如果一個(gè)集合不是頻繁項(xiàng)集，則它的所有超集都不是頻繁項(xiàng)集。

現(xiàn)階段研究中固定支持度約束下進(jìn)行頻繁項(xiàng)集的搜索依舊是以頻繁項(xiàng)集挖掘?yàn)楹诵牡年P(guān)聯(lián)規(guī)則挖掘算法的研究重心。目前，許多關(guān)聯(lián)規(guī)則挖掘?qū)嵺`中，支持度和置信度的取值方法仍舊依據(jù)先驗(yàn)知識(shí)進(jìn)行人為制定，文獻(xiàn)[10]提出的自適應(yīng)關(guān)聯(lián)規(guī)則挖掘算法使用統(tǒng)計(jì)擬合技術(shù)，對(duì)支持度和置信度進(jìn)行自動(dòng)化調(diào)整，降低算法對(duì)先驗(yàn)知識(shí)的依賴。

集覆蓋問(wèn)題是在一個(gè)集合中，滿足覆蓋集合中所有個(gè)體條件的情況下，所選擇的總的子集個(gè)數(shù)最小或費(fèi)用最小的問(wèn)題。

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

3 兩階段航班排班優(yōu)化模型

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

求解候選航班串是兩階段算法的基礎(chǔ)，研究如何快速求解一個(gè)好的候選航班串可以減小集合覆蓋的困難程度，有效提高問(wèn)題求解的效率。航班正常性的統(tǒng)計(jì)存在以下特點(diǎn)，若某個(gè)航班串符合正常性要求，那么其所有子航班串也必定符合正常性要求；若航班串不符合正常性要求，則所有包含它的航班串也不符合正常性要求?；诖?，本文使用的候選航班串構(gòu)建算法參考關(guān)聯(lián)規(guī)則挖掘的思想，以航班串的正常性作為支持度和置信度，待排航班作為初始數(shù)據(jù)集進(jìn)行頻繁項(xiàng)的挖掘，其中得到的頻繁項(xiàng)即為所求候選航班串。

相應(yīng)的數(shù)學(xué)模型如下

(1)

(2)

xk=0,1

(3)

4 閾值動(dòng)態(tài)調(diào)整策略

在前述算法流程中僅僅考慮在符合正常性約束情況下使用最少飛機(jī)數(shù)量執(zhí)行航班計(jì)劃，但是由于航空公司實(shí)際可執(zhí)行任務(wù)的飛機(jī)數(shù)量有限，很難設(shè)置一個(gè)合適的閾值，使得得到的結(jié)果恰好滿足飛機(jī)數(shù)量需求，所以為了滿足航空公司實(shí)際運(yùn)行需求，往往需要對(duì)正常性閾值進(jìn)行動(dòng)態(tài)調(diào)整。在前述兩階段混合求解算法中，由于產(chǎn)生的候選集合中包含航班串?dāng)?shù)量很大，且每一次計(jì)算所花費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)候選集覆蓋所需的時(shí)間，動(dòng)態(tài)調(diào)整策略做如下設(shè)計(jì)：

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

圖1 正常性閾值與最小飛機(jī)數(shù)量散點(diǎn)趨勢(shì)

正常性閾值動(dòng)態(tài)調(diào)整過(guò)程中一共涉及到兩種閾值變化情況：

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

(2)s′

第一種情況下，只需要在原有的頻繁項(xiàng)集合中去除正常性小于閾值的個(gè)體和它們的超集，得到新的頻繁項(xiàng)集；在這個(gè)過(guò)程中不需要重新計(jì)算集合中每個(gè)個(gè)體的正常性，需要花費(fèi)的時(shí)間代價(jià)不高，計(jì)算較為簡(jiǎn)單。第二種情況下，當(dāng)正常性閾值變小時(shí)，為了避免對(duì)已計(jì)算過(guò)頻繁項(xiàng)集進(jìn)行重復(fù)計(jì)算，在候選航班串集合Lk生成的過(guò)程中，保存每一次計(jì)算得到的候選集合，對(duì)正常性低于閾值的個(gè)體并不是簡(jiǎn)單的刪除，而是保留下來(lái)，存儲(chǔ)在航班串集合Nk中，Nk+Lk=Ck，Ck為所有被計(jì)算過(guò)的候選K-項(xiàng)集；當(dāng)s′

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

輸入：航班任務(wù)集合F，飛機(jī)數(shù)量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中的各集合，將正常性小于新閾值的項(xiàng)及其超集加入到對(duì)應(yīng)的Nk中，得到更新后的L、N；

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

所以加入閾值動(dòng)態(tài)調(diào)整策略后的整體算法流程如下：

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

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

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

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

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

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

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

5 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)使用航空公司2016至2017歷史運(yùn)行數(shù)據(jù)對(duì)吉祥航空2018年冬春航班計(jì)劃進(jìn)行正常性的優(yōu)化。選取其中一天的總計(jì)326個(gè)航班任務(wù)，分配給65架飛機(jī)執(zhí)行。表1為所有待排航班信息。

5.1 生成初始航班計(jì)劃表

使用前文所述方法，選取民航局規(guī)定的處罰標(biāo)準(zhǔn)70%作為初始正常性閾值，構(gòu)建候選航班串集合，并以此為基礎(chǔ)，以所需飛機(jī)數(shù)量最少為目標(biāo)構(gòu)建航班覆蓋模型，基于分支定界法對(duì)構(gòu)建的航班覆蓋模型求解，得到的結(jié)果見(jiàn)表2，這個(gè)結(jié)果為在符合航班覆蓋條件約束和正常約束條件下，所需要的飛機(jī)最少情況下的航班計(jì)劃表。

表1 航班信息

表2 初始計(jì)劃

由得到的初始航班計(jì)劃表可知，若要所有航班都符合正常性要求，至少需要105架飛機(jī)執(zhí)行該航班任務(wù)，大于航空公司現(xiàn)有的飛機(jī)數(shù)量，若要保證所有航班實(shí)際運(yùn)行符合正常性要求，計(jì)劃執(zhí)行過(guò)程中需要依據(jù)實(shí)際運(yùn)行情況進(jìn)行實(shí)時(shí)調(diào)整。

初始正常性閾值改變，若計(jì)算得到的結(jié)果依舊不滿足飛機(jī)數(shù)量條件，依舊需要進(jìn)入下一步動(dòng)態(tài)調(diào)整中，最終結(jié)果不會(huì)變化。若初始正常性閾值變小到初始最優(yōu)結(jié)果能夠滿足實(shí)際運(yùn)行需求，那么初始最優(yōu)方案就為最終結(jié)果。

5.2 閾值的動(dòng)態(tài)調(diào)整

正常性閾值是算法中的一項(xiàng)重要指標(biāo)，當(dāng)?shù)玫降慕Y(jié)果無(wú)法滿足航空公司實(shí)際運(yùn)行條件時(shí)，使用動(dòng)態(tài)調(diào)整策略，在有限的飛機(jī)數(shù)量下，盡可能保證航班計(jì)劃整體正常性，得到的結(jié)果見(jiàn)表3。

表3 改進(jìn)的計(jì)劃

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

表4 仿真結(jié)果

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

6 結(jié)束語(yǔ)

傳統(tǒng)飛機(jī)排班方法針對(duì)飛機(jī)延誤問(wèn)題考慮不到位，在航班運(yùn)行過(guò)程中無(wú)法預(yù)先在計(jì)劃編排的過(guò)程中對(duì)航班延誤進(jìn)行有效控制與預(yù)防。在飛機(jī)排班的過(guò)程中考慮航班延誤時(shí)，對(duì)延誤產(chǎn)生的原因以及其后續(xù)影響方式進(jìn)行分析。本文將航班延誤分為獨(dú)立延誤以及波及延誤，且利用歷史運(yùn)行數(shù)據(jù)對(duì)獨(dú)立延誤的產(chǎn)生和后續(xù)的波及延誤進(jìn)行預(yù)估，基于此建立了面向航班正常的排班優(yōu)化模型。航空公司依靠預(yù)先對(duì)航班計(jì)劃進(jìn)行優(yōu)化減少波及延誤，即獨(dú)立延誤對(duì)后續(xù)航班產(chǎn)生的影響。模型求解方面使用兩階段啟發(fā)式算法對(duì)模型進(jìn)行優(yōu)化求解并且創(chuàng)新性的使用動(dòng)態(tài)調(diào)整策略對(duì)正常性閾值進(jìn)行有效的控制和調(diào)整以快速求得有效的航班計(jì)劃。通過(guò)實(shí)例分析，本模型在減少航班計(jì)劃性延誤方面有著較好的效果，對(duì)于航空公司預(yù)防航班延誤，編排一個(gè)計(jì)劃正常性較高的航班計(jì)劃有一定的參考價(jià)值。