基于減少旅客延誤的航班中轉(zhuǎn)行程優(yōu)化

郭 梁，馬麗娜，王 倩，孫夢圓

(南京航空航天大學(xué) 民航學(xué)院，南京 210000)

隨著經(jīng)濟(jì)的快速發(fā)展，人們對出行尤其是遠(yuǎn)距離出行的需求與日俱增，具備明顯速度優(yōu)勢的航空運(yùn)輸逐漸成為人們首選的出行方式。然而目前航空運(yùn)輸單位的運(yùn)營、管理和協(xié)調(diào)能力同日益增長的旅客運(yùn)輸量之間還存在著巨大的矛盾，產(chǎn)生了大量的航班和旅客延誤現(xiàn)象，導(dǎo)致旅客滿意度降低，有損航空公司形象，降低民航行業(yè)競爭力。

航空公司和旅客的損失很大一部分是由旅客錯(cuò)過中轉(zhuǎn)造成的，旅客錯(cuò)過航班中轉(zhuǎn)產(chǎn)生的旅客延誤極大影響到旅客對航空運(yùn)輸承運(yùn)人的滿意度和忠誠度，如何通過優(yōu)化行程來減少旅客延誤是學(xué)者需要研究的重點(diǎn)。Farley等[1]提出了一種基于運(yùn)籌學(xué)的延誤時(shí)間最小化算法，通過對航班計(jì)劃進(jìn)行調(diào)整來最小化旅客延誤；Farley和Brodsky等[2]提出了一種航班優(yōu)化算法，減少因航班錯(cuò)過或取消產(chǎn)生的旅客延誤；Brunner[3]提出了一種根據(jù)地面等待計(jì)劃調(diào)整航班時(shí)刻的方法，盡可能降低航班延誤及取消時(shí)產(chǎn)生的各種成本；Barnhar和Fearing等[4]建立了旅客歷史行程的延誤模型，使用改進(jìn)的貪婪算法來計(jì)算旅客延誤；Maher和Stephen[5]在考慮客流的同時(shí)，考慮了航班時(shí)刻表、飛機(jī)和機(jī)組人員的恢復(fù)問題；Montlaur和Delgado[6]采用了多種成本函數(shù)比較了使航班延誤和旅客延誤的不同優(yōu)化策略的差異；Voltes-Dorta等[7]評估了大型機(jī)場在關(guān)閉時(shí)的脆弱性，并將受到干擾的旅客轉(zhuǎn)移到產(chǎn)生延誤最少的航班；Mccarty和Cohn[8]通過對延誤航班進(jìn)行預(yù)測提前將旅客分配到新的行程，并且進(jìn)一步調(diào)整仍然錯(cuò)過中轉(zhuǎn)的旅客行程；Montlaur和Delgado[9]從航空公司和乘客角度建立公平性指標(biāo)，在保證公平的情況下減少航班延誤和旅客延誤。

國內(nèi)對于旅客延誤的研究主要是從航班計(jì)劃調(diào)整和不正常航班恢復(fù)角度出發(fā)。王飛等[10]以航班正點(diǎn)率、旅客延誤時(shí)間、延誤成本、基尼系數(shù)等指標(biāo)的不同組合為優(yōu)化目標(biāo),建立了多目標(biāo)優(yōu)化模型；張靜等[11]以旅客整體為對象建立了旅客總體延誤時(shí)間最小的航班恢復(fù)模型；齊莉[12]針對樞紐機(jī)場最大化航班銜接水平的特點(diǎn)，構(gòu)建了航班時(shí)刻優(yōu)化模型對航班時(shí)刻表進(jìn)行優(yōu)化；楊新湦[13]結(jié)合航空公司和旅客的利益建立了航班網(wǎng)絡(luò)和航班時(shí)刻雙層優(yōu)化模型，以航空公司收益；姜思露等[14]針對航班頻率的優(yōu)化問題建立了基于旅客計(jì)劃延誤的航班頻率優(yōu)化模型，使旅客計(jì)劃延誤成本和航班運(yùn)行成本之和最??；張舜堯等[15]將軟備份運(yùn)力分配在飛行時(shí)間和過站時(shí)間中建立航班計(jì)劃優(yōu)化模型，提高了航班正常率。

