基于Danzig-Wolfe 算法的不正常航班旅客流恢復(fù)問題

王 瑩，朱金福

(南京航空航天大學(xué) 民航學(xué)院，江蘇 南京210016)

旅客流恢復(fù)是不正常航班恢復(fù)問題中必不可少的部分。如果在獲取旅客訂座信息、航班延誤信息以及不正常航班恢復(fù)方案的基礎(chǔ)上，站在全局的角度為行程受擾動(dòng)的旅客重新安排航班，減少旅客退票和延誤時(shí)間，就能實(shí)現(xiàn)航空收入和旅客滿意度的大幅提高，實(shí)現(xiàn)航空公司和旅客的雙贏。

JAFARI 和ZEGORDI 研究了不正常航班中飛機(jī)路線和旅客流同步恢復(fù)問題，采用Lingo 軟件求解大規(guī)模線性規(guī)劃問題［1］，其重新定義了恢復(fù)期的概念，并采用路線恢復(fù)而非航班恢復(fù)的概念，減小了問題的規(guī)模，但由于問題規(guī)模仍太大，求解效率不高。BISAILLON 等通過構(gòu)建、修復(fù)、改進(jìn)3個(gè)階段解決飛機(jī)路線恢復(fù)、機(jī)型指派和旅客流恢復(fù)的問題［2］，其在構(gòu)建完可行的飛機(jī)路線之后，采用最短路算法進(jìn)行旅客路線的初始構(gòu)建，為實(shí)現(xiàn)運(yùn)送旅客人數(shù)的最大化，進(jìn)行了放松延誤時(shí)間的枚舉嘗試。其雖然考慮了旅客行程的銜接性，但枚舉算法效率較低，且無法保證最優(yōu)性。陸宏蘭、高強(qiáng)、嚴(yán)俊等構(gòu)建了延誤成本最小的旅客流恢復(fù)模型，將問題轉(zhuǎn)化為運(yùn)輸匹配問題，使用單純形法進(jìn)行了問題的精確求解［3-5］。他們雖然優(yōu)化了存儲(chǔ)方法和搜索策略，但由于要生成所有OD(origin-destination)對的可行路徑，并要對所有OD 對進(jìn)行路徑重排，未能充分利用原方案，因此影響了求解效率。謝云雙分析了航班延誤補(bǔ)償?shù)慕?jīng)濟(jì)效益問題，討論了造成航班延誤的原因以及影響賠償金額的因素［6］。李雄等研究了航班延誤引發(fā)的航空公司及旅客經(jīng)濟(jì)損失問題，詳細(xì)分析了不正常航班成本構(gòu)成、旅客賠償和隱性損失［7］。文獻(xiàn)［6］和文獻(xiàn)［7］只進(jìn)行了定性分析，未進(jìn)行旅客流恢復(fù)的優(yōu)化研究。

筆者在航班恢復(fù)方案的基礎(chǔ)之上，根據(jù)航班訂座信息，對行程受到擾動(dòng)的旅客進(jìn)行行程調(diào)整，將旅客流恢復(fù)問題處理成經(jīng)典的多商品流模型，采用Danzig-Wolfe 算法進(jìn)行求解，并通過一個(gè)實(shí)際規(guī)模的算例驗(yàn)證了該算法的可行性和效率。

1 旅客流恢復(fù)模型

1.1 模型假設(shè)

為簡化模型和算法，對航空公司不正常航班恢復(fù)的實(shí)際操作規(guī)范和原則進(jìn)行適當(dāng)抽象，做以下假設(shè):

(1)航班不正常發(fā)生后，已獲得了航班恢復(fù)方案，調(diào)整旅客行程的過程中不對航班計(jì)劃進(jìn)行調(diào)整。

(2)只針對受擾動(dòng)旅客進(jìn)行行程調(diào)整。受擾動(dòng)旅客通過簽轉(zhuǎn)方式獲得新的行程;無法簽轉(zhuǎn)的旅客進(jìn)行取消行程操作。

