王順，劉杰，姜寧宇，王正武

多換乘站多車場響應(yīng)型接駁公交的協(xié)調(diào)優(yōu)化

王順1，劉杰2，姜寧宇2，王正武2

(1. 長沙市建設(shè)工程質(zhì)量安全監(jiān)督站，湖南 長沙 410016；2. 長沙理工大學(xué) 智能道路與車路協(xié)同湖南省重點實驗室，湖南 長沙 410114)

為提高響應(yīng)型接駁公交系統(tǒng)的運行效率，針對具有多個換乘站、多個車場的響應(yīng)型接駁公交系統(tǒng)，提出了多換乘站多車場協(xié)同運營、車輛路徑與調(diào)度協(xié)調(diào)設(shè)計的思路。同時考慮預(yù)約需求和實時需求，構(gòu)建了響應(yīng)型接駁公交多換乘站多車場地協(xié)同運行車輛路徑與調(diào)度協(xié)調(diào)的二階段模型，設(shè)計了多染色體遺傳算法。計算結(jié)果表明：在給定的混合需求下，與獨立運營相比，協(xié)同運營模式的總費用降低了14.4%，運行時間減少了24.2%，發(fā)車次數(shù)減少了3次；增加小車型占50%時，獨立運營和協(xié)同運營的系統(tǒng)總費用分別降低了7.3%和7.5%。

兩階段法；多車場；多換乘站；響應(yīng)型接駁公交

為解決城市邊緣地區(qū)居民出行的“第一或最后一公里”問題。響應(yīng)型接駁公交(responsive feeder transit，簡稱為RFT)受到了廣泛的關(guān)注[1]。為完善城市的公交系統(tǒng)，推動RFT的實際應(yīng)用，Guo[2]等人通過24 h的運營模擬驗證了低需求量條件下RFT具有的優(yōu)勢。Edwards[3]等人采用客流數(shù)據(jù)確定了RFT的最佳運行時段。Frei[4]等人發(fā)現(xiàn)出行者選擇地鐵出行的同時也傾向于選擇RFT。為更好地契合實際情況，Ghannadpour[5?6]等人提出了考慮多種約束的多目標模型和雙層規(guī)劃模型。Lu[7]等人以車輛總運行時間最小為目標，構(gòu)建了可優(yōu)化發(fā)出車輛數(shù)的調(diào)度模型。Chen[8]等人驗證了RFT系統(tǒng)中徑向網(wǎng)絡(luò)的優(yōu)勢。Rahimi[9]等人根據(jù)經(jīng)驗數(shù)據(jù)與所構(gòu)建連續(xù)模型的關(guān)系，求解了新澤西州公交系統(tǒng)的運行成本。隨著研究的不斷深入，不同的啟發(fā)式算法也應(yīng)用到模型的計算中[10?11]，并構(gòu)建了混合需求下的運行線路優(yōu)化模型[12]，同時探討了分區(qū)協(xié)調(diào)運行模型、同時接送的線路優(yōu)化模型、多換乘站的協(xié)調(diào)優(yōu)化模型[13?15]。但現(xiàn)有研究均為關(guān)注車場單一且位于換乘站的情況，接駁車輛一般從運營公司的停車場出發(fā)，接送乘客，回到停車場。當(dāng)系統(tǒng)服務(wù)范圍較大時，為合理規(guī)劃運行，路徑車輛需分多個車場停放，現(xiàn)有研究很少考慮協(xié)調(diào)運營多個換乘站。因此，本研究擬以多個換乘站、多個車場的RFT系統(tǒng)為研究對象，考慮同時有預(yù)約需求與實時需求時，通過多換乘站多車場的協(xié)調(diào)運行、車輛路徑與調(diào)度的協(xié)調(diào)優(yōu)化，確定系統(tǒng)中所有車輛服務(wù)的換乘站、運行路徑、發(fā)車時刻、發(fā)出車型、返回車場等，提高RFT系統(tǒng)的運行效率。

1 混合需求問題的兩階段法