通過對國內(nèi)外研究現(xiàn)狀的分析，國內(nèi)外研究仍存在以下不足：目前國內(nèi)研究主要是對航班計(jì)劃進(jìn)行調(diào)整及行程的恢復(fù)，并沒有考慮錯(cuò)過中轉(zhuǎn)的旅客以及被調(diào)整航班上的旅客。為減少中轉(zhuǎn)行程中產(chǎn)生的旅客延誤，針對旅客延誤較嚴(yán)重的中轉(zhuǎn)行程，建立行程優(yōu)化模型，在同時(shí)考慮后序航班與當(dāng)前航班旅客延誤的情況下對后序航班的離場時(shí)間進(jìn)行調(diào)整優(yōu)化，為中轉(zhuǎn)旅客提供更多預(yù)留時(shí)間來減少旅客中轉(zhuǎn)中斷的情況，最終達(dá)到降低旅客延誤的目的，并且比較了不同最短旅客銜接時(shí)間和選用不同遺傳算法時(shí)的優(yōu)化結(jié)果，證明了模型和算法的穩(wěn)定性。

1 中轉(zhuǎn)行程優(yōu)化模型

1.1 模型優(yōu)化思路

旅客錯(cuò)過中轉(zhuǎn)的原因往往是由于前序航班發(fā)生延誤，導(dǎo)致旅客的中轉(zhuǎn)時(shí)間不足。本文的優(yōu)化思路主要是對后序航班的離場時(shí)間進(jìn)行調(diào)整，在不增加后序航班旅客延誤的條件下使得中轉(zhuǎn)旅客的中轉(zhuǎn)時(shí)間能夠大于旅客最短銜接時(shí)間，進(jìn)而可以正常中轉(zhuǎn)，以達(dá)到降低旅客延誤的目標(biāo)。圖1為后序航班時(shí)間調(diào)整示意圖，圖中f1與f2為同一中轉(zhuǎn)行程中的前序、后序航班，當(dāng)前序航班f1發(fā)生延誤，后序航班f2按照計(jì)劃離場時(shí)間起飛，航班f2離場時(shí)間與航班f1到達(dá)時(shí)間的差值小于旅客最短銜接時(shí)間時(shí)，航班f1轉(zhuǎn)乘到航班f2的中轉(zhuǎn)旅客將錯(cuò)過中轉(zhuǎn)。此時(shí)對后序航班的離場時(shí)刻進(jìn)行調(diào)整，為后序航班f2以特定時(shí)間為間隔建立z個(gè)副本f2,1、f2,2、f2,3、…、f2,z，分別表示航班f2的z個(gè)可供選擇的離場時(shí)間，通過建立的優(yōu)化模型，在符合航班運(yùn)行限制的條件下選擇一個(gè)合適的航班f2的副本，使得后序航班f2的離場時(shí)刻與前序航班f1的到達(dá)時(shí)刻之間的差值大于旅客最短銜接時(shí)間，即中轉(zhuǎn)旅客可以完成中轉(zhuǎn)。

圖1 后序航班時(shí)間調(diào)整示意圖

在本文的研究中，模型的建立基于以下假設(shè)條件：

1)所需要的前序、后序航班的運(yùn)行計(jì)劃、中轉(zhuǎn)旅客數(shù)量等基本信息完備且已知。

2)所有涉及離場航班調(diào)整的航班均為發(fā)生航班取消的情況。

3)后序航班可按照特定時(shí)間間隔進(jìn)行調(diào)整。

4)航班班次以及航線方案保持不變。

1.2 目標(biāo)函數(shù)

以錯(cuò)過中轉(zhuǎn)旅客與后序航班上旅客的總延誤最小為目標(biāo)建立目標(biāo)函數(shù)，即

(1)

(2)

(3)

1.3 約束條件

為使得調(diào)整后的航班能夠合理有效地運(yùn)行，根據(jù)航班實(shí)際運(yùn)行限制提出以下約束條件：

1)航班限制約束。后序航班j只能有一個(gè)副本作為前序航班i的中轉(zhuǎn)航班，表示為

(4)

2)旅客人數(shù)約束。前序航班i上的錯(cuò)過中轉(zhuǎn)至航班j的副本z的旅客人數(shù)應(yīng)小于需要從前序航班i中轉(zhuǎn)至后序航班j的旅客人數(shù)，表示為

(5)

3)容量約束。每個(gè)時(shí)間窗內(nèi)離場航班總數(shù)受到最大離場容量的限制，表示為

(6)

4)航班連續(xù)性約束。同一架飛機(jī)在按照航班時(shí)刻表進(jìn)行飛行時(shí)，如果其中一個(gè)航班被調(diào)整，那么后續(xù)其他航班也會(huì)受到影響，所以在調(diào)整的時(shí)候應(yīng)該對航班的時(shí)間間隔進(jìn)行限制，連續(xù)性航班應(yīng)滿足航班最大最小中轉(zhuǎn)時(shí)間的約束，表示為

(7)

(8)

(9)

5)旅客延誤約束?？紤]到后序航班上的旅客，調(diào)整后后序航班上增加的旅客延誤應(yīng)小于不進(jìn)行調(diào)整時(shí)旅客錯(cuò)過中轉(zhuǎn)產(chǎn)生的延誤，表示為

(10)

(11)

(12)

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

