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

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

（長(zhǎng)沙理工大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙410114）

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

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

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

1 問題描述

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

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

2 模型建立

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

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

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

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

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

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

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

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

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

4 算例分析

設(shè)有一機(jī)場(chǎng)需求響應(yīng)接駁系統(tǒng)，運(yùn)營(yíng)公司車場(chǎng)編號(hào)為0，坐標(biāo)（0，0 ），機(jī)場(chǎng)編號(hào)為24，坐標(biāo)（40 ，0 ）以及23 位乘客預(yù)約請(qǐng)求（編號(hào)1-23），機(jī)場(chǎng)接駁車輛采用12 座的中型巴士，乘客下車之后趕上飛機(jī)所花費(fèi)的時(shí)間為60 分鐘，車輛最大行駛距離Dmax=70km，最大行駛時(shí)間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)運(yùn)營(yíng)期間，航班延誤動(dòng)態(tài)出現(xiàn)，設(shè)在時(shí)刻8:20、9:44 發(fā)布航班延誤信息，延誤后航班起飛時(shí)間分別為12:00，12:25。8:20 時(shí)，接駁車輛均未發(fā)出，航班晚點(diǎn)45分鐘，系統(tǒng)通過反饋更新乘客期望時(shí)間窗，將以上信息帶入網(wǎng)絡(luò)模型中，重新計(jì)算，得到航班延誤后初始車輛路徑安排。初始車輛路徑安排和8:20 航班延誤后車輛路徑安排如表2、表3 和圖2、圖3 所示。

9:44 時(shí)，網(wǎng)絡(luò)已發(fā)出3 輛車，車輛3 還未發(fā)車其出發(fā)時(shí)間可同時(shí)在實(shí)時(shí)階段下進(jìn)行優(yōu)化；系統(tǒng)通過時(shí)間軸記錄了當(dāng)前時(shí)刻P=9:44 下的相關(guān)信息：關(guān)鍵點(diǎ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è)計(jì)圖

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

表2 初始車輛路徑安排

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

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

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

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

5 結(jié) 論

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

圖2 初始車輛路徑

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

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

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

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

（3） 通過研究算例驗(yàn)證了模型與算法的有效性，能夠?yàn)槊窈匠丝吞峁└又悄芑c便捷化的接駁服務(wù)。