基于灰狼优化K-means聚类算法的公交地铁换乘效率评价方法

韩丽东

（苏州高博软件技术职业学院，江苏苏州215163）

近年来，经济的飞速发展与城市化进程的加快使原有的地面交通越来越不能满足居民的日常出行需求，公共交通方式成为了未来交通运输的发展趋势[1-3]。而作为衡量公共交通运行服务水平的指标，换乘服务质量一直都受到广泛关注[4-5]。与此同时，交通智能卡的广泛普及，居民可以凭借智能卡选择任意的公共交通出行，正是因为这样，交通智能卡中记录的数据可以作为用户的基本特征，为交通换乘服务质量的评估提供数据支撑[6-7]。

目前，国内外学者针对公共交通的服务质量评价也开展了一定的研究。文献[8]建立了公交线路网络的优化模型，对现有公交线路进行评价，得到运营商与服务水平的关系，但其结果准确性可以借助智能卡数据来提高。文献[9]采用层次聚类可视化分析方法，将智能卡数据与车站周围信息进行融合，分析各区域的客流特点，但没有指出换乘次数等形式对于服务质量的影响。文献[10]以成都铁路为研究对象，基于差异驱动原理建立了相应的地铁换乘效率模型。文献[11]计及换乘线路及换乘影响因素等条件，采用数据包络分析法构建换乘效率评价模型，但两者都没有针对车站类型给出提升效率建议。

本文借助于智能卡的大数据支持，针对公交与轨道交通换乘的出行方式，提出一种灰狼优化K-means 聚 类 算 法 （Grey Wolf Optimized K-means Clustering Algorithm，GWO-KM）的换乘率评价方法。首先利用交通智能卡采集的用户数据，结合灰狼优化的K-means算法对站点进行分类，分析影响站点换乘效率的因素，并将处理后的数据投入数据包络分析（Data Envelopment Analysis，DEA）模型进行换乘效率的估算。最后，结合某城市的交通枢纽作为实际算例验证所提方法的正确性。

1 灰狼优化的K-means聚类算法

选取距离市中心距离、等区域特点作为聚类分析指标，基于GWO-KM 对轨道主要站点进行轨道站点分类模型搭建完成车站类型划分，为下一步换乘效率评价方法提供分析依据。

1.1 灰狼算法基本数学模型

灰狼优化算法（Grey Wolf Optimizer，GWO）受到自然界中灰狼种群的严格社会等级制度的启发[12]。在进行灰狼算法设计中，按照狩猎能力和社会等级，将灰狼群体依次划分为4 个等级。α、β和γ等级的狼群决定了狩猎行为的方向，而ω狼受到其他等级的狼群完成狩猎行动。也就是说，在整个优化过程中，αβγ狼指导其他ω狼对最优值进行搜索，并且也在一直更新自己的位置。其数学方程式可以表达为：

式中，W为灰狼向量位置，Wp为猎物向量位置，J为两者距离向量，A和C分为距离系数和位置系数，其计算公式如下：

式中，c1、c2为[0,1]的随机数，a为[0,2]的下降值，a值越大，全局搜索能力越强，a值越小，收敛速度越快。

在建立改进聚类算法模型中，选择车站区域特点作为灰狼优化方法中的分群指标。从地理特点考虑，选择距市中心距离k1和建筑数量k2作为分群指标；从区域人口特点考虑，选择登记车辆数量k3和周围人口数量k4作为分群指标，如表1所示。从这两个方面考虑，可以避免进行分群操作时因指标单一化产生的误差，进而提高改进聚类算法的分类精度。

表1 算法分群指标

确定最优位置的数学公式为

1.2 灰狼优化的K-means聚类算法

传统的K-means 算法对站点进行分类时具有收敛速度快，收敛准确度高的特点，但是会因聚类中心的特性影响造成对站点分类结果产生偏差[13]。而灰狼优化算法在全局寻优方面具有一定优势，为了得到更好的聚类效果，故采用灰狼优化算法改进K-means聚类算法[14]。

