基于改进轨迹聚类算法的定制公交线路多目标优化方法

1.本发明涉及基于改进轨迹聚类算法的定制公交线路多目标优化方法，属于地理大数据信息挖掘与公共交通系统设计的交叉应用领域。


背景技术：

2.随着城市的规模不断地扩大，职住分离的现象逐渐变得愈发普遍，人们对通勤的便利性、舒适性、快速性的要求不断提高。作为需求响应式公交，定制公交能够向乘客提供一种预订线路和车次的差异化、集约化、高品质的城市公共交通服务模式；作为一种基于互联网的公共交通新模式，定制公交介于常规公交与出租车之间，其推行是吸引更多乘客、减少私家车使用和减少道路交通温室气体排放的主要策略之一。
3.定制公交的线路优化设计是关键，目前国内外很多学者从时空特征出发对其进行了深入的研究，大致可分为以下几方面：(1)基于出行需求空间特征的路径优化问题。陈汐等构建了多区域通勤定制公交线路优化模型并设计两阶段启发式算法进行求解。(2)基于乘客时间特性的路径优化问题。杨明等考虑软时间窗，构建了一个兼顾运营公司和乘客利益、满足多个上下车站点和多车型的定制公交线网优化模型，并采用遗传算法进行求解。(3)基于时空特性的路径优化问题。程仁辉等考虑时空因素，建立了通勤定制公交线路双层规划模型并设计了一种改进的遗传算法。
4.如何选取最优线路，使得系统能够服务和吸纳更多的出行者和出行需求，是决定定制公交系统高效运营的一个关键环节。线路选取合理，能够吸纳更多意向客户选用定制公交作为出行方式，从而提高服务率和上座率，提高定制公交出行系统的服务水平和盈利能力。因此，探索一种科学的考虑并行道路乘客服务率定制公交站点设计方法具有较强的现实意义。
5.现有技术中，郭乃琨等人提出了一种基于时空特征的船舶轨迹密度聚类方法(cn 111582380 a)，计算任意两子轨迹段之间的时空距离，再通过dbscan算法对各子轨迹段进行聚类。计算时间距离考虑了航速信息，能够更加真实地反映不同子轨迹段的时间距离信息，从而提高聚类精度。存在以下缺陷：在进行聚类分析时没有考虑路网限制。
6.马东方等人提出了一种基于轨迹聚类技术的定制公交线路生成方法(cn 114722312a)，通过获取出租车gps轨迹数据，进而计算轨迹相似度，使用dbscan模型对轨迹集进行聚类，并基于多目标优化方法vikor优化dbscan中的eps、minpts参数，最终完成开设线路的提取。存在以下缺陷：dbscan算法对高维数据处理比较困难，对于密度不均匀的样本处理质量差。
7.邹志云等人提出了一种夜间定制公交的站点确定及线路优化方法(cn 115587657a)，考虑了定制公交的服务水平，兼顾乘客出行时间价值成本和公交运营成本。首先获取每个目的地的位置及乘客人数；采用dbscan算法对目的地散点进行聚类分析，得出若干个离散点和簇类；将离散点作为单独的站点设置，其他簇类采用改进的k-means算法求取聚类中心；调整确定站点,构建多线路动态规划模型，最终确定路线。存在以下缺陷：对
点进行聚类分析，缺少对拓扑结构的考虑；k-means算法对k值和噪声点敏感。
8.现有方法或发明的缺陷：
9.1)目前研究多数通过聚类的方式将相近的起终点划分为一类进行分析，可能会导致所得的最优线路缺乏灵活性，在一定程度上会降低定制公交服务的吸引力。
10.2)目前研究多选取最短路径作为定制公交线路，对相邻道路的存量空间在一定程度上有所忽视，对此范围的意向乘客考虑欠佳。
11.3)目前定制公交线路优化研究主要针对静态出行需求场景，处理的多是静态乘车请求，对于实时的动态乘车请求的研究较少。


技术实现要素：

