胡玉真，張 聳

(哈爾濱工程大學(xué) 經(jīng)濟(jì)管理學(xué)院，黑龍江 哈爾濱 150001)

0 引言

在民航運(yùn)輸業(yè)中，航班日常運(yùn)行較易受到天氣、空中流量以及公司內(nèi)部等諸多因素干擾而偏離原計(jì)劃，出現(xiàn)不正常航班。不正常航班會(huì)給航空公司帶來(lái)直接的經(jīng)濟(jì)損失和潛在的隱形損失。要徹底根除這些干擾帶來(lái)的損失是不可能的，目前主要是通過(guò)對(duì)飛機(jī)等資源的重調(diào)度使得航班盡快恢復(fù)正常，盡量降低干擾帶來(lái)的各種損失，這個(gè)過(guò)程稱(chēng)之為航班干擾管理[1]。

航班干擾管理問(wèn)題一直受到國(guó)內(nèi)外航空領(lǐng)域和運(yùn)籌優(yōu)化領(lǐng)域研究者的關(guān)注，經(jīng)典的航班干擾管理問(wèn)題是追求延誤和取消總成本的最小化。Hu et al.[2]在2015年已經(jīng)證明，當(dāng)問(wèn)題的目標(biāo)包括最小化總的航班延誤時(shí)間時(shí)，飛機(jī)路徑恢復(fù)問(wèn)題是NP難問(wèn)題。以往的大部分文獻(xiàn)，都嘗試運(yùn)用求解整數(shù)規(guī)劃模型的相關(guān)方法(網(wǎng)絡(luò)流算法、列生成算法、拉格朗日松弛算法)以及智能算法(如遺傳算法、GRASP算法以及鄰域搜索算法等)求解該問(wèn)題。

最早是由Teodorovic et al.[3]運(yùn)用分支定界算法求解3架飛機(jī)8個(gè)航班的航空運(yùn)輸網(wǎng)絡(luò)在受到干擾后的飛機(jī)路徑優(yōu)化問(wèn)題。Yan et al.[4]、Xu et al.[5]、Marla et al.[6]和Vink[7]分別建立了基于時(shí)空網(wǎng)絡(luò)構(gòu)建飛機(jī)恢復(fù)問(wèn)題的整數(shù)規(guī)劃模型。Eggenberg et al.[8]利用列生成算法使得飛機(jī)恢復(fù)問(wèn)題得到解決，其中主問(wèn)題是集合覆蓋問(wèn)題，而子問(wèn)題是帶邊界限制的最短路問(wèn)題，其中對(duì)每個(gè)飛機(jī)，都建立了一個(gè)基于時(shí)段網(wǎng)絡(luò)的恢復(fù)網(wǎng)絡(luò)。詹晨旭和樂(lè)美龍[9]設(shè)計(jì)了基于遺傳算法的啟發(fā)式算法求解分飛機(jī)路徑恢復(fù)問(wèn)題。Bisaillon et al.[10]對(duì)包括飛機(jī)路徑和旅客恢復(fù)的航班調(diào)整問(wèn)題，設(shè)計(jì)了鄰域搜索算法，且目標(biāo)為最小化相應(yīng)的運(yùn)營(yíng)成本以及對(duì)旅客的影響，隨后基于Bisaillon et al.[10]，Sinclair et al.[11]在算法中添加了某些步驟，使得算法更有效。張力菠和鮑和映[12]針對(duì)飛機(jī)資源短缺、機(jī)場(chǎng)臨時(shí)關(guān)閉導(dǎo)致的航班干擾狀況，設(shè)計(jì)算法構(gòu)建了離散時(shí)空網(wǎng)絡(luò)模型，并用商業(yè)軟件進(jìn)行求解。Aktürk et al.[13]在航班恢復(fù)中考慮油耗和航行速度的權(quán)衡。Vos et al.[14]對(duì)每架飛機(jī)建立時(shí)空網(wǎng)絡(luò)模型，并結(jié)合肯尼亞航空公司的實(shí)際數(shù)據(jù)進(jìn)行案例分析和模擬仿真。胡玉真等[15,16]探討了單架飛機(jī)受干擾后的飛機(jī)路徑恢復(fù)問(wèn)題的多項(xiàng)式算法。隨后Hu et al.[17]添加參與恢復(fù)的飛機(jī)數(shù)量和最大延誤時(shí)間作為優(yōu)化目標(biāo)，對(duì)飛機(jī)路徑恢復(fù)問(wèn)題進(jìn)行多目標(biāo)優(yōu)化建模，并運(yùn)用鄰域搜索算法求解該問(wèn)題。