當(dāng)RFT系統(tǒng)有2個或以上換乘站時，系統(tǒng)將乘客分為2類：①對目標換乘站有特定要求；②目標換乘站為任意換乘站。本研究以第一類情況為例。當(dāng)RFT系統(tǒng)有多個車場時，其運行模式也可分為2類：①各車場獨立運行，各車場僅接或送各自服務(wù)范圍內(nèi)的乘客至目標換乘站；②所有車場協(xié)同運行，各車場之間協(xié)同調(diào)度，服務(wù)整個RFT系統(tǒng)內(nèi)的乘客至目標換乘站。本研究以第二類模式為例，基于虛擬車場法[16]，利用虛擬車場串聯(lián)多條路徑成一條路徑，對該路徑進行協(xié)調(diào)優(yōu)化。多換乘站多車場RFT系統(tǒng)的協(xié)同運行示意如圖1所示。

系統(tǒng)中乘客需求可分為預(yù)約需求(車輛發(fā)出前乘客發(fā)出的乘車申請)和實時需求(車輛發(fā)出后乘客對當(dāng)前班次車輛發(fā)出的乘車申請)，本研究采用兩階段法處理混合需求(同時存在預(yù)約與實時需求)的問題[17]。兩階段處理流程如圖2所示。

從圖2中可以看出，第一階段處理預(yù)約需求時，根據(jù)預(yù)約需求和初始車輛分布，協(xié)調(diào)優(yōu)化目標(換乘站、發(fā)出車場、發(fā)出車型、發(fā)車時刻、運行線路和返回車場)。第二階段處理實時需求時，先建立實時需求的響應(yīng)規(guī)則，再將實時需求分為普通需求和弱勢群體的特殊需求。特殊需求應(yīng)優(yōu)先響應(yīng)，若車輛剩余容量不夠，則立即發(fā)出下一班次車輛進行服務(wù)。一般需求需滿足車輛容量及最大運行時間約束才響應(yīng)，否則拒絕響應(yīng)。根據(jù)響應(yīng)規(guī)則對實時需求響應(yīng)時，先按實時需求的位置與當(dāng)前車輛的距離從小到大排序。根據(jù)判斷規(guī)則，逐一判斷是否響應(yīng)各個實時申請。根據(jù)響應(yīng)情況，優(yōu)化當(dāng)前班次的剩余線路和返回車場、后續(xù)班次的運行線路和調(diào)度方案，若不能響應(yīng)則轉(zhuǎn)為預(yù)約申請，被下一班次響應(yīng)。

圖1 多換乘站多車場響應(yīng)型接駁公交系統(tǒng)協(xié)同運行

圖2 兩階段法流程

2 預(yù)約需求下多換乘站多車場RFT的協(xié)調(diào)優(yōu)化

2.1 基本假設(shè)

假設(shè)多換乘站多車場RFT系統(tǒng)的服務(wù)范圍內(nèi)，乘客需求被系統(tǒng)響應(yīng)后，不會更改或者取消；車輛以恒定的車速沿各點間固定不變的最短路程行駛，乘客上車后車輛立即啟動；乘客在預(yù)約的上車時間到達需求點，并只前往預(yù)約的目標換乘站；同一需求點乘客的時間窗及目標換乘站相同。

2.2 模型構(gòu)建

本研究車輛成本包括車輛啟動成本、車輛運行成本、車輛早到或晚到產(chǎn)生的成本及其他成本。

以車輛成本和乘客等待成本組成系統(tǒng)。成本最小為目標，以車輛容量、最大運行時間等為約束構(gòu)建協(xié)調(diào)優(yōu)化模型：

