動態(tài)航班信息下機場需求響應(yīng)接駁車輛路徑優(yōu)化

劉勇杰，李樹民 LIU Yongjie， LI Shumin

（長沙理工大學(xué) 交通運輸工程學(xué)院，湖南 長沙410114）

需求響應(yīng)式運輸模式作為新興出行方式在機場接駁中起著重要作用，然而航班的延誤使得機場整體接駁的效率與質(zhì)量不高，給乘客帶來額外的時間損失。隨著互聯(lián)網(wǎng)時代的發(fā)展，目前國內(nèi)各大航空公司提供了航班動態(tài)查詢功能，因此，有必要結(jié)合動態(tài)航班信息進行接駁車輛的行車計劃決策，提高接駁效率，滿足乘客對出行品質(zhì)的要求。

國外針對需求響應(yīng)式接駁運輸?shù)难芯勘容^早，內(nèi)容相對比較豐富。Perera[1]提出一種對乘客需求作出快速反應(yīng)的需求響應(yīng)系統(tǒng)，實時響應(yīng)乘客需求。Charisis[2]針對城市交通最后一公里問題，提出DRT 數(shù)學(xué)模型，并應(yīng)用遺傳算法求解。Sun Bo[3]根據(jù)乘客選擇的地鐵時刻以及服務(wù)時間窗口，提出一類考慮個性化出行的混合整數(shù)線性規(guī)劃模型。Shen J[4]提出考慮服務(wù)提供者和用戶的兩階段路徑優(yōu)化模型。隨著國內(nèi)出行模式智能化的發(fā)展，定制公交、網(wǎng)約車等響應(yīng)式運輸模式逐漸走向成熟。彭巍[5]考慮區(qū)間路網(wǎng)阻抗信息對機場定制巴士的路徑優(yōu)化進行了研究。孫博[6-7]提出一類需求響應(yīng)型接駁公交調(diào)度模型。阮冠軒[8]根據(jù)乘客支付意愿，研究了需求響應(yīng)型接駁公交路徑規(guī)劃問題。鄭漢[9]提出考慮混合車型的需求響應(yīng)公交定制服務(wù)方法。本文所提出的需求響應(yīng)接駁模式，是結(jié)合互聯(lián)網(wǎng)根據(jù)機場旅客的實時航班延誤信息，為旅客提供動態(tài)延誤下的接駁路徑服務(wù)，滿足旅客出行時間要求。

考慮研究問題屬于帶有軟時間窗的動態(tài)車輛路徑優(yōu)化問題[10]。關(guān)于動態(tài)車輛路徑研究，文獻[11-13]提出兩階段求解算法對動態(tài)車輛優(yōu)化問題進行求解，將問題處理為基于時間軸下的一系列靜態(tài)子問題，為此本文采用以上方法，構(gòu)建基于時間軸的混合整數(shù)動態(tài)規(guī)劃模型，通過計算不同時刻發(fā)生延誤下的最優(yōu)車輛安排方案，達到減少旅客時間損失的目的。

1 問題描述

依照需求響應(yīng)系統(tǒng)給出乘客預(yù)約請求，其中預(yù)約請求包括乘客要求的上車地點、期望上車時間窗、航班時刻信息等，運營公司根據(jù)以上信息合理安排出發(fā)時間以及行駛路徑，在滿足乘客服務(wù)質(zhì)量情況下減少企業(yè)運營成本；由于航班延誤信息動態(tài)出現(xiàn)，當(dāng)航班發(fā)生延誤時，未完成服務(wù)乘客的期望接駁時間窗以及航班起飛時間發(fā)生改變，原先制定的行駛方案可能出現(xiàn)質(zhì)量低劣情況，因此需結(jié)合當(dāng)前信息對此時網(wǎng)絡(luò)進行重新優(yōu)化，得到發(fā)生延誤下的最優(yōu)行駛方案，保證接駁服務(wù)質(zhì)量；即在整個優(yōu)化階段，制定的車輛行駛路徑分為發(fā)車前的初始路徑和發(fā)車后的實時優(yōu)化路徑。