但是上述很多算法都是指數(shù)級(jí)的，且無(wú)法從理論上證明求解方案的最優(yōu)性或近似性。并且大部分文獻(xiàn)為了使得模型具有較好的整數(shù)規(guī)劃模型的性質(zhì)，只建立單目標(biāo)規(guī)劃模型。有些即使建立多目標(biāo)規(guī)劃模型，也會(huì)運(yùn)用線性加權(quán)的方式將目標(biāo)整合為單目標(biāo)形式。但是，航空公司日常運(yùn)營(yíng)比較復(fù)雜，純粹單目標(biāo)的優(yōu)化解并不能真正反應(yīng)航空公司航班運(yùn)營(yíng)恢復(fù)的實(shí)際情況，而運(yùn)用多目標(biāo)建模求解實(shí)際航班調(diào)整方案，可以使得航空公司運(yùn)行控制中心根據(jù)航班計(jì)劃和資源的實(shí)際情況從非劣解集中進(jìn)行選擇，更增加了航班計(jì)劃和飛機(jī)路徑恢復(fù)的靈活性。

如果飛機(jī)只是受到短時(shí)間輕度的干擾，不需要取消航班就能使得航班計(jì)劃在當(dāng)天恢復(fù)正常，那么運(yùn)行控制中心的主要目的就是如何通過(guò)飛機(jī)交換、航班延誤等調(diào)整手段降低航班的延誤時(shí)間。按照中國(guó)民用航空總局的規(guī)定，航班延誤時(shí)間超過(guò)30分鐘，需要向旅客通報(bào)延誤信息。因此，盡量降低最大的航班延誤時(shí)間，會(huì)有效的改善航空公司的服務(wù)質(zhì)量。另外，如何在保證航班延誤時(shí)間較小的目標(biāo)下，實(shí)現(xiàn)動(dòng)用盡可能少的飛機(jī)資源，也更符合航班干擾管理的基本思想。

因此本文針對(duì)輕度航班干擾狀況，以降低航班最大延誤時(shí)間和參與飛機(jī)交換的數(shù)量為雙重目標(biāo)，對(duì)飛機(jī)路徑恢復(fù)的多目標(biāo)規(guī)劃問(wèn)題展開(kāi)研究。本文在前期研究成果的基礎(chǔ)上，結(jié)合航空公司日常運(yùn)營(yíng)的實(shí)際情況，研究在不正常航班出現(xiàn)后，以最小化航班最大延誤時(shí)間和最小化參與交換的飛機(jī)數(shù)量為雙層目標(biāo)的飛機(jī)路徑恢復(fù)的全局優(yōu)化問(wèn)題。首先根據(jù)常用的航班調(diào)整原則，分析問(wèn)題的一些特點(diǎn)，揭示出以最小化航班最大延誤時(shí)間為第一目標(biāo)的問(wèn)題全局最優(yōu)解僅通過(guò)交換一次航班序列即可得到。并設(shè)計(jì)基于快速排序的組合構(gòu)造算法求得最優(yōu)解。然后分析在滿足上層目標(biāo)的所有最優(yōu)解中，求解以最小化參與交換的飛機(jī)數(shù)量為目標(biāo)的最優(yōu)化問(wèn)題可以等價(jià)為最小費(fèi)用最大流問(wèn)題，最后設(shè)計(jì)基于網(wǎng)絡(luò)流的組合算法求得雙層目標(biāo)的飛機(jī)路徑恢復(fù)的全局最優(yōu)解。

