多車場響應型接駁公交運行線路與調(diào)度的協(xié)調(diào)研究

王正武，劉杰，鄒文竹

多車場響應型接駁公交運行線路與調(diào)度的協(xié)調(diào)研究

王正武，劉杰，鄒文竹

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

為提高響應型接駁公交運行效率，提出響應型接駁公交系統(tǒng)多車場協(xié)同運行、多車型協(xié)調(diào)調(diào)度、線路與調(diào)度協(xié)調(diào)設計的思想。引入虛擬車場將多車場設計問題轉換為單一車場設計問題；建立混合需求問題的兩階段法來分階段處理預約需求和實時需求；構建預約需求下車輛路徑與調(diào)度的協(xié)調(diào)優(yōu)化模型及其求解算法。計算結果表明：在給定相同的預約需求和混合需求下，與獨立運行相比，協(xié)同運行的總費用分別降低了8.6%和13.0%，車輛總運行時間分別減少了5.7%和12.5%；多車場的協(xié)同運行有效地提高了運營效率。小型車比例增加50%，大型車比例同時減少50%時，系統(tǒng)總費用的變化率在獨立運行和協(xié)同運行下分別達到11.2%和5.9%，車型比例對系統(tǒng)總費用具有顯著影響。

交通工程；協(xié)同運行；兩階段法；多車場；響應型接駁公交

地鐵、快速公交等干線公交的低覆蓋率導致距干線公交站較遠區(qū)域的乘客在選擇干線公交出行時存在“第一/最后一公里”問題，因此，能有效解決該問題的響應型接駁公交(Responsive Feeder Transit，RFT)逐漸被推廣實施。RFT在運行線路與車輛調(diào)度方面的研究主要集中于預約需求(當前班次發(fā)出之前對當前班次提出的乘坐申請)下考慮乘客等待成本和車輛運行成本等的車輛路徑研究[1?3]和車輛路徑與調(diào)度的協(xié)調(diào)研究[4]。隨著研究的深入，更貼近實際情況的實時需求(當前班次已發(fā)出尚未到達需求點之前，對當前班次提出的乘坐申請)被考慮[5?7]。邱豐等[8?9]建立了RFT系統(tǒng)混合需求(同時具有預約需求和實時需求)的兩階段法，較好地解決了混合需求下車輛調(diào)度問題、多換乘站車輛路徑與調(diào)度的協(xié)調(diào)優(yōu)化問題。因啟發(fā)式算法比傳統(tǒng)的精確算法尋優(yōu)能力強、收斂快，現(xiàn)有研究主要采用啟發(fā)式算法來求解車輛路徑與調(diào)度問題[10?12]。Barma 等[13?15]分別基于動態(tài)分配車場、虛擬車場等方法研究了多車場物流系統(tǒng)的協(xié)調(diào)調(diào)度問題，與傳統(tǒng)的分級分區(qū)調(diào)度相比，多車場的協(xié)調(diào)調(diào)度有效提高了物流系統(tǒng)的運行效率。到目前為止，現(xiàn)有研究主要關注的是車場惟一、且位于換乘站內(nèi)的RFT系統(tǒng)，實際上，因換乘站的用地限制，換乘站幾乎不會建設公交車場，接駁公交需從換乘站外的車場出發(fā)并回到車場；同時，接駁公交可能分多個車場停放，需要進行多車場的協(xié)調(diào)調(diào)度。其次，現(xiàn)有研究均忽視了返回車場的優(yōu)化，然而返回車場的選擇對各車場后續(xù)班次的運行線路、調(diào)度以及系統(tǒng)總成本均有重要影響。最后，現(xiàn)有研究多數(shù)僅考慮預約需求，實際上，在車輛運行途中，也有乘客會提出即時乘車申請。針對現(xiàn)有研究的不足，本文以多車場RFT系統(tǒng)為研究對象，同時采用虛擬車場方法、兩階段法來分別處理多車場協(xié)調(diào)調(diào)度問題、混合需求問題，構建混合需求下多車場RFT系統(tǒng)發(fā)出車場、發(fā)出車型、發(fā)車時間、運行線路、返回車場協(xié)調(diào)優(yōu)化的兩階段法，從而有效提高RFT系統(tǒng)的運行效率，為RFT系統(tǒng)的推廣應用提供有力的技術支持。

1 問題描述