(3)航班容量限制為航班剩余座位數(shù);OD 對的旅客需求已知，且不再變化。

1.2 構(gòu)造時(shí)空網(wǎng)絡(luò)

筆者采用時(shí)空網(wǎng)絡(luò)建立旅客流恢復(fù)問題的多商品流模型。該多商品流模型中包含3 個(gè)主要信息，即商品、弧和成本，分別對應(yīng)時(shí)空網(wǎng)絡(luò)中的OD 對、航班和成本。

1.2.1 受擾動(dòng)OD 對的構(gòu)造

根據(jù)航班恢復(fù)方案和訂座信息，采集銜接失敗的旅客信息。由于航班信息以及旅客信息規(guī)模較大，如果根據(jù)旅客信息一一搜索對應(yīng)的航班信息，效率將會(huì)降低。筆者首先根據(jù)航班恢復(fù)方案，采集受擾動(dòng)的航班信息，結(jié)合航班訂座情況，查看該航班上的旅客是否出現(xiàn)銜接失敗情況，構(gòu)造出受擾動(dòng)的旅客信息，再將相同始發(fā)地和目的地以及相同計(jì)劃離港時(shí)間的旅客分到一個(gè)OD 對中，對同一個(gè)OD 對進(jìn)行訂座旅客人數(shù)統(tǒng)計(jì)和預(yù)測，獲得OD 對的旅客需求。

1.2.2 航班弧的存儲(chǔ)

筆者根據(jù)航班恢復(fù)方案構(gòu)造航班弧信息，建立航班弧的連接表，完成多商品流模型中弧的構(gòu)建。航班弧的連接矩陣是一個(gè)大規(guī)模的稀疏矩陣，筆者采用十字鏈表存儲(chǔ)航班弧連接，配合棧的使用，以便求解OD 對的可行路徑。為了減小鏈表規(guī)模，十字鏈表中不包含取消航班弧。在初始化鏈表時(shí)，對航班恢復(fù)方案的航班出發(fā)時(shí)刻進(jìn)行排序，以便對其子問題快速求解。

1.2.3 成本的表達(dá)

不正常航班旅客流恢復(fù)問題中的成本主要包括旅客行程取消成本、旅客延誤成本，以及旅客中轉(zhuǎn)成本。每一個(gè)OD 對選擇一條航班路徑(可能包括多個(gè)航班)均有對應(yīng)的成本，而多商品流模型要求每一個(gè)OD 對選擇每一條弧(即一個(gè)航班)均有相應(yīng)的成本，這就需要對成本進(jìn)行分解。

1.3 符號定義

1.4 數(shù)學(xué)模型

1.4.1 多商品流模型

根據(jù)構(gòu)造的時(shí)空網(wǎng)絡(luò)和符號定義，可給出不正常航班旅客流恢復(fù)問題的多商品流模型如下:

式(1)為目標(biāo)函數(shù)，要求總成本最小，包括運(yùn)輸成本和取消成本;式(2)～式(4)為約束條件，其中:式(2)為流平衡約束，要求每個(gè)時(shí)空節(jié)點(diǎn)滿足旅客流量平衡，始發(fā)和目的節(jié)點(diǎn)保證實(shí)際運(yùn)輸?shù)穆每土髁颗c取消旅客流量之和等于OD 對旅客需求，由于實(shí)際運(yùn)輸?shù)穆每土髁看笥诘扔诹悖赜衴k≤dk;式(3)為航班弧的容量約束，要求改簽到該航班的旅客總量不超過該航班的剩余座位數(shù);式(4)為決策變量的非負(fù)約束，要求每個(gè)航班上乘坐的旅客人數(shù)和取消行程的旅客人數(shù)大于等于零且為整數(shù)。

1.4.2 成本的分解

