基于路口联合建模的对偶图卷积网络的行程时间估计方法

1.本发明涉及道路网络分析技术领域，更具体地，涉及一种基于路口联合建模的对偶图卷积网络的行程时间估计方法。


背景技术：

2.估计给定路径的行程时间在许多城市交通系统中起着重要作用，例如用于导航、路线规划和拼车等。由于交通网络上的路径序列是由依次交替的路段和交叉路口组成，因此表征交叉路口和路段的潜在特征对于道路网络上的行程时间的估计非常重要。通常引入交通信号灯或者其他交通标志引导交通行为的交叉路口对行车速度有显著影响。如何对路口和路段进行联合建模是一个极具挑战的问题。首先，路口和路段之间存在复杂的关系。具体而言，两个相邻的路口之间存在相互影响，并且它们的相关性随着交通状况的变化而变化，例如当一个路口发生交通拥堵时，则这种拥堵状态很可能将传播到邻接的路口。同时，与同一路口相连的路段也是紧密关联的，它们之间的相互作用取决于它们的上游或下游路段。交通流是从上游路段流向下游路段，而路段的拥堵状态则是从下游到上游路段进行反向传播，因此邻接的上下游路段之间也存在很强的相关性。此外，交通网络上所附着的时空属性不仅与小范围的局部交通模式有关，还可能受到大范围区域内的全局交通模式的影响。
3.在现有技术中，有关行程时间估计的方法主要包括基于路段、基于路径和基于深度学习的行程时间估计方法。
4.基于路段的行程时间估计相关的工作主要研究个体路段的行程时间估计。例如，使用支持向量回归来预测路段的行程时间。然而，由于现有基于路段的方法没有考虑路段之间的交叉路口和相关性，因此很难准确预测整条路径的行程时间。基于路径的行程时间估计方法用于解决完整路径行程时间估计问题。例如，基于具有相似来源和目的地的路径具有相似行程时间的假设，通过查找附近的历史轨迹来估计路径的行程时间。然而，这种方法难以有效地捕捉路径沿线交通的复杂时空模式，因此导致准确性较差。
5.基于深度学习的行程时间估计方法能够更好地学习路径相关的复杂时空特征。例如，利用端到端的深度学习框架deeptte来估计路径的行程时间，该模型能够捕捉给定路径的空间和时间的关联特征。然而，该模型没有考虑针对路口和路径的联合建模。
6.综上，现有的大多数工作都侧重于对路段或交叉路口进行单独建模来估计路径的行驶时间，这些工作没有考虑交叉路口和路段的复杂关系，从而不能准确估计行驶时间，这是因为交叉路口和路段作为路径的基本要素，不仅各自包含多样化的空间属性和时间动态，而且它们之间还具备较强的耦合相关性，如没有同时考虑路口和路段的特征，难以在行程时间估计任务中获得更高的准确性。


技术实现要素：