式(2)為車輛早到或晚到成本的計算式。式(3)為乘客等待成本的計算，乘客等待成本包括車輛晚到時的等車成本1、車輛早到時車內(nèi)乘客等待新乘客的等待成本2與換乘站成本3。式(4)與式(5)分別為2種乘客成本的計算式。式(6)為乘客換乘站成本。式(8)為發(fā)車約束，若x=1，即班次發(fā)出的車輛經(jīng)過車場，則說明該車型車輛能從車場發(fā)出，那么車場相應(yīng)車型的車輛保有量大于0；x=0時，該等式恒成立，表明車場相應(yīng)車型的車輛保有量不小于0。式(9)為車輛數(shù)量約束，任意時刻某車型車輛行駛的數(shù)量與停放在車場的數(shù)量之和為該車型車輛總量。式(10)與式(11)為某車型正在行駛的車輛與停放在停車場的車輛數(shù)量不小于0且不大于該車型車輛總量。式(12)確保所有預(yù)約的乘客均被車輛送至換乘站。式(13)為車輛的容量約束。式(14)為車輛的單程最大運行時間約束。式(15)為乘客的上車過程，車內(nèi)人數(shù)在車輛到達需求點后增加。式(16)為保障車輛路徑的合理性。式(17)表示所有目標換乘站類別的乘客總和為系統(tǒng)收到的乘車申請乘客總量。式(18)表示系統(tǒng)應(yīng)調(diào)度車輛滿足乘客的換乘站目標。式(19)表示同一需求點的所有乘客被同一個班次服務(wù)。

3 預(yù)約需求下協(xié)調(diào)優(yōu)化模型的求解

式(1)～(19)的混合整數(shù)線性規(guī)劃為NP-hard問題。為保證計算速度，本研究采用搜索能力較強且收斂速度快的遺傳算法[17]。因系統(tǒng)中存在多個換乘站，若采用傳統(tǒng)的單鏈遺傳算法，將增大需求點與換乘站之間的不匹配度，會增加非法個體出現(xiàn)的概率。因多染色體遺傳算法的個體含有多條染色體，可以較直觀地表達多車輛的運行路徑，交叉時能避免產(chǎn)生過多的非法解，所以本研究采用多鏈結(jié)構(gòu)的遺傳算法，即多染色體遺傳算法。算法流程如圖3所示。

圖3 計算流程

圖4 編碼方式

4 算例分析

4.1 參數(shù)說明

設(shè)系統(tǒng)中2個換乘站坐標分別為1(1.21, 2.61)、2(3.68, 2.47)；3個停車場的坐標分別為1(1.77, 4.55)、2(2.04, 1.84)、3(4.23, 3.82)；乘客預(yù)約需求及實時需求信息見表1、2，乘客目標換乘站信息見表3，其中目標換乘站o是乘客對換乘站沒有要求。

為便于計算與對比，根據(jù)文獻[13]，15分別取值為0.6元/min、0.6元/min、1.2元/min、0.6 元/min和1.2元/min；1和2分別取值為0.4和0.6；車輛最大運行時間max取值30 min，車輛行駛速度取為30 km/h。初始時刻3個車場均擁有1、2、3型號的車輛各2臺，其中，1容量為10人，啟動成本為5元，單位行駛成本為1元/km；2容量為15人，啟動成本為10元，單位行駛成本為1.5元/km；3容量為20人，啟動成本為15元，單位行駛成本為2元/km。其他費用在1 h的研究時段內(nèi)取25元，實時需求被拒絕的單位懲罰費用為5元/人。設(shè)種群規(guī)模為100，最大迭代次數(shù)為100，交叉概率為0.4，變異概率為0.15，錦標賽個體數(shù)為5。

表1 預(yù)約需求信息

表2 實時需求信息

4.2 運營模式的比較

其他條件不變，按車場協(xié)同運營、獨立運營分別進行協(xié)調(diào)優(yōu)化，優(yōu)化過程如圖5所示，優(yōu)化結(jié)果見表4～6。

表3 乘客目標換乘站信息

圖5 收斂過程