12.定制公交适合在传统公交线路覆盖不全、城市半径较大；城市路网密度较高，有较多的公交专用道或快速路；城市人口密度较大，通勤需求大的城市开设。针对现有定制公交线路规划对意向乘客服务率有较大提高空间这一问题，本发明提出了一种基于改进轨迹聚类算法的定制公交线路多目标优化方法，该方法结合轨迹相似性分析，将轨迹聚类用于定制公交最短路径选取范畴，可以优化现有定制公交线路绕行远、耗时长和上座率低等问题，得到更加符合用户需求的合乘轨迹。有助于吸引更多乘客，提高公共交通系统满意度，缩短通勤时长，提高出行幸福感，减缓人们购买使用小汽车的需求，实现绿色出行的新型交通模式。
13.为了达到上述效果，本发明采用如下技术方案：
14.基于改进轨迹聚类算法的定制公交线路多目标优化方法，步骤如下：
15.第一步：数据采集及处理：采集现有乘客出行数据，从中提取或转化所需出行信息，包括出行起终点坐标及编号、出行距离、出发时间、要求到达时间等；采集城市矢量地图和路网数据作为地图数据集，并进行路网图结构的储存、创建网络图。
16.第二步：k条最短路选取：基于第一步提取的出行信息数据，采用a*算法寻找每一起终点(od)对之间的最短k条路径，要求绕行距离占比不超过乘客接受的绕行距离占最短路长度的百分比。结合最短路长度、公交车自由流状态下的运行速度、乘客候车时间容忍阈值，得到乘客接受的绕行距离占最短路长度的百分比。k取值为指定od对之间线路长度不超过最短路的绕行百分比的线路数量。
17.k值的选取采用以下公式：
[0018][0019]
其中，path length为od对之间线路长度，percentage为乘客接受的绕行距离占最短路长度的百分比，shortestpath length为最短路长度。
[0020]
第三步：k/2条最短路提取：利用第二步生成的k条最短路，基于longest common subsequence(lcss)最长公共子序列算法计算轨迹间的相似度，筛选得到od对之间相似度最低的k/2条最短路。具体步骤如下：
[0021]
s3.1:相似度比较：提取k条最短路中的最短路径并定义为轨迹a＝[a1,a2,...,am]，其余k-1条路径定义为bi＝[b
i1
,b
i2
,...,b
in
]，整数i取值范围为[1,k-1]。以a为基准，以lcss的方法进行相似度分析，如下：
[0022][0023]
其中，m，n代表轨迹a，b的轨迹点数，δ为整数阈值，ε为距离阈值，head(a)为轨迹a的第一个轨迹点，rest(a)为轨迹a的剩余所有轨迹点。
[0024]
s3.2:低相似度路径选取：对步骤s3.1获得的相似度进行归一化处理，即可获得相似度的百分比，选取最短路1条及与其最不相似轨迹k/2-1条合计k/2条为备选时空路径。
[0025]
第四步，轨迹聚类：利用第三步选取的所有最短路，基于quickbundles(qb)快速捆绑算法进行轨迹聚类，选取最少乘客数量，使聚类后的簇内至少包含与最少乘客数量相等的路径数量，得到合乘线路。具体实施步骤如下。
[0026]
s4.1:求取备选时空路径属性：根据轨迹点编码读取经纬度，按照规定速度算得每段路耗时，进行时间累加并转换为标准时间戳，从而获得每条轨迹的备选时空路径，即每位乘客所经过点的经度、纬度、时间戳。
[0027]
s4.2：划分区域：根据od点预先划分可合乘区域：获取轨迹起终点的经纬度信息，以此为轴线，选取有子轨迹被包含于延轴线垂直方向距离为ver_dis的范围内的完整轨迹作为聚类子区域。根据“超过95％的乘客可忍受等待时间为5分钟以上”的统计规律，结合当地公交车自由流状态下的运行速度speed(km/h)，ver_dis取值定义如下：
[0028]
ver_dis＝speed*5/60
[0029]
同时，计算可合乘区域中所有完整轨迹间基于lcss算法的轨迹相似度矩阵，取轨迹相似度矩阵平均值作为聚类子区域的轨迹相似度similarity。
[0030]
s4.3：采用基于最小平均直接翻转距离mdf距离的轨迹距离度量：定义轨迹s＝[s1，s2，...，s
p
]、t＝[t1，t2，...，t
p
]和翻转版本sf＝[s
p
，s
p-1
，...，s1]、tf＝[t
p
，t
p-1
，...，t]，此时，直接距离d
direct
(s，t)、翻转距离d
flipped
(s，t)、mdf距离mdf(s，t)计算如下：
[0031][0032]dflipped
(s，t)＝d(s，tf)＝d(sf，t)
[0033]
mdf(s，t)＝min(d
direct
(s，t)，d
flipped
(s，t))
[0034]
其中，|s
x-t
x
|表示两个经纬度点s
x
和t
x
之间的距离，直接距离d
direct
(s，t)是指两条轨迹s和t对应点之间距离的均值。只有当两条轨迹具有相同的轨迹点数量时，才可以使用mdf距离进行计算。基于此，选取最短路轨迹点数量作为轨迹点数量，若轨迹点数量少于最短路轨迹点，则使用md距离计算两点轨迹之间距离，即通过简单的线性插值算法，使得任意两条轨迹具有相同的数量轨迹点数量，再采用mdf距离进行计算。
[0035]
s4.4：算法实现：
[0036]
定制公交在线路优化是通常会选取上座率作为优化目标之一。簇内最小数量num_min，即最少乘客数量，由下面公式计算得出：
[0037]
num_min＝num_pass*att_rate
[0038]
定义，其中num_pass为公交公司车型核载人数，att_rate为上座率阈值。如果簇内轨迹数量达到簇内最小数量，则可将其定为定制公交规划线路。
[0039]
根据空间阈值确定公式：
[0040][0041][0042]
其中，threshold_dis为空间阈值，n是所有轨迹的数量，为轨迹pi与其第m条最近轨迹之间的mdf距离，am为所有的平均值。m值可根据公交公司车型核载人数num_pass及上座率阈值确定。
[0043]
根据时间阈值确定公式：
[0044]
threshold_time＝θ*threshold_dis/speed
[0045]
其中，threshold_time为时间阈值，speed为车辆平均速度，θ为时间调整参数，可根据实际情况选取合适值。
[0046]
定义nb_points为最短路轨迹点数量，将其作为轨迹聚类取点数。按照轨迹长度排序，优先选取较长轨迹作为cluster[i]中的合乘轨迹之一。计算可合乘区域内轨迹之间的时空距离。如果计算得到两个轨迹之间的时空距离小于空间阈值和时间阈值，将此轨迹添加到聚类cluster[i]中，否则创建一个新的cluster[i+1]，如此循环，直至遍历所有轨迹，同时进行聚类个数和簇内轨迹数量的统计。
[0047]
本发明的有益效果：
[0048]
与现有技术相比，本发明公开提供的基于改进轨迹聚类算法的定制公交线路多目标优化方法，具有以下优点：
[0049]
(1)针对意向乘客服务率有较大的提升空间的问题，本发明采用的轨迹聚类充分考虑路网实际拓扑邻接结构，在实际定制公交线路优化方面，以吸纳人数为标准，对并行线路的高相似度进行轨迹聚类，可将相邻道路的意向乘客纳入服务，从而提高服务率；
[0050]
(2)针对出行者出行需求的实时便利和定制公交运营成本之间的博弈，本发明建立了考虑运营线路长度、意向乘客服务率、服务范围的多目标优化模型，有助于实现通勤效率和空间通勤成本整体最优；
[0051]
(3)针对乘客不断新增的动态出行需求，本发明采用的a*算法在降低时间复杂度的同时也适用于大型路网，有助于解决乘客临时出行需求，扩大服务范围；
[0052]
(4)针对相同od对之间轨迹相似度不同计算方法之间的差异，本发明采用的lcss算法可以处理仅在平行路段具有一定差异的两个序列的相似性，且很好地解决对噪声点敏感的问题，更加鲁棒，可以使定制公交线路在订单需求变化不大时线路更加固定，可以稳定的提供服务，吸纳周边潜在用户；
[0053]
(5)针对乘客临时出行需求可能无法被及时相应的问题，本发明采用的qb算法相对其他聚类算法速度更快、效率更高，以满足定制公交线路规划的实时响应。
附图说明
[0054]
图1为本发明提供的基于改进轨迹聚类算法的定制公交线路多目标优化方法实施流程图；
[0055]
图2为本发明实施例中已有站点(字母标号)和未被相应的需求点(数字标号)；
[0056]
图3为本发明实施例中提供的k/2条最短路位置计算结果图；
[0057]
图4为本发明实施例中可合乘区域示意图(区域宽度为5km，字母标号轨迹可纳入该可合乘区域，数字标号不可纳入)；
[0058]
图5为本发明实施例中提供的两对od之间的多条时空备选路径图(线条虚实表示不同od对)；
[0059]
图6为本发明实施例中选取的最短路聚类结果，选取该路径作为定制公交轨迹聚类优化线路。
具体实施方式
[0060]
以下结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，所描述的实施例仅是本发明一部分实施例，并非全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0061]
参见图1，本发明实施例公开了一种基于改进轨迹聚类算法的定制公交线路多目标优化方法，具体包括以下步骤：
[0062]
第一步，数据采集及处理：本实施例采用定制公交乘客出行数据作为本实施例的需求数据样本集；采集城市矢量地图和路网数据作为地图数据集。提取或计算出行需求信息，包括出行起终点坐标、出发时间、要求到达时间，并进行路网图结构的储存、创建网络图。
[0063]
第二步，k条最短路提取：
[0064]
在满足绕行距离不超过最短路的10％的前提下(根据数据统计显示，乘客接受的绕行距离占最短路长度的百分比一般取值为10％)，各od对之间计算得到的k条最短路条数，部分乘客出行需求k条最短路提取数据如表1所示。
[0065]
od对id为2-8的起终点可作为图2中已有站点(字母标号)和od对id为1的起终点可作为图2中未被响应的需求点(数字标号)。
[0066]
表1部分乘客出行需求k条最短路提取数据
[0067][0068]
第三步，低相似度最短路预先选取：
[0069]
基于lcss算法进行相似度计算并对相似度进行归一化处理，即可获得相似度的百分比，选取最短路及与其最不相似轨迹合计k/2条为备选时空路径。表2为部分轨迹相似度计算数据示例，其中线路1为起止点(10564194286，668475129)之间的最短路，其余线路为应用lcss算法计算得到的其余路线与最短路之间的相似度。表3为低相似度轨迹提取后的备选时空路径编号数据，其中k/2为向下取整计算。
[0070]
起止点(10564194286，668475129)之间的备选时空路径可表示为图3中起终点ab之间的k/2条最短路。
[0071]
表2部分轨迹相似度计算数据
[0072][0073]
表3低相似度轨迹提取后的轨迹编号数据
[0074][0075]
第四步，基于quickbundles算法的轨迹聚类：
[0076]
通过提取低相似度路径属性，划分区域，mdf距离计算，确定ver_dis＝2.5km，threshold
dis
＝1.65km，threshold_time＝500s,num_min＝32*80％＝26。
[0077]
可合乘区域可由图4表示，其中起止点ab作为较长轨迹被优先选取作为cluster[i]中的合乘轨迹之一，取ver_dis＝2.5km，od对pq、mn、12有子轨迹在ab的可合乘区域内，od对3和4不在ab的可合乘区域内。计算可合乘区域内轨迹之间的时空距离，
[0078]
时空备选路径图可由图5表示，od对ab之间的时空备选路径如实线所示，od对12之间的时空备选路径如虚线所示。
[0079]
根据threshold
dis
＝1.65km，threshold_time＝500s,num_min＝26，图6可解释为od对12的一条轨迹满足上述要求，可经过轨迹聚类后纳入od对ab的簇内，即可选取图示路径作为定制公交轨迹聚类优化线路。
[0080]
部分乘客出行需求轨迹聚类结果数据如表4所示，可显示未被纳入服务的乘客获得服务的优化结果。以(8581973713，377951112)、(4609591245，377951112)、(1873269659，4897757764)为例，对轨迹聚类结果进行分析。在采用点聚类的传统思路进行定制公交线路优化时，(8581973713，377951112)未被纳入服务。当采用轨迹聚类的方法进行线路优化时，由于此od对之间的备选时空路径与(4609591245，377951112)、(1873269659，4897757764)在轨迹聚类时满足相应的时空阈值，可纳入同一条路线，实现服务率最高的优化目标。
[0081]
表4部分乘客出行需求轨迹聚类结果数据
[0082]