如果首先計(jì)算整個(gè)路徑對應(yīng)OD 對的成本，再對各航段進(jìn)行成本分?jǐn)偅瑒t需要生成各個(gè)OD對的所有可行路徑，效率極低［8］。如圖1 所示，筆者定義的航班弧有3 種，即取消弧、延誤弧和中轉(zhuǎn)弧，分別對應(yīng)旅客流恢復(fù)問題中3 個(gè)主要成本。根據(jù)生成的OD 對信息，每一個(gè)OD 對均設(shè)有一條虛擬的取消弧，從始發(fā)地到目的地，取消弧的單位流成本為航班平均票價(jià)，假設(shè)取消一位旅客的訂票不發(fā)生其他費(fèi)用，只是減少了相應(yīng)的機(jī)票收入。根據(jù)航班恢復(fù)方案，現(xiàn)行航班均為一條延誤弧或中轉(zhuǎn)弧，旅客行程最后一個(gè)航段決定旅客的總延誤時(shí)間，屬于延誤弧，旅客延誤成本與旅客總延誤時(shí)間有關(guān)［9］，因此延誤弧的成本為延誤成本。其他始發(fā)和中轉(zhuǎn)航段為中轉(zhuǎn)弧，中轉(zhuǎn)弧的成本為簽轉(zhuǎn)方案導(dǎo)致旅客出行不便的固定費(fèi)用。為保證在成本相同的情況下，減少旅客簽轉(zhuǎn)，設(shè)定旅客原行程中的中轉(zhuǎn)弧成本為零。

圖1 成本分解示意圖

2 Danzig－Wolfe 算法設(shè)計(jì)

筆者采用Danzig-Wolfe 分解算法求解多商品流問題，子問題是無容量約束的廣義最短路問題。子問題的解構(gòu)成主問題的一列。模型中式(3)為“難處理”約束條件，用來構(gòu)造主問題，式(2)和式(4)為“易處理”約束，用來構(gòu)造子問題。式(2)和式(4)構(gòu)成的可行域X 是一個(gè)K 維空間封閉的凸多面體，其中任意一點(diǎn)可以表達(dá)成如下形式:

式中:L 為X 頂點(diǎn)指標(biāo)集;xl為X 的一個(gè)頂點(diǎn)，是子問題的一個(gè)基本可行解，即k 個(gè)無容量約束最短路問題最優(yōu)解的組合;λl為極點(diǎn)xl的凸組合系數(shù)且0 ≤λl≤1 。

2.1 主問題

根據(jù)模型的分解，筆者采用路徑變量表示主問題:

主問題是一個(gè)規(guī)模較小的線性規(guī)劃問題，采用修正單純形法配合熱啟動(dòng)的方法進(jìn)行求解。

2.2 子問題

2.3 子問題搜索算法

子問題是k 個(gè)OD 對的廣義最短路問題。筆者采用棧的存儲(chǔ)結(jié)構(gòu)和深度優(yōu)先的搜索策略，配合十字鏈表的使用，用回溯的方法搜索OD 對的最短路。根據(jù)十字鏈表，可以快速地找到OD 對的延誤弧，將該弧推入棧中，依次尋找前繼中轉(zhuǎn)弧入棧，直到找到可以作為該OD 對始發(fā)航班的弧。在棧的結(jié)構(gòu)中設(shè)置一個(gè)存儲(chǔ)單元，每一次入棧都進(jìn)行一次標(biāo)號，以記錄當(dāng)前累計(jì)成本，若弧A 出棧后，下一個(gè)引入的弧B 標(biāo)號大于A，則舍棄，尋找同一級的下一個(gè)弧C。若無法找到可行路徑或生成的路徑成本大于取消弧成本，則將棧置空，取消弧入棧。同時(shí)，根據(jù)旅客最大可接受的中轉(zhuǎn)次數(shù)(設(shè)為2 次)，可以設(shè)置棧的容量(設(shè)為3)，這樣問題的規(guī)模就被大大縮小了。

2.4 Danzig－Wolfe 算法步驟

(1)解限制主問題，得到對偶變量π=(πij，π0);

(2)將對偶變量π 代入子問題，求解子問題，根據(jù)子問題的最優(yōu)解得到第l 個(gè)極點(diǎn)xl;