為將動態(tài)問題靜態(tài)化，通過引入時間軸和關(guān)鍵點[12-13]，將問題處理成一系列靜態(tài)子問題。實時優(yōu)化階段，關(guān)鍵點為在發(fā)生航班延誤時車輛到達或正在前往的乘客節(jié)點，此時關(guān)鍵點可被視為虛擬的配送中心，只能發(fā)出一輛車，車輛的容量為動態(tài)更新后的車載容量，問題變?yōu)槎嗯渌椭行牡能囕v路徑問題；在發(fā)車前階段，起始車場視為關(guān)鍵點。

2 模型建立

2.1 相關(guān)符號定義。集合：Gt表示t時刻網(wǎng)絡(luò)中的所有關(guān)鍵點；Wt表示t時刻機場、未被服務(wù)的預(yù)約乘客；Mt表示t時刻未被服務(wù)的預(yù)約乘客；Nt表示t時刻所有未被服務(wù)的預(yù)約乘客、關(guān)鍵點、機場。

參數(shù)與變量：Ut表示t時刻航班信息下的起飛時間；為t時刻下乘客i期望的接駁時間窗表示t時刻車輛e已行駛的距離；Dmax為車輛行駛的最大距離；Tmax為車輛最長行駛時間；為時刻t車輛k已行駛時間；TW為乘客下車之后趕上飛機所需花費的時間；tij為節(jié)點i、j之間的路段阻抗值；tik為車輛k到達節(jié)點i的時刻；qik為車輛到達節(jié)點i的載客人數(shù)；F表示機場；qi表示預(yù)約訂單的隨行人數(shù)；Q為車輛容量；dij為節(jié)點之間的最短距離；Si為接乘客時的服務(wù)時間；β1、β2、β3為目標函數(shù)的權(quán)重系數(shù)。

2.2 基于時間軸的動態(tài)規(guī)劃模型。根據(jù)上述研究建立以車輛行駛成本、乘客時間窗懲罰成本、機場到達等待時間成本最小為優(yōu)化目標的混合整數(shù)動態(tài)規(guī)劃模型如下：

式（1） 為目標函數(shù)；式（2） 和式（3） 表示接駁車輛從關(guān)鍵點出發(fā)到達機場F；式（4） 表示接駁車輛進出流量守恒；式（5） 表示乘客的預(yù)約請求都要得到滿足；式（6） 表示t時刻安排車輛接送的人數(shù)不能超過剩余載客容量；式（7）、式（8） 為

車輛到達節(jié)點時刻的線性化表達式，Z表示極大的固定值；式（9） 表示車輛到達機場的時刻不超過允許時間；式（10） 表示車輛行駛的距離不超過允許最大值； 式（11） 表示乘客在車時間不超過允許最大值。

3 兩階段求解算法設(shè)計

第一階段：在車輛未發(fā)出時，關(guān)鍵點位于車場，根據(jù)乘客預(yù)約信息和動態(tài)的航班時刻信息，通過Lingo 求解獲得最優(yōu)行駛路線以及出發(fā)時間，得到初始車輛路徑安排。

第二階段：在車輛發(fā)出時，將研究問題基于時間軸進行實時優(yōu)化，通過時間軸不斷更新接駁車輛的位置坐標、車載人數(shù)、關(guān)鍵點、未服務(wù)的乘客等相關(guān)信息；當(dāng)航班出現(xiàn)延誤信息時，更新乘客期望接駁時間窗以及旅客航班起飛時間，并對此時的網(wǎng)絡(luò)進行車輛的路徑優(yōu)化，得到最佳行駛路線，其中位于車場的車輛可調(diào)整其出發(fā)時間，在途車輛不再調(diào)整；當(dāng)車輛行駛途中未出現(xiàn)航班延誤信息，接駁車輛按初始計劃路線行駛。

算法設(shè)計圖如圖1 所示。

4 算例分析