由表4～6可知，與獨立運營模式相比，協(xié)同運營模式的系統(tǒng)總費用減少了14.4%，總運行時間和發(fā)車次數(shù)分別減少了24.2%和3次，平均滿載率增加了13.9%。因此，混合需求下多換乘站系統(tǒng)中，多車場的協(xié)同運營模式優(yōu)于各車場的獨立運行。系統(tǒng)協(xié)同運行時，因為54號實時需求被班次1拒絕插入，54號需求被當(dāng)作班次2的預(yù)約需求進行重新優(yōu)化。54號需求點3位乘客加入，班次2發(fā)車車型也由小車型1調(diào)整為2。多車場獨立運行時，分別從車場1、2發(fā)出的班次2，乘車人數(shù)均為10，但因車場1車型的保有量限制，所以2個班次發(fā)出的車型均為2。

表4 多車場協(xié)同運營結(jié)果

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

其他條件不變時，各車場小車型1數(shù)量增加50%，車型3數(shù)量減少50%，車輛總數(shù)仍為18輛，分析車型比例的變化對多換乘站系統(tǒng)運行結(jié)果的影響。車場協(xié)同運營、獨立運營的優(yōu)化過程如圖6所示，協(xié)同運營、獨立運營結(jié)果見表7～9。

表5 多車場獨立運營結(jié)果

表6 運營模式的比較

比較表7、8和表4、5可知，初始時刻各車場小型車1增加，有效解決了因1車型的緊缺導(dǎo)致啟動成本與車輛行駛成本上升的問題。比較表6、9可知，由于啟動成本與行駛成本較低的小型車增加且更合理地利用，獨立運營模式與協(xié)同運營模式的系統(tǒng)總費用分別下降了7.3%、7.5%，運行時間分別減少了7.1%、2%，協(xié)同運營模式的平均滿載率基本不變，而獨立運營模式的平均滿載率上升了6.4%。因此，車型比例的變化對系統(tǒng)產(chǎn)生顯著影響。

圖6 不同車型比例收斂過程

表7 增加車型V1同時減少車型V3后多車場協(xié)同運營結(jié)果

表8 增加車型V1同時減少車型V3后多車場獨立運營結(jié)果

表9 增加車型V1同時減少車型V3后2種運營方式比較

5 結(jié)語

以系統(tǒng)總成本最小為目標，乘客時間窗、車輛容量、最大運行時間等為約束條件，構(gòu)建了預(yù)約需求下多個換乘站、多個車場RFT系統(tǒng)運行路徑與調(diào)度的協(xié)調(diào)優(yōu)化模型，設(shè)計了求解算法。考慮了實時需求，構(gòu)建了混合需求問題的兩階段法。通過算例，得到結(jié)論：

1) 利用該方法，能有效獲取多換乘站、多車場RFT系統(tǒng)的運行路徑和發(fā)車時間，驗證了本模型的有效性。

2) 車場運營模式和車型比例均是系統(tǒng)運行性能的重要影響因素。

后續(xù)研究應(yīng)考慮動態(tài)路網(wǎng)下的協(xié)調(diào)優(yōu)化。

[1] Qiu F,Shen J X,Zhang X C,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.

[2] Guo Q W,Chow J Y J,Schonfeld P.Stochastic dynamic switching in fixed and flexible transit services as market entry-exit real options[J].Transportation Research Part C: Emerging Technologies, 2018, 94: 288?306.

[3] Edwards D, Watkins K. Comparing fixed-route and demand-responsive feeder transit systems in real-world settings[J]. Transportation Research Record: Journal of the Transportation Research Board, 2013, 2352(1): 128? 135.

[4] Frei C,Hyland M,Mahmassani H S.Flexing service schedules: Assessing the potential for demand-adaptive hybrid transit via a stated preference approach[J]. Transportation Research Part C: Emerging Technologies, 2017, 76: 71?89.

[5] Ghannadpour S F,Noori S,Tavakkoli-Moghaddam R,et al. A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application[J]. Applied Soft Computing,2014,14:504?527.

[6] Pan S L,Yu J,Yang X F,et al.Designing a flexible feeder transit system serving irregularly shaped and gated communities: Determining service area and feeder route planning[J]. Journal of Urban Planning and Development, 2015,141(3):04014028.