7.本发明的目的是克服上述现有技术的缺陷，提供一种基于路口联合建模的对偶图
卷积网络的行程时间估计方法。该方法包括以下步骤：
8.获取目标路径和对应的出发时间，所述目标路径是道路网络中的一系列路段和路口的序列；
9.针对所述目标路径和对应的出发时间，利用对偶图卷积网络估计行程时间，该对偶图卷积网络以设定的损失函数最小化为目标，利用历史轨迹数据集训练获得；
10.其中，所述对偶图卷积网络包括嵌入层、时空图学习层和多任务学习层，所述时空图学习层通过对节点图和边图进行对偶图卷积捕获时空特征；
11.其中，所述节点图的每个节点和边分别代表一个路口和路段，所述边图的节点是节点图中的对应边。
12.与现有技术相比，本发明的优点在于，提出一种新颖的端到端深度学习模型框架，即面向行程时间估计的对偶图卷积网络，用于对交叉路口和路段进行联合建模。所提供的模型采用对偶图卷积方法来捕获路口和路段的复杂关系，其中构建节点图用于刻画路口之间的相关性，构建边图来表征路段之间的交互特征。此外，为捕捉空间和时间特征的联合关系，还引入一种在捕捉时间依赖性的同时结合从多个邻域范围内整合多尺度空间关系的时空学习模块。
13.通过以下参照附图对本发明的示例性实施例的详细描述，本发明的其它特征及其优点将会变得清楚。
附图说明
14.被结合在说明书中并构成说明书的一部分的附图示出了本发明的实施例，并且连同其说明一起用于解释本发明的原理。
15.图1是根据本发明一个实施例的基于路口联合建模的对偶图卷积网络的行程时间估计方法的流程图；
16.图2是根据本发明一个实施例的深度学习模型的总体框架图；
17.图3是根据本发明一个实施例的嵌入层的总体框架图；
18.图4是根据本发明一个实施例的时空图学习层的示意图；
19.图5是根据本发明一个实施例的增强的图卷积网络示意图；
20.图6是根据本发明一个实施例的多任务学习层的架构图；
21.图7是根据本发明一个实施例的不同参数组合下的模型性能变化趋势图。
具体实施方式
22.现在将参照附图来详细描述本发明的各种示例性实施例。应注意到：除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、数字表达式和数值不限制本发明的范围。
23.以下对至少一个示例性实施例的描述实际上仅仅是说明性的，决不作为对本发明及其应用或使用的任何限制。
24.对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，所述技术、方法和设备应当被视为说明书的一部分。
25.在这里示出和讨论的所有例子中，任何具体值应被解释为仅仅是示例性的，而不
是作为限制。因此，示例性实施例的其它例子可以具有不同的值。
26.应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步讨论。
27.本发明提出一种创新的基于图卷积神经网络(gcn)的端到端的学习模型框架(或称为dgcn-tte)来估计行程时间。首先，为学习交叉路口和路段的复杂关系，提出一种对偶图卷积架构，该架构不仅考虑了不同路口之间，不同路段之间的相关性，还探索了路口和路段之间的交互模式。进一步，提出了增强型gcn(r-gcn)模块用于整合不同邻域范围内的空间信息，并且将门控循环神经网络(gru)结构与r-gcn整合，在捕获道路网络动态属性的时间相关性的同时结合空间关系来实现时空依赖关联的学习。最后，本发明采用多任务学习的方法同时估计完整路径、每个通行路段和路口的行程时间。
28.参见图1所示，所提供的路口联合建模的对偶图卷积网络的行程时间估计方法包括以下步骤。
29.步骤s110，对路段和路口进行联合建模，以估计给定路径的行程时间。
30.首先，根据以下定义对路段和路口进行联合建模。
31.轨迹：将轨迹y定义为一系列连续的gps观测y＝{y1，y2，...，y
|y|
}，其中每个值都包括位置(即纬度经度和时间戳)。
32.路网：奔放定义路网为有向图g＝(v，e)，其中v和e分别表示节点集和边集。节点v∈v表示路网中的一个交叉路口。边e
i，j
∈e表示连接交叉路口vi和vj的路段。
33.路径：路径p是道路网络中的一系列路段和路口的序列，例如表示为p＝{e
start，1
，v1，e
1，2
，v2，...，e
m-1，end
}。路径可通过路网匹配的方法从原始轨迹数据中获得。
34.任务描述：给定路径p和出发时间td，本发明旨在利用历史轨迹数据集d以及对应的网络g来估计行程时间t
θ
，可以表示为：
[0035][0036]
其中θ＝{p，v
p
，s
p
}表示整条路径及其对应的路段和交点的集合。是用于行程时间估计的函数，即本发明所提出的深度学习模型。
[0037]
步骤s120，采用对偶图卷积网络构建端到端的深度学习模型，其中节点图用于刻画路口之间的相关性，边图用于表征路段之间的交互特征。
[0038]
为行程时间估计联合建模路口和路段是具有挑战性的。首先，路口和路段关系复杂。其次，这种关系中还隐含有多样化的时空特征。此外，这两种特征并不是相互独立的。为了解决这些问题，本发明提出一种新颖的模型，即对偶图卷积网络(dgcn-tte)，该模型包含嵌入层、时空图学习层和多任务学习层，总体框架如图2所示。
[0039]
(1)嵌入层设计
[0040]
良好的路段和路口的初始表示向量(也称为嵌入)对于在模型的其他部分有效学习它们的复杂特征非常重要。一种可行的方式是使用独热编码表示，但该方法生成的数据过于稀疏，无法很好地区分不同路段和路口的特征。为解决这个问题，在一个实施例中，通过整合外部因素(例如，路段的类型和路口的地理空间属性)用于初始化路段和路口的表示向量。特别是对于路口，还可将其相邻路段的信息合并到路口表示向量中。
[0041]
例如，通过将影响路径行程时间的重要因素(如行驶速度、道路类型和行驶距离
等)纳入所提供的模型来初始化路段的表示，如图3所示，具体而言，在时间t的路段的表示可以定义如下：
[0042][0043]
其中se(t)是在时间t的路段平均速度，de是路段的距离，pe是道路类型。we是一个可学习的参数矩阵。[]是一个合并操作运算符。
[0044]
对于路口，由于它们与多个路段相连接，因此它们的表示可通过聚合连接路段的表示来初始化。同时，它们也有其特定的地理空间属性(例如十字路口的红绿灯)。因此，在时间t的路口的表示可以定义为：
[0045][0046]
其中f(v)表示与路口节点v连接的路段集。pv表示路口是否有红绿灯。w1和w2表示可学习的参数矩阵。
[0047]
(2)时空图学习层
[0048]
为解决路口和路段如何联合建模的挑战，本发明首先设计节点和边图卷积用于捕获它们的复杂关系。进一步，为捕获不同尺度的空间特征，提出r-gcn模型用于整合来自多个空间信息尺度的特征。接着，引入了时空学习方法来联合学习它们的时空特征。
[0049]
时空图学习层如图4所示，主要包括对偶图卷积方法、增强型gcn(r-gcn)和时空学习方法，从而实现对路口和路段的联合建模。
[0050]
对偶图卷积：现有的方法利用带有加权图的gcn来学习路段之间的交互，而连接路段的路口由固定标量(例如，加权和)表示，这种方法忽略了路段与其相连的路口之间复杂的相互作用。为学习它们的联合特征，本发明设计了一种对偶图卷积方法来同时建模它们的复杂关系。
[0051]
令g＝(v，e，w)表示节点图，其中每个节点和边分别代表一个路口和路段。g
′
＝(v
′
，e
′
，q)是对应的边图，e
′
则表示边图中新的边，g
′
的节点v
′
是节点图边集合e中的对应边，即v
′
(i
→
j)，(i，j)∈e且|v
′
|＝|e|。w和q分别表征它们相互作用的加权邻接矩阵。
[0052]
在节点图g中，任意两个相邻节点i和j之间的边权重均不相同。直观而言，如果节点i和节点j分别有较大的出度和入度，那么它们代表节点i和节点j之间相关性的边权重很小。因此，边权重w定义如下：
[0053][0054]
其中，deg
+
(i)和deg
+
(j)分别代表节点i和节点j的出度数和入度数。口是节点度数的标准差。r
ij
表示图中节点i和节点j之间的相邻关系。具体而言，对于每一对(i，j)∈v
×
v，如果(i，j)∈e则r
ij
为1，否则为0。
[0055]
在边图g
′
中，边权重q
i，j
定义为从路段i到路段j的流量的分数。显然，如果路段i到路段j的流量大于路段i到其他相邻路段的流量，则i到路段j之间的相关性很强。因此，边权重q定义如下：
[0056][0057]
其中，z
ij
是从节点i到节点j的轨迹数。n(i)是节点i的一跳邻居的集合。
[0058]
因此，k跳对偶图卷积可表述为：
[0059][0060]
其中，θ
*g
是带有参数θ的图卷积运算，是关联矩阵对节点和边之间的连接关系进行编码，定义为：m
i，(i
→
j)
＝m
j，(i
→
j)
＝1，否则为0。z
(l+1)
和h
(l+1)
分别表示节点图和边图的输出。
[0061]
增强型gcn(r-gcn)：图卷积可以聚合一跳邻居的信息。通过堆叠多个图卷积层，能够扩大感受邻域的范围。然而随着网络层数的增加，节点的特征往往倾向于全局模式，而丢失了局部模式特征。因此，在一个实施例中，整合多尺度信息以同时捕获全局和局部特征。为了解决这个问题，提出增强型gcn(r-gcn)，如图5所示。
[0062]
为了从前几层的输出中捕获重要特征，本发明对现有工作进行改进，采用滚雪球方法增量连接多尺度特征的方式。例如，首次提出使用门控循环单元(gru)进行特征的过滤和选择。与其他类型的rnn模型相比，gru是一种简单但有效的结构。该结构表示为：
[0063][0064]
其中，a是一个对称邻接矩阵，i是一个单位矩阵。σ是一个非线性激活函数，例如使用函数tanh。r
(l)
是第l跳处的路口或路段的隐藏表示。c
l
是处理第l-1跳邻居后的隐藏状态，它的初始值c
(-1)
＝0。再由gru推导出隐藏状态的向量表示，定义为：
[0065][0066]
其中
⊙
代表逐元素乘法。是权重参数，是偏置参数。
[0067]
时空学习方法：本发明使用gru来捕获路口和路段特征的时序依赖性，如图5所示。具体来说，使用路口和路段的历史信息来学习它们的时序特征，公式可以表示为：
[0068][0069]
其中f()代表对偶图卷积的函数，l代表对偶图卷积的层数。hi(t)是在时间步t的第i个路口的表示，zi(t)是在时间步t的第i个路段的表示，si(t)是在时间步t经对偶图卷积操作处理后的第i个路口后的隐藏状态，xi(t)在时间步t经对偶图卷积操作处理后的第i个路段后的隐藏状态。w
ω
、w
′
ω
、u
ω
和u
′
ω
是权重矩阵，b
ω
，b
′
ω
是偏置参数，其中ω∈{u，r，h}。特别地，本发明将对偶图卷积操作同时应用于gru的输入和隐藏表示，以充分学习空间和时间信息。
[0070]
(3)多任务学习层
[0071]
为同时估计各个路段、路口和整条路径的行程时间，本发明采用具有多任务损失函数的多任务序列模型，可以同时进行局部(即路口和路段)和全局(即路径)行程时间的估计。
[0072]
由于交通信息总是顺序依赖的，本发明使用反映路段和路口之间时序依赖关系的路径信息来进一步学习它，如图6所示。为简单起见，使用q来表示s和x。因此公式可以表示为：
[0073][0074]
其中，ci(t)代表第i个路段或路口在时间步t的最终表示。
[0075]
预测：为估计每个路段(路口)的行程时间，例如使用规格为λ和1的两层全连接神经网络，并定义为第i个路段(第j个路口)的行程时间。
[0076]
为直接估计整条路径的行程时间，需要将特征序列ci转换成一个固定长度的向量。对于完整路径行程时间的估计表示为：
[0077][0078]
其中，|p|是路径p中的路段和路口的总数。最后，将g
p
传递给几个大小相等的全连接层，并获得对整个路径行程时间的估计。
[0079]
步骤s130，利用设定的损失函数训练深度学习模型。
[0080]
在训练阶段，使用平均绝对百分比误差(mape)作为目标函数用于估计整个路径的行程时间，损失函数表示为：
[0081]
[0082]
其中，ti表示估计的旅行时间，是第i条路径的行程时间的真实值。此外，添加了一个参数∈，以避免分母接近0时导致损失值爆炸。例如，∈设置为5。
[0083]
对于局部路径行程时间估计，定义了相应的损失为所有局部路径的平均损失：
[0084][0085]
其中，表示第j个路段的行程时间的真实值，表示第j个路段的行程时间的估计值。
[0086]
对于路口通行时间的估计，定义相应的损失为所有路口的平均损失：
[0087][0088]
其中是第j个路口的行程时间的真实值，表示第j个路口的行程时间的估计值。
[0089]
在对所提出的模型训练过程，以最小化三个损失项的加权组合作为总体损失，表示为：
[0090]
l＝αl
p
+βl
l
+(1-α-β)lvꢀꢀꢀꢀ
(15)
[0091]
其中，α和β用于平衡l
p
、l
l
和lv。
[0092]
步骤s140，利用经训练的深度学习模型估计目标路径的行程时间。
[0093]
在模型训练完成后，即可应用于实际路网，针对目标路径估计行程时间。由于所提出的模型框架能够并行估计路段、路口和整条路径的行程时间，有助于将其部署到实用的地图导航服务中。
[0094]
需说明的是，上述模型训练过程可在服务器或云端离线进行，将经训练的模型嵌入到电子设备即可实时地估计目标路径的行程时间。该电子设备可以是终端设备或者服务器，终端设备包括手机、平板电脑、个人数字助理(pda)、销售终端(pos)、车载电脑、智能可穿戴设备(智能手表、虚拟现实眼镜、虚拟现实头盔等)等任意终端设备。服务器包括但不限于应用服务器或web服务器，可以为独立服务器、集群服务器或云服务器等。
[0095]
为验证本发明的效果，利用真实数据集对模型进行了验证，并利用消融实验进一步证明模型各组成部分的有效性。实验过程描述如下。
[0096]
1)数据集介绍
[0097]
使用三个真实世界的数据集评估所提出的模型，分别是成都数据集、波尔图数据集和北京数据集。
[0098]
成都数据集包含2014年8月中国成都超过1.4万辆出租车的出租车轨迹，在(taxi travel time prediction challenge[z].http：//www.dcjingsai.com.2016)公开。
[0099]
波尔图数据集包含2013年7月至2014年6月在葡萄牙波尔图的442辆出租车的出租车轨迹，可以很容易地从https：//www.kaggle.com/crailtap/taxi-trajectory获得。
[0100]
北京数据集包含来自中国北京2020年12月15日上午8：00至下午1：00期间流行的移动应用程序amap的34696条匿名轨迹。本发明使用这个数据集在高德地图的服务提供商的深度学习平台上评估所提出的框架。
[0101]
对于两个公共数据集，首先从openstreetmap中获取成都和波尔图的路网信息，包括路段、路口及其连通性。接下来对于每个数据集，使用现有的地图匹配方法将每条轨迹投影到道路网络中，从而获得对应的路径，并过滤与原始轨迹有显着偏差(
±
10％)的不匹配路径。最后，分别从波尔图和成都的数据集中提取310507和1788723条路径。由于计算资源的限制，本发明没有使用两个数据集中的所有匹配路径，选择了分布在市中心的轨迹，因为这些区域存在相对大量的轨迹。对于北京数据集，经过高德数据平台的预处理，得到每条轨迹的路段和路口的序列。与其他两个数据集不同，该数据集中每个路口的行驶时间都可获得，这使得同时估计整个路径、路段和路口的行程时间成为可能。
[0102]
表1是实验中使用的三个数据集的统计数据。由于地理空间和时间因素可能会影响旅行时间的预测性能，为验证所提出模型的普遍性，本发明还根据郊区、高峰期和非高峰期三种场景选择成都数据集上的轨迹。特别是对于郊区场景，由于沿着郊区的路径遍历了一些轨迹，它可以进一步验证数据稀疏性对所提出模型性能的影响。同时，在市区定义了高峰和非高峰时间的场景。需要注意的是，在实验中，工作日的高峰时间定义为上午7：00-9：00和下午5：00-7：00，其他时间段被视为非高峰时间。表2是成都数据集在三种场景下的统计数据。
[0103]
表1实验数据集的基本信息
[0104]
数据集成都波尔图北京轨迹数量153031268334696路段数量873544714路口数量807450320平均行程时间(秒)246.54248.49343.3平均移动距离(米)1435.341394.823929.7
[0105]
表2成都数据集在郊区、高峰和非高峰三个场景下的数值统计
[0106][0107]
[0108]
2)评价指标及损失函数
[0109]
实验选择了三个指标来评估模型性能，包括平均误差(mae)、均方根误差(rmse)和平均绝对百分比误差(mape)。mae和rmse可以很好地反映估计结果与真实值之间的误差，其中rmse对大误差更有用。mape是衡量估计精度的相对误差。通过这些指标可以全面评估模型的性能。这些指标的定义如下i
[0110][0111][0112][0113]
对于上述指标，较小的值代表更好的预测性能。在所提出的模型中，路口和路段的表示的维度大小设置为20。r-gcn层数设置为3，对偶图卷积的跳数默认设置为1。使用前12个时间步以5分钟为基本时间单元的路口和路段的历史信息来捕获它们的时空动态特征。多任务学习层中的全连接层数均设置为2，隐藏层数均设置为60。采用adam优化器训练模型，并在titan xp gpu上运行本发明的模型，并在python中使用pytorch 1.5环境中实现，对于每个实验都重复进行5次取平均值。
[0114]
3)基准模型
[0115]
为评估所提出模型的有效性，选择了十种最先进的对比方法，总结如下：
[0116]
avg：计算特定时间间隔内城市的平均路段速度。有了这样的历史平均速度，可根据出发时间估计给定行驶路径的行驶时间。
[0117]
temp：这是一种集体行程时间估计方法，它使用具有相似起点和目的地的相邻历史轨迹。本发明为每个要在实验中估计的轨迹分配五个相邻轨迹并取这些轨迹的平均行程时间为待估计轨迹的行程时间。
[0118]
gbdt：使用梯度提升决策树进行回归来估计行程时间。每个gps点序列统一采样到128个。树模型的最大深度设置为8。
[0119]
m1ptte：采用多层感知器来估计行程时间。在实验中，该模型的层数设置为5，激活函数为relu。mlptte中隐藏层的大小固定为64。
[0120]
rnntte：利用gru作为循环神经网络的实现，将原始gps序列处理为128维特征向量。然后将其传递给两个全连接层以获得行程时间的估计值。
[0121]
deeptte：这是一个用于行程时间估计的端到端深度学习模型，该模型基于查询路径上的连续采样gps点捕获空间和时间依赖性。geo-conv层和gru层的隐藏大小分别设置为64和128。
[0122]
t-gcn：这是一个时序gcn模型，该模型结合gcn和gru，同时表征交通预测的空间和
时间依赖性。实验中，使用该模型的核心架构来估计旅行时间。gcn模型的嵌入大小设置为20，gru的隐藏大小设置为128。
[0123]
dcrnn：这是一个用于交通预测的时空图神经网络。该模型利用gcn捕获空间依赖性，然后使用递归神经网络对时间依赖性进行建模。实验中，利用其核心架构用于估计旅行时间。gcn嵌入大小和gru隐藏大小的设置与t-gcn模型相同。
[0124]
constgat：该模型采用图注意力机制来探索时空信息的联合关系，在旅行时间估计中被证明是有效的。实验中，使用其核心架构，其中图注意力网络的嵌入大小设置为32。
[0125]
gcnatttte：该模型首先使用gcn对路段进行建模，然后采用注意力机制通过对连接路段的嵌入求和来学习路口的特征。在实验中，路段的嵌入大小设置为20。
[0126]
4)实验结果
[0127]
经过实验验证，与基线模型相比，本发明所提出模型取得显著的提升。该现象可以从两个方面来解释。首先，对于一些基于图的方法，如t-gcn、dcrnn和constgat，它们只专注于对路段进行建模。然而，交叉路口作为连接多条连接路段的关键节点，在行程时间估计中也发挥着重要作用。因此，在不考虑路口的情况下，模型无法获得更高的精度。其次，对于如gcnatttte这样的模型，它已经同时考虑了路口和路段，但没有充分利用它们的联合关系，因此gcnatttte无法获得最佳性能。与上述模型不同，本发明提出的dgcn-tte模型不仅考虑路口和路段特征，还能够捕获它们的复杂关系。因此dgcn-tte的性能最佳。
[0128]
表3dgcn-tte和其他方法在三个数据集上的性能对比
[0129][0130]
由于本发明所提出的模型可以同时估计路段、路口和整个路径的行程时间，实验中，将所提出的模型与其他基于图学习的方法在预测路段和路口的行程时间方面进行比较。需要注意的是，只有北京数据集有路口行程时间信息，并且对比的基线模型中除gcnatttte外的其他模型不考虑路口。因此，将本发明的模型与gcnatttte进行比较，用于北京数据集的路口行程时间估计，其中路口的预测结果列在符号“/”之后。参见表4，观察到对于路段本发明提出的模型在三个数据集上获得了更好的预测性能。对于路口，本发明提出
的模型与gcnatttte相比，rmse提高了12.23％，mae提高了20.55％，mape提高了20.53％，这是因为本发明提出的模型捕获了路段和路口之间的交互关系，这有助于提高估计路段和路口行程时间的准确性。
[0131]
表4dgcn-tte和其他方法在三个数据集上的性能对比
[0132][0133]
不同场景下的性能：由于地理空间和时间因素对行程时间估计有显著影响。具体来说，不同类型的地区有不同的交通状况。例如，市中心通常交通繁忙，而郊区则有少量机动车辆行驶。同时，交通状况随时间变化。例如，高峰时段比非高峰时段更容易发生交通拥堵。基于上述分析，通过实验来评估所提出的模型在三种不同场景下估计路径的行程时间的性能，包括郊区、高峰时间和非高峰时间。参见表5的实验结果。可以观察到，虽然高峰时段可能会出现交通拥堵，但所提出的模型在rmse、mae和mape方面至少可以实现7.36％、7.56％和6.86％的改进。然而，在非高峰时段，所提出的模型在rmse、mae和mape方面至少实现了10.81％、13.24％和8.58％的改进。同时在轨迹数量较少的郊区，所提出的模型在rmse、mae和mape的预测性能上也获得了至少2.27％、4.84％和8.46％的提升。相对而言，所提出的模型在非高峰时段的场景下提升最大。但是无论在哪种情况下，所提出的模型都明显优于其他方法。
[0134]
表5dgcn-tte和其他方法在三种场景下的性能对比
[0135][0136]
消融实验：为了验证dgcn-tte中的时空学习方法如何有效地捕捉空间和时间属性的联合关系，我们在处理序列时首先将r-gcn从gru的隐藏状态中移除得到变体dgcn-tte w/o r-gcn。分析表6，可以发现在两个数据集上与dgcn-tte相比，它无法获得良好的性能。例如，通过与所提出的模型比较，它在成都数据集上的rmse、mae和mape性能分别下降4.41％、5.4％5.38％。这是因为空间信息被纳入时间依赖关系中，这证明了所提出模型的有效性。然后，构建了没有rnn的dgcn-tte，该模型移除dgcn-tte中的时间部分，得到变体dgcn-tte w/o rnn。结果参见表6，结果表明去除时间部分后两个数据集的预测性能有明显下降。这是因为时间部分对于捕获路径沿线的交通历史信息至关重要，这表明单纯捕获空间特征无法获得更好的性能。基于上述分析，可以得出结论，本发明的时空学习方法可以有效地解决时空属性的联合关系。
[0137]
接下来，研究路口建模如何影响性能。在dgcn-tte w/o intersection变体中，仅对路段进行建模以估计行程时间。参见表6，可以观察到无论哪个数据集，性能都会变差。具体来说，在rmse、mae和mape方面，dgcn-tte w/o intersection的性能在成都数据集上下降了2.45％、2.5％和2.16％，在波尔图数据集上下降了5.58％、2.34％和3.23％。原因是路口不仅包含自己的重要信息，而且与多个连接的路口具有很强的相关性。因此忽略路口特征的dgcn-tte w/o intersection无法获得良好的性能。最后，展示了r-gcn在所提出模型中的影响。具体来说，在dgcn-tte simple gcn变体中使用简单的gcn代替了r-gcn，然后评估其性能。结果表明，将所提出的模型与r-gcn结合使用可以在两个数据集上取得更好的性能，因此r-gcn在捕获多尺度时空信息方面具备更强的能力。
[0138]
表6dgcn-tte及其变体在两个数据集上的性能对比
[0139][0140]
参数分析：为了进一步展示所提出模型的有效性，在不同的参数组合下进行了实验，包括r-gcn的层数(记为n)和对偶图卷积的跳数(记为k)。具体来说，针对某个k在不同的n下评估所提出的模型，参见图7所示，其中图7(a)是当图卷积的跳数k＝1时，r-gcn的层数n的变化对性能的影响，图7(b)是当图卷积的跳数k＝2时，r-gcn的层数n的变化对性能的影响，各图中的上方曲线对应成都数据集，下方曲线对应波尔图数据集。如图7(a)所示，在rmse、mae和mape方面，在两个城市的数据集上，在k＝1的条件下，当n从1逐渐变为3时，性能逐渐提高。但是，当n＝4时性能会变差。这表明r-gcn的层数越高并不表示性能越好。在图7(b)中观察到，无论是哪个数据集，当r-gcn的层数为2时，其性能在k＝2的条件下均达到最优。此外，在每个数据集上比较了不同参数组合下的性能。表7的结果表明，所提出的模型在成都数据集上在n＝3和k＝1的条件下取得了最好的性能，而在波尔图数据集上n＝2和k＝2时取得最好性能。这表明r-gcn的层数和对偶图卷积的跳数都在获得更高的行程时间估计精度方面发挥着关键作用。总而言之，r-gcn的层数越多，对偶图卷积的跳数越大并不意味着更好的性能，并且应根据相应的数据集选择最合适的参数数值。
[0141]
表7dgcn-tte及其变体在两个数据集上的性能对比
[0142]
[0143]
综上所述，本发明提出了一个端到端的深度学习框架来估计路径、路段和交叉路口的行程时间。这是第一次尝试对路口和路段的特征进行联合建模以进行行程时间估计。并且，提出对偶图卷积来建模路口和路段的关系。该方法采用节点图来捕捉路口相关性，并构建边图来刻画路段的交互特征。此外，本发明提出一种可以集成多尺度空间信息的增强型gcn，同时引入时空学习方法来充分探索空间和时序特征的联合依赖关联。进一步地，通过对三个真实世界数据集的多次实验来评估所提出的框架。实验结果表明，所提出的框架在多个指标下优于已有的最先进的方法。
[0144]
本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机可读程序指令。
[0145]
计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是但不限于电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、静态随机存取存储器(sram)、便携式压缩盘只读存储器(cd-rom)、数字多功能盘(dvd)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。
[0146]
这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。
[0147]
用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(isa)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言-诸如smalltalk、c++、python等，以及常规的过程式编程语言-诸如“c”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络-包括局域网(lan)或广域网(wan)-连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(fpga)或可编程逻辑阵列(pla)，该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。
[0148]
这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/
或框图中各方框的组合，都可以由计算机可读程序指令实现。
[0149]
这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。
[0150]
也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。
[0151]
附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。对于本领域技术人员来说公知的是，通过硬件方式实现、通过软件方式实现以及通过软件和硬件结合的方式实现都是等价的。
[0152]
以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。本发明的范围由所附权利要求来限定。