遺傳算法(genetic algorithm，GA)是一種模擬自然界生物優(yōu)勝劣汰、適者生存的經(jīng)典進(jìn)化算法，具有搜索范圍大、收斂速度快等優(yōu)點(diǎn)，而種馬遺傳算法(Stud GA)[14]與經(jīng)典的遺傳算法相比具有更快的收斂速度，因此本文采用種馬遺傳算法對模型進(jìn)行求解。算法流程圖如圖2所示。具體算法步驟如下：

圖2 種馬遺傳算法流程

步驟1染色體編碼。對于本文提出的中轉(zhuǎn)行程優(yōu)化問題，每個(gè)后序中轉(zhuǎn)航班的副本構(gòu)成解的集合，所以選擇二進(jìn)制編碼，基因片段數(shù)由航班副本數(shù)決定，每個(gè)片段采用0～1編碼，編碼后染色體一一對應(yīng)每個(gè)航班副本。

步驟2初始化種群。種群的初始化將從后序中轉(zhuǎn)航班j的所有副本z中隨機(jī)選擇組成初始個(gè)體，所得到的種群就是一個(gè)可行解的集合，在可行解集合中初始化將有利于種群的快速進(jìn)化。

步驟3適應(yīng)度函數(shù)。根據(jù)中轉(zhuǎn)旅客的延誤時(shí)間構(gòu)建適應(yīng)度函數(shù)，本文為最小化問題，因此設(shè)置其為目標(biāo)函數(shù)的倒數(shù)，表示為

(13)

式中：f(x)為目標(biāo)函數(shù)。

步驟4算子設(shè)計(jì)。采用錦標(biāo)賽選擇策略從當(dāng)前種群中獨(dú)立的選擇1個(gè)父體，然后在剩余種群中獨(dú)立的選擇一個(gè)母體，檢查父體與母體間的漢明距離，若漢明距離超過設(shè)定值，則對進(jìn)行交叉操作產(chǎn)生子代，否則對母體進(jìn)行變異產(chǎn)生子代。

步驟5種馬策略。選擇其他母體重復(fù)進(jìn)行步驟4直到所有母體都被選擇，將父體和交叉變異得到的種群進(jìn)行合并，得到規(guī)模為N的新一代種群。

步驟6中止判斷。如果迭代次數(shù)到達(dá)設(shè)定的迭代次數(shù)，則結(jié)束算法，否則返回步驟4。

3 實(shí)例驗(yàn)證

3.1 實(shí)驗(yàn)設(shè)計(jì)

選用2013年1月7日以北京首都國際機(jī)場為中轉(zhuǎn)機(jī)場的旅客行程數(shù)據(jù)及相應(yīng)航班運(yùn)行數(shù)據(jù)進(jìn)行驗(yàn)證模型，部分?jǐn)?shù)據(jù)見表1。當(dāng)日內(nèi)北京首都機(jī)場起降航班共計(jì)1 521 架次，而參與中轉(zhuǎn)的前序航班和后序航班共有973 架次，占所有航班的64%。在中轉(zhuǎn)行程中，發(fā)生延誤的前序航班有212 架次，占前序航班總數(shù)的近33%。由此可見，有必要對航班中轉(zhuǎn)行程進(jìn)行時(shí)刻優(yōu)化。

表1 北京首都國際機(jī)場旅客客流數(shù)據(jù)(部分)

根據(jù)首都機(jī)場發(fā)布的中轉(zhuǎn)最短銜接時(shí)間(minimum connection time,MCT)，國內(nèi)轉(zhuǎn)國內(nèi)的旅客最短銜接時(shí)間應(yīng)為120 min，所以設(shè)置旅客最短銜接時(shí)間為120 min。設(shè)置每個(gè)可選擇的航班副本間隔為1 min，每個(gè)航班有15個(gè)可供調(diào)整的航班副本，采用Stud GA優(yōu)化求解，經(jīng)過多次試驗(yàn)，參數(shù)選擇為：群體規(guī)模為50，交叉概率為0.6，變異概率為0.1，最大迭代次數(shù)為500。

3.2 結(jié)果分析

按照1.2和1.3節(jié)中的目標(biāo)函數(shù)和約束條件，以及2節(jié)中設(shè)計(jì)的優(yōu)化算法進(jìn)行算例實(shí)施，以航班副本為染色體進(jìn)行編碼，采用錦標(biāo)賽選擇法，在每次迭代時(shí)選擇部分航班抽樣擇優(yōu)進(jìn)行求解，其目標(biāo)均值與每代最優(yōu)值的變化情況如圖3所示，可以看出旅客延誤在90 代內(nèi)快速降低，在迭代91 代后達(dá)到最優(yōu)，錯(cuò)過中轉(zhuǎn)旅客與后序航班旅客的總延誤由初始的74 517 min減少至52 165 min，旅客延誤得到了大幅度降低，由于離場時(shí)間為整值，優(yōu)化調(diào)整后的后序航班時(shí)刻表見表2。

