王正武，刘杰，邹文竹

多车场响应型接驳公交运行线路与调度的协调研究

王正武，刘杰，邹文竹

(长沙理工大学 交通运输工程学院，湖南 长沙 410114)

为提高响应型接驳公交运行效率，提出响应型接驳公交系统多车场协同运行、多车型协调调度、线路与调度协调设计的思想。引入虚拟车场将多车场设计问题转换为单一车场设计问题；建立混合需求问题的两阶段法来分阶段处理预约需求和实时需求；构建预约需求下车辆路径与调度的协调优化模型及其求解算法。计算结果表明：在给定相同的预约需求和混合需求下，与独立运行相比，协同运行的总费用分别降低了8.6%和13.0%，车辆总运行时间分别减少了5.7%和12.5%；多车场的协同运行有效地提高了运营效率。小型车比例增加50%，大型车比例同时减少50%时，系统总费用的变化率在独立运行和协同运行下分别达到11.2%和5.9%，车型比例对系统总费用具有显著影响。

交通工程；协同运行；两阶段法；多车场；响应型接驳公交

地铁、快速公交等干线公交的低覆盖率导致距干线公交站较远区域的乘客在选择干线公交出行时存在“第一/最后一公里”问题，因此，能有效解决该问题的响应型接驳公交(Responsive Feeder Transit，RFT)逐渐被推广实施。RFT在运行线路与车辆调度方面的研究主要集中于预约需求(当前班次发出之前对当前班次提出的乘坐申请)下考虑乘客等待成本和车辆运行成本等的车辆路径研究[1−3]和车辆路径与调度的协调研究[4]。随着研究的深入，更贴近实际情况的实时需求(当前班次已发出尚未到达需求点之前，对当前班次提出的乘坐申请)被考虑[5−7]。邱丰等[8−9]建立了RFT系统混合需求(同时具有预约需求和实时需求)的两阶段法，较好地解决了混合需求下车辆调度问题、多换乘站车辆路径与调度的协调优化问题。因启发式算法比传统的精确算法寻优能力强、收敛快，现有研究主要采用启发式算法来求解车辆路径与调度问题[10−12]。Barma 等[13−15]分别基于动态分配车场、虚拟车场等方法研究了多车场物流系统的协调调度问题，与传统的分级分区调度相比，多车场的协调调度有效提高了物流系统的运行效率。到目前为止，现有研究主要关注的是车场惟一、且位于换乘站内的RFT系统，实际上，因换乘站的用地限制，换乘站几乎不会建设公交车场，接驳公交需从换乘站外的车场出发并回到车场；同时，接驳公交可能分多个车场停放，需要进行多车场的协调调度。其次，现有研究均忽视了返回车场的优化，然而返回车场的选择对各车场后续班次的运行线路、调度以及系统总成本均有重要影响。最后，现有研究多数仅考虑预约需求，实际上，在车辆运行途中，也有乘客会提出即时乘车申请。针对现有研究的不足，本文以多车场RFT系统为研究对象，同时采用虚拟车场方法、两阶段法来分别处理多车场协调调度问题、混合需求问题，构建混合需求下多车场RFT系统发出车场、发出车型、发车时间、运行线路、返回车场协调优化的两阶段法，从而有效提高RFT系统的运行效率，为RFT系统的推广应用提供有力的技术支持。

1 问题描述

1) 多车场RFT系统存在2种运行方式：独立运行(各车场仅接送各自服务范围内的乘客)、协同运行(协同调度各车场的车辆来接送所有车场服务范围内的乘客)，本文研究RFT系统多车场的协同问题、运行线路与调度的协调问题。

2) 本文引入虚拟车场[14]方法，将多车场中由发出车场−需求点−换乘站−返回车场组成的各车辆的运行线路串联起来，形成一条由虚拟车场、发出车场、需求点、换乘站、返回车场等要素组成的运行线路。虚拟车场的设置要求如下：

虚拟车场是系统中虚拟的惟一车辆停靠地，其位置任选；

虚拟车场与所有实际车场相连，但其间的费用(包括距离、阻抗等)均为0；

实际车场均变为特殊的需求点，但需求均为0；

引入虚拟车场后，乘客将不固定隶属于某个实际车场的服务范围。

3) 本文采用两阶段思想[8−9]处理混合需求，构建混合需求下多车场RFT系统运行线路与调度协调优化的两阶段法，优化流程如图1所示。

图1 两阶段法流程

