郭權(quán)，周和平，歐陽瑞祥，劉勇杰

動態(tài)信息下的機(jī)場定制巴士路徑優(yōu)化

郭權(quán)，周和平，歐陽瑞祥，劉勇杰

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

為解決因航班延誤而造成旅客候機(jī)時(shí)間較長問題，考慮現(xiàn)實(shí)路網(wǎng)中阻抗不確定性和機(jī)場接駁定制化及差異化出行需求，以運(yùn)營收益最大、車輛出行成本最小和車輛提前到達(dá)的時(shí)間窗懲罰成本最小為目標(biāo)函數(shù)，建立了動態(tài)信息下機(jī)場定制巴士路徑優(yōu)化模型，并采用差分進(jìn)化算法對其進(jìn)行求解。為避免算法早熟，提出了改進(jìn)的自適應(yīng)操作方法，增強(qiáng)算法的全局尋優(yōu)能力。通過算例計(jì)算表明：考慮航班延誤和路網(wǎng)實(shí)時(shí)訂單的動態(tài)路徑優(yōu)化模型，可以減少旅客26.61%～46.68%的候機(jī)時(shí)間，該模型具有較強(qiáng)的可靠性和應(yīng)用價(jià)值。

區(qū)間路網(wǎng)阻抗；機(jī)場接駁路徑優(yōu)化；動態(tài)信息；定制性；差分進(jìn)化算法

隨著網(wǎng)絡(luò)與大數(shù)據(jù)技術(shù)的快速發(fā)展，以“線上預(yù)約，接送服務(wù)”為特點(diǎn)的機(jī)場定制巴士具有形式靈活、方便快捷和高效低碳等特點(diǎn)，可以解決出行者多種出行需求，為旅客去機(jī)場提供了出行便利。國內(nèi)外學(xué)者針對機(jī)場定制巴士路徑從模型構(gòu)建和模型求解展開了深入研究。張文博[1]等人針對帶時(shí)間窗的車輛路徑提出了兩階段規(guī)劃策略。劉欣萌[2]等人構(gòu)建了行駛時(shí)間最短和客戶等待時(shí)間最小的雙目標(biāo)優(yōu)化模型，設(shè)計(jì)了多智能體進(jìn)化算法進(jìn)行求解。王芳[3]等人采用合理范圍的區(qū)間數(shù)對交通需求進(jìn)行了度量。辛春林[4]等人將不確定性風(fēng)險(xiǎn)數(shù)據(jù)用區(qū)間數(shù)的形式來表示，并結(jié)合最小最大準(zhǔn)則構(gòu)建了雙層危險(xiǎn)品運(yùn)輸網(wǎng)絡(luò)魯棒規(guī)劃模型。Desrosiers[5]等人采用精確算法與經(jīng)典啟發(fā)式算法進(jìn)行了早期研究，但只適用求解小規(guī)模的網(wǎng)絡(luò)問題。Br?ysy[6]等人采用了智能啟發(fā)式算法進(jìn)行了研究。何小峰[7]等人結(jié)合量子計(jì)算，提出了一種求解VRPTW的量子蟻群算法。靳文舟[8]等人提出了一種精英選擇遺傳算法進(jìn)行模型求解，提高了收斂速度和搜索結(jié)果。這些研究主要集中于車輛路徑模型的不斷優(yōu)化改進(jìn)和求解，但考慮路徑優(yōu)化中實(shí)時(shí)動態(tài)需求的研究鮮見。因此，本研究擬構(gòu)建動態(tài)信息下機(jī)場定制巴士路徑優(yōu)化模型，為乘客提供個(gè)性化、定制化的接駁服務(wù)，并結(jié)合區(qū)間路網(wǎng)阻抗信息對車輛行駛路線進(jìn)行優(yōu)化。根據(jù)乘客航班延誤狀況和路網(wǎng)實(shí)時(shí)訂單，實(shí)時(shí)調(diào)整路徑優(yōu)化方案，為乘客提供準(zhǔn)點(diǎn)到達(dá)機(jī)場登機(jī)服務(wù)，避免長時(shí)間候機(jī)。

1 模型建立