[7] Lu X L,Yu J,Yang X F,et al.Flexible feeder transit route design to enhance service accessibility in urban area[J]. Journal of Advanced Transportation, 2016, 50(4): 507? 521.

[8] Chen P,Nie Y.Optimal design of demand adaptive paired-line hybrid transit: Case of radial route structure[J]. Transportation Research Part E: Logistics and Transportation Review,2018,110:71?89.

[9] Rahimi M,Amirgholy M,Gonzales E J.System modeling of demand responsive transportation services: Evaluating cost efficiency of service and coordinated taxi usage[J]. Transportation Research Part E:Logistics and Transportation Review,2018,112:66?83.

[10] Shen Y D,Wang S Q.Maximal synchronization of feeder buses to metro using particle swarm optimization[C]// Bio-Inspired Computing--Theories and Applications, 2015: 350?361.DOI:10.1007/978-3-662-49014-3_32.

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

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

[13] 王正武,袁媛,高志波.高自由度響應(yīng)公交分區(qū)路徑與調(diào)度的協(xié)調(diào)優(yōu)化[J].長沙理工大學(xué)學(xué)報(自然科學(xué)版),2018, 15(1):41?48.(WANG Zheng-wu, YUAN Yuan, GAO Zhi-bo.Coordination optimization for partition path and scheduling with high degree of freedom demand response transit[J].Journal of Changsha University of Science & Technology (Natural Science), 2018, 15(1): 41?48. (in Chinese))

[14] 王正武,陳濤,宋名群.同時接送模式下響應(yīng)型接駁公交運行路徑與調(diào)度的協(xié)調(diào)優(yōu)化[J].交通運輸工程學(xué)報, 2019, 19(5): 139?149. (WANG Zheng-wu, CHEN Tao, SONG Ming-qun. Coordinated optimization of operation routes and schedules for responsive feeder transit under simultaneous pick-up and delivery mode[J]. Journal of Traffic and Transportation Engineering, 2019, 19(5): 139?149.(in Chinese))

[15] 宋名群.混合需求下多換乘點響應(yīng)接駁型公交運行線路的協(xié)調(diào)優(yōu)化[D].長沙:長沙理工大學(xué),2019.(SONG Ming-qun. Coordinated optimization of multiple transfer points responsive feeder transit operation route under mixed demand[D]. Changsha: Changsha University of Science & Technology,2019.(in Chinese))

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

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

Coordinated optimization of responsive feeder transit with multiple depot and transfer station

WANG Shun1, LIU Jie2, JIANG Ning-yu2, WANG Zheng-wu2

(1. Changsha Construction Project Quality and Safety Supervision Station, Changsha 410016, China;2. Hunan Key Laboratory of Smart Roadway and Cooperative Vehicle-Infrastructure Systems, Changsha University of Science & Technology, Changsha 410114, China)

In order to improve the operational efficiency of responsive feeder transit, an idea of method for responsive feeder transit system was proposed. Which consists of the coordinated operation of multiple depots and transfer stations, the coordinated design of running routes, and the vehicle scheduling. Considering the mixed demand of reservation and real-time, the two-stage model of responsive feeder transit system was built to coordinate the running routes and vehicle scheduling. The multi- chromosomes genetic algorithm was then designed. The results show that, under the same conditions of mixed demand, the total cost, the running time and the number of departures of the collaborative operation mode is reduced by 14.4%, 24.2%, and 3 times respectively, compared with the independent operation. By increasing the proportion of small vehicle to 50%, the total system cost of the independent operation and the collaborative operation is reduced by 7.3% and 7.5% respectively.

two-stage method; multi-depot; multiple transfer station; responsive feeder transit

U491.1

A

1674 ? 599X(2021)02 ? 0076 ? 09

2020?07?23

國家自然科學(xué)基金(51678075)；湖南省重點領(lǐng)域研發(fā)計劃項目(2019SK2171)

王順(1972?)，男，長沙市建設(shè)工程質(zhì)量安全監(jiān)督站高級工程師。