图1中，第1阶段处理预约需求，即根据预约需求和初始车辆分布，协调优化发出车场、发出车型、发出时间、运行线路和返回车场；第2阶段处理实时需求，按实时需求的位置与当前车辆的距离从小到大的顺序根据判断规则逐一判断是否响应各个实时需求，并根据响应情况优化当前班次的剩余线路和返回车场、后续班次的运行线路和调度方案，不能响应的实时需求则转为预约需求，应被下一班次响应。

2 预约需求下多车场RFT系统运行线路与调度的协调

2.1 基本假设

服务区域内车辆沿各点间最短路行驶且行驶速度恒为；仅考虑在需求点接乘客到换乘站(从换乘站送乘客至需求点为其逆过程)的问题；乘客只能在预约的需求点上车，在换乘站下车；乘客需求一旦被系统响应便不会被取消；所有乘客均在预约上车时间到达需求点，当乘客上车后接驳车辆立即 发车。

2.2 模型构建

协调模型的目标是使由车辆运行费用和乘客等待费用构成的系统总费用最小：

其中，{1,2,…,,…,}为实际车场集合；v为班次发出的车辆；表示车辆类型；r是车型为的车辆总量；=[γsk]×S为班次发出前所有车场的车辆分布矩阵，元素d为班次发出前车场车型的车辆保有量；为车场数，为车型总量；是S列的行向量，其元素d为班次发出前正在行驶的属于车型的车辆数。

式(7)为发车约束，班次能经过车场也即能从车场发出说明车场相应车型的车辆保有量大于0；式(8)~(10)为确保各车型车辆运行数量与车场保有量的约束；式(11)保证所有乘客均被服务；式(12)为车辆容量约束；式(13)为车辆单程最大行驶时间约束。

3 实时需求的响应

3.1 响应规则

将实时需求分为残疾人、老年人等发出的特殊实时需求和其他人发出的一般实时需求，特殊实时需求必须优先响应。一般实时需求则根据规则判别是否响应：按一般实时需求点的位置与当前班次车辆的距离从小到大的顺序依次判断，若采用最节约插入法[9]插入后依然满足最大运行时间约束和车辆容量约束，则接受，否则不接受。不接受的实时需求转为预约需求应被下一班次响应。

3.2 运行线路与调度的再优化

实时需求被响应后，系统将调用第1阶段模型对当前班次的剩余线路及返回车场、后续班次的运行线路与调度方案进行重新优化；若实时需求被拒绝，该实时需求应被下一班次响应，以此为约束，调用第1阶段模型优化后续班次的运行线路与调度方案。此时，第2阶段调用第1阶段的模型进行优化时，发生了以下变化：1）增加了应被响应的实时需求约束；2）车辆运行成本中增加了因拒绝实时需求引起的惩罚成本，故由式(2)变为式(14)：

4 模型求解

混合需求下多车场RFT系统运行线路与调度协调的两阶段模型的求解关键是第1阶段模型的求解。第2阶段则是在第1阶段的基础上，先判断实时需求能否被接受，然后根据接受情况重新优化线路和调度方案，仍可按照第1阶段算法求解。

第1阶段的路径优化问题是典型的NP-hard问题，随着乘客需求点、车场数量、车辆数等的增加，其计算复杂度会显著增加，不宜采用精确算法进行求解，故本文采用遗传算法(Genetic Algorithm，GA)求解。

图2中，适应度函数为系统总费用的倒数。编码方式为自然数编码[14]，因每个染色体包括个班次个需求点，每个班次的基因包括虚拟车场、发出车场、需求点、换乘站、返回车场、虚拟车场，如图3所示，故每条染色体的长度为+3+1；生成种群时将所有需求点随机排序后，按序随机插入虚拟车场−发出车场，换乘点−返回车场次，重复多次即可得到种群。

图2 算法流程

交叉时按照交叉率，选择2个个体进行交叉操作，在2个个体间随机选择交叉点，将选中的基因相互交换得到子代。变异时按照变异率，对个体进行变异操作：首先识别变异点，若为需求点，则随机在[1,]间产生变异基因，执行变异；若为车场，则随机产生[1,]间的变异基因，执行变异操作；若为换乘站，则不变异。交叉变异时，为确保染色体的合理性，要删除重复基因补充缺失基因，还要对交叉和变异的基因进行校对，即当前基因为需求基因时，其前置基因只能为实际车场基因和需求基因等。

图3 编码方式

5 算例分析

5.1 参数说明