所提GWO-KM 算法的目标是找到最佳的聚类中心，即在对主要轨道车站进行聚类后每类区域样本数据到该类的聚类中心的距离和最小作为目标函数，其数据表达式如下：

式中，tj为每类聚类的中心位置，vij为站点区域样本数据，K 为聚类分类数目。本文提出的G-KM具体过程如图1所示：

图1 GWO-KM算法流程

2 基于智能卡数据换乘效率评价方法

数据包络分析模型是Chames团队基于“相对效率评价”方法发展形成的一种新的系统分析方法[15-16]。DEA模型是一种基于线性规划的非参数模型，可用于估算生产边界。通过计算决策单元（Decision Making Units，DMUs）的相对效率，并将各DMUs的相对效率进行对比，DEA模型可以确定用于衡量效率的全要素生产率比。DEA的最初模型是CCR模型，通常用来考虑多输入多输出的问题，允许输出和输入按比例扩大或缩小[17]。

交通智能卡中真实记录了几乎所有乘客的途径站点、进出站时间等相关数据，将智能卡数据作为DMU 输入指标，可以使换乘效率模型更加真实可靠，表2 显示智能卡数据的指标。本文选取数据索引中的8 个指标来构建数据集，用于获取评估换乘效率所需数据的选定指标分别为：卡ID，车辆ID，进站ID，出战ID，进站时间，出站时间，换乘次数和日期。

表2 智能卡数据信息

提取的数据被重新计算为DEA 模型的输出变量和输入变量。本文将输出变量设定为换乘次数和运输速率。输入变量则是从智能卡数据和设施数据中采集了8 个与供电相关的因素，即运输时间、运输等待时间、运输距离、门数、地铁线路数、公交线路数、公交车站数以及站区内的公交分配数量。

智能卡系统中出行者可在地铁门或公共汽车上标记他们的智能卡。因此，从地铁到公共汽车记录的时间差包括换乘时间和公共汽车等待时间，而从公共汽车到地铁记录的时间差仅包括换乘时间。本研究以公车至地铁站的平均时差计算各站的换乘时间；平均换乘等待时间按地铁、公交等车时间的平均值计算；地铁等候时间按服务间隔的一半计算；公交候车时间由地铁到公交平均时差减去各站换乘时间计算。其他4 个变量，如地铁线路数量、公交线路数量、公交车站数量和公交分配数量，通过计算出每个车站上下车的旅客使用的设施数量来排除未使用的设施。在8个变量中，相关系数大于0.5 的变量被排除在模型之外。最后，选择5个指标作为输入变量。

假设有j 个中转站作为评价对象，每一个评价对象分别标记为DMU，且每一个DMU有m种的投入指标和n种的产出指标。分别用和表示DMU的投入和产出：

3 实验算例

3.1 实验对象

本文案例选取南方某城市一轨道线路上15个站点作为研究对象，线路长度接近60公里，其中换乘车站7座。自2010年以来，该城市一直在运行基于交通智能卡的自动售检票系统，99%的居民使用智能卡出行，其智能卡数据每天包含1 500万个出行信息实例，对城市交通规划分析有很高的参考价值。将1周5天工作日的早高峰（07:30～09:30）出行数据作为案例实验依据。

3.2 地铁站点分类

不同的站点的辐射区域不同，对所选15个站点的区域特点进行统计，如表3 所示。将指标参数结合GWO-KW 算法对站点样本进行分类，其分类指标要求为辐射区域和换乘距离。

采用“肘部法则”实现样本数据聚类划分。图2可知，基于灰狼算法优化后的K-mean聚类方法较传统K-means算法分类效果更为明显。改进K-means 算法可保证对样本数据处理时始终以最快速度实现聚合分类，避免因局部寻优导致对数据处理时产生冗余运行。

