基于刷卡数据的民族节日期间公交线网优化

程 刚，张 艳

(1.西藏大学工学院，拉萨 850000; 2.中国铁路青藏集团有限公司，西宁 810000)

地处世界屋脊的拉萨，以独特的藏地人文风情吸引着国内外众多的朝圣者.在高原城市拉萨，公共交通在满足居民出行需求的过程中发挥着重要的作用.在民族宗教节日期间，大量居民集中出行，其核心目的地为布达拉宫—大昭寺区域，出行时间和空间的双重叠加，让本来就公交资源配给不足的高原城市拉萨面临更大的压力.朝圣人群作为该区域的出行主体，其出行需求得不到有效的满足的状况更为凸出，影响了高原城市正常的出行秩序.因此本文考虑民族宗教节日期间高原居民的出行需求，对核心区域的公交线网进行优化，重点满足朝圣人群的出行需求，具有较强的实践性.

民族宗教节日作为藏地文化的典型与精华，在内容和形式上均有别于其他一般节日，与此同时，高原城市稀缺的公共交通资源在满足节日出行需求存在短板.然而，受语言交流和恶劣气候条件的影响，学者们对民族宗教节日期间公交线网的优化问题研究存在不足.因此本文基于公交IC卡刷卡数据和车载GPS数据，分析布达拉宫—大昭寺区域范围内的公交网络薄弱环节，利用图论方法对该地的公交线网进行网络应用优化，最大限度的运用高原来之不易的公共交通资源满足民族宗教节日期间公众的出行需求.

1 公交刷卡数据挖掘

基于公交IC卡信息处理来获取客流信息在公交客流调查中的应用较为广泛，其核心在于对公交IC卡获取的信息进行数据挖掘.陈学武等[1-2]对IC卡数据进行挖掘居民公交出行特征信息，提出了乘客起讫点的推算方法；随着 GPS 等车辆自动定位系统的普及，大多城市都能获得实时公交位置信息，相较于行车计划表能实现对公交车辆的准确定位.通过设计适当的算法，可根据乘客IC卡刷卡数据和车载位置信息设备获得刷卡乘客的上下车站点，为进一步获取公交线网 OD 提供依据.侯现耀等[3]提出了基于IC卡和AVL系统数据的公交乘客上下车站点判别方法，为获取公交刷卡乘客的站点 OD 分布及公交线网 OD 分布提供了依据；秦政等[4]在以往研究的基础上，考虑到同行人员代刷卡行为的情况，改进了下车站点的判断机理；学者们在此项基础上对公交IC卡数据进行了深度挖掘，包括智能付费方式[5-8].

常规公交采用“一票制”的收费模式，即乘客只需上车刷卡，下车不会再次刷卡.本文所述方法涉及到的IC卡数据有：卡号、刷卡时间、线路编号和车辆信息编号.车载GPS系统可记录车辆的实时信息，包括经纬度，运行状态等.要用到的是GPS数据中的车载机编号、线路编号、运行状态、站点编号、记录时间.IC卡数据中，上下车站点是不能直接得到的，只要将GPS数据与IC卡数据进行比较，找到与IC卡数据对应的GPS数据，查出GPS数据中的站点编号，即可知道上车站点，下车站点可根据乘客行为规律进行推算.

1.1 乘客上车站点的识别

在乘客在选择公交出行的过程中，刷卡行为一般发生在公交车进站之后出站之前，但是存在一些非常情况，例如高峰期间，在车辆驶出车站才刷卡，另外也不排除GPS定位延迟，导致刷卡时间在车辆进站之前.秦政提出，利用前后2个站点的进站时间来判断乘客的上车站点[4].

本文采用传统的弹性时间控制，虽然会在一定程度上存在漏判，但较前者数据处理工作大大减少，而且此误差在可接受范围内.

判断上车站点的工作实际上是将刷卡数据与GPS数据进行对应，算法思路为：

1)获取IC卡数据，对数据进行清洗，形成IC卡数据集，并提取卡号、刷卡时间、线路编号和车辆编号.

2)获取车辆GPS数据，对数据进行清洗，形成GPS数据集，并提取车载机编号、线路编号、运行状态、站点编号、进出站时间.

