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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 目標函數(shù)

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

(1)

(2)

(3)

1.3 約束條件

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

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

(4)

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

(5)

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

(6)

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

(7)

(8)

(9)

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

(10)

(11)

(12)

2 算法設計

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

圖2 種馬遺傳算法流程

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

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

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

(13)

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

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

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

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

3 實例驗證

3.1 實驗設計

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

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

3.3 算法對比

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

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

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

4 結(jié)論

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

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

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

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

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