圖3 中轉(zhuǎn)中產(chǎn)生的旅客延誤隨迭代次數(shù)的變化

表2 優(yōu)化后的后序航班離場時(shí)間(部分)

由于機(jī)場的中轉(zhuǎn)最短銜接時(shí)間可能會(huì)根據(jù)旅客流量、機(jī)場設(shè)施、中轉(zhuǎn)程序的變化而進(jìn)行調(diào)整，中轉(zhuǎn)旅客延誤的時(shí)間也會(huì)發(fā)生變化，所以本文比較了不同旅客最短銜接時(shí)間下模型的優(yōu)化效果，分析模型在不同條件下的適用性。

隨著智能化技術(shù)的發(fā)展和基礎(chǔ)設(shè)施的改善，機(jī)場中轉(zhuǎn)流程更加暢通和高效，旅客的最短銜接時(shí)間也將逐步縮小。對此分別設(shè)置中轉(zhuǎn)最短銜接時(shí)間為90 min和60 min，采用行程優(yōu)化模型對其進(jìn)行優(yōu)化，結(jié)果見表3。

表3 不同中轉(zhuǎn)最短銜接時(shí)間下的優(yōu)化結(jié)果比較

由表3可知，當(dāng)中轉(zhuǎn)最短銜接時(shí)間縮短后，代表機(jī)場中轉(zhuǎn)水平提高，中轉(zhuǎn)所需要的最大時(shí)間縮短，錯(cuò)過航班的旅客人數(shù)減少，同時(shí)后序航班也不用進(jìn)行調(diào)整，所以旅客延誤將會(huì)減少。同時(shí)通過對不同旅客最短銜接時(shí)間設(shè)置下的優(yōu)化結(jié)果進(jìn)行比較，可以看出，雖然優(yōu)化的程度略有不同，但差異并不明顯，整體優(yōu)化百分比為25%～30%，表明模型有較好的穩(wěn)定性，可以使中轉(zhuǎn)行程中的旅客延誤達(dá)到一定程度的優(yōu)化。

3.3 算法對比

為說明算法選擇的合理性，分別使用經(jīng)典遺傳算法(Simple GA，SGA)、增強(qiáng)精英保留遺傳算法(Strengthen Elitist GA，SEGA)和種馬遺傳算法對行程優(yōu)化模型進(jìn)行求解，求解時(shí)設(shè)置旅客最短銜接時(shí)間為120 min，3種算法參數(shù)均與3.1節(jié)中所設(shè)參數(shù)一致，圖4為3種算法迭代對比。

圖4 不同算法求解的迭代結(jié)果對比

對比圖4中采用不同算法求解的迭代曲線，發(fā)現(xiàn)Stud GA的收斂速度最快，種群在90代后趨于穩(wěn)定，種群中最優(yōu)個(gè)體出現(xiàn)在91 代，而SEGA和SGA分別在145 代和275 代時(shí)達(dá)到最優(yōu)，在收斂速度上均弱于Stud GA，這表明Stud GA在復(fù)雜的搜索空間內(nèi)，在不犧牲優(yōu)化效果的前提下，具有更高的搜索能力和穩(wěn)定性，在解決大規(guī)模復(fù)雜問題方面具備效率優(yōu)勢。

4 結(jié)論

為減少中轉(zhuǎn)行程中產(chǎn)生的旅客延誤，在考慮中轉(zhuǎn)過程中后序航班旅客延誤的情況下，建立行程優(yōu)化模型并采用優(yōu)化算法進(jìn)行求解，對航班時(shí)刻進(jìn)行調(diào)整，并且對不同旅客最短銜接時(shí)間和采用不同算法時(shí)的優(yōu)化結(jié)果進(jìn)行了比較，得到以下結(jié)論：

1)與經(jīng)典遺傳算法和增強(qiáng)精英保留遺傳算法相比，使用種馬遺傳算法進(jìn)行優(yōu)化有更快的收斂速度。

2)在旅客最短銜接時(shí)間為120 min的條件下，經(jīng)過模型優(yōu)化后中轉(zhuǎn)行程中的旅客延誤減少了29.9%。

3)當(dāng)旅客最短銜接時(shí)間越短時(shí)產(chǎn)生的旅客延誤越少，但模型優(yōu)化效果較為穩(wěn)定，優(yōu)化百分比為25%～30%。

4)本研究是基于中轉(zhuǎn)行程的優(yōu)化，未考慮取消行程等特殊情況，后續(xù)研究可將一些特殊情況加以考慮，對行程優(yōu)化問題做進(jìn)一步的研究。