3)分别任意从IC卡数据集中和GPS数据集中提取数据进行条件判定.若满足匹配条件，则记录GPS中的站点编号作为上车站点，并将匹配成功的数据分别从2个数据集中去掉；若不满足匹配条件，则保持IC卡数据不变，改变GPS数据继续进行比较，一直进行至IC卡数据集为空集结束.

采用弹性时间控制方法只要IC卡数据中的刷卡时间和车辆编号与GPS集中的进出站时间和车载机编号都分别对应，即可匹配成功.所以，匹配条件见式(1)：

Ni=Nj&qe-ty≤ts

(1)

式中，Ni为第i条IC卡数据中的车辆编号对应的车辆；Nj为第j条GPS数据中车载机编号对应的车辆；qe为公交车j进站的时间；qo为公交车j的出站时间；保证qe、qo是公交车j在同一站点的进出站时间，两者需满足qo-qe

1.2 下车站点判断

常规公交采用“一票制”的收费模式，只有上车需要刷卡，因此IC卡记录的只有上车的数据，无法直接得到下车站点.但是公交车运行定线定站，居民的出行也有其特点，公交出行在路线的选择上和客流的分布上具有一 定的规律性和稳定性.因此可根据乘客的某些公交出行特性进行下车站点的推导.

在推导之前做如下假设：

1)乘客出行为连续公交出行链，所谓连续公交出行链[9]，即乘客在乘坐两次公交之间不使用其他社会出行工具.

2)乘客若连续乘坐公交车，上一次下车站点距下一次上车站点之间的距离不超过最远可接受步行范围(本文取非固定距离，即相邻车站之间的距离).

3)乘客最后1次乘坐公交车的目的是基于家的出行[10]，即下车站点为第2天上车站点.

若乘客的上车站点数据已经得到，按照乘客出行行为，可将IC卡数据分为二类[7]：第1类为1 d内只刷卡1次的IC卡数据，此类乘客只上车1次，需根据其乘车历史数据进行分析，具有很大不确定性，不做过多研究.第2类刷卡两次及以上的IC卡数据，此类又可分为2类：一是此数据之后此IC卡本日无刷卡行为，称之为最后1次出行；另一种为此数据之后此IC卡还出现刷卡行为的，称之为连续出行.

对于最后1次出行的IC卡数据，若最后1次上车的车站与乘客当天首次出行上车的车站在同一条线路上，则下车车站为此乘客今日首次上车的车站；若最后1次上车的车站同次日首次出行的车站在同一线路上，则下车点为乘客次日出行上车的车站.

对于连续出行的数据，如图1所示，若下一次上车的车站(车站2.2)距此次上车车站(车站1.2)所在线路(线路1)中的最近车站(车站1.6)的距离少于能接受的最大步行距离[8](称为最大步行距离规则)，则可推断乘客在此最近车站(车站1.6)下车.

图1 交叉线路与站点示意图

2 基于刷卡数据的公交网络优化方法

在对公交线网的优化研究方面，已有大量文献提出了不同的优化方法，考虑到不合理的线网调整可能会打破乘客的出行习惯，无法在短时间内适应新的公交网络，调整线路不当会引起乘客满意度降低和公交吸引力下降，本文将关注点放在对已有线网进行应用优化.学者的研究主要不同之处在于优化目标和优化方法的选择.对于优化目标的选择陈彦等[9-12]做出了大量研究，常见优化目标有直达乘客最多、公交公司效益最大等；对于优化手段，主要的研究方法有：图论最短路算法[13-15],整数规划[16]和其他优化模型[12].

大多数已有的刷卡数据挖掘研究，未能将研究结果运用到实际的公交运营管理中，不能验证得出数据的实用性；公交线网优化的研究中，多考虑单一线路，使用的OD数据陈旧或有失准确.本文在前人研究基础上，提出将刷卡数据挖掘得出的OD数据运用到城市公交的优化中.

2.1 线路起终点选择

将扩大样本后的各路公交车的全部上下车车站数据构建成OD表.本文通过在客流需求较大的站点设置起终点，增开相应区间的公交车，达到快速将乘客运离车站到达目的地的目标.

假设研究区域内的所有公交线路共有n个公交站点，i表示第i个出发站点，j表示第j个目标站点，则可构建元素n×n维的OD矩阵：[OiDj]，具体情况如表1所示.

