交通预见未来(17): 基于时空网络的出租车OD需求预测
1、文章信息
《Contextualized Spatial–Temporal Network for Taxi rigin-Destination Demand Prediction》。
2019发在IEEE Transactions on Intelligent Transportation Systems上的一篇文章（运输科技2区，IF:5.744）。
2、摘要
目前大量的研究是基于出行起点的出行需求预测，很少有人关注这些人前往何处，即D点，本文认为仅根据出租车的原产地需求将出租车预先分配到每个区域并不是最优的。因此本文主要是进行所有区域之间即所有OD对之间的出租车OD需求预测。它的主要挑战来自于如何有效地捕获各种环境信息来学习需求模式。本文提出了一种新的符合实际环境的时空网络(contextualized spatial–temporal network，CSTN)，它由局部空间环境 (local spatial context ，LSC)、时间演化环境(temporal evolution context TEC)和全局相关环境(global correlation context ，GCC)三部分组成。（context这个词，网上大部分都是翻译成上下文，我感觉好像环境更好一点，本文所有context的翻译均为环境）。首先，局部空间环境模块利用两个卷积神经网络分别从起点和终点两个角度学习局部空间依赖关系。其次，将出租车需求的局部空间特征和气象信息集成到卷积长短时记忆网络(ConvLSTM)中，分析出租车需求演化。最后，为了捕获相隔较远的区域之间的相关性，全局相关环境模块计算任意两个区域之间的相似性，并将所有区域的特征与相似性权重相加，生成每个区域的全局相关性特征。实验表明本文模型的表现最好。
3、简介
滴滴出行等出租车服务仍然存在着一些低效经营的问题，例如乘客等候时间较长及空载次数较多。主要是由于出租车需求预测不准确导致供需不匹配，导致大量出租车聚集在一些繁忙地区，造成供过于求，而在其他偏远地区，出租车的分布极为稀疏。解决这一问题的方法包括预测未来的出租车需求，同时提前将出租车分配到各个区域。
出租车需求预测作为智能交通系统中的一项重要任务，已经引起了广泛的研究兴趣，并取得了显著的成功。然而，现有的方法大多只对出租车在出发地点的需求进行建模，估计各个地区或某些特定地点的出租车需求，忽略了乘客目的地的影响。我们认为乘客目的地信息对于出租车预分配系统是至关重要的。出租车预分配系统在不考虑乘客目的地分布的情况下，仅根据预测的出租车发车需求提前部署出租车，可能存在以下问题:
（1）受城市管理规定的限制(如北京的驾驶限制政策)，一些司机只允许在某些特定地区开车。如果一个出租车司机被分配到一个大部分乘客都要去的区域，而这个区域是司机被限制的地方，那么他就不能接受命令，这可能会导致资源的浪费。
（2）一些司机更喜欢在他们熟悉的区域搭载乘客。与此同时，一些司机不愿意接受利润微薄的短途旅行订单。如果司机预分配区域内的大部分乘客的目的地不在他的操作区域，或者离接机地点太近，司机可能会拒绝这些请求。
（3）如果一个司机被派往一个大部分乘客都会去，但是司机不熟悉的地区，即使有GPS导航，司机也可能会花更多的时间把乘客带到他们的目的地。这将降低出租车市场的运营效率和乘客满意度水平。
在本文中，我们提出了一个具有挑战性的出租车初始需求预测任务，该任务旨在预测任意两个区域之间未来的出租车需求。如果能够很好地预测出租车的发车需求和乘客的目的地，我们可以更有效地提前调配出租车，满足乘客的需求，同时避免上述问题。本文的关键在于如何捕捉不同时空的环境信息来学习需求模式。例如，一些在空间上相邻的区域通常具有相似的需求模式(比如出租车需求数量和需求趋势)，在我们的工作中称为局部空间环境(local spatial context , LSC)。此外，即使两个区域在空间上相距遥远，如果它们具有相似的功能(例如，它们都是住宅区)，需求模式可能仍然具有一定的相关性。我们将两个相距遥远的区域之间的这种关系称为全局关联环境 (global correlation context, GCC)。最后，出租车需求是一个时变的过程，出租车需求的演变与出租车目前所处的状态以及不断变化的天气等多种因素有关，出租车需求的演变可以用时间演化环境(time evolution context, TEC)来表示。
本文提出了一种新的符合实际环境的时空网络，它由局部空间环境、时间演化环境和全局相关环境三部分组成。首先，局部空间环境模块利用两个卷积神经网络分别从起点和终点两个角度学习局部空间依赖关系。然后将两个网络的输出结合起来生成最终的局部空间特征，其中包含了不同视角下出租车需求模式的混合信息。其次，将出租车需求的局部空间特征和气象信息集成到卷积长短时记忆网络(ConvLSTM)中，分析出租车需求演化。最后，为了捕获相隔较远的区域之间的相关性，全局相关环境模块模块计算任意两个区域之间的相似性，并将所有区域的特征与相似性权重相加，生成每个区域的全局相关性特征。这样，每个区域包含了所有区域的信息，主要与与之有高度相似性的区域相关。最后，将TEC模块生成的局部时空特征与GCC模块生成的全局相关特征相结合，对未来出租车发车目的地需求进行预测。
这项工作的主要贡献有三方面:
（1）将现有的出租车需求预测扩展到出租车原目的地需求预测的任务中，对智能交通系统具有更大的探索价值。据我们所知，我们是第一个研究跨区域出租车需求预测的。
（2）提出了一种新的时空网络解决了这一问题，它很好地将局部空间环境、时间演化环境和全局相关环境集成到一个统一的框架中。
（3）在出租车OD需求预测的很多基准上进行的大量实验表明，我们的方法比现有的最先进的方法有一定的优势。
4、预备知识
A、全网的区域划分
我们根据经纬度将一个城市划分为H×W不重叠网格地图。每个矩形网格代表城市中不同的地理区域。网格映射第i行和第j列上的区域在下面的部分中表示为R(i, j)。图1(a)显示了纽约市曼哈顿的分区区域。通过这种简单的划分方法，原始出租车请求记录可以直接转化为矩阵或张量，这是深度神经网络中最常见的输入数据格式。
B、出租车OD需求
OD需求这块有点绕，需要搞明白，一个区域的需求产生量可能会前往其他所有区域（一对多的关系），而一个区域的需求吸引量可能会来自其他所有区域（多对一的关系）。
在打车行业，出租车公司或滴滴出行、优步等在线平台每秒钟都会收到大量乘客的打车请求。每个原始出租车请求包含乘客的起始位置、目的地位置、时间戳和其他信息(例如用户标识和电话号码)。在我们的工作中，出租车始发目的地需求定义为在每个时间间隔内从始发区域到目的地区域的出租车请求总数。
我们将时间区间t内出租车OD需求表示为三维矩阵Xt∈R（N×H×W），其中H和W分别为城市网格地图的高度和宽度。N是城市区域总数，等于H·W。（此处N=H·W是上面提及的多对一的关系，即到达一个区域的乘客可能来自其他所有区域，所以，一个区域得需要一个矩阵，N个区域需要H·W个矩阵）（高亮部分是一个总体表达式，是针对所有O点所有D的，公式好多, 不写了直接上图……）
C、出租车OD需求预测
出租车OD需求预测问题是给定t 时刻之前的数据，预测时间间隔t内的出租车OD 需求。如图2所示，出租车需求受到气象条件的严重影响，因此我们也加入了历史气象数据来处理这个任务，我们将时间间隔i中的气象数据表示为Mi。
5、模型简介
下面对模型的三个部分（蓝框、黄框、红框）依次进行介绍。
A、Local Spatial Context Modeling局部空间环境
一般情况下，出租车的需求往往与当地的空间位置有关，空间相邻区域可能具有相似的需求模式。例如，人们倾向于在早高峰时段离开居住地前往就业地区。在这种情况下，城市郊区的大部分居住区域都有较高的O点需求，而城市中心的大部分工作区域都有较高的D点需求。反之亦然。近年来，研究者利用卷积层对出租车O点需求的局部空间环境进行了建模，但忽略了D点的需求。
在这项工作中，我们提出的LSC模块同时从O点视角和D点视角捕获出租车需求的局部空间信息。相当于利用了两个张量，一个是OD矩阵，一个是DO矩阵。下图说明了从OD矩阵转换为DO矩阵的过程。
对两个矩阵分别进行卷积在进行特征融合即可，不再详述。文章将下图称为ConvNets。
B、Temporal Evolution Context Modeling时间演化环境
出租车需求是一个时变的过程，通常受多种复杂因素的影响。除了自身的内部状态，气象条件也影响着未来的需求。例如，持续的降雪可能会严重削弱居民的出行意愿，导致出行需求下降。因此，我们结合历史需求特征和不断变化的气象条件，把握出租车需求沿时间维度的演变趋势。
这一块也比较简单，即将第一部分的卷积结果和对天气数据的卷积结果进行融合，然后输入到ConvLSTM层即可。（这一块文章中写的比较复杂，把ConvLSTM的来龙去脉和公式都详细解释了一遍）
我们的目标是利用过去n个时间间隔的历史需求和气象条件来预测Xt的出租车需求。对于气象数据Mi，我们用多层感知器(MLP)对其进行编码，多层感知器由三个堆叠的全连接层实现，分别由64个、16个和8个神经元组成。然后将MLP的输出特征复制H·W次，构建3D气象特征，以便与上一部分的输出结果进行融合。
C、Global Correlation Context Modeling全局相关环境
在上述两个模块中，ConvNets和ConvLSTM只捕获了出租车需求的局部信息。然而，出租车需求分布也与区域属性有关，例如，城市不同区域的大部分居住区在早高峰时段可能会有较高的出租车需求。因此，即使两个区域相距遥远，只要两个区域的属性一致，它们的出租车需求模式也可能是相似的。我们将这种关联称为全局相关环境。
本文通过全局特征融合操作，获取各区域间的全局相关性。具体来说，我们将每个区域的全局相关特征表示为所有区域特征的加权和，权重计算为对应OD对之间的相似性。这样，每个区域包含了所有区域的信息，主要与与之高度相似的区域相关。
这一块比较复杂（可解释性也不太强），具体操作就是，先将B部分的输出经过一个有Cs个filter的Conv层，输出形状为Cs*H*W, 再将该输出reshape成Cs*N，然后转置为N*Cs, 两者点成得到N*N的相似性矩阵S。
将B部分的输出reshape成Cf*N, 并与相似性矩阵相乘, 结果形状为Cf*N，再将该结果reshape成Cf*H*W。该结果（即下图中的Fg）对全局相关环境进行编码，但这样缺乏结构性的局部特征，这会导致性能下降，因此再将该结果与B部分的输出连接，最后经过一个Conv层，得到最终的输出结果。该特征Fltg融合了局部空间信息、时间演化信息和全局相关信息的混合信息。
6、总结
文章后面的实验部分不再介绍。文章总来说很新颖，尤其是全局空间相似性这块个人感觉可以借鉴学习。后台回复“纽约”获取文章的使用的纽约出租车数据集。
关注微信公众号《当交通遇上机器学习》，
后台回复“数据”即可获取高达175G的四个月的滴滴GPS数据和滴滴订单数据的获取方式，以及从数据处理（Oracle数据库）、模型构建（机器学习）、编程实现（python）到可视化（ArcGIS）等一系列视频教程。
后台回复“纽约”获取美国纽约10年的出租车轨迹数据以及7年的共享单车轨迹数据下载地址。
公众号以交通大数据为主线，专注于人工智能、机器学习、深度学习在道路交通和轨道交通领域内的科研前沿与应用，在交通大数据与机器学习的道路上越走越远！