基于路径拼接模型的路径行程时间估计方法*

李烨焘， 黄敏， 黄春婷， 张小兰

1.中山大学智能工程学院 / 广东省智能交通系统重点实验室，广东 深圳 518107

2.广东工贸职业技术学院，广东 广州 510510

交通管理与控制技术的进步与发展，交通信息采集设备的增加，提高了道路交通信息采集与实时处理的能力。例如，以AVI 系统（电警卡口、RFID设备等）为代表的道路监控系统，对路径行程时间的相关参数进行了直接测量（刘晓波等，2019）。行程时间作为智能交通信息系统服务的重要组成部分，对实现交通流诱导、提高道路服务质量具有重要的意义，在交通政策制定、路径规划等方面具有基础性的作用。

基于车牌识别数据的路径行程时间估计相关的研究按照研究尺度的大小可以分为2个方面：基于路段层面与基于路径层面。基于路段层面的研究思路一般为先对组成路径的单个路段进行行程时间估计，再由路段行程时间得到路径行程时间（刘张雷和史忠科，2010；马闻博，2020；千梦晗，2020）。将路段行程时间的简单叠加来估计路径行驶时间方便快捷，但同时也将带来包括路段行程时间误差的累积以及经过信控交叉口时可能的延误等。基于路径层面的研究将路径作为一个整体，通过把握路径整体特征避免了路段误差的累积，实现对路径行程时间更加精准的估计。李先通等（2022）对路径的空间特征展开研究，考虑路段空间依赖、时序依赖以及粗颗粒度中时间飘移问题，利用卷积神经网络及长短期记忆网络对路径行程时间进行估计；Han et al.（2022）提出多语义模型，考虑了路径长度、交叉口数量及不同驾驶员个体对于路径行程时间的影响；Li et al.（2019）构建了深度生成模型，结合路径的动静态特征给出了路径行程时间分布。此类方法利用数据驱动的方法，结合大数据技术、深度学习模型对行程时间进行估计，十分依赖于给定路径上的出行轨迹的数量是否充足。已有研究（冯轩，2019）给出了稀疏数据下路径行程时间估计的方法，但相关方面文献较少，值得进一步探究。

基于路段层面的路径行程时间估计方法会积累各路段上行程时间估计的误差，造成路径行程时间总体偏差较大；在路径层面整体预测路径行程时间，误差较小，这类方法需要大量长出行轨迹数据的作为支撑，但在实际中由于种种原因，待研究长路径上的出行轨迹数据可能不足。针对此现象，本文利用大量卡口检测数据探究路径可拼接的条件，综合考虑路段与路径层面上进行行程时间估计的优劣，提出用于构建目标路径的路径拼接方案的选择方法，利用此方法对城市道路中长路径行程时间进行估计，以概率分布函数的形式记录各路径的行程时间，再次使用时可直接利用，为后续研究提供数据支撑，具体步骤见图1。

1 路径拼接模型

本文提出一种路径拼接模型，介绍了路径拼接时要满足的条件以及确定拼接方案的方法，在交通状态相近的前提下将不同的短路径行程时间拼接得到待研究的长路径行程时间及其概率。首先根据研究需求选取待研究的目标路径，再根据卡口检测数据计算各子路径所处路网状态，提取目标路径所包含的子路径并计算行程时间，分析子路径所处的交通状态，选取若干满足路径拼接条件的子路径拼接为待研究的目标路径，根据各子路径行程时间计算目标路径行程时间。

路径拼接旨在获取卡口检测数据中未记录到足够车辆出行轨迹的路径的行程时间，利用卡口检测数据中若干有真实车辆出行轨迹覆盖的路径，选取路径中与目标路径重合的部分，在满足一定条件的前提下组合成目标路径。图2（a）为有真实出行轨迹覆盖的路径1～3；图2（b）中所示的目标路径（蓝）为无真实出行轨迹覆盖的路径。为了得到目标路径的出行数据，分别在路径1～3中选取结点O 到A、结点A 到C 以及C 到D 的部分路径，即可在空间上组合成目标路径。再根据不同路径在拼接结点（结点A 和C）处交通状态是否相近确定该拼接方案是否成立。

图2 路径拼接示意图Fig.2 Path splicing

1.1 路径拼接条件

1） 物理约束。物理条件保证了拼接路径在空间上是连续的，用于拼接的两段相邻轨迹Li，Li+1必须有一部分是在空间上重合，即两条轨迹至少有一个共同的结点（拼接结点）。