1) 多車場RFT系統(tǒng)存在2種運行方式：獨立運行(各車場僅接送各自服務范圍內(nèi)的乘客)、協(xié)同運行(協(xié)同調(diào)度各車場的車輛來接送所有車場服務范圍內(nèi)的乘客)，本文研究RFT系統(tǒng)多車場的協(xié)同問題、運行線路與調(diào)度的協(xié)調(diào)問題。

2) 本文引入虛擬車場[14]方法，將多車場中由發(fā)出車場?需求點?換乘站?返回車場組成的各車輛的運行線路串聯(lián)起來，形成一條由虛擬車場、發(fā)出車場、需求點、換乘站、返回車場等要素組成的運行線路。虛擬車場的設置要求如下：

虛擬車場是系統(tǒng)中虛擬的惟一車輛?？康?，其位置任選；

虛擬車場與所有實際車場相連，但其間的費用(包括距離、阻抗等)均為0；

實際車場均變?yōu)樘厥獾男枨簏c，但需求均為0；

引入虛擬車場后，乘客將不固定隸屬于某個實際車場的服務范圍。

3) 本文采用兩階段思想[8?9]處理混合需求，構建混合需求下多車場RFT系統(tǒng)運行線路與調(diào)度協(xié)調(diào)優(yōu)化的兩階段法，優(yōu)化流程如圖1所示。

圖1 兩階段法流程

圖1中，第1階段處理預約需求，即根據(jù)預約需求和初始車輛分布，協(xié)調(diào)優(yōu)化發(fā)出車場、發(fā)出車型、發(fā)出時間、運行線路和返回車場；第2階段處理實時需求，按實時需求的位置與當前車輛的距離從小到大的順序根據(jù)判斷規(guī)則逐一判斷是否響應各個實時需求，并根據(jù)響應情況優(yōu)化當前班次的剩余線路和返回車場、后續(xù)班次的運行線路和調(diào)度方案，不能響應的實時需求則轉為預約需求，應被下一班次響應。

2 預約需求下多車場RFT系統(tǒng)運行線路與調(diào)度的協(xié)調(diào)

2.1 基本假設

服務區(qū)域內(nèi)車輛沿各點間最短路行駛且行駛速度恒為；僅考慮在需求點接乘客到換乘站(從換乘站送乘客至需求點為其逆過程)的問題；乘客只能在預約的需求點上車，在換乘站下車；乘客需求一旦被系統(tǒng)響應便不會被取消；所有乘客均在預約上車時間到達需求點，當乘客上車后接駁車輛立即 發(fā)車。

2.2 模型構建

協(xié)調(diào)模型的目標是使由車輛運行費用和乘客等待費用構成的系統(tǒng)總費用最小：

其中，{1,2,…,,…,}為實際車場集合；v為班次發(fā)出的車輛；表示車輛類型；r是車型為的車輛總量；=[γsk]×S為班次發(fā)出前所有車場的車輛分布矩陣，元素d為班次發(fā)出前車場車型的車輛保有量；為車場數(shù)，為車型總量；是S列的行向量，其元素d為班次發(fā)出前正在行駛的屬于車型的車輛數(shù)。

式(7)為發(fā)車約束，班次能經(jīng)過車場也即能從車場發(fā)出說明車場相應車型的車輛保有量大于0；式(8)~(10)為確保各車型車輛運行數(shù)量與車場保有量的約束；式(11)保證所有乘客均被服務；式(12)為車輛容量約束；式(13)為車輛單程最大行駛時間約束。

3 實時需求的響應

3.1 響應規(guī)則

將實時需求分為殘疾人、老年人等發(fā)出的特殊實時需求和其他人發(fā)出的一般實時需求，特殊實時需求必須優(yōu)先響應。一般實時需求則根據(jù)規(guī)則判別是否響應：按一般實時需求點的位置與當前班次車輛的距離從小到大的順序依次判斷，若采用最節(jié)約插入法[9]插入后依然滿足最大運行時間約束和車輛容量約束，則接受，否則不接受。不接受的實時需求轉為預約需求應被下一班次響應。

3.2 運行線路與調(diào)度的再優(yōu)化

實時需求被響應后，系統(tǒng)將調(diào)用第1階段模型對當前班次的剩余線路及返回車場、后續(xù)班次的運行線路與調(diào)度方案進行重新優(yōu)化；若實時需求被拒絕，該實時需求應被下一班次響應，以此為約束，調(diào)用第1階段模型優(yōu)化后續(xù)班次的運行線路與調(diào)度方案。此時，第2階段調(diào)用第1階段的模型進行優(yōu)化時，發(fā)生了以下變化：1）增加了應被響應的實時需求約束；2）車輛運行成本中增加了因拒絕實時需求引起的懲罰成本，故由式(2)變?yōu)槭?14)：