車輛在道路上行駛時(shí)會受到交通管制、交通擁堵、天氣變化等不確定因素的影響[9]。本研究通過引入?yún)^(qū)間數(shù)[10]，描述現(xiàn)實(shí)路網(wǎng)阻抗的不確定性，以保證建立模型的可靠性。機(jī)場定制巴士在行駛過程中，除必須提前預(yù)約的訂單節(jié)點(diǎn)外，對實(shí)時(shí)動態(tài)的訂單節(jié)點(diǎn)可決定是否響應(yīng)。時(shí)刻，若某些訂單節(jié)點(diǎn)處的乘客航班發(fā)生延誤，則系統(tǒng)可根據(jù)延誤信息對車輛排班路徑進(jìn)行實(shí)時(shí)優(yōu)化調(diào)整。航班發(fā)生延誤后，乘客可及時(shí)通過系統(tǒng)反饋決定是否取消訂單。若乘客沒有反饋，則系統(tǒng)默認(rèn)為不取消訂單。因此，考慮動態(tài)區(qū)間路網(wǎng)阻抗變化，建立動態(tài)信息下的機(jī)場定制巴士路徑優(yōu)化模型。

1.1 目標(biāo)函數(shù)與決策變量

以運(yùn)營公司收益最大、車輛出行成本最小及車輛提前到達(dá)的時(shí)間窗懲罰成本最小為目標(biāo)函數(shù)，建立的數(shù)學(xué)模型為：

1.2 約束條件

機(jī)場定制巴士路徑優(yōu)化受到的約束：①流量進(jìn)出守恒的約束；②考慮提前預(yù)約客戶的優(yōu)先權(quán)，即接送必須保證完成其服務(wù)的優(yōu)先權(quán)，所以還受到供給約束；③考慮一些定量約束，如：車輛容量以及時(shí)間窗約束。

1) 站點(diǎn)約束

接駁車輛從起點(diǎn)出發(fā)到終點(diǎn)結(jié)束，中間節(jié)點(diǎn)滿足流量進(jìn)出守恒。

式(4)、(5)表示接駁車輛從起點(diǎn)出發(fā)到達(dá)終點(diǎn)，式(6)、(7)表示車輛在起點(diǎn)時(shí)只出不進(jìn)，到達(dá)終點(diǎn)后只進(jìn)不出，式(8)表示車輛滿足進(jìn)出流量守恒原則。

2) 供給約束

為鼓勵乘客提前預(yù)定，針對提前預(yù)定的乘客優(yōu)先得到服務(wù)，可建立供給約束為：

3) 車輛容量約束

車內(nèi)的乘客數(shù)不能超過車輛的額定載客量。

式中：為車輛的額定載客量；Q為時(shí)刻時(shí)已經(jīng)上車人數(shù)。

4) 時(shí)間窗約束

車輛到達(dá)終點(diǎn)的時(shí)刻是由車輛出發(fā)時(shí)刻和車輛行駛時(shí)間決定的，所有車輛到達(dá)終點(diǎn)的時(shí)刻不能超過車輛最晚到達(dá)時(shí)間窗。其中，車輛服務(wù)乘客的時(shí)間暫時(shí)忽略不計(jì)。

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

動態(tài)信息下的機(jī)場定制巴士路徑優(yōu)化屬于VRPTW問題[11?13]。差分進(jìn)化算法(differential evolution，簡稱為DE)對搜索空間中最優(yōu)解可能存在的區(qū)域有良好發(fā)現(xiàn)能力，具有求解高效特點(diǎn)。適用于求解VRPTW問題，所以采用差分進(jìn)化算法對其進(jìn)行求解。為避免算法早熟，本研究提出了一種改進(jìn)的自適應(yīng)操作方法，增強(qiáng)其在全局當(dāng)中的尋優(yōu)能力。

2.1 個(gè)體編碼

采用實(shí)數(shù)編碼，如：路網(wǎng)中包含起點(diǎn)、終點(diǎn)、個(gè)乘客訂單節(jié)點(diǎn)和輛車，則個(gè)體生成：[1,2,…,a]，a為實(shí)數(shù)，滿足1≤a≤+1，其中，a代表訂單節(jié)點(diǎn)。通過(a)函數(shù)對實(shí)數(shù)a進(jìn)行取整，車輛(a)對相應(yīng)乘客進(jìn)行接送。a的大小決定車輛訪問順序，數(shù)值小的先被訪問。若數(shù)值相等，則按照個(gè)體從左到右先后出現(xiàn)順序進(jìn)行排列。

2.2 初始種群的生成

設(shè)初始種群為Z,0=(Z,1,Z,2,…,Z,V)，=(1, 2,3,…,)，Z,0為第0代第條個(gè)體，為初始種群的規(guī)模，為Z,0的維數(shù)。初始種群{Z,0|1≤Z,0≤+1}隨機(jī)產(chǎn)生。

2.3 變異操作