表1 上下车O-D表

从O-D表中能看出交通出行量与吸引量较大的前M个站点,应该在此几点处设置起终点站，则可由此几个站点组成(M2-M)/2条备选线路.

2.2 最佳路径选择

对于(M2-M)/2条备选线路，根据实际的城市道路网，每条线路都有多条可供选择的实际路径，采用图论Dijkstra算法寻求备选线路的最佳走向[11].对于站点间的最佳路径，求解步骤如下：

步骤1采用Dijkstra算法求出公交站点间的最短路径P1，并求出P1上的单位时间客流效益Q(P1)；

步骤2采用Dijkstra算法求出公交站点间的次短路径P2，求出P2上的单位时间客流效益Q(P2)；

步骤3采用Dijkstra算法求出公交站点间的第K短路径PK，求出PK上的单位时间客流效益Q(Pk),直到T(Pk)>Tmax或者无剩余未计算路径时算法终止，令d=k，T(Pk)为公交车在此线路上的行驶时间，Tmax为乘客所能接受的最大乘坐时间；

步骤4令Q(Pm)max=MAX{Q(P1),Q(P2),…,Q(Pd-1)}，则最大单位时间客流效益对应的路径Pm就是最佳路径.

最大单位时间客流效益[8]的计算方法见式(2)：

(2)

式中，∑M为线路所能运送直达客流量总和；T为公交运行时间；A1为加权公交车票价；A2为转化为时间单位的运营成本(元/min人).根据此算法，分别计算出(M2-M)/2条备选线路的最佳路径.

2.3 换乘比例最小的线路方案

公交路网中选取了M个起终站点，两两组合可形成M/2条双向线路，以直达乘客量最大为优化目标可构建以下0-1规划模型，寻找使乘客换乘最少的线路方案[12].

(3)

式中，F为公交线网总直达客流量；n为线路起终点个数；Mij为起终点为i，j时，线路上的直达客流量(通过表4可计算)；Xij为0-1规划变量，当i和j配对时取1，否则取0.由于线路i—j为双向线路，考虑其两方向的平均流量，所以将表中数据进行修正：将关于对角线对称的2个值改为此2个值的平均值.利用匈牙利算法即可对模型进行求解，利用Matlab最模型进行求解，即可得出增设起终点的方案.

3 布达拉宫—大昭寺区域公交网络优化

拉萨目前运营的有30余条公交线路，其中有多条公交线路在布达拉宫—大昭寺区域经过的站点相同，对于覆盖站点相同的线路，只选择其中的1条作为研究对象.本文研究的公交有1、2、3、7、8、11、13路，因为去掉了路线重复的公交线路，并且没有考虑整个拉萨市全部公交覆盖区域，所以会给算法结果带来一定的影响，最直观的就是同一IC卡的刷卡出现频率降低，结合学者们跟团队以往研究，本文的解决办法是在得到的OD矩阵中乘以误差系数4.3[17-18].

民族节日期间，公众在出行过程中，除刷卡乘车，还有部分为投币付费，依据项目组前期调研的结果，在后续的研究中将刷卡乘车的比例为71%.依据民族节日期间，该区域的公交运营状况，设定公交车的行驶速度相同，均为40 km/h，加上停站上下客时间，换算速度为15 km/h，进而依据两站点间的道路长度，将路段的权重设为公交车的行驶时间.研究区域的路网权重图如图2所示，布达拉宫所在位置用七角星表示.交叉点处的数字为节点编号，相邻节点间线段上的数字为该路段的权重.

图2 路网权重图

在数据清洗后，可用的刷卡数据为原数据的95%，可用的GPS数据为原数据的96.22%.利用前文算法可将IC卡数据与GPS数据进行一一对应，匹配成功的刷卡数据为原数据的91%，按照比例对样本数据进行扩充，最终确定居民选择公交出行的OD矩阵.

将扩大样本后的1、2、3、7、8、11、13路公交车在布达拉宫附近3 km范围内的全部上下车车站数据构建成OD表.布达拉宫附近3 km范围内共有68个公交站，计算各站点之间的OD数据.在全天的非单次刷卡的87 964条数据中，匹配到下车站点的OD对有6 161个，算法成功比例达到了72.7%.