本文的結(jié)構(gòu)安排如下所示：第一部分對(duì)問(wèn)題進(jìn)行描述并結(jié)合相關(guān)假設(shè)建立多目標(biāo)規(guī)劃模型；第二部分基于假設(shè)對(duì)問(wèn)題體現(xiàn)出的性質(zhì)進(jìn)行分析；在第三部分中設(shè)計(jì)了組合算法來(lái)解決該問(wèn)題，并證明其能得到最優(yōu)解；第四部分設(shè)計(jì)算例驗(yàn)證算法的有效性；最后，第五部分對(duì)本文進(jìn)行了總結(jié)。

1 問(wèn)題描述

本章研究多架飛機(jī)受到短時(shí)間干擾后飛機(jī)路徑恢復(fù)的多目標(biāo)優(yōu)化問(wèn)題(HOARP)。描述如下：已知同一個(gè)機(jī)場(chǎng)的若干架飛機(jī)受到干擾，其原計(jì)劃執(zhí)行的航班不能按照原計(jì)劃進(jìn)行出港，求如何使用飛機(jī)交換(用航班任務(wù)少的飛機(jī)與受到干擾的飛機(jī)交換)和航班順延(根據(jù)受到干擾的飛機(jī)或者新交換的飛機(jī)可用時(shí)刻重新調(diào)整航班的出港時(shí)間)等手段重新調(diào)整航班使得航班能夠在短時(shí)間內(nèi)恢復(fù)正常，并分層實(shí)現(xiàn)航班干擾管理的雙重目標(biāo)：第一目標(biāo)為最小化航班的最大延誤時(shí)間，第二目標(biāo)為最小化參與飛機(jī)交換的飛機(jī)數(shù)量。在滿足上述目標(biāo)的同時(shí)也需要滿足以下約束限制：i)每個(gè)航班只能被一架飛機(jī)執(zhí)行；ii)每架飛機(jī)只能執(zhí)行一個(gè)航班序列，即得到一條飛機(jī)路徑；iii)在當(dāng)天宵禁結(jié)束之前，每個(gè)機(jī)場(chǎng)應(yīng)該有足夠的數(shù)量飛機(jī)停駐，且和原計(jì)劃的數(shù)量一致，以不影響第二天的正常航班運(yùn)行。

依據(jù)上述目標(biāo)設(shè)置、約束限制以及相關(guān)的假設(shè)，基于連接網(wǎng)絡(luò)建立如下多目標(biāo)規(guī)劃模型。

索引：

I飛機(jī)索引

F航班索引

r航班序列索引

s機(jī)場(chǎng)索引

集合：

P受干擾的和參與交換的飛機(jī)集合

F航班集合

R航班序列集合

S機(jī)場(chǎng)集合

R(f) 包含航班f的航班序列集合；f∈F

R(s) 落地機(jī)場(chǎng)為s的航班序列集合；s∈S

參數(shù)：

yri=0 表示航班序列r原計(jì)劃被飛機(jī)i執(zhí)行；r∈R,i∈P

trfi航班序列r被飛機(jī)i執(zhí)行時(shí)，航班序列中航班f的延誤時(shí)間；r∈R(f),f∈F,i∈P

ms按照計(jì)劃在機(jī)場(chǎng)s應(yīng)該停駐的飛機(jī)數(shù)量s∈S

Q1,Q2目標(biāo)的優(yōu)先因子

決策變量:

xri=1表示航班序列r由飛機(jī)i執(zhí)行；否則=0；r∈R,i∈P

(1)

(7)