設(shè)有一機場需求響應(yīng)接駁系統(tǒng)，運營公司車場編號為0，坐標（0，0 ），機場編號為24，坐標（40 ，0 ）以及23 位乘客預(yù)約請求（編號1-23），機場接駁車輛采用12 座的中型巴士，乘客下車之后趕上飛機所花費的時間為60 分鐘，車輛最大行駛距離Dmax=70km，最大行駛時間Tmax=70min，β1、β2、β3權(quán)重系數(shù)分別取值為0.8、0.1、0.1，表1 為預(yù)排班乘客的預(yù)約信息。

在未發(fā)車前，結(jié)合乘客預(yù)約信息以及當(dāng)前航班信息，通過Lingo 求解獲得初始行車路徑。系統(tǒng)運營期間，航班延誤動態(tài)出現(xiàn)，設(shè)在時刻8:20、9:44 發(fā)布航班延誤信息，延誤后航班起飛時間分別為12:00，12:25。8:20 時，接駁車輛均未發(fā)出，航班晚點45分鐘，系統(tǒng)通過反饋更新乘客期望時間窗，將以上信息帶入網(wǎng)絡(luò)模型中，重新計算，得到航班延誤后初始車輛路徑安排。初始車輛路徑安排和8:20 航班延誤后車輛路徑安排如表2、表3 和圖2、圖3 所示。

9:44 時，網(wǎng)絡(luò)已發(fā)出3 輛車，車輛3 還未發(fā)車其出發(fā)時間可同時在實時階段下進行優(yōu)化；系統(tǒng)通過時間軸記錄了當(dāng)前時刻P=9:44 下的相關(guān)信息：關(guān)鍵點GP={0，5，6，8}，WP={4，7，9，10，11，12，13，14，15，16，17，18，19，20，21，22，2 3，24 };N P={4，7，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，0，5，6，8} ;MP={4，7，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23}。

圖1 算法設(shè)計圖

表1 乘客預(yù)約信息

表2 初始車輛路徑安排

表3 8:20 航班延誤后車輛路徑

更新未完成服務(wù)乘客的期望時間窗信息，將更新后的相關(guān)信息輸入到上述動態(tài)網(wǎng)絡(luò)模型中由Lingo 求解，得到9:44 航班信息發(fā)生延誤下的最優(yōu)行駛路徑，如表4 和圖4 所示。

通過以上結(jié)果可以看出：（1） 在航班發(fā)生延誤狀態(tài)下乘客期望接駁時間窗以及航班起飛時刻發(fā)生改變，原先的行駛路徑已不再是最優(yōu)，使得優(yōu)化后的車輛路徑發(fā)生變化，改變了到達乘客節(jié)點的接駁時間和機場到達時間。（2） 模型求解得到的滿載率和行駛時間都在規(guī)定范圍內(nèi)，同時乘客需求都得到了滿足，證明了模型的有效性。（3） 延誤優(yōu)化后車輛到達機場時間整體推遲，減少了乘客機場等待時間。

由此可見，兩階段算法可以很好地處理實時延誤下的車輛路徑優(yōu)化，具有良好的適用性。

5 結(jié) 論

（1） 結(jié)合動態(tài)航班延誤信息，構(gòu)建了基于時間軸的機場需求響應(yīng)接駁車輛動態(tài)路徑優(yōu)化模型，將動態(tài)問題處理為不同時刻下的靜態(tài)子問題。其以車輛行駛成本、乘客時間窗懲罰成本、乘客機場等待時間成本最小為優(yōu)化目標，在降低企業(yè)運營成本的同時提高了接駁的品質(zhì)。

圖2 初始車輛路徑

圖3 8:20 航班延誤后車輛路徑

圖4 9:44 航班延誤后車輛路徑

表4 9:44 航班延誤后車輛路徑安排

（2） 模型求解方面，利用兩階段求解策略，得到發(fā)車前的初始行駛路徑以及發(fā)車后實時延誤下的行駛路徑。

（3） 通過研究算例驗證了模型與算法的有效性，能夠為民航乘客提供更加智能化與便捷化的接駁服務(wù)。