(3)計(jì)算最小檢驗(yàn)數(shù)δ = min w - π0。若δ ＜0，則將極點(diǎn)的組合系數(shù)λl作為入基變量，返回步驟(1);若δ ≥0 ，則停止迭代，求得主問題的最優(yōu)解，即原問題的松弛解。

2.5 分枝定界算法求整數(shù)解

3 算例分析

筆者根據(jù)國內(nèi)某航空公司一天的實(shí)際航班計(jì)劃、訂座情況、簽轉(zhuǎn)/賠償方案設(shè)計(jì)出算例數(shù)據(jù)，如表1 所示。根據(jù)航空公司補(bǔ)償標(biāo)準(zhǔn)，設(shè)定取消一名旅客行程的成本為航班平均票價(jià)，旅客延誤每小時(shí)的成本為100 元，升艙無成本，降艙成本為艙位差價(jià)。

在硬件配置為Inter(R)Core(TM)2 Duo CPU，E7500 2.93 GHz，2 GB 內(nèi)存的臺(tái)式計(jì)算機(jī)上進(jìn)行運(yùn)算求解。共生成航班弧602 條，OD 對166 對，子問題迭代1 532 次得到最優(yōu)解，耗時(shí)1分53 秒，減少航班取消旅客人數(shù)83.52%，挽回航空公司損失1 718 790 元，受擾旅客平均延誤時(shí)間95 分鐘，增加中轉(zhuǎn)和延誤成本561 537 元，運(yùn)算結(jié)果如表2 所示。

表1 不正常航班實(shí)例數(shù)據(jù)

表2 旅客流恢復(fù)方案性能指標(biāo)

4 結(jié)論

筆者建立了不正常航班旅客流恢復(fù)的多商品流模型，采用Danzig-Wolfe 分解算法對旅客流恢復(fù)問題進(jìn)行了精確求解，該算法配合多種存儲(chǔ)結(jié)構(gòu)和搜索策略能夠在符合實(shí)時(shí)決策要求的前提下，快速有效地提供受擾旅客的行程恢復(fù)方案。實(shí)例分析驗(yàn)證了模型的正確性和算法的有效性，表明采用筆者的方法不但可以減少旅客延誤時(shí)間，還可以增加航空公司的收入，減少航空公司損失，解決航空公司不正常航班恢復(fù)問題。

［1］ JAFARI N，ZEGORDI S H.Simultaneous recovery model for aircraft and passengers［J］.Journal of the Franklin Institute，2011，48(7):1638 -1655.

［2］ BISAILLON S，CORDEAU J F，LAPORTE G，et al. A large neighborhood search heuristic for the aircraft and passenger recovery problem ［J］. A Quarterly Journal of Operations Research，2011，9(2):139 -157.

［3］ 陸宏蘭.基于旅客行程的飛機(jī)航班一體化恢復(fù)研究［D］.南京:南京航空航天大學(xué)圖書館，2010.

［4］ 高強(qiáng)，嚴(yán)俊，陸宏蘭. 不正常航班旅客流恢復(fù)方法［J］.科學(xué)技術(shù)與工程，2011，27(11):6670 -6673.

［5］ 嚴(yán)俊，高強(qiáng)，吳桐水.航班計(jì)劃恢復(fù)中旅客流恢復(fù)問題的研究［J］.交通信息與安全，2012，30(1):20-23.

［6］ 謝云雙.航班延誤補(bǔ)償?shù)慕?jīng)濟(jì)效益分析［J］.中國民用航空，2004，44(8):33 -34.

［7］ 李雄，劉光才，顏明池.航班延誤引發(fā)的航空公司及旅客經(jīng)濟(jì)損失［J］.系統(tǒng)工程，2007，12(25):20-24.

［8］ BARNHART C，KNIKER T S，LOHATEPANONT M.Itinerary- based airline fleet assignment ［J］. Transportation Science，2002，36(2):199 -217.

［9］ BRATU S，BARNHART C.An analysis of passenger delays using flight operations and passenger booking data［J］.Air Traffic Control Quarterly，2005，13(1):1-28.