模型目標(biāo)表示如下，其中公式(1)表示最小化第一目標(biāo)為所有航班的延誤時(shí)間最大值，公式(2)表示最小化第二目標(biāo)為參加飛機(jī)交換的飛機(jī)數(shù)量，表達(dá)式(3)表示目標(biāo)Z1的優(yōu)先級(jí)遠(yuǎn)遠(yuǎn)大于目標(biāo)Z2。

約束(4)表示每個(gè)航班都需要由一架飛機(jī)執(zhí)行，約束(5)表示參與交換的每架飛機(jī)最多只能一條航班序列，約束(6)表示在每個(gè)機(jī)場(chǎng)應(yīng)該有足夠數(shù)量的飛機(jī)停駐，以至于不影響第二天的航班任務(wù)。

為了使得問(wèn)題具有一些較好的性質(zhì)、以及后續(xù)分析和算法設(shè)計(jì)的方便，現(xiàn)給出若干概念的定義如下。設(shè)航班集合為F={Fi|i∈P}，F(xiàn)i={fi1,fi2,…}表示原計(jì)劃由飛機(jī)i∈P執(zhí)行的航班序列。在航班序列{fiu,fi(u+1),…,fiv}中({fiu,fi(u+1),…,fiv}?{fi1,fi2,…})，如果航班fiu的出港機(jī)場(chǎng)與航班fiv的進(jìn)港機(jī)場(chǎng)相同，則航班序列{fiu,fi(u+1),…,fiv}被稱(chēng)為航班環(huán)。

假設(shè)如下：i)受干擾的飛機(jī)以及參與交換的飛機(jī)都屬于同一個(gè)機(jī)型，且干擾發(fā)生在同一個(gè)機(jī)場(chǎng)；ii)在航班計(jì)劃中，所有的航班都可以正常出港，即原計(jì)劃執(zhí)行該航班的飛機(jī)在出港機(jī)場(chǎng)的可用時(shí)刻不晚于該航班的計(jì)劃出港時(shí)刻；iii)本文采用的航班調(diào)整手段為飛機(jī)交換和航班延誤，不包括航班取消、調(diào)機(jī)等措施；iv)無(wú)論是否進(jìn)行飛機(jī)路徑恢復(fù)，所有的飛機(jī)能在機(jī)場(chǎng)宵禁之前完成所有的航班；v)干擾時(shí)間窗的長(zhǎng)度小于所有的航班環(huán)長(zhǎng)度，即所有受干擾飛機(jī)執(zhí)行航班的計(jì)劃出港時(shí)刻的最小值到所有受干擾飛機(jī)的實(shí)際可用時(shí)刻的最大值之間的時(shí)間段長(zhǎng)度小于所有航班環(huán)時(shí)間跨度的最小值。

在航班運(yùn)行的過(guò)程中，可以分為若干個(gè)時(shí)間區(qū)間，某一個(gè)時(shí)間區(qū)間內(nèi)，出港航班數(shù)量遠(yuǎn)多于進(jìn)港航班，稱(chēng)為出港航班波；在另一個(gè)時(shí)間區(qū)間內(nèi)，進(jìn)港航班數(shù)量遠(yuǎn)多于出港航班，稱(chēng)為進(jìn)港航班波。當(dāng)干擾發(fā)生時(shí)，航空公司一般運(yùn)用出港航班波結(jié)構(gòu)，依次在延誤航班發(fā)生的各個(gè)機(jī)場(chǎng)進(jìn)行調(diào)度。首先，需要在發(fā)生干擾的機(jī)場(chǎng)利用出港航班波，尋找可用飛機(jī)集合(記為P′，P′?P)，與受干擾的飛機(jī)P″?P進(jìn)行飛機(jī)交換，這被稱(chēng)為交換階段1。在交換階段1之后，如果仍存在延誤航班fik,?i∈P,k=2,3,…,(注意航班序列{fik|i∈P,k=1,2,…}在飛機(jī)交換階段1后，并不一定被飛機(jī)i∈P執(zhí)行)。然后在航班fi2的出港機(jī)場(chǎng)，再次利用出港航班波尋找可用的飛機(jī)與執(zhí)行航班序列{fik|k=2,3, …}的飛機(jī)繼續(xù)進(jìn)行交換。以此類(lèi)推，直到在后續(xù)的航班序列不存在延誤航班。