4 模型求解

混合需求下多車場RFT系統(tǒng)運行線路與調(diào)度協(xié)調(diào)的兩階段模型的求解關鍵是第1階段模型的求解。第2階段則是在第1階段的基礎上，先判斷實時需求能否被接受，然后根據(jù)接受情況重新優(yōu)化線路和調(diào)度方案，仍可按照第1階段算法求解。

第1階段的路徑優(yōu)化問題是典型的NP-hard問題，隨著乘客需求點、車場數(shù)量、車輛數(shù)等的增加，其計算復雜度會顯著增加，不宜采用精確算法進行求解，故本文采用遺傳算法(Genetic Algorithm，GA)求解。

圖2中，適應度函數(shù)為系統(tǒng)總費用的倒數(shù)。編碼方式為自然數(shù)編碼[14]，因每個染色體包括個班次個需求點，每個班次的基因包括虛擬車場、發(fā)出車場、需求點、換乘站、返回車場、虛擬車場，如圖3所示，故每條染色體的長度為+3+1；生成種群時將所有需求點隨機排序后，按序隨機插入虛擬車場?發(fā)出車場，換乘點?返回車場次，重復多次即可得到種群。

圖2 算法流程

交叉時按照交叉率，選擇2個個體進行交叉操作，在2個個體間隨機選擇交叉點，將選中的基因相互交換得到子代。變異時按照變異率，對個體進行變異操作：首先識別變異點，若為需求點，則隨機在[1,]間產(chǎn)生變異基因，執(zhí)行變異；若為車場，則隨機產(chǎn)生[1,]間的變異基因，執(zhí)行變異操作；若為換乘站，則不變異。交叉變異時，為確保染色體的合理性，要刪除重復基因補充缺失基因，還要對交叉和變異的基因進行校對，即當前基因為需求基因時，其前置基因只能為實際車場基因和需求基因等。

圖3 編碼方式

5 算例分析

5.1 參數(shù)說明

設干線公交換乘站坐標為(3.00,3.00)；3個實際車場的坐標分別為1(1.77,4.55)，2(2.04,1.84)和3(4.23,3.82)；預約需求見表1。根據(jù)文獻[9]，參數(shù)分別取值為：max30 min；=30 km/h；1?5分別取每分鐘0.6，0.6，1.2，0.6和1.2元；t取3 s/人；1和2分別取0.4和0.6；設置容量分別為10，15和20人，啟動成本和單位行駛成本分別為5，10和15元/臺和1，1.2和2元/km的車型為1，2和3的車輛各2臺/車場。

表1 乘客預約信息

5.2 預約需求下各車場獨立運行與協(xié)同運行的比較

車場獨立運行時，只需將發(fā)出車場和返回車場均統(tǒng)一為同一車場，調(diào)用兩階段法計算即可。在所設條件下，分別采用協(xié)同運行、獨立運行方式進行運行線路與調(diào)度的優(yōu)化，2種運行方式的結果比較如表2所示。

表2 預約需求下運行結果比較

由表2可知，在預約需求情況下，3個車場協(xié)同運行與獨立運行相比，系統(tǒng)總費用降低了8.6%，平均滿載率增加了8.5%，總運行時間和發(fā)車次數(shù)分別減少了5.7%和2次；而且班次5發(fā)出后，車場P1車型1的數(shù)量為0，班次8返回車場P1后使得班次13能在車場P1發(fā)出1，說明模型能有效地提升車場的發(fā)車能力；獨立運行方式中，車型3僅在車場P1發(fā)出1次，而在協(xié)同運行方式中，3發(fā)出次數(shù)增加至2次，說明協(xié)同運行方式下，增加了大型車利用次數(shù)，平衡了各車型的利用次數(shù)；因此預約需求下3車場協(xié)同運行方式效果顯著。

5.3 混合需求下各車場獨立運行與協(xié)同運行的比較

系統(tǒng)新增的實時需求信息見表3。設拒絕實時需求的懲罰為10元/人，比較多車場獨立運行、協(xié)同運行的兩階段法，運行結果比較如表4所示。

表3 新增的實時需求

表4 混合需求下2種運行方式運行結果比較