為種群進(jìn)化代數(shù)，為縮放系數(shù)，0＜＜1。因?yàn)榻?jīng)過變異，個(gè)體“基因”值可能會超出邊界范圍，所以對此進(jìn)行邊界條件的處理，將不符合邊界條件“基因”值通過初始種群生成方法重新產(chǎn)生。

2.4 交叉操作

為增加種群多樣性，防止算法早熟，對代種群目標(biāo)個(gè)體Z,n和變異個(gè)體V,n通過交叉操作，產(chǎn)生實(shí)驗(yàn)個(gè)體L,n。為保證實(shí)驗(yàn)個(gè)體能夠繼承父代變異個(gè)體的優(yōu)良結(jié)構(gòu)，通過隨機(jī)選擇第i位“基因”作為交叉操作后L,n的第i位等位“基因”，剩下基因通過交叉概率選擇由Z,n或V,n來貢獻(xiàn)：

2.5 選擇操作

為避免算法早熟收斂，對縮放系數(shù)增加自適應(yīng)變異操作，設(shè)計(jì)方法為：

式中：min為縮放系數(shù)的最小值；max為縮放系數(shù)的最大值；為調(diào)整系數(shù)，控制的下降速度。

該縮放系數(shù)為一個(gè)動態(tài)的概率參數(shù)，數(shù)值區(qū)間為 [0,1]。

2.6 計(jì)算步驟

1) 設(shè)置迭代次數(shù)=0；對參數(shù)進(jìn)行初始化；

2) 根據(jù)設(shè)定的規(guī)則對初始種群進(jìn)行編碼操作，隨機(jī)生成滿足條件的初始種群；

3) 令=+1，種群目標(biāo)個(gè)體索引號=1；

4) 選定目標(biāo)個(gè)體Z,i，隨機(jī)從初代種群中選取2個(gè)不同個(gè)體；

5) 根據(jù)縮放系數(shù)計(jì)算公式進(jìn)行更新初始化，執(zhí)行變異操作，獲得變異個(gè)體V,i；

6) 對變異后的個(gè)體實(shí)施交叉操作，獲得實(shí)驗(yàn)個(gè)體L,i；

7) 計(jì)算個(gè)體L,i適應(yīng)函數(shù)值，并執(zhí)行選擇操作；

8) 目標(biāo)個(gè)體索引號更新=+1，返回步驟4，直至=，否則進(jìn)入步驟9；

9) 當(dāng)?shù)螖?shù)=0大于最大的迭代次數(shù)max時(shí)，循環(huán)結(jié)束并輸出獲得此時(shí)計(jì)算信息，否則返回步驟3繼續(xù)迭代。

3 算例分析

假設(shè)某機(jī)場定制接駁巴士系統(tǒng)，運(yùn)營公司的車場為，考慮到車輛在機(jī)場高速上行駛時(shí)不能隨意更改路線，所以將終點(diǎn)設(shè)置為機(jī)場高速入口處，并預(yù)留出車輛在機(jī)場高速行駛時(shí)間，車輛在機(jī)場高速上行駛時(shí)所需時(shí)間為20 min。機(jī)場定制接駁巴士采用16座型的巴士，乘客到達(dá)機(jī)場后至登機(jī)所需時(shí)間為60 min，=2.5元/人，=50元/輛，0=1 元/km，=0.5元/min。算法中涉及的參數(shù)設(shè)定為：初始種群規(guī)模=150，最大的進(jìn)化代數(shù)G=120，交叉概率值=0.6，min=0.3，max=0.9，=100。現(xiàn)有24位乘客提前進(jìn)行了預(yù)約，具體信息見表1。

表1 提前預(yù)約旅客訂單信息

表2 初始路徑方案

圖1 初始路徑方案

根據(jù)表2中各車輛到達(dá)終點(diǎn)的時(shí)間和所有乘客到達(dá)終點(diǎn)的最晚時(shí)間等信息進(jìn)行計(jì)算，可得到在初始路徑方案中，乘客的平均等候時(shí)間為18.51 min至35.77 min。當(dāng)=8:15時(shí)，車輛1即將接上節(jié)點(diǎn)2處乘客，車輛2已經(jīng)接上節(jié)點(diǎn)1處乘客，車輛3已經(jīng)接上或即將接上節(jié)點(diǎn)3處乘客，車輛4即將出發(fā)前往節(jié)點(diǎn)6處。此時(shí)，起飛時(shí)刻為10:45的航班延誤45 min，更新為11:30起飛，則乘客的平均等候時(shí)間變?yōu)?3.16 min至50.42 min，通過系統(tǒng)反饋航班發(fā)生延誤的乘客均未取消訂單。航班實(shí)時(shí)延誤信息代入模型中，由差分進(jìn)化算法求解獲得考慮航班延誤后的實(shí)時(shí)路徑優(yōu)化方案見表3。

