動態信息下的機場定制巴士路徑優化

郭權，周和平，歐陽瑞祥，劉勇杰

動態信息下的機場定制巴士路徑優化

郭權，周和平，歐陽瑞祥，劉勇杰

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

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

區間路網阻抗；機場接駁路徑優化；動態信息；定制性；差分進化算法

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

1 模型建立

車輛在道路上行駛時會受到交通管制、交通擁堵、天氣變化等不確定因素的影響[9]。本研究通過引入區間數[10]，描述現實路網阻抗的不確定性，以保證建立模型的可靠性。機場定制巴士在行駛過程中，除必須提前預約的訂單節點外，對實時動態的訂單節點可決定是否響應。時刻，若某些訂單節點處的乘客航班發生延誤，則系統可根據延誤信息對車輛排班路徑進行實時優化調整。航班發生延誤后，乘客可及時通過系統反饋決定是否取消訂單。若乘客沒有反饋，則系統默認為不取消訂單。因此，考慮動態區間路網阻抗變化，建立動態信息下的機場定制巴士路徑優化模型。

1.1 目標函數與決策變量

以運營公司收益最大、車輛出行成本最小及車輛提前到達的時間窗懲罰成本最小為目標函數，建立的數學模型為：

1.2 約束條件

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

1) 站點約束

接駁車輛從起點出發到終點結束，中間節點滿足流量進出守恒。

式(4)、(5)表示接駁車輛從起點出發到達終點，式(6)、(7)表示車輛在起點時只出不進，到達終點后只進不出，式(8)表示車輛滿足進出流量守恒原則。

2) 供給約束

為鼓勵乘客提前預定，針對提前預定的乘客優先得到服務，可建立供給約束為：

3) 車輛容量約束

車內的乘客數不能超過車輛的額定載客量。

式中：為車輛的額定載客量；Q為時刻時已經上車人數。

4) 時間窗約束

車輛到達終點的時刻是由車輛出發時刻和車輛行駛時間決定的，所有車輛到達終點的時刻不能超過車輛最晚到達時間窗。其中，車輛服務乘客的時間暫時忽略不計。

2 算法設計

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

2.1 個體編碼

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

2.2 初始種群的生成

設初始種群為Z,0=(Z,1,Z,2,…,Z,V)，=(1, 2,3,…,)，Z,0為第0代第條個體，為初始種群的規模，為Z,0的維數。初始種群{Z,0|1≤Z,0≤+1}隨機產生。

2.3 變異操作

為種群進化代數，為縮放系數，0＜＜1。因為經過變異，個體“基因”值可能會超出邊界范圍，所以對此進行邊界條件的處理，將不符合邊界條件“基因”值通過初始種群生成方法重新產生。

2.4 交叉操作

為增加種群多樣性，防止算法早熟，對代種群目標個體Z,n和變異個體V,n通過交叉操作，產生實驗個體L,n。為保證實驗個體能夠繼承父代變異個體的優良結構，通過隨機選擇第i位“基因”作為交叉操作后L,n的第i位等位“基因”，剩下基因通過交叉概率選擇由Z,n或V,n來貢獻：

2.5 選擇操作

為避免算法早熟收斂，對縮放系數增加自適應變異操作，設計方法為：

式中：min為縮放系數的最小值；max為縮放系數的最大值；為調整系數，控制的下降速度。

該縮放系數為一個動態的概率參數，數值區間為 [0,1]。

2.6 計算步驟

1) 設置迭代次數=0；對參數進行初始化；

2) 根據設定的規則對初始種群進行編碼操作，隨機生成滿足條件的初始種群；

3) 令=+1，種群目標個體索引號=1；

4) 選定目標個體Z,i，隨機從初代種群中選取2個不同個體；

5) 根據縮放系數計算公式進行更新初始化，執行變異操作，獲得變異個體V,i；

6) 對變異后的個體實施交叉操作，獲得實驗個體L,i；

7) 計算個體L,i適應函數值，并執行選擇操作；

8) 目標個體索引號更新=+1，返回步驟4，直至=，否則進入步驟9；

9) 當迭代次數=0大于最大的迭代次數max時，循環結束并輸出獲得此時計算信息，否則返回步驟3繼續迭代。

3 算例分析

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

表1 提前預約旅客訂單信息

表2 初始路徑方案

圖1 初始路徑方案

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

表3 考慮航班延誤信息的實時路徑優化方案

由表3可知，系統針對當前的航班延誤信息得到了優化后的路徑方案，其中，車輛4的出發時間作出了相應的推遲調整。通過計算可得，乘客的平均等候時間優化為22.12 min至38.74 min，與優化前相比，乘客的最短等候時間減少了33.29%，最長等候時間減少了23.17%。

當=8:19時，此時車輛1已經接上或即將接上節點2處乘客，車輛2已經接上或即將接上節點6處乘客，車輛3已經接上節點3處乘客，車輛4暫未出發。此時，路網中新增了4個實時訂單，具體訂單信息見表4。路網中新增實時訂單信息代入模型中，由差分進化算法求解獲得考慮航班延時和實時訂單信息的實時路徑優化方案，具體見表5。

表4 實時旅客訂單信息

表5 考慮航班延誤和實時訂單信息的實時路徑優化方案

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

4 結語

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

[1] 張文博,蘇秦,程光路.基于動態需求的帶時間窗的車輛路徑問題[J].工業工程與管理,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] 劉欣萌,何世偉,陳勝波,等.帶時間窗VRP問題的多智能體進化算法[J].交通運輸工程學報,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] 王芳.區間需求下魯棒交通分配研究[D].長沙:長沙理工大學,2015.(WANG Fang. Study on the robust traffic assignment under interval demand[D].Changsha: Changsha University of Science & Technology, 2015. (in Chinese))

[4] 辛春林,張建文,張艷東.基于最小最大準則的危險品運輸網絡優化研究[J].中國安全科學學報,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] 何小鋒,馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統工程理論與實踐,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] 靳文舟,郭獻超,龔雋.基于精英選擇遺傳算法的需求響應公交規劃[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] 程旭.考慮變化調整時間及帶有時間窗的車輛調度問題研究[D].沈陽:沈陽工業大學,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] 周和平,馮軒,彭巍.區間阻抗下的魯棒最短路算法[J]. 系統工程,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] 章宇.不確定旅行時間環境下帶時間限制的路徑優化模型與算法[D].沈陽:東北大學,2017.(ZHANG Yu.Time- constrained routing optimization models and algorithms under uncertain travel times[D].Shenyang:Northeastern University, 2017.(in Chinese))

[13] 祁航,周和平,蘇貞旅.高鐵站定制性靈活線路接駁巴士路徑優化[J].交通科學與工程,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

湖南省自然科學基金資助項目(2019JJ40311)

郭權(1995?)，男，長沙理工大學碩士生。