技术特征：
1.一种路口联合建模的对偶图卷积网络的行程时间估计方法，包括以下步骤：获取目标路径和对应的出发时间，所述目标路径是道路网络中的一系列路段和路口的序列；针对所述目标路径和对应的出发时间，利用对偶图卷积网络估计行程时间，该对偶图卷积网络以设定的损失函数最小化为目标，利用历史轨迹数据集训练获得；其中，所述对偶图卷积网络包括嵌入层、时空图学习层和多任务学习层，所述时空图学习层通过对节点图和边图进行对偶图卷积捕获时空特征；其中，所述节点图的每个节点和边分别代表一个路口和路段，所述边图的节点是节点图中的对应边。2.根据权利要求1所述的方法，其特征在于，所述嵌入层基于行驶速度、道路类型和行驶距离来初始化路段的表示，对于在时间t的路段的表示，定义为：其中，s
r
(t)是在时间t的路段平均速度，d
e
是路段的距离，p
e
是道路类型，w
e
是可学习的参数矩阵，[]是合并操作运算符。3.根据权利要求1所述的方法，其特征在于，对于路口，所述嵌入层通过聚合连接路段的表示来初始化路口的表示，对于在时间t的路口的表示，定义为：其中，f(v)表示与路口节点v连接的路段集，p
v
表示路口是否有红绿灯，w1和w2是可学习的参数矩阵。4.根据权利要求1所述的方法，其特征在于，所述对偶图卷积堆叠多跳图卷积层，每跳图卷积层输出不同尺度的特征，并且每跳图卷积层的输出特征经由门控循环单元进行特征的过滤和选择。5.根据权利要求1所述的方法，其特征在于，所述多任务学习层采用门控循环单元。6.根据权利要求4所述的方法，其特征在于，所述时空图学习层采用门控循环单元来捕获路口和路段特征的时序依赖性，表示为：s
i
(t)＝gru(h
i
(t),s
′
i
(t-1)∣w
ω
,u
ω
,b
ω
)x
i
(t)＝gru(z
i
(t),x
′
i
(t-1)∣w
′
ω
.u
′
ω
,b
′
ω
)s
′
i
(t-1),x
′
i
(t-1)＝f(g,g
′
,s
i
(t-1),x
i
(t-1),l)其中f()代表对偶图卷积的函数，l代表对偶图卷积的层数，h
i
(t)是在时间步t的第i个路口，z
i
(t)是在时间步t的第i个(路段)的表示，s
i
(t)是在时间步t经对偶图卷积操作处理后的第i个路口(路段)后的隐藏状态，x
i
(t)是在时间步t经对偶图卷积操作处理后的第i个路段后的隐藏状态，w
ω
、w
′
ω
、u
ω
和u
′
ω
是权重矩阵，b
ω
，b
′
ω
是偏置参数，g表示节点图，g
′
表示边图。7.根据权利要求1所述的方法，其特征在于，将所述损失函数设置为：l＝αl
p
+βl
l
+(1-α-β)l
v
其中，l
p
整个路径的行程时间损失函数，l
l
表示局部路径行程时间的损失函数，l
v
表示
路口通行时间的损失函数，α和β是设定的参数。8.根据权利要求7所述的方法，其特征在于，将所述整个路径的行程时间损失函数设置为：其中，t
i
表示估计的旅行时间，是第i条路径的行程时间的真实值，∈是设定参数，d表示历史轨迹数据集；将所述局部路径行程时间的损失函数设置为：其中，p表示路径，表示第j个路段的行程时间的真实值，表示第j个路段的行程时间的估计值；将所述路口通行时间的损失函数设置为：其中，是第j个路口的行程时间的真实值，表示第j个路口的行程时间的估计值。9.一种计算机可读存储介质，其上存储有计算机程序，其中，该计算机程序被处理器执行时实现根据权利要求1至8中任一项所述方法的步骤。10.一种计算机设备，包括存储器和处理器，在所述存储器上存储有能够在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至8中任一项所述的方法的步骤。

技术总结
本发明公开一种路口联合建模的对偶图卷积网络的行程时间估计方法。该方法包括：获取目标路径和对应的出发时间；针对所述目标路径和对应的出发时间，利用对偶图卷积网络估计行程时间，该对偶图卷积网络以设定的损失函数最小化为目标，利用历史轨迹数据集训练获得，其中所述对偶图卷积网络包括嵌入层、时空图学习层和多任务学习层，所述时空图学习层通过对节点图和边图进行对偶图卷积捕获时空特征，所述节点图的每个节点和边分别代表一个路口和路段，所述边图的节点是节点图中的对应边。本发明采用对偶图卷积方法来捕获路口和路段的复杂关系，能够对交叉路口和路段进行联合建模，提升了行程估计时间的准确性。提升了行程估计时间的准确性。提升了行程估计时间的准确性。


技术研发人员：张金雷 金广垠 杨立兴 沙恒宇 黄金才 杨咏杰 高自友
受保护的技术使用者：北京交通大学
技术研发日：2022.12.16
技术公布日：2023/6/12