刘莹
哈尔滨市城乡规划设计研究院 黑龙江省哈尔滨市 150010
摘要：通过收集到的用户信息，共同乘车体现在规划共同乘车站和车辆行驶路线的运营。设置共乘站会导致车辆运行时间的增加，从而影响乘车正点性。合乘站点过少，则会导致资源浪费，无法体现预约公交公益性优势。因此，既要便利乘客出行，使乘客走行距离最小，又要充分考虑合乘站点数量与合乘路径的问题，合理的站点布设就显得尤其重要。
关键词：需求响应式公交；步行距离；DBＳCＡN；软时间窗；
作为传统公交车的有力补充，需求响应式公交的出现为人们提供了解决问题的新思路，它能够即时采集乘客出行需求信息，确定走行路线，提供个性化定制服务。但自需求响应式公交运营以来，步行距离长、候车时间久等问题也日益凸显，极大地影响了乘客的出行体验。
一、合乘站点的布设
1.剔除数据中的噪音点。为了向尽可能多的乘客提供服务，因此在站点布设过程中仅对远离乘客密集区的孤立乘客进行剔除，即去除“噪声点”。对于模拟需求点，为避免模拟点中的极端值影响，应先对模拟数据进行清洗，对于空间二维离散点，采用密度聚类的方法进行数据的先行筛选。在聚类数不可预知的情况下，可利用DEBSCAN算法进行一次聚类。该算法需要确定最小聚类数和最大扫描半径。考虑行人可接受最长行走距离将乘客所能接受的乘车最远步行距离平均值d作为筛选噪声点的主要依据。考虑需求响应式公交的开行要求，一个站点最少向两名乘客提供服务，当一个站点只服务两名乘客时，两个乘客间的最大距离为２d。因此根据DEBSCAN算法的性质，采取的聚类参数为Ｅps＝２d，MinＰts＝４。根据问卷调研数据和相关参考文献，我们d值选定为800。考虑到随着城市交通发展，出行需求不断增加，一个站点服务的乘客过少势必造成资源的浪费。一辆小汽车最多同时能为４名乘客提供出行服务，为了承担更多客流。故在算例中将聚类参数调整为Ｅps＝1600，MinＰts＝４，再去除噪声点后，随着聚类要求的提高，噪声点数量增加。DEBSCAN的参数取决于数据中最稀疏的区域，其他较密较高的区域不受参数趋于严格的影响，因此DBＳCＡN算法对于剔除服务困难的乘客是十分有效的。
2.站点区域划分。对于去除噪声点后的数据集，由于预聚类采用密度聚类原理的DEBSCAN算法，数据集中度较高，一般的聚类算法无法达到良好的聚类效果。针对该问题，采用基于距离聚类的K-ｍeans算法作为进一步聚类的核心指标，该算法将两点距离作为评价相似度的基本指标，可以将密集度较高的数据集进行进一步的簇类划分。K-ｍeans算法特点在于：同一聚类簇内的对象相似度较高，而不同聚类的簇内的对象相似度较小。应用过程中其难点在于初始K值的选取，文中采用K值从１开始逐步增加，直至达到乘客至合乘站点的步行距离满足要求。K值不能无休止的增长，其最大值为簇类乘客数量，当K值等于乘客数量时，意味着每一名乘客的步行距离为０，变成一种“车找人”的模式，这势必会导致停车过于频繁，这种模式适用于乘客密度较低的情形。对于乘客密度较高的区域，为降低过多停站对乘客出行体验和成本带来的影响，可以规定一个站点的最少服务人数pｍin，因此K值上限K*为簇类乘客数／pｍin。因此布设站点前应对簇类乘客密度高低进行区分。一个簇类的乘客密度即该簇类单位面积所含有的乘客数，由于乘客的分布是随机的，不确定的，使用包裹簇类的最小凸多边形作为簇类面积将会使得乘客密度偏小，因此在计算乘客密度时，以包裹簇类的凹多边形作为该簇类的面积。
3.参数优化。对于大规模的数据处理，凭经验手动调整聚类参数K值是不现实的，因此需要采用算法对聚类参数K进行进一步优化计算。采用走行距离和最小为优化目标，采用启发式算法进行大规模求解，具体算法描述如下：（1）按照密度聚类结果，将数据集进行预分类。（2）对于低密度类，无需进行优化直接输出K值即为最优参数。（3）对于高密度类对K赋值并计算各站点距离和Z。（4）若得到Z值小于原有Z值，将新值覆盖原值。（5）改变K值重复（２）～（４）步骤直至最大循环步长结束。对于１区域，K＝３满足要求，聚类结果及站点布设情况如图1所示。
.png)
图1 k＝3时站点布设情况
二、线路的规划
1.具有软时间窗的多车队约束模型。将需求响应式公交的服务模式可抽象为每辆车从起点出发，依次经过各个具有软时间窗的需求点最终到达终点的最短路径规划问题。由于需求点的访问过程必须在规定的时间窗内访问，如早到，则等待至指定时间，并计算等待费用；如晚到，则拒绝服务。因此对该问题进行研究并得到良好的决策结果对于公交运营服务质量的提升有重要意义。在建立模型时的条件约束主要是乘客时间窗约束、车队容量约束。考虑到需求响应式公交的运营特性，文中采用综合成本包括运输成本、等待成本和固定使用成本作为目标函数。在约束条件方面，算法实现过程中，在每一个站点均要考虑：（1）软时间窗（Ｔiｍe Windows）。车辆在整个过程中需要遵守时间规则：当到达指定需求点时，如早到，则等待至指定时间，并计算等待费用；超出时间范围则提前通过客户端告知乘客，对乘客进行票价优惠等补偿。（2）车队（Fleet）。Fleet由Vehicles组成，且对其设置最大数量限制。Fleet的起终点均在发车中心Depot。车队的装载能力统一为Capacity。装载量在任何时刻不得超过装载能力。一般认为Fleet的服务范围为全路网，运行速度v＝60kｍ／h。实际应用过程中，可通过移动端收集乘客的起讫点及到达起讫点的时间窗数据，针对同一个时间窗内的起讫点布设合乘站点。站点布设完毕后，每个站点将具有服务人数、服务时间窗两个属性，即可建立数学模型进行求解。
2.模型建立。假设模拟实验区域内有一个站场中心，n个乘客上车点和对应的m个下车点，对每个乘客，要求将其从上车点送至下车点，所有站点的集合为V。车辆从站场中心出发并最后返回中心，且在文中车库（站场中心）集合K中只有一个元素时，即单车型。每辆车的装载能力已知，每时刻每辆车承载人数不得大于满载人数。到达公交站的时间需满足相应的时间范围约束。期望综合各种因素使得综合成本（包括运输成本、等待成本、固定使用成本）最低。公交车从站场中心出发，服务完乘客后仍需返回站场中心。每次载客人数应满足限制要求。车辆到达公交站点的时间必须在乘客要求的最晚时间前到达（含），同时，先于客户要求的最早到达时间则有等待成本，路上时间为运输成本。从站场中心出发要满足各个点的乘客出行预期需求，同时还要满足车辆自身的承载能力与用户点的软时间窗约束，具体的成本包括运输成本、等待成本和固定使用成本之和作为目标函数。因此，案例中决策变量为每辆车经过各站点的顺序以及到达、出发的时刻。
总之，文中充分考虑了行人走行距离，通过对具有软时间窗的需求点数据进行二次聚类，采用密度聚类算法进行预聚类，将清洗后的精细化数据进行按距离聚类，并将数据集进行分类，采用启发式算法对参数进行优化。对于聚类结果，基于行人走行距离和最短作为约束条件对站点选址进行分析。对于规划好的站点选址建立具有软时间窗的多车队规划模型，并对模型进行求解，最终可以得到优化后车辆走行方案。可以有效地减少行人的步行距离及候车时间，对优化乘客乘车体验，提高车辆上座率，节约公交企业的经营成本具有重要意义。
参考文献：
［1］蔡永平．考虑乘客出行体验的需求响应式公交规划．2018.
［2］陈博文．需求响应式公交乘客出行中心确认方法研究.2019.