2） 交通状态约束。交通状态反映了路网交通流运行情况，可依据路径流量与密度判断交通状态通畅与否。路径的行程时间受交通状态影响，假设同一路径的路径路网状态相近时，该路径上的行程时间服从相同的分布。对于相邻的子路径Li，Li+1，要求下游子路径Li+1在其出发的时刻所对应的实时路径路网状态与上游路径Li到达拼接结点时路径Li+1所对应的路径的初始路径路网状态相同。

设满足上述物理条件以及交通状态条件的拼接路径L={L1，L2，L3，…，Lm}中各子路径的行程时间为TLi，则路径L的总行程时间为各子路径的行程时间之和。

1.2 拼接方案选择

选择行程时间误差最小的拼接方案可转为求解行程时间的整体方差最小的优化问题：

使用遗传算法（靳文舟等，2020）求解上述问题，将拼接方案编码为一个0-1 字符串，涉及到n个路段的拼接问题染色体长度为n- 1，每一位用字符0 或1 表示对应相邻路段是否被打断。如图3所示，以目标路径为L'={l1，l2，l3，l4}为例，目标路径由4 个路段组成，则其染色体长度为3，对应4 个路段形成的3 个路口，染色体“101”表示第1 个和第3 个路口不打断，第2 个路口打断，即拼接方案为L'={{l1，l2}，{l3，l4}}.

图3 路径拼接方案编码示意图Fig.3 Example of chromosome composition

适应度代表了染色体存活概率的大小，将适应度函数设置为Fi= -Var(L，L1，L2，…，Lm)，采用“轮盘赌”选择方法确定下一代个体，则方案的整体方差越小染色体被选中的概率越大；染色体交叉过程采用二点交叉法，在两条父代染色体上分别随机抽取长度相等的两条染色体片段并交换；变异过程采用点位变异，随机选择多个基因依照设置的概率在子代染色体上进行变异，由于采用了0-1编码，变异时将基因编码取反即可。

2 路径行程时间估计

2.1 交通状态划分

交通流基本图模型由Greenshields et al.（1935）提出，描述了宏观交通运行过程中流量、密度和速度之间关系。宏观基本图由Daganzo（2007）提出，相较于传统交通流基本图，宏观基本图更关注道路网络层面上交通流3 参数之间的关系和性质。参考传统基本图与宏观基本图，提出介于二者之间的描述路径3参数间关系的路径交通流基本图，用于对路径所处的交通状态进行划分。参考Edie（1963）提出的交通流参数的观测方法，定义路径L的流量：

根据Greenshields 模型中交通流速度与密度存在的正比关系，可以推出流量与密度间存在二次函数关系，利用二次函数拟合路径流量与路径密度之间的关系，图4中绘制了拟合后的曲线。设路径L上流量与密度的关系为：

图4 路径交通流基本图示意图Fig.4 Basic diagram of a path

则临界密度kLm= -( )b2a.根据路径L在时刻t的密度划分其所处的交通状态CL(t)，参考Lin（2019）的密度划分依据，可将CL(t)划分为畅通、基本畅通、拥堵、严重拥堵4类，具体划分方法为

2.2 考虑交通状态的路径行程时间分布

路径行程时间在不同交通状态下会呈现不同分布，分别对路径在不同交通状态下的行程时间分布进行拟合，得到路径L在交通状态CL(t)下的路径行程时间概率密度函数为f(TL，CL)，则行程时间小于Tx的概率

由于出行者对连续变化的时间感知度有限，为了便于后续计算，可以将行程时间分布离散化处理。将行程时间为[)Tx-τ，Tx的概率作为行程时间为Tx的概率，以P(Tx，CL)表示路径L上路径行程时间为Tx的概率，即

其中Tx=hτ，h= 1，2，3，…，Tx单位为s.

2.3 路径行程时间概率

在出发时间已知的情况下，给定目标行程时间，则概率计算步骤：

1）将目标路径分解，选取所有拼接方案中Var 最小的拼接方案，为该方案中各子路径分配行程时间使得各子路径的行程时间之和为给定的目标行程时间；

2）根据子路径的起始时刻所对应的交通状态及相应的概率分布函数，计算各子路径对应行程时间的概率，将每段子路径行程时间概率相乘即得到该时间分配方案下路径行程时间的概率，累加所有时间分配方案的概率，即为目标路径的行程时间为给定值的概率（图5）。

图5 路径行程时间概率计算过程Fig.5 Process of path travel time probability

假设待研究的拼接方案为

3 案例分析

为了验证基于路径拼接的行程时间估计方法可行性及准确性，选取广州市工业大道、南田路、前进路、东晓路及新滘路所围的区域内，于2021 年8 月29 日卡口过车数据进行实例研究。研究区域内共有可观测路口21 个，可观测路段32条，见图6。卡口过车数据记录车辆车牌、所处路段、进入和离开路段的时刻等信息，结合路网拓扑结构提取车辆出行记录。剔除车辆出行轨迹中路径平均速度小于5 km/h 或大于120 km/h 的异常值后，研究区域内单日提取车辆出行20 万余次，单次出行路径长度均值约为2 km，单次出行时间均值为664 s。