表3 考慮航班延誤信息的實(shí)時(shí)路徑優(yōu)化方案

由表3可知，系統(tǒng)針對當(dāng)前的航班延誤信息得到了優(yōu)化后的路徑方案，其中，車輛4的出發(fā)時(shí)間作出了相應(yīng)的推遲調(diào)整。通過計(jì)算可得，乘客的平均等候時(shí)間優(yōu)化為22.12 min至38.74 min，與優(yōu)化前相比，乘客的最短等候時(shí)間減少了33.29%，最長等候時(shí)間減少了23.17%。

當(dāng)=8:19時(shí)，此時(shí)車輛1已經(jīng)接上或即將接上節(jié)點(diǎn)2處乘客，車輛2已經(jīng)接上或即將接上節(jié)點(diǎn)6處乘客，車輛3已經(jīng)接上節(jié)點(diǎn)3處乘客，車輛4暫未出發(fā)。此時(shí)，路網(wǎng)中新增了4個(gè)實(shí)時(shí)訂單，具體訂單信息見表4。路網(wǎng)中新增實(shí)時(shí)訂單信息代入模型中，由差分進(jìn)化算法求解獲得考慮航班延時(shí)和實(shí)時(shí)訂單信息的實(shí)時(shí)路徑優(yōu)化方案，具體見表5。

表4 實(shí)時(shí)旅客訂單信息

表5 考慮航班延誤和實(shí)時(shí)訂單信息的實(shí)時(shí)路徑優(yōu)化方案

由表5可知，系統(tǒng)針對航班延誤和路網(wǎng)實(shí)時(shí)訂單信息給出了新的路徑優(yōu)化方案。其中，車輛4的出發(fā)時(shí)間作出了相應(yīng)調(diào)整，實(shí)時(shí)訂單26、27、28得到了響應(yīng)接駁。通過計(jì)算可得到乘客的平均等候時(shí)間為17.68 min至37.00 min，較上一次優(yōu)化有所減少。新的車輛實(shí)時(shí)路徑優(yōu)化方案，滿足了乘客需求，得到了進(jìn)一步的優(yōu)化，乘客的最小等候時(shí)間減少了46.68%，最大等候時(shí)間減少了26.61%，整體客座率也得到了提高。

4 結(jié)語

考慮區(qū)間路網(wǎng)阻抗的影響，將動態(tài)問題轉(zhuǎn)化為一系列不同時(shí)刻下的靜態(tài)子問題，進(jìn)而以系統(tǒng)收益最大、車輛出行成本最小以及車輛提前到達(dá)的時(shí)間窗懲罰成本最小為目標(biāo)，建立了動態(tài)信息下的機(jī)場定制巴士動態(tài)路徑優(yōu)化模型，解決了航班延誤下乘客候機(jī)時(shí)間較長的問題。采用差分進(jìn)化算法，求解所提模型。為避免算法早熟，通過增加參數(shù)的自適應(yīng)操作，提高了算法在全局當(dāng)中的尋優(yōu)能力。通過算例分析可得，本模型在保障多目標(biāo)成本最小的前提下，可以最大減少旅客46.68%候機(jī)時(shí)間，充分滿足了人們個(gè)性化以及差異化的出行需求，為旅客提供了更優(yōu)良的服務(wù)，具有廣闊的應(yīng)用前景。

[1] 張文博,蘇秦,程光路.基于動態(tài)需求的帶時(shí)間窗的車輛路徑問題[J].工業(yè)工程與管理,2016,21(6):68?74. (ZHANG Wen-bo,SU Qin,CHENG Guang-lu.Vehicle routing problem with time windows based on dynamic demands[J]. Industrial Engineering and Management, 2016, 21(6): 68?74.(in Chinese))

[2] 劉欣萌,何世偉,陳勝波,等.帶時(shí)間窗VRP問題的多智能體進(jìn)化算法[J].交通運(yùn)輸工程學(xué)報(bào),2014,14(3):105?110. (LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, et al. Multi-agent evolutionary algorithm of VRP problem with time window[J].Journal of Traffic and Transportation Engineering, 2014, 14(3): 105?110. (in Chinese))

[3] 王芳.區(qū)間需求下魯棒交通分配研究[D].長沙:長沙理工大學(xué),2015.(WANG Fang. Study on the robust traffic assignment under interval demand[D].Changsha: Changsha University of Science & Technology, 2015. (in Chinese))

