基于停靠站选址的响应型接驳公交调度优化

吴典文,彭 宇,田 奇,王正武,姜宁宇

(1.湖南省交通规划勘察设计院有限公司，湖南 长沙 410200；2.长沙理工大学 交通运输工程学院，湖南 长沙 410114；3.汕头市城区公共交通服务所，广东 汕头 515031)

0 引言

在城市边缘地区，居民居住区域较分散，轨道交通和常规公交的覆盖率较低，公共交通设施有限，居民出行起讫点距离公共交通站点距离较远，难以实现居民出行便捷、低成本的“门到门”的服务。响应型接驳公交(Responsive Feeder Transit，RFT)如图1所示，根据乘客预约或实时申请，确定乘客接送时间、分配适宜车型、规划最佳车辆线路及途经停靠站，能为地铁等干线公交提供高效、便捷的接驳服务。根据响应方式的不同，可以分为基于乘客需求点(即乘客上传的上下车位置)的车辆路径优化模型与基于停靠站(即车辆实际停靠位置)选址的车辆路径优化模型对RFT系统路径进行调度优化。基于乘客需求点的车辆路径优化模型是指响应每一位乘客上传的需求点进行停靠服务，而基于停靠站选址的车辆路径优化模型则是对乘客需求点进行整合，确定停靠位置及每个位置服务的乘客，再通过路径优化等方法确定车辆路径与对应的停靠位置等。

图1 系统示意图Figure 1 System diagram

目前，公交停靠站选址的相关研究主要集中于停靠站覆盖率[1-3]、覆盖半径[4-5]、设置间距[6-8]及停靠站选址方法[9-10]，少数研究者探讨了校车、应急公交停靠站设置及路径优化的协调问题[11-12]。高选幸[11]在校车路径优化中分析了停靠站设置的影响，支晓宇[12]在城市轨道交通应急公交线路优化中探讨了驻车点的选址分配问题。响应型接驳公交的相关研究主要集中于车辆路径优化[13-14]，运行路径几乎均是根据乘客需求点来优化的，很少基于停靠站选址来进行车辆路径优化；而且停靠站选址研究中，对乘客出行因素的考虑较为单一，实际上，不同乘客的出行行为特性、出行目的存在差异，会影响到乘客对上车站点的选择，从而影响车辆运营路径。

针对上述不足，本文对基于乘客需求点的车辆路径优化模型进行改进，考虑乘客需求空间分布，基于聚类分析和重心位置法进行停靠站选址，以企业运营成本最小为目标构建车辆路径优化模型并设计模拟退火求解算法，尽量提高RFT系统的乘客服务质量、降低车辆运营成本。

1 基于停靠站选址的路径优化

受到土地利用性质、出行目的、出行方式等因素影响，乘客出行需求在空间上随机散状分布。响应型接驳公交通过两种坐乘模式为乘客提供接驳服务：乘客在自主选择的需求点坐乘和乘客需步行到要求的停靠站坐乘。两种模式的比较如表1所示。由表1可知，为兼顾乘客便利性和运营成本，宜采用小间距停靠站布设策略。

表1 两种坐乘模式的比较Table 1 Comparison of two ride modes坐乘模式在需求点坐乘在停靠站坐乘乘客便利程度便利性高,乘客步行距离短便利性一般,乘客需步行至停靠站,步行约100～300 m运营费用车辆运营费用较高车辆运营费用较低,伴随着乘客步行时间增加车辆运行路径车辆运行距离较长,存在绕行车辆运行距离较短,路径选择较简单路网条件要求路网密度大,否则车辆不能到达路网密度要求一般

本文分停靠站选址与车辆路径优化两步，停靠站的选址又由两步确定：首先根据乘客需求分布采用K-means聚类，在乘客最大步行距离阈值下基于聚类分析对乘客需求点进行空间聚类，确定各聚类簇的质心；然后考虑乘客需求的多样性和差异性，基于重心位置法确定停靠站选址。在停靠站选址确定之后，再由系统对RFT车辆路径进行优化，具体流程如图2所示。

图2 系统流程Figure 2 System flow

1.1 基于K-means的乘客空间聚类

为降低K-means聚类算法中点之间距离的复杂程度，减小孤立点的影响，避免陷入局部最优解，本文在K-means聚类算法中引入Canopy初始聚类方法。聚类算法步骤如图3所示。

图3 乘客空间聚类流程Figure 3 Passenger space clustering process

图3中，L可根据乘客步行距离要求确定，一般为100～300 m。算法终止准则是乘客需求点到聚类中心的距离均小于L、且新质心与原质心的距离小于约定的一个值。

1.2 基于重心位置法的停靠站选址

考虑乘客出行需求的差异性和多样性，本文采用重心位置法[15]确定了各聚类簇对应的停靠站选址。本文考虑乘客年龄、出行目的、支付意愿、违背时间窗等4个影响来运用重心位置法调整聚类簇pi所有乘客位置：

(1)

(2)

1.3 车辆路径模型

根据乘客需求和确定的停靠站选址，系统进行车辆调度，在满足乘客时间窗、车辆容量等约束下，通过车辆路径优化模型，使系统中企业运营成本最小。车辆路径优化时，遵循如下假设：①接驳公交在行驶中按匀速行驶，一个班次服务的线路唯一；②乘客需求均为预约需求；③接驳公交的容量和保有量已知；④接驳公交在停靠站之间以最短路运行，且中途不停车。