3.1 线路的起终点选择

从O-D表中能看出交通出行量与吸引量较大的几个站点为：国际城西桥站(附近应节点是23)，甲热站(附近应节点是14)，药王山农贸市场站(附近应节点是17)，罗布林卡南站(附近应节点是22)，冲赛康站(附近应节点是21)，鲁固站(附近应节点是27)，具体情况如图3所示.因而在客流量较大的站点设置为起终点站，因考虑新设站点的施工造价以及拉萨市布达拉宫附近公交车站站点布置密度较高，本文探讨在原有站点布置情况下进行起终点设置而不是在道路节点重新设置新的站点为方便描述，使用节点数字代指车站，则备选路径有：23-14，23-17，23-22，23-21，23-27，14-17，14-22，14-21，14-27，17-22，17-21，17-27，22-21，22-27，21-27.

图3 吸引点分布图

3.2 最佳线路选择

以道路权重作为最短路求解的参数，利用前文所提图论Dijkstra算法寻求备选线路的最佳走向.

对于算法涉及的参数A1、A2，本文中A2取值为0.021元/min.A1的计算需要综合拉萨市公交票卡种类、票价等因素.拉萨市的公交卡类型分为老年卡、学生卡、普通卡和优惠卡(包括银联IC卡).老年卡为免费卡，为60岁以上老年人持有使用；学生卡为半价卡，刷卡乘车0.5元/次，为我市12周岁以下学生持有使用；普通卡为实名制卡，刷卡乘车1.0元/次，全体市民群众都可持有使用；银联IC卡和优惠卡刷卡乘车0.8元/次.根据拉萨市公交产业集团 2018年雪顿节期间公交IC卡对账明细，可计算出各卡种刷卡频率的比重，进而可计算出加权票价的金额为0.27元.据此，计算出所有备选线路的最佳路径.

计算出最佳路径结果如下：23-14:23-22-14；23-17:23-15-16-17；23-22:23-22；23-21:23-15-16-17-18-19-20-21；23-27:23-24-27；14-17:14-15-16-17；14-22:14-22；14-21:14-22-23-24-27-28-21；14-27:14-15-16-17-18-19-20-26-27；17-22:17-16-15-23-22；17-21:17-18-19-20-21；17-27:17-18-19-20-26-27；22-21:22-14-15-16-17-18-19-20-21；22-27:22-23-24-27；21-27:21-20-26-27；计算15条最佳路径的直达乘客量，如表2所示.

表2 直达乘客量分布表

网络中选取了6个起终站点，两两组合可形成3条双向线路，以直达乘客量最大为优化目标可构建0-1规划模型，利用匈牙利算法即可对模型进行求解，利用Matlab最模型进行求解.依据求解结果，可获得民族节日期间，公交网络优化的结果，即增设起终点线路方案为23-17,14-21,22-27：最大直达客流量为388/2=194人.最佳的增设线路的方案如表3所示.

表3 增设线路路径方案

使乘客换乘比例最小的线路方案为：增设以国际城西桥站和药王山农贸市场站、甲热站和冲赛康站、罗布林卡南站和鲁固站为起终点站的线路.此优化方案在现有的公交线路基础上对公交始末站设置进行应用优化，可更好的缓解民族节日期间，公众的出行需求，更好的满足布达拉宫—大昭寺区域朝圣人群的出行需求.

4 总结

本文分析了拉萨市布达拉宫—大昭寺区域范围内民族节日期间公交刷卡数据和车载GPS数据，对公众下车站点判定方法，从而得到客流O-D数据，在此基础上，运用Dijkstra算法寻求客流需求大的站点间的备选线路，通过比较备选线路的最大单位时间客流效益选择客流需求大的站点间之间的最优路径，计算车辆按照最优路径行驶所能运送的最大直达客流量，最后用0-1规划求得使直达乘客量最大的线路方案，避免了严格按照最短路径选择线路走向，尽量满足公众的出行需求，最后在已有的线网和路网条件下，增设始末站，无需新设车站和开设新的线路，最大限度的满足节日期间朝圣人群在城市核心区域集中出行的需求，提出的方法简单实用，具有较强的实践性.