图6 研究区域Fig.6 Study area

选取图6 中绿色路径为目标路径，起点A 为南田路与工业大道交叉口，终点B 为昌岗路与东晓路交叉口，该路径长约4.5 km，2021 年8 月29日目标路径上共有真实出行轨迹1 232 条，平均路径行程时间为816.8 s。一天内该路径的行程时间分布如图7所示。

图7 真实轨迹行程时间分布Fig.7 Travel time distribution of real trajectory

3.1 宏观基本图拟合

以目标路径L的拼接方案为例，依据式（1）和（2）计算各子路径Li的流量与密度，并绘制各子路径的路径交通流基本图（图8）。

图8 子路径交通流基本图Fig.8 Basic diagram of sub-paths

绘制目标路径及其子路径的路径交通流基本图并使用二次函数进行拟合，选取确定系数R2以及均方根误差RMSE 表征拟合优度。其中R2∈[0，1]，越接近1 则拟合程度越高；RMSE用于衡量拟合值与真实值之间的偏差；拟合情况见表1。由表1 可知，利用二次函数拟合的结果中R2>0.85，RMSE>10，拟合度较好。

表1 路径交通流基本图拟合情况（部分）Table 1 Fitting of basic diagram of path

3.2 行程时间分布函数拟合

按照式（3）将子路径划分为“畅通”“基本畅通”“拥堵”和“严重拥堵”等4 种交通状态，以子路径L2为例，不同交通状态下子路径行程时间分布情况如图9所示。

图9 不同交通状态下行程时间分布Fig.9 Travel time distributions under different traffic status

分别利用Gamma、Normal 以及Burr 分布对行程时间分布进行拟合，利用残差平方和评价分布拟合效果。残差平方和越小，则拟合效果越好。子路径在不同交通状态下的残差平方和见表2。由表2 可知，Burr分布在各种交通状态下拟合的残差平方和均为最小，因此采用Burr 分布对所有状态下的行程时间分布进行拟合。特别地，若交通状态为“严重拥堵”时的路径行程时间数据量不足时，则认为该路段不存在此状态，在进行路径拼接时不考虑该状态。

表2 子路径在不同交通状态下路径行程时间分布拟合残差平方和Table 2 RSS of travel time distribution of sub routes under different traffic status 10-6

3.3 路径行程时间概率分布

将2021 年8 月29 日8：00 时刻的路径路网状态作为输入，分别计算目标路径上行程时间为0～2 000 s 的概率，得到目标路径行程时间估计值分布。将其与该路径上2021 年8 月29 日8：00～9：00时段内轨迹的行程时间真实值分布进行对比，结果见图10，部分行程时间对应的概率密度与累计概率如表3所示。在此时间段内，真实出行轨迹的行程时间均值为714 s，本方法所得行程时间估计值均值为693 s，误差3.04%。

表3 行程时间真实值与估计值对应累计概率与概率密度Table 3 Cumulative probability and probability density of different travel times

图10 目标路径行程时间真实值与估计值对比Fig.10 Comparison of target path travel time distributions

使用JS 散度（Chen & Liu，2021）进一步判断上述2 种分布的相似性。JS 散度是基于KL 散度提出的一种概率统计方法（Kullback & Leibler，1951），在信息论中广泛应用于定量衡量两个概率分布间的差异性。离散型分布U，V的KL散度为

JS散度取值在0～1之间，相同分布的JS散度为0，JS 散度越大，两个分布间的相似性越小。按照式（4）计算可得目标路段行程时间分布的估计值与实际值的JS散度为0.05，可以认为本文方法得到的行程时间分布与真实行程时间分布的趋势一致，同一行程时间所对应的概率相近。因此，从行程时间均值与分布两方面来看，本方法对行程时间估计的结果可靠，可为后续相关研究提供数据基础。

4 总 结

针对行程时间相关研究中可能出现的路径行程时间数据量不足的问题，本文提出了基于路径拼接模型的路径行程时间估计方法，通过路径拼接模型确定路径拼接方案。使用Burr 分布拟合不同路网状态下的路径行程时间分布，结合路径拼接方案给出目标路径行程时间及其概率分布。该方法计算得到的行程时间与实际行程时间的均值误差较小，所得行程时间分布与实际分布相似，对路径行程时间的估计结果较为准确，可为后续行程时间可靠性、个性化路径推荐等基于路径行程时间的研究提供数据支撑。