根据上述假设，预约需求、固定发车时间下响应型接驳公交发出车型和运行路径的协调优化模型可描述为：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(3)表示所有接驳公交的启动成本和运行成本之和最小；式(4)保证停靠站服务范围的乘客均被响应；式(5)、 式(6)为车辆容量约束； 式(7)为车辆行程时间约束； 式(8)表示车辆单次运行线路长度约束； 式(9)、 式(10)为车辆到达停靠站pj的时间约束。

车辆路径问题可用遗传算法等启发式算法求解，本文选用模拟退火算法(Simulated Annealing，SA)求解基于停靠站的车辆路径问题[14]。模拟退火算法是一种通用的概率算法，常用来搜寻较大空间的最优解，且对于初始值和参数条件要求较低，适用于本文的车辆路径问题。路径优化模型求解模拟退火算法的具体流程见图4。

图4 SA算法求解流程图Figure 4 SA algorithm solution flow chart

2 算例分析

尚双塘地铁站是长沙市轨道交通1号线一期工程的终点站，地处长沙郊区三环外，周边公共交通系统不完善，附近居民分散，出行分布不均匀，符合需求RFT的设置初衷，本文拟以尚双塘地铁站为仿真案例进行研究，设定地铁站点坐标为(0，0)，正东方向为X轴正方向，正北方向为Y轴正方向建立直角坐标系。服务半径是R=4 000 m的圆形区域，接驳车辆的速度为v=30 km/h。设定两种类型的接驳车辆：车型A有8辆、容量为15人/辆、启动成本5元/辆、γA=0.001 5元/m；车型B有5辆、容量为20人/辆、启动成本10元/辆、γB=0.002元/m。L为200 m、Tmax为40 min、Lmax、Lmin分别为10、4 km。随机生成研究时段8:00～9:00内乘客需求90位，乘客需求分布情况如图5、图6所示。

图5 基于停靠站选址的协调调度结果图Figure 5 Coordinated dispatching results based on station location

图6 基于需求点的协调调度结果图Figure 6 Coordination and scheduling results based on demand points

通过改进K-means聚类算法生成了20个聚类簇，基于重心位置法确定的停靠站选址表2所示。

表2 停靠站选址Table 2 Location of stops停靠站编号X坐标Y坐标停靠站编号X坐标Y坐标18781 05011-2 2861 65421 7682 44512-234-2 49031 8972 51613-161-1 06049561 51914-1 015-1 73353 04062315-2 195-2 39462 0811 55416-2 019-1 9557-66396617648-7958-1 5342 081183 022-1 5259-76236219129-3 12110-2882 665201 585-2 147

基于MATLAB编程，应用模拟退火算法求解协调调度模型，设降温速率q为0.9、初始温度T0为1 000、结束温度Tend为0.001、链长N为200。调用模拟退火算法分别应用基于停靠站选址的、基于需求点的车辆协调调度模型获得优化的车辆路径和发出车型(其中基于需求点的协调调度模型与基于停靠站选址的基本相同，只需将停靠站改为需求点)，基于停靠站选址的协调调度结果如表3与图5所示，基于需求点的协调调度结果如表4与图6所示。

表3 基于停靠站选址的协调调度结果表Table 3 Table of coordinated dispatching results based on station location序号发车时刻到达时刻发出车型载客量/人车辆路径18:008:37B170-1-10-8-11-028:108:41B180-7-4-2-3-038:208:56B160-9-16-15-12-048:308:59B190-13-14-19-20-058:409:15B200-17-18-5-6-0注:平均满载率为90%,运行距离为42.84 km,系统总成本为135.86元。

表4 基于需求点的协调调度结果表Table 4 Coordinated dispatching results based on demand points序号发车时刻到达时刻发出车型18:008:40B28:108:49B38:208:58B48:309:07B58:409:18B载客量/人服务的需求点201、42～45、33～37、46～48、28～32、38～39、203、2、4～5、15～18、6～9、10～14、25～271340～41、67～70、64～66、60～631754～59、49～53、82～872071～75、88～90、76～81、19～24注:平均满载率为90%,运行距离为47.62 km,系统总成本为167.84元。

比较表3和表4可知：① 基于停靠站选址的方法，发出车型B5次，乘客的人均坐乘距离476 m/人、人均总成本1.510元/人，平均行驶距离成本0.003 1元/m；② 基于需求点的方法，发出车型B5次，乘客的人均坐乘529 m/人，人均总成本1.865元/人，平均行驶距离成本0.003 5元/m；③ 与基于需求点的方法比较，基于停靠站选址的方法，乘客的人均坐乘距离减少了10%，人均总成本减少了23.5%，平均行驶距离成本减少了11.4%，基于停靠站选址的方法能显著提升系统运行效率。

3 结论

a.运用改进K-means聚类算法和重心位置法进行了停靠站选址研究，并以系统运营成本最小为目标，建立了基于停靠站的RFT协调调度模型。

b.算例表明，基于停靠站选址的协调调度方法能显著降低系统总成本，运行效率提升效果显著。

下阶段的研究应是乘客时空分布影响下的响应型接驳公交协调调度研究，同时具有预约需求、实时需求下的响应型接驳公交协调调度研究。