基于航班環(huán)和干擾區(qū)間的定義，則假設(shè)v)可以用公式表示如下:

ma-ms

(8)

其中c表示航班環(huán)，tc表示航班環(huán)的時(shí)間區(qū)間長(zhǎng)度，即從航班環(huán)中首個(gè)航班的計(jì)劃出港時(shí)刻到航班環(huán)中最后一個(gè)航班的計(jì)劃進(jìn)港時(shí)刻之間的時(shí)間跨度。

圖1 交換/干擾區(qū)間示意圖

2 性質(zhì)分析

在交換階段1中，令可以參與飛機(jī)交換的交換區(qū)間集合記為IN，則按照飛機(jī)交換區(qū)間的定義、以及和干擾區(qū)間的關(guān)系，我們把交換階段1中找到的飛機(jī)交換區(qū)間集合IN分為6類(lèi)。

IN=IN1∪IN2∪IN3∪IN4∪IN5∪IN6

(9)

IN1={ini|ai≤ms,ma≤si1,i∈P′}

(10)

IN2={ini|ai≤ms

(11)

IN3={ini|ms

(12)

IN4={ini|ms

(13)

IN5={ini|si1≤ms,i∈P′}

(14)

IN6={ini|ai≥ma,i∈P′}

(15)

設(shè)SOLm表示在交換階段m中得到的可行解集合，valuesol表示可行解sol∈SOLm的第一個(gè)目標(biāo)值，則可以得到以下引理。

在以下的敘述中，設(shè)(inl,fi1)表示航班序列{fij|j=1,2,…}被飛機(jī)l執(zhí)行，其中l(wèi),i∈P′；OPT表示問(wèn)題的最優(yōu)解集合；INsol表示在實(shí)際中參與飛機(jī)交換的交換區(qū)間集合。

由引理3和引理4得知，IN5和IN6集合中的飛機(jī)交換區(qū)間不會(huì)參與最優(yōu)解中的飛機(jī)交換?？梢酝ㄟ^(guò)在集合IN1、IN2、IN3和IN4中選取交換區(qū)間進(jìn)行飛機(jī)交換。在下一部分將會(huì)介紹多項(xiàng)式算法求解飛機(jī)路徑恢復(fù)的多目標(biāo)規(guī)劃。

3 算法設(shè)計(jì)

根據(jù)Z1和Z2的分層結(jié)構(gòu)，本文設(shè)計(jì)一種多項(xiàng)式時(shí)間算法(QSMCF)來(lái)求得多目標(biāo)規(guī)劃的最優(yōu)解，然后給出算法的時(shí)間復(fù)雜度分析和算法的最優(yōu)性證明。

QSMCF算法是在快速排序算法和最小費(fèi)用流算法結(jié)合的基礎(chǔ)上設(shè)計(jì)的多項(xiàng)式時(shí)間算法。在算法中，首先運(yùn)用快速排序算法求得航班的最大延誤時(shí)間valuemax，其次根據(jù)飛機(jī)和航班的匹配狀態(tài)，建立網(wǎng)絡(luò)圖CN=(o,t,V,A,ω,y,b)。在網(wǎng)絡(luò)圖中，o和t代表網(wǎng)絡(luò)流的起點(diǎn)和終點(diǎn)；V=I∪J，其中I和J分別代表飛機(jī)集合和對(duì)應(yīng)的航班序列的集合；A=A1∪A2∪A3，其中A1={(o,i)|i∈I}代表飛機(jī)I開(kāi)始被安排，A3={(j,t)|j∈J}代表所有航班序列已被飛機(jī)覆蓋完畢，A2={(i,j),i∈I,j∈J}，在A2中的每一條弧(i,j)∈A2代表飛機(jī)i∈I可能會(huì)被安排執(zhí)行航班序列j∈J。對(duì)于每一條弧(i,j)∈A2，ωij代表飛機(jī)i執(zhí)行航班序列j時(shí)首個(gè)航班的延誤時(shí)間，即ωij=max{ai-sj1,0}；yij是航班序列j是否是由原飛機(jī)執(zhí)行的標(biāo)示，=0表示航班序列j由原飛機(jī)i執(zhí)行，=1表示執(zhí)行航班序列j的飛機(jī)i不是航班序列j的原飛機(jī)；bij表示弧(i,j)∈A2的容量，且bij=1，?(i,j)∈A2。對(duì)于弧(o,i)∈A1和(j,t)∈A3有yoi=0，boi=1，?i∈I，yjt=0,bjt=1,?j∈J。

算法QSMCF:

輸入：IN1,IN2,IN3,IN4以及對(duì)應(yīng)的航班序列

第1步運(yùn)用快速排序算法分別對(duì){ai|i∈P}和{sj1|j∈P}從小到大進(jìn)行排序；

第2步設(shè)ai(1)≤ai(2)≤…≤ai(|P|)，且sj(1)1≤sj(2)1≤…≤sj(|P|)1,sol={(i(k),j(k))|k=1,2,…,|P|}，valuemax=max(i,j)∈solωij。

第4步設(shè)網(wǎng)絡(luò)圖CN′中從o到t的初始流為fl，令初始流的大小valfl=0；

第5步如果valfl=|P|，則轉(zhuǎn)第8步，否則轉(zhuǎn)第6步；

第6步建立增量網(wǎng)絡(luò)圖CN′(fl)，并找到一條從o到t的最小費(fèi)用增廣路M，以及對(duì)應(yīng)的最小費(fèi)用yij，轉(zhuǎn)第7步；

第7步設(shè)C(M)為增廣路M中的最小弧容量，設(shè)θ=min{C(M),|P|-valfl}，在CN′中沿M對(duì)fl增流θ，得新流fl，轉(zhuǎn)第5步；

輸出：solopt,value1QSMCF和value2QSMCF。

算法QSMCF的復(fù)雜度為O(|P|4)。首先，根據(jù)C.A.R. Hoare[18]，第1步的復(fù)雜度為O(|P|log(|P|))；第4～7步為最小費(fèi)用路算法，其每次增流至少一個(gè)單位，因此需要經(jīng)過(guò)至多|P|次找最小費(fèi)用增廣路并增流；而第6步中每次求最小費(fèi)用增廣路可以使用最短路算法，其計(jì)算量不超過(guò)O((2|P|+2)3)；第7步中沿增廣路增流過(guò)程的計(jì)算量不超過(guò)O(2|P|+2)。因此，計(jì)算得到QSMCF算法的復(fù)雜度為O(|P|log(|P|)+|P|×((2|P|+2)3+(2|P|+2)))=O(|P|4)。

設(shè)valuemax=max(i,j)∈so|ωij=ωi*j*=max{ai*-sj*1,0}，我們首先根據(jù)ai*和sj*1將集合sol里的元素分為四個(gè)子集，并以此將對(duì)應(yīng)的飛機(jī)集合I和航班序列集合J分別分為四個(gè)子集，然后根據(jù)各子集之間元素的數(shù)量比對(duì)關(guān)系用反證法分析證明出ai*sj*1是Z1的最優(yōu)值。

定義1集合sol可以分為M1、M2、M3和M4四個(gè)子集。

如果ai*≥sj*1，子集如下所示：

M1={(i,j)∈sol|ai

M2={(i,j)∈sol|sj1

M3={(i,j)∈sol|sj*1≤sj1

M4={(i,j)∈sol|ai≥ai*,sj1≥ai*}

如果ai*

M1={(i,j)∈sol|ai

M2={(i,j)∈sol|ai

M3={(i,j)∈sol|ai*≤ai

M4={(i,j)∈sol|ai≥sj*1,sj1≥sj*1}

定義2飛機(jī)集合I分為A1、A2和A3三個(gè)子集；航班序列集合J分為B1、B2和B3三個(gè)子集。

如果ai*≥sj*1，則A1={i∈I|ai

如果ai*

引理5如果ai*≥sj*1，則|A1|=|M1|,|A2|=|M2|,|A3|=|M3∪M4|=|M3|+|M4|,|B1|=|M1∪M2|=|M1|+|M2|,|B2|=|M3|,|B3|=|M4|;

如果ai*

4 算例分析

為了更精確的分析多目標(biāo)規(guī)劃用于航班干擾管理的效果，以及驗(yàn)證算法QSMCF的有效性，我們給出一個(gè)恢復(fù)規(guī)模為6架飛機(jī)的算例，具體航班計(jì)劃信息如表1所示。在該算例中，飛機(jī)在各機(jī)場(chǎng)的最小過(guò)站時(shí)間為40分鐘，各機(jī)場(chǎng)的宵禁時(shí)間為當(dāng)天的24時(shí)。從表1中可以看出，飛機(jī)1、2受到干擾，可用時(shí)刻分別為12∶00和12∶10。如果沒(méi)有其他飛機(jī)參與與飛機(jī)1和飛機(jī)2的交換，則航班序列S1={f11,f12,f13,f14}中各航班的延誤時(shí)間分別為180分鐘、119分鐘、58分鐘和0分鐘，航班序列S2={f21,f22,f23,f24}中各航班的延誤時(shí)間分別為132分鐘、58分鐘、56分鐘和0分鐘，即所有的航班都能在宵禁之前完成生產(chǎn)任務(wù)。我們需要做的是在機(jī)場(chǎng)PEK尋找其他可用的飛機(jī)用來(lái)與飛機(jī)1和2交換，以降低最大的航班延誤時(shí)間，并使得參與交換的飛機(jī)數(shù)量最少。

表 1 航班計(jì)劃表和飛機(jī)狀態(tài)信息

在第一階段調(diào)整時(shí)，首先由表1中6架飛機(jī)的可用時(shí)刻和首個(gè)航班的計(jì)劃出港時(shí)刻之間的關(guān)系，找到飛機(jī)交換區(qū)間，IN1=?，IN2={in6}，IN3={in4,in5}，以及IN4={in3}。在進(jìn)行飛機(jī)交換時(shí)，每個(gè)航班序列中的所有航班都和首個(gè)航班是被同一架飛機(jī)執(zhí)行，而且這些航班序列被任何一架飛機(jī)執(zhí)行，都能在宵禁之前完成生產(chǎn)任務(wù)。

圖2和圖3分別給出了sol中飛機(jī)和航班序列首個(gè)航班的匹配信息以及算法得到的飛機(jī)路徑優(yōu)化解solopt中飛機(jī)和航班序列首個(gè)航班的匹配信息。圖4則顯示了solopt中所有航班信息。在圖2和圖3中，弧左邊是飛機(jī)交換區(qū)間信息以及對(duì)應(yīng)的飛機(jī)的可用時(shí)刻，弧右邊是飛機(jī)交換區(qū)間后面的航班序列中首個(gè)航班信息、首個(gè)航班的計(jì)劃出港時(shí)刻、以及如果由弧所指的飛機(jī)交換區(qū)間對(duì)應(yīng)的飛機(jī)執(zhí)行得到首班延誤時(shí)間。例如，在圖2中，飛機(jī)交換區(qū)間中飛機(jī)和航班序列的匹配為：(in1,f41)、(in2,f31)、(in3,f51)、(in4,f61)、(in5,f21)和(in6,f11)，共有4架飛機(jī)(飛機(jī)3、4、5、6)參與與受干擾飛機(jī)1和2的交換，至少有三個(gè)航班(f41、f51、f61)發(fā)生延誤，延誤時(shí)間分別為30分鐘、30分鐘和20分鐘，且最大延誤時(shí)間為30分鐘。而圖3中，飛機(jī)和航班序列的匹配為：(in1,f41)、(in2,f31)、(in3,f51)、(in4,f21)和(in5,f11)，共有3架飛機(jī)(飛機(jī)3、4、5)參與與受干擾飛機(jī)1和2的交換，從圖4可知，solopt中共有四個(gè)航班(f11、f21、f41、f51)發(fā)生延誤，延誤時(shí)間分別為30分鐘、22分鐘、30分鐘和30分鐘。從圖2和圖3的對(duì)比可以看出，本文的算法在保證航班的最大延誤時(shí)間不變的情況下，能夠最大程度的降低參與交換的飛機(jī)數(shù)量，這更符合航班干擾管理的原則。

圖2 Z1的最優(yōu)解中首個(gè)航班與飛機(jī)的匹配信息

圖3 本文算法得到的最優(yōu)解中首個(gè)航班與飛機(jī)的匹配信息

圖4 本文算法得到的最優(yōu)解

5 結(jié)論

在本文中，我們考慮了同一機(jī)場(chǎng)中多架飛機(jī)受到干擾后的雙目標(biāo)航班調(diào)整問(wèn)題(HOARP)，該問(wèn)題目標(biāo)為最小化航班延誤時(shí)間最大值和最小化參與交換的飛機(jī)數(shù)量。并結(jié)合分層序列法的思想求解該問(wèn)題。基于航空公司在實(shí)際的航班調(diào)整中一般利用航班波的特點(diǎn)，我們分析了多目標(biāo)規(guī)劃問(wèn)題的一些性質(zhì)，并且總結(jié)出第一個(gè)目標(biāo)的最優(yōu)值在第一階段調(diào)整后就能得到。然后設(shè)計(jì)了一個(gè)基于快速排序算法和最小費(fèi)用路算法的多項(xiàng)式算法(QSMCF)，得到問(wèn)題的最優(yōu)解。結(jié)合HOARP問(wèn)題的結(jié)構(gòu)特點(diǎn)，本文分析出QSMCF的復(fù)雜度O(n4)，其中n為參與干擾恢復(fù)的飛機(jī)總數(shù)量。最后給出一個(gè)小算例驗(yàn)證了算法的有效性。

在后續(xù)的研究工作中，我們將會(huì)針對(duì)以下幾個(gè)方向進(jìn)行研究：首先，我們會(huì)試圖對(duì)不同機(jī)場(chǎng)的飛機(jī)受到干擾后的航班調(diào)整問(wèn)題研究多項(xiàng)式時(shí)間算法，當(dāng)受干擾的飛機(jī)處于不同的機(jī)場(chǎng)時(shí)，由于后續(xù)航班序列可能會(huì)出現(xiàn)機(jī)場(chǎng)的交叉，交換階段會(huì)很難界定，同時(shí)問(wèn)題的性質(zhì)也會(huì)發(fā)生改變；其次，通過(guò)將旅客恢復(fù)網(wǎng)絡(luò)潛入到飛機(jī)網(wǎng)絡(luò)中的方法求解飛機(jī)和旅客同時(shí)恢復(fù)的問(wèn)題將會(huì)比較有意義；最后，本文主要是尋找飛機(jī)受到干擾后的路徑恢復(fù)最優(yōu)解，屬于被動(dòng)處理干擾，在實(shí)際情況中修改航班計(jì)劃使其更具有魯棒性也是很熱點(diǎn)的一個(gè)研究方向。