[4] 辛春林,張建文,張艷東.基于最小最大準(zhǔn)則的危險(xiǎn)品運(yùn)輸網(wǎng)絡(luò)優(yōu)化研究[J].中國安全科學(xué)學(xué)報(bào),2016,26(8): 84?89. (XIN Chun-lin, ZHANG Jian-wen, ZHANG Yan-dong.Hazardous materials transportation network optimization based on Min-max criterion[J]. China Safety Science Journal,2016,26(8):84?89.(in Chinese))

[5] Desrosiers J,Dumas Y,Solomon M M,et al.Chapter 2 Time constrained routing and scheduling[J].Handbooks in Operations Research and Management Science,1995,8: 35?139.

[6] Br?ysy O,Gendreau M.Vehicle routing problem with time windows, part I: Route construction and local search algorithms[J]. Transportation Science, 2005, 39(1): 104? 118.

[7] 何小鋒,馬良.帶時(shí)間窗車輛路徑問題的量子蟻群算法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(5):1255?1261.(HE Xiao-feng,MA Liang.Quantum-inspired ant colony algorithm for vehicle routing problem with time windows[J].Systems Engineering-Theory & Practice, 2013, 33(5):1255?1261.(in Chinese))

[8] 靳文舟,郭獻(xiàn)超,龔雋.基于精英選擇遺傳算法的需求響應(yīng)公交規(guī)劃[J].公路工程,2020,45(2):44?49.(JIN Wen-zhou, GUO Xian-chao, GONG Jun.Based on elitist selection genetic algorithm for demand responsive transit planning[J]. Highway Engineering, 2020, 45(2): 44?49. (in Chinese))

[9] 程旭.考慮變化調(diào)整時(shí)間及帶有時(shí)間窗的車輛調(diào)度問題研究[D].沈陽:沈陽工業(yè)大學(xué),2019.(CHENG Xu. Research on vehicle routing problem with time windows and variable adjustment time[D]. Shenyang: Shenyang University of Technology,2019.(in Chinese))

[10] 周和平,馮軒,彭巍.區(qū)間阻抗下的魯棒最短路算法[J]. 系統(tǒng)工程,2017,35(12):121?125.(ZHOU He-ping, FENG Xuan, PENG Wei. Robust shortest path algorithm under interval impedence[J]. Systems Engineering, 2017, 35(12):121?125.(in Chinese))

[11] Khouadjia M R, Sarasola B, Alba E, et al. A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests[J]. Applied Soft Computing,2012,12(4):1426?1439.

[12] 章宇.不確定旅行時(shí)間環(huán)境下帶時(shí)間限制的路徑優(yōu)化模型與算法[D].沈陽:東北大學(xué),2017.(ZHANG Yu.Time- constrained routing optimization models and algorithms under uncertain travel times[D].Shenyang:Northeastern University, 2017.(in Chinese))

[13] 祁航,周和平,蘇貞旅.高鐵站定制性靈活線路接駁巴士路徑優(yōu)化[J].交通科學(xué)與工程,2018,34(4):71?76.(QI Hang, ZHOU He-ping, SU Zhen-lv.Route optimization of customized flexible line feeder bus for the high-speed rail station[J].Journal of Transport Science and Engineering, 2018,34(4):71?76.(in Chinese))

Route optimization of customized airport bus base on dynamic information

GUO Quan, ZHOU He-ping, OUYANG Rui-xiang, LIU Yong-jie

(School of Traffic and Transportation Engineering, Changsha University of Science & Technology, Changsha 410114, China)

In order to reduce the waiting time caused by the flight delay, an route optimization model for the customized airport bus was established considering the uncertainty of the road network and the trip demand of the customization and differentiated. Then the maximum operating income, the minimum cost of vehicle and the minimum penalty cost for early arrival of vehicles were proposed as objective function, which was solved by differential evolution algorithm. To avoid algorithm premature, an improved adaptive operation method was introduced to enhance the ability of the global optimization. The calculation examples show that the waiting time of passengers can be reduced from 26.61% to 46.68%, when the dynamic path optimization model is used considering the flight delay and the booking of road network. The model is considered as reliable to optimize the route of airport bus.

interval road network impedance; route optimization of airport bus; dynamic information; customization; differential evolution algorithm

U491

A

1674 ? 599X(2021)02 ? 0085? 06

2020?07?09

湖南省自然科學(xué)基金資助項(xiàng)目(2019JJ40311)

郭權(quán)(1995?)，男，長沙理工大學(xué)碩士生。