英语原文共 8 页

基于深度神经网络的旅行时间估算

摘要：估算城市中任何路径（由一系列连接的路段表示）的行程时间对于交通监控，路线规划，乘坐共乘，出租车/优步调度等非常重要。但是，这是一个非常具有挑战性的问题，受到影响通过各种复杂因素，包括空间相关性，时间依赖性，外部条件（例如天气，交通信号灯）。先前的工作通常侧重于估计各个路段或子路径的行程时间，然后总结这些时间，这导致估计不准确，因为这些方法不考虑道路交叉口/交通灯，并且可能累积局部误差。为了解决这些问题，我们提出了一个端到端的旅行时间估计深度学习框架（称为DeepTTE），它直接估计整个路径的旅行时间。更具体地说，我们通过将地理信息集成到能够捕获空间相关性的经典卷积中来呈现地理卷积运算。通过在geo-convoluton层上堆叠循环单元，我们的DeepTTE也可以捕获时间依赖性。在DeepTTE的顶部给出了一个多任务学习组件，它学习在训练阶段同时估计整个路径和每个本地路径的传播时间。对两个轨迹数据集的大量实验表明，我们的DeepTTE显着优于最先进的方法。

引言：估计给定路径的行进时间（由一系列连接的子路径表示）是路线规划，导航和交通调度中的基本问题。 当用户搜索候选路线时，准确的旅行时间估计有助于他们更好地规划路线并避免拥挤的道路，这反过来有助于缓解交通拥堵。 几乎所有电子地图和在线carhailing服务都在其应用程序中提供旅行时间估算（TTE），例如Google Map，Uber和Didi。 估算的质量对于这些应用的用户体验至关重要 虽然这个问题在过去已经得到了广泛的研究，但提供准确的旅行时间仍然非常具有挑战性，受以下几个方面的影响：1）个体与集体：主要存在两种估计路径的旅行时间的方法：a）首先将路径分成若干路段（或本地路径）的个别TTE，然后估计每个本地路径的行进时间，最后总结他们以获得总的旅行时间。 b）直接估计整个路径的旅行时间的集体TTE。虽然个别TTE方法（Yang，Guo和Jensen 2013; Wang等人2016c; Pan，Demiryurek和Shahabi 2012; Wang，Zheng和Xue 2014）可以估计每个路段的准确旅行时间，但它无法模拟复杂的交通整个路径内的条件，包括道路交叉口，交通信号灯和方向转弯。此外，如果给定路径中存在许多路段，则可能累积局部误差。集体TTE方法（例如（Jenelius和Koutsopoulos 2013））能够隐含地捕获上述交通状况。然而，随着路径的长度增加，在路径上行进的轨迹的数量减少，这降低了行进时间的置信度（从少数驾驶员导出），指出较长的路径难以估计。而且，在许多情况下，没有轨迹通过整个路径。 2）不同的复杂因素：流量受空间相关性，时间依赖性和外部因素的影响。空间相关性是多种多样的，甚至是复杂的，如图1所示。通过三个连续的GPS点，它描绘了不同的驾驶情况，显示驾驶员可以直行，右转，转弯，驶入主要道路或坡道。明确地提取这些特征是耗时的，甚至是不可行的，因为在现实世界中驾驶情况更复杂。我们需要在方法中隐含地考虑它们。此外，这些空间相关性是时间变化的。以图1（b）为例，在傍晚高峰时段，主要道路上有很多车辆，司机不得不从匝道上一个接一个地慢慢驶入主干道，但是驶出主干道可能很快但在非高峰时段，驶入主干道的速度很快。此外，交通受到许多外部因素的影响，如天气，驾驶员习惯，星期几。

图1：各种驾驶情况

为了解决上述挑战，在本文中，我们提出了一个名为DeepTTE的旅行时间估算的端到端框架。 本文的主要贡献可归纳如下：

bull;我们提出了一个时空组件来学习原始GPS序列的空间和时间依赖性。 详细地，时空分量由两部分组成：a）基于地理的卷积层，其将原始GPS序列变换为一系列能够捕获局部空间相关性的特征图（如图1中的各种驾驶情况）隐含地从连续的GPS点开始; b）递归神经网络（LSTM），其学习所获得的特征图的时间依赖性和来自外部因素的嵌入。

bull;我们提出了一个多任务组件，它学习通过多任务损失函数同时估计每个本地路径和整个路径的传播时间，能够平衡个体和集体估计之间的权衡。 为了准确地估计整个路径，我们设计了一个多因素注意机制，以根据隐藏的表示和外部因素来学习不同局部路径的权重。

bull;我们提供了一个属性组件，它集成了外部因素，包括天气状况，星期几，路径距离和驾驶员习惯。 学习后的潜在表征被输入模型的几个部分，以增强这些外部因素的重要性。