设干线公交换乘站坐标为(3.00,3.00)；3个实际车场的坐标分别为1(1.77,4.55)，2(2.04,1.84)和3(4.23,3.82)；预约需求见表1。根据文献[9]，参数分别取值为：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 预约需求下各车场独立运行与协同运行的比较

车场独立运行时，只需将发出车场和返回车场均统一为同一车场，调用两阶段法计算即可。在所设条件下，分别采用协同运行、独立运行方式进行运行线路与调度的优化，2种运行方式的结果比较如表2所示。

表2 预约需求下运行结果比较

由表2可知，在预约需求情况下，3个车场协同运行与独立运行相比，系统总费用降低了8.6%，平均满载率增加了8.5%，总运行时间和发车次数分别减少了5.7%和2次；而且班次5发出后，车场P1车型1的数量为0，班次8返回车场P1后使得班次13能在车场P1发出1，说明模型能有效地提升车场的发车能力；独立运行方式中，车型3仅在车场P1发出1次，而在协同运行方式中，3发出次数增加至2次，说明协同运行方式下，增加了大型车利用次数，平衡了各车型的利用次数；因此预约需求下3车场协同运行方式效果显著。

5.3 混合需求下各车场独立运行与协同运行的比较

系统新增的实时需求信息见表3。设拒绝实时需求的惩罚为10元/人，比较多车场独立运行、协同运行的两阶段法，运行结果比较如表4所示。

表3 新增的实时需求

表4 混合需求下2种运行方式运行结果比较

由表4可知，混合需求下，协同运行方式与独立运行方式相比，系统总费用减低了13%，系统总运行时间减少了12.5%，发车次数减少了3次，平均满载率增加了15.2%，说明在混合需求下，协同运行方式运行效率优于独立运行方式；比较表2和表4可知，在新增10个实时需求后，协同运行方式与独立运行方式相比，系统总费用增加率少5.8%，系统总运行时间增加量少25 min，说明协同运行方式能更快捷更经济地响应实时需求。

5.4 车型比例对线路与调度的影响

当乘客需求及其他参数相同的条件下，各车场车型1数量均增加50%，车型3数量均减少50%，总数18辆不变情况下，分析车型比例变化对运行结果的影响。协同运行方式、独立运行方式的优化结果比较如表5所示。

由表5可知，改变车辆比例时，相比独立运行方式，协同运行方式的系统总费用降低了7.9%，运行时间减少了13.3%，发车次数减少了3次，平均满载率增加了20.8%，因此，在当前需求水平下，小型车比例的增加，能更显著地增加协同运行方式的运营效率；对比表4和5，对车型比例进行如上改变，系统总费用在独立运行方式和协同运行方式下分别达到了11.2%和5.9%，说明车型比例对系统总费用有显著影响。

表5 增加车型v1后混合需求下2种运行方式优化结果比较

6 结论

1) 研究响应型接驳公交系统多车场的协同问题，应用虚拟车场处理多车场问题、两阶段法处理混合需求问题，构建混合需求下RFT系统多车场协同、线路与调度协调的优化模型及算法流程。

2) 算例结果表明在乘客需求相同情况下，无论是预约需求还是混合需求下，与多车场独立运行方式相比，多车场的协同运行均能显著增加系统的运营效率；车型比例对系统总费用有显著影响，多车场协同运行时，宜适当增加小型车比例。

3) 下一步研究工作应是动态路网下多车场的协同问题、线路与调度的协调问题。

[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] 孙博, 杨春风, 魏明, 等. 考虑乘客个性化出行的需求响应型接驳公交调度模型[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] 潘述亮, 卢小林, 邹难. 灵活型接驳公交路径优化及协同调度模型[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] 高煦明. 固定站点需求响应式接驳公交调度模型研究[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] 王正武, 易童翔, 高志波. 响应型接驳公交运行路径与车辆调度的协调优化[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] 邱丰, 李文权, 沈金星. 可变线路式公交的两阶段车辆调度模型[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] 王正武, 宋名群. 多换乘点响应型接驳公交运行线路的协调优化[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] 葛显龙, 王旭, 邓蕾. 基于联合配送的开放式动态车辆路径问题及算法研究[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] 葛显龙, 许茂增, 王伟鑫. 基于联合配送的城市物流配送路径优化[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)；湖南创新型省份建设专项经费资助项目(2019SK2171)

王正武(1973−)，男，湖南长沙人，教授，博士，从事交通运输规划与管理研究；E−mail：zhengwu.wang@126.com

(编辑 阳丽霞)