由表4可知，混合需求下，協(xié)同運行方式與獨立運行方式相比，系統(tǒng)總費用減低了13%，系統(tǒng)總運行時間減少了12.5%，發(fā)車次數(shù)減少了3次，平均滿載率增加了15.2%，說明在混合需求下，協(xié)同運行方式運行效率優(yōu)于獨立運行方式；比較表2和表4可知，在新增10個實時需求后，協(xié)同運行方式與獨立運行方式相比，系統(tǒng)總費用增加率少5.8%，系統(tǒng)總運行時間增加量少25 min，說明協(xié)同運行方式能更快捷更經(jīng)濟地響應實時需求。

5.4 車型比例對線路與調(diào)度的影響

當乘客需求及其他參數(shù)相同的條件下，各車場車型1數(shù)量均增加50%，車型3數(shù)量均減少50%，總數(shù)18輛不變情況下，分析車型比例變化對運行結果的影響。協(xié)同運行方式、獨立運行方式的優(yōu)化結果比較如表5所示。

由表5可知，改變車輛比例時，相比獨立運行方式，協(xié)同運行方式的系統(tǒng)總費用降低了7.9%，運行時間減少了13.3%，發(fā)車次數(shù)減少了3次，平均滿載率增加了20.8%，因此，在當前需求水平下，小型車比例的增加，能更顯著地增加協(xié)同運行方式的運營效率；對比表4和5，對車型比例進行如上改變，系統(tǒng)總費用在獨立運行方式和協(xié)同運行方式下分別達到了11.2%和5.9%，說明車型比例對系統(tǒng)總費用有顯著影響。

表5 增加車型v1后混合需求下2種運行方式優(yōu)化結果比較

6 結論

1) 研究響應型接駁公交系統(tǒng)多車場的協(xié)同問題，應用虛擬車場處理多車場問題、兩階段法處理混合需求問題，構建混合需求下RFT系統(tǒng)多車場協(xié)同、線路與調(diào)度協(xié)調(diào)的優(yōu)化模型及算法流程。

2) 算例結果表明在乘客需求相同情況下，無論是預約需求還是混合需求下，與多車場獨立運行方式相比，多車場的協(xié)同運行均能顯著增加系統(tǒng)的運營效率；車型比例對系統(tǒng)總費用有顯著影響，多車場協(xié)同運行時，宜適當增加小型車比例。

3) 下一步研究工作應是動態(tài)路網(wǎng)下多車場的協(xié)同問題、線路與調(diào)度的協(xié)調(diào)問題。

[1] DENG L, GAO W, ZHOU W, et al. Optimal design of feeder-bus network related to urban rail line based on transfer system[J]. Procedia-Social and Behavioral Sciences, 2013, 96(2): 2383?2394.

[2] LU Xiaolin, YU Jie, YANG Xianfeng, et al. Flexible feeder transit route design to enhance service accessibility in urban area[J]. Journal of Advanced Transportation, 2016, 50(4): 507?521.

[3] 孫博, 楊春風, 魏明, 等. 考慮乘客個性化出行的需求響應型接駁公交調(diào)度模型[J]. 昆明理工大學學報(自然科學版), 2019, 44(1): 122?126, 137. SUN Bo, YANG Chunfeng, WEI Ming, et al. A demand-responsive feeder bus scheduling model for personalized travel[J]. Journal of Kunming University of Science and Technology (Natural Science), 2019, 44(1): 122?126, 137.

[4] 潘述亮, 盧小林, 鄒難. 靈活型接駁公交路徑優(yōu)化及協(xié)同調(diào)度模型[J]. 吉林大學學報(工學版), 2016, 46(6): 1827?1835. PAN Shuliang, LU Xiaolin, ZOU Nan. Route planning and coordinated scheduling model for flexible feeder transit service[J]. Journal of Jilin University (Engineering and Technology Edition), 2016, 46(6): 1827?1835.

[5] 高煦明. 固定站點需求響應式接駁公交調(diào)度模型研究[D]. 南京: 東南大學, 2015. GAO Xuming. Research on dispatching system of demand-responsive connector with on-demand stations [D]. Nanjing: Southeast University, 2015.

[6] QIU F, SHEN J, ZHANG X, et al. Demi-flexible operating policies to promote the performance of public transit in low-demand areas[J]. Transportation Research Part A: Policy and Practice, 2015, 80: 215?230.