技术特征：
1.基于改进轨迹聚类算法的定制公交线路多目标优化方法，其特征在于，步骤如下：第一步：数据采集及处理：采集现有乘客出行数据，从中提取或转化所需出行信息，包括出行起终点坐标及编号、出行距离、出发时间和要求到达时间；采集城市矢量地图和路网数据作为地图数据集，并进行路网图结构的储存、创建网络图；第二步：k条最短路选取：基于第一步提取的出行信息数据，采用a*算法寻找每一起终点od对之间的最短k条路径，要求绕行距离占比不超过乘客接受的绕行距离占最短路长度的百分比；结合最短路长度、公交车自由流状态下的运行速度、乘客候车时间容忍阈值，得到乘客接受的绕行距离占最短路长度的百分比；k取值为指定od对之间线路长度不超过最短路的绕行百分比的线路数量；k值的选取采用以下公式：其中，path length为od对之间线路长度，percentage为乘客接受的绕行距离占最短路长度的百分比，shortest path length为最短路长度；第三步：k/2条最短路提取：利用第二步生成的k条最短路，基于lcss最长公共子序列算法计算轨迹间的相似度，筛选得到od对之间相似度最低的k/2条最短路；具体步骤如下：s3.1:相似度比较：提取k条最短路中的最短路径并定义为轨迹a＝[a1,a2,...,a
m
]，其余k-1条路径定义为b
i
＝[b
i1
,b
i2
,...,b
in
]，整数i取值范围为[1,k-1]；以a为基准，以lcss的方法进行相似度分析，如下：其中，m，n代表轨迹a，b的轨迹点数，δ为整数阈值，ε为距离阈值，head(a)为轨迹a的第一个轨迹点，rest(a)为轨迹a的剩余所有轨迹点；s3.2:低相似度路径选取：对步骤s3.1获得的相似度进行归一化处理，即可获得相似度的百分比，选取最短路1条及与其最不相似轨迹k/2-1条合计k/2条为备选时空路径；第四步，轨迹聚类：利用第三步选取的所有最短路，基于qb快速捆绑算法进行轨迹聚类，选取最少乘客数量，使聚类后的簇内至少包含与最少乘客数量相等的路径数量，得到合乘线路；具体实施步骤如下；s4.1:求取备选时空路径属性：根据轨迹点编码读取经纬度，按照规定速度算得每段路耗时，进行时间累加并转换为标准时间戳，从而获得每条轨迹的备选时空路径，即每位乘客所经过点的经度、纬度、时间戳；s4.2:划分区域：根据od点预先划分可合乘区域：获取轨迹起终点的经纬度信息，以此为轴线，选取有子轨迹被包含于延轴线垂直方向距离为ver_dis的范围内的完整轨迹作为聚类子区域；根据“超过95％的乘客可忍受等待时间为5分钟以上”的统计规律，结合当地公交车自由流状态下的运行速度speed，ver_dis取值定义如下：ver_dis＝speed*5/60
同时，计算可合乘区域中所有完整轨迹间基于lcss算法的轨迹相似度矩阵，取轨迹相似度矩阵平均值作为聚类子区域的轨迹相似度similarity；s4.3:采用基于最小平均直接翻转距离mdf距离的轨迹距离度量：定义轨迹s＝[s1，s2，...，s
p
]、t＝[t1，t2，...，t
p
]和翻转版本s
f
＝[s
p
，s
p-1
，...，s1]、t
f
＝[t
p
，t
p-1
，...，t]，此时，直接距离d
direct
(s，t)、翻转距离d
flipped
(s，t)、mdf距离mdf(s，t)计算如下：d
flipped
(s，t)＝d(s，t
f
)＝d(s
f
，t)mdf(s，t)＝min(d
direct
(s，t)，d
flipped
(s，t))其中，|s
x-t
x
|表示两个经纬度点s
x
和t
x
之间的距离，直接距离d
direct
(s，t)是指两条轨迹s和t对应点之间距离的均值；只有当两条轨迹具有相同的轨迹点数量时，才使用mdf距离进行计算；基于此，选取最短路轨迹点数量作为轨迹点数量，若轨迹点数量少于最短路轨迹点，则使用md距离计算两点轨迹之间距离，即通过线性插值算法，使得任意两条轨迹具有相同的数量轨迹点数量，再采用mdf距离进行计算；s4.4：算法实现：定制公交在线路优化是通常会选取上座率作为优化目标之一；簇内最小数量num_min，即最少乘客数量，由下面公式计算得出：num_min＝num_pass*att_rate定义，其中num_pass为公交公司车型核载人数，att_rate为上座率阈值；如果簇内轨迹数量达到簇内最小数量，则将其定为定制公交规划线路；根据空间阈值确定公式：根据空间阈值确定公式：其中，threshold_dis为空间阈值，n是所有轨迹的数量，为轨迹p
i
与其第m条最近轨迹之间的mdf距离，a
m
为所有的平均值；m值可根据公交公司车型核载人数num_pass及上座率阈值确定；根据时间阈值确定公式：threshold_time＝θ*threshold_dis/speed其中，threshold_time为时间阈值，speed为车辆平均速度，θ为时间调整参数，可根据实际情况选取合适值；定义nb_points为最短路轨迹点数量，将其作为轨迹聚类取点数；按照轨迹长度排序，优先选取较长轨迹作为cluster[i]中的合乘轨迹之一；计算可合乘区域内轨迹之间的时空距离；如果计算得到两个轨迹之间的时空距离小于空间阈值和时间阈值，将此轨迹添加到
聚类cluster[i]中，否则创建一个新的cluster[i+1]，如此循环，直至遍历所有轨迹，同时进行聚类个数和簇内轨迹数量的统计。

技术总结
本发明公开一种基于改进轨迹聚类算法的定制公交线路多目标优化方法，通过低相似度路径的预先选取，利用轨迹聚类进行线路优化，能够纳入并服务相邻道路意向用户的需求，从而提高意向乘客服务率。发明提出的优化方法采用启发式算法进行大规模高效k条最短路；充分考虑了路网的邻接拓扑结构，提取k条最短路中低相似度的轨迹，保障平行道路空间意向乘客的需求；利用轨迹聚类进行定制公交的线路优化设计，通过合并并行道路的出行者，增加轨迹的重叠度，提高定制公交上座率、提高性能，本发明可以实现一种绿色出行的新型交通模式，从用户角度考虑，能够更好地实现用户需求，提高定制公交对意向用户的服务率。交对意向用户的服务率。交对意向用户的服务率。


技术研发人员：张云茜 刘锴 陈兴祎 王江波
受保护的技术使用者：大连理工大学
技术研发日：2023.08.08
技术公布日：2023/10/15