bull;我们对两个真实的大型数据集进行了大量实验，这些数据集由成都和北京的出租车产生的GPS点组成。 这两个数据集的百分比误差分别为11.89％和10.92％，明显优于现有方法。

初步：

在本节中，我们首先介绍几个预赛并正式定义我们的问题。

定义1（历史轨迹）我们将历史轨迹T定义为连续历史GPS点的序列，即T = {p1，...，p | T |}。 每个GPS点pi包含：纬度（pi.lat），经度（pi.lng）和时间戳（pi.ts）。 此外，对于每个轨迹，我们记录其外部因素，例如开始时间（timeID），星期几（weekID），天气条件（weatherID）和相应的驱动程序（driverID）。然后我们说明了我们的目标。

定义2（目标）在训练阶段，我们学习如何基于从定义中定义的历史轨迹中提取的时空模式来估计给定路径的行程时间和相应的外部因素。 1.在测试阶段，给定路径P，我们的目标是通过P估计从起始到目的地的旅行时间，以及相应的外部因素。 我们假设旅行路径P由用户指定或由路线规划应用生成。GPS设备通常为每个固定的产生一条记录长度时间差距。 这可能导致我们的模型学习trival模式（例如，简单地计算GPS记录的数量）。 为了避免这种情况，我们重新采样每个历史轨迹，使得两个连续点之间的距离间隙约为200到400米。

在测试阶段，为了使测试数据与训练数据一致，我们将路径P转换为具有相等距离间隙的位置点序列。 每个位置都表示为一对经度和纬度。

备注：在我们的实验中，为了生成测试数据，我们删除历史轨迹中的时间戳，并将每个轨迹重新采样到GPS位置序列中等距离间隙。 在本文中，我们不考虑如何优化路径P.

模型架构：

在本节中，我们描述了我们提出的DeepTTE的体系结构，如图2所示.DeteTTE由三个部分组成：属性组件，时空学习组件和多任务学习组件。 属性组件用于处理外部因素（例如天气）和给定路径的基本信息（例如，开始时间）。 它的输出作为输入的一部分馈送到其他组件。 时空学习组件是主要建筑组件，其从原始GPS位置序列学习空间相关性和时间依赖性。 最后，多任务学习组件基于前两个组件估计给定路径的传播时间，能够平衡个体估计和集体估计之间的权衡。

图2：DeepTTE架构。 Dis：距离; concat：连接。

属性组件：

正如我们所提到的，路径的行程时间受许多复杂因素的影响，例如开始时间，星期几，天气状况以及驾驶习惯。我们设计了一个简单而有效的组件，将这些因素合并到我们的模型中，我们将其称为属性组件。作为图2中的示例，我们结合了天气状况的属性（下雨/晴天/刮风等），驾驶员ID，时间信息（星期几和旅行开始的时间段）。我们使用weatherID，driverID，weekID和timeID分别表示这些属性。请注意，这些因素是分类值，不能直接提供给神经网络。在我们的模型中，我们使用嵌入方法（Gal和Ghahramani 2016）将每个分类属性转换为低维实数向量。具体地，嵌入方法通过将参数矩阵Wisin;RVtimes;E相乘，将每个分类值visin;[V]映射到实空间REtimes;1（我们将这样的空间称为嵌入空间）。这里V表示原始分类值的词汇量大小，E表示嵌入空间的维度。通常，我们有。与单热编码（Gal和Ghahramani 2016）相比，嵌入方法主要有两个优点。首先，由于分类值的词汇量大小可能非常大（例如，我们的数据集中有20442个驱动程序），嵌入方法有效地减少了输入维度，因此计算效率更高。此外，已经表明具有相似语义含义的分类值通常嵌入到近距离位置（Gal和Ghahramani 2016）。因此，嵌入方法有助于在不同轨迹之间找到并共享相似的模式。

除了嵌入的属性，我们进一步包含另一个重要属性，即行程距离。形式上，我们使用Delta;dpa→pb来表示沿着路径从GPS点pa到pb的总行进距离，即Delta;dpa→pb =其中Dis是两个GPS点之间的地理距离。然后，我们将获得的嵌入向量与行进距离Delta;dp1→p | T |连接起来。连接用作属性组件的输出。我们将这样的输出矢量表示为attr。

时空成分：时空部分由两部分组成。第一部分是地理卷积神经网络，它将原始GPS序列转换为一系列特征映射。这种分量捕获连续GPS点之间的局部空间相关性。第二部分是递归神经网络，它学习所获得的特征图的时间相关性。