[7] 王正武, 易童翔, 高志波. 響應型接駁公交運行路徑與車輛調(diào)度的協(xié)調(diào)優(yōu)化[J]. 交通科學與工程, 2018, 34(1): 68?73. WANG Zhengwu, YI Tongxiang, GAO Zhibo. Coordinated optimization of running route and vehicle scheduling for responsive feeder transit[J]. Journal of Transport Science and Engineering, 2018, 34(1): 68?73.

[8] 邱豐, 李文權, 沈金星. 可變線路式公交的兩階段車輛調(diào)度模型[J]. 東南大學學報(自然科學版), 2014, 44(5): 1078?1084. QIU Feng, LI Wenquan, SHEN Jinxing. Two-stage model for flex-route transit scheduling[J]. Journal of Southeast University (Natural Science Edition), 2014, 44(5): 1078? 1084.

[9] 王正武, 宋名群. 多換乘點響應型接駁公交運行線路的協(xié)調(diào)優(yōu)化[J]. 中國公路學報, 2019, 32(9): 164?174. WANG Zhengwu, SONG Mingqun. Coordinated optimization of operation routes for responsive feeder transit systems with multiple transfer points[J]. China Journal of Highway and Transport, 2019, 32(9): 164?174.

[10] QIU F, LI W, ZHANG J. A dynamic station strategy to improve the performance of flex-route transit services[J]. Transportation Research Part C: Emerging Technologies, 2014, 48: 229?240.

[11] YU Y, Machemehl R B, XIE C. Demand-responsive transit circulator service network design[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 76: 160?175.

[12] van Engelen M, Cats O, Post H, et al. Enhancing flexible transport services with demand-anticipatory insertion heuristics[J]. Transportation Research Part E: Logistics and Transportation Review, 2018,110: 110?121.

[13] Barma P S, Dutta J, Mukherjee A. A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem[J]. Decision Making: Applications in Management and Engineering, 2019, 2(2): 112?125.

[14] 葛顯龍, 王旭, 鄧蕾. 基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究[J]. 管理工程學報, 2013, 27(3): 60?68. GE Xianlong, WANG Xu, DENG Lei. Research on open and dynamic vehicle routing problem based on joint distribution[J]. Journal of Industrial Engineering/ Engineering Management, 2013, 27(3): 60?68.

[15] 葛顯龍, 許茂增, 王偉鑫. 基于聯(lián)合配送的城市物流配送路徑優(yōu)化[J]. 控制與決策, 2016, 31(3): 503?512. GE Xianlong, XU Maozeng, WANG Weixin. Route optimization of urban logistics in joint distribution[J]. Control and Decision, 2016, 31(3): 503?512.

Coordination research of running lines and vehicle scheduling for multi-depots responsive feeder transit

WANG Zhengwu, LIU Jie, ZOU Wenzhu

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

In order to improve the operational efficiency of Responsive Feeder Transit, an idea of coordinated operation of multi-depots, coordinated dispatching of multiple vehicle types, coordinated design of running lines and scheduling for Responsive Feeder Transit system was proposed. A virtual depot was introduced to convert multi-depot design problem into single-depot design problem. A two-stage method for the mixed demands problem was used to deal with reservation requirements and real-time requirements in stages. The coordination model of vehicle routing and scheduling under reservation demands and its solving algorithm were constructed. Calculation results show that under the same conditions of reserved demand and mixed demand, compared to the independent operation, the total system cost of coordinated operation is reduced by 8.6% and 13% respectively, and that the total vehicle traveling of cooperated operation time is reduced by5.7% and 12.5% respectively. Multi-depots coordinated operation can improve the operational efficiency effectively. When the ratio of small vehicle is increased by 50% and large vehicle is decreased by 50%, the change rate of total system costs of multi-depot coordinated operation and independent operation reached 11.2% and 5.9% respectively. Vehicle ratio has an effective influence on the total system cost.

traffic engineering; coordinated operation; two-stage method; multi-depot; responsive feeder transit

10.19713/j.cnki.43?1423/u.T20190865

U491.1

A

1672 ? 7029(2020)07 ? 1849 ? 08

2019?09?29

國家自然科學基金資助項目(51678075)；湖南創(chuàng)新型省份建設專項經(jīng)費資助項目(2019SK2171)

王正武(1973?)，男，湖南長沙人，教授，博士，從事交通運輸規(guī)劃與管理研究；E?mail：zhengwu.wang@126.com

(編輯 陽麗霞)