表3 样本数据

图2 两种聚类算法对比示意

GWO-KW算法聚类结果划分为3类，Cluster A=（Z1，Z3，Z6，Z14），此类站点辐射区域大，换乘距离远；Cluster B=（Z5，Z8，Z11，Z13，Z15），此类站点辐射区域较大，换乘距离较远；Cluster A=（Z2，Z4，Z7，Z9，Z10，Z12），此类站点辐射区域较小，换乘距离近。

3.3 换乘效率评价方法分析

选取聚类结果的每一类中客流量较大的3 个站点作为效率评价的案例站点，分别是作为首末站的A 类站点Z1，作为换乘站的B 类站点的Z13，作为中间站的C 类站点Z7。平均换乘时间估计为8 min，中转过程的途中时间和等待时间分别为5 min和3 min。换乘效率是指运输系统根据换乘次数和每个站点的运输速率进行管理的程度。考虑换乘站的绝对值和相对值，设置DEA模型的输出变量，以换乘次数为绝对值变量，以运输速率为相对值变量。表4 显示了Z1、Z13 和Z7，3个站点的输入数据集。

表4 DEA模型输入数据集

图3显示了3个站点的效率和输出变量之间的关系。根据这两个变量的归一化值，得出了换乘出行和换乘率的分布。结果表明，效率得分的趋势似乎与产出变量的大小有直接关系。换乘效率的大小通常随着输出变量的增加而增加。换乘效率通过输出变量权重和输入变量权重之和的比率来估计。因此，效率得分受输出变量大小的影响，换乘效率值通常与换乘次数和运输速度成正比。

图3 换乘效率函数关系

图4 显示了3 个站点的输出变量的松弛比。结果表明，可以提高3 个站点的换乘速率，以提高站点的效率。Z1 站、Z13 站和Z7 站的运输速率松弛率分别为0.131、0.096 和0.141。这说明，Z1、Z13 和Z7 站可分别增加13.1%、9.1%的和14.1%运输速率，以达到最佳换乘效率。

图4 输出变量松弛比

图5 描述了输入变量的松弛率，可以根据松弛比率改变输入变量来提高换乘效率。例如，在3 个车站中，Z1 站的公交线路松弛率估计为0.328，Z13 站的公交线路松弛率估计为0.191，Z7 站的公交线路松弛率估计0.261。需要指出，Z1、Z13和Z7有32.8%、19.1%和26.1%的公交线路应重新布置，以提高各自车站的换乘效率。

图5 输入变量松弛比

综上分析，Z1车站是地铁首末车站，站内换乘环境小，换乘时间长，换乘距离较远，且辐射范围较大，可通过开发专属的公交线路，实现少停靠、快换乘的点对点服务，提高站点换乘效率；Z7车站为中间车站，换乘距离较近，辐射范围较小，客流量较大，可增加换乘指示牌进行换乘疏导；Z13 是地铁换乘站，换乘距离相对较远，辐射区域较大，客流量较大，同样也可以通过增加换乘指示牌来提高换乘效率。

4 结论

本文面向智能城市的方便交通需求，缓解因城市快速发展引起的交通换乘效率低下问题，提出一种基于智能卡与GWO-KM 算法的公交地铁换乘效率评价方法：①基于灰狼算法对K-means聚类算法进行改进，改善因聚类中心特性引起的收敛不稳定问题，提高了聚类效果。②计及地铁站周围社会指标因素对车站进行GWO-KM 算法区域分类，为下一步换乘效率评价方法提供了依据。③对聚类结果的车站进行换乘效率分析，针对性不同车站类型提出了相应的换乘效率建议。

通过对南方某城市公交地铁换乘线路进行实例仿真研究，实验证明换乘效率评价方法的有效性，并针对车站特点提出了公交地铁相应换乘效率的提升建议，为交通从业人员与研究人员对于公共交通的换乘服务质量研究提供了一定的研究见解与方向。