Geo-Conv层我们首先介绍Geo-Conv层。回想一下，历史轨迹T是GPS位置点{p1，...，p | T |}的序列，其中每个pi包含相应的经度/纬度（参见定义1）。正如我们在介绍部分中提到的，捕获GPS序列中的空间依赖性对于旅行时间估计是至关重要的。捕获空间依赖性的标准技术是卷积神经网络（CNN），其广泛用于图像分类，对象跟踪和视频处理等（Simonyan和Zisserman 2014; Krizhevsky，Sutskever和Hinton 2012）。典型的卷积层由几个卷积滤波器组成。对于多通道输入图像，滤波器通过对每个二维局部贴片应用卷积运算来学习输入中的空间依赖性。我们将这种卷积层称为2D-CNN。 （Zhang et al.2016）使用2D-CNN来预测全市人群流量。在他们的工作中，他们首先将城市划分为Itimes;J网格，然后将每个GPS坐标映射到网格单元格中。然而，在我们的例子中，直接将GPS坐标映射到网格单元中的准确度不足以表示数据中的原始空间信息。例如，如果相关位置映射到同一单元格，则无法区分转弯。因此，我们的任务需要更精细的粒度。由此推动，我们提出了一种Geo-Conv层，它能够捕获地理位置序列中的空间依赖性，同时保留细粒度的信息。

Geo-Conv层的体系结构如图3所示。对于序列中的每个GPS点pi，我们首先使用非线性映射loci = tanh（Wloc·[pi.lat◦pi.lng]）（1）将第i个GPS坐标映射到矢量轨迹isin;R16，其中◦表示连接操作，Wloc是可学习的权重矩阵。 因此，输出序列locisin;R16times;| T | 表示非线性映射的位置。 注意，这种序列可以看作是16通道输入。 每个通道描述原始GPS序列的地理特征。 我们引入卷积滤波器，参数矩阵Wconvisin;Rktimes;16（我们将k称为滤波器的内核大小）。 它在序列loc上应用卷积运算，以及一维滑动窗口。 我们使用*来表示卷积运算。 其输出的第i维表示为， （2）其中b是偏差项，loci：i k-1是从索引i到索引i k-1的loc中的子序列，sigma;cnn是相应的激活函数。

图3：Geo-Conv层。

定义3（本地路径）我们将从点pi到点pi k-1的子序列称为第i个本地路径。因此，locconvi基本上捕获第i个本地路径的空间特征。通过连接c滤波器的输出，我们获得具有形状Rctimes;（| T | -k 1）的局部路径的特征映射。在自然语言处理的文献中，这种架构被称为1D-CNN（Kim 2014）。然而，在我们的任务中，旅行时间与路径的总距离高度相关。 1D-CNN很难直接从原始经度/纬度提取几何距离。因此，在Geo-Conv层中，我们进一步将列添加到先前获得的特征映射。新附加列的第i个元素（绿色部分）图3）是Dis（pj-1，pj），即第i个本地路径的距离。因此，我们通过Geo-Conv层获得形状R（c 1）times;（| T | -k 1）的最终特征图。我们将此特征映射表示为locf。层功能映射locf捕获所有本地路径的空间依赖性。为了进一步捕获这些本地路径之间的时间依赖性，我们在模型中引入了循环层。递归神经网络（RNN）是一种人工神经网络，广泛用于捕获顺序学习中的时间依赖性，如自然语言处理和语音识别（Krizhevsky，Sutskever和Hinton 2012; Graves，Mohamed和Hinton 2013） ）。循环神经网络能够“记忆”处理序列中的历史。当处理序列中的当前时间步长时，它根据当前输入和先前隐藏状态更新其存储器（也称为隐藏状态）。递归神经网络的输出是序列中所有时间步骤的隐藏状态序列。

在我们的模型中，递归神经网络的输入序列是Geo-Conv层输出的特征映射locf。特征映射locf可以被视为具有长度| T |的空间特征序列 - k 1.此外，我们发现合并属性信息有助于进一步增强复现层的估计能力（回想一下，我们已经在属性组件中获得了属性表示向量attr）。因此，简单来说，我们的重复层的更新规则可以表示为

hi =sigma;rnn（Wx·locfi Wh·hi-1 Wa·attr）（3）其中hi是处理第i个局部路径后的隐藏状态，sigma;rnn是我们在中指定的非线性激活函数实验部分。 Wx，Wh和Wa是在循环层中使用的可学习参数矩阵。在实践中，由于梯度消失和梯度问题爆炸，方程（3）通常无法处理长序列（Hochreiter和Schmidhuber 1997）。为了克服这个问题，我们使用两个堆叠的长短期记忆（LSTM）（Hochreiter和Schmidhuber 1997）层。 LSTM引入了输入门和忘记门来控制输入/输出信息流。这样的门使得LSTM能够忘记一些不重要的信息并有效地缓解梯度消失/爆炸问题。此外，已经表明，与单层LSTM相比，堆叠LSTM更有效地增加模型容量（Yao等人2017）。现在，通过利用Geo

资料编号：[5578]