混合时空图卷积网络：能“推导”未来路况的智能算法

会员服务 ·

混合时空图卷积网络：能“推导”未来路况的智能算法

2020 年 10 月 11 日 DataFunTalk

分享嘉宾：冀晨光阿里高级算法专家

内容来源：公众号"高德技术"

导读： 本次分享来自冀晨光老师在云栖大会上的分享。主要介绍高德提出的时空图卷积算法，巧妙利用海量用户的导航规划信息，“推导”出未来拥堵状况，显著提升预测准确度，并重点介绍了这一业界领先的技术及其在高德业务中的应用。

作为一款国民级出行生活服务平台，高德拥有5.3亿+月活用户，在过去一年间，为出行用户节省至少19.3亿+小时拥堵时间，创造了巨大的社会效益。这里广为大家所熟知的躲避拥堵功能背后的核心技术，就是交通路况预测算法。

本次分享的主要内容包括：

路况预测是什么？
混合时空图卷积网络:能“推导”未来路况的算法
应用前瞻:从“路况预测”到“交通调度”

路况预测是什么？

下面的三幅图，展示了北京西单金融街附近的区域，在三个相邻时间点上的交通状况。其中绿色代表畅通，黄色代表缓行，红色代表拥堵。假设现在是18点整，路况预测的目标就是预估未来时刻上的交通状况，例如半小时之后、18:30的路况。从三个时刻的路况状态及彼此的关联中可以观察到，拥堵会在时空上演化和传播，路况预测就是要对这背后的规律进行精确的刻画和建模。

路况预测技术支撑了高德地图很多的核心功能。冀晨光举了两个代表性的案例。第一个案例是路线的旅行时间预估，术语上叫做ETA。下方左图是驾车路线规划页面，右图是导航的页面。其中红框高亮的部分就是预估的ETA。ETA是路线排序的重要因子，ETA预估的准确与否，直接决定了能否帮助用户有效躲避拥堵。

第二个案例是随时间推演的路线规划。北京有外地小客车早晚高峰限行的政策，命中该政策的车在7到9点间不能进入五环。假设有一个这样的车在6:45分出发。如下图左图所示，常规路线规划只能基于当前时刻的限行信息算路，而6:45分时限行政策尚未生效，所以算出的路线就是穿越五环区域的路线，会导致用户在7点后违章。

为了解决这个问题，高德设计了随时间推演的路线规划算法，这个算法具有未来视角，能帮助用户避让未来即将来到的限行，如下图右图所示，推演路线会引导用户在7点前驶出五环，走六环到达目的地。因此未来路况预测的是否精准，会影响到对用户驶离五环时刻的判断，也就会直接影响到用户是否违章。

在如何预测准未来路况的问题上，业界主要有两类方法。一类是交通仿真，在车辆行驶的起终点信息之上，结合交通动力学理论，联合仿真、预估车辆的行驶路径和交通路况。这类方法属于知识驱动的方法。另一类是数据驱动的方法，通过训练模型学习历史路况和未来路况之间的统计关联进而进行预测。这类方法是目前各大出行科技公司所主要依赖的方法。

业界现有的数据驱动方案，主要以历史交通状况为特征，辅助以部分事件类特征，例如异常天气、体育赛事等，常常难以预测准拥堵的起始时刻，导致预测延迟的问题。以下图中右图为例，横轴代表一天的不同时刻，纵轴代表一条道路的旅行时间。红色曲线代表道路的实际旅行时间，即真值。绿色曲线代表模型提前一小时给出的预测值。可以看到，在拥堵发生的阶段，大约8-9点之间，模型的预测表现出了显著的延迟。

这类问题不能通过单纯升级模型的表达能力来彻底解决，不管是早期的经典机器学习模型，如随机森林、GBDT，抑或是初期的深度学习模型，如stacked autoencoder、sequence-to-sequence model，还是近期提出的基于卷积网络、图卷积网络的更先进的结构等等，就预测效果而言都存在类似的缺陷。

究其原因，从物理上讲，拥堵来源于车流量的增大，现有方案的事件类特征时空颗粒度较粗，不能在分钟级别、路段级别上充分表达未来车流量的信息，也即缺乏一个预示拥堵发生的提前量信号，因此无法从根本上克服这个问题。

随后，冀晨光重点介绍了高德提出的解法。这项研究成果发表在今年的数据挖掘顶会KDD上。

混合时空图卷积网络：能“推导”未来路况的算法

第一步，从高德海量的实时驾车导航数据中预估出每条道路未来的车流量。如下图中左图的所示，在导航开始时刻，以及行中每隔固定的时间段，用户的高德客户端都会与云端的导航引擎进行交互，请求引擎更新剩余旅程的ETA。对应的，在导航引擎侧，根据这同一个ETA，就能预估出单个用户未来贡献的流量值。

接下来，高德对全体用户的未来流量值按道路进行聚合，就获取了未来任一时刻全路网的车流量分布。以下图中右图为例，黄、红、绿三辆车在出发时均使用了高德导航，对应颜色的虚线代表高德给出的规划路线，箭头代表预计到达该道路的时间点。可以看到，在8点05分，三辆车将一同到达灰色方框里的道路。通过这样的方式，高德可以提前几十分钟预判到这条道路在8点05分的车流量为3。实际中，高德导航行业领先的路面渗透率，让这种方式预估的未来车流量能够较好的近似真实的未来车流量。

第二步，高德提出了一个独特的混合时空图卷积网络，简称HSTGCN，能够有效的将这个未来车流量的特征与传统的道路旅行时间特征整合处理。

具体来说，高德提出了一个域转换器结构，将未来车流量特征转换成对应的道路通行时间特征。接下来，一维时域门控卷积从这两部分时间特征上提取出更高维的模式。之后，基于提出的复合关联矩阵的图卷积网络会捕捉住路网上各处拥堵之间的空间关联关系。最后，两个额外的时域门控卷积和全连接网络进一步处理前述信号后进行解码，输出全路网道路未来的通行时间。

直观的讲，HSTGCN可以学习到车流量增大、道路变拥堵的交通动力学规律，能够基于规划的流量，推导出未来路况。这个方案，作为知识驱动和数据驱动方法的有机结合体，兼备了交通仿真和统计学习这两种主流方法双方的优势。

下图是模型布署的工程架构图。从左至右，导航客户端实时上传相关数据。其中路线规划数据经过Blink实时流处理，生成前面提到的全路网未来的流量分布。定位轨迹数据，经过路网匹配和处理，生成各个道路的旅行时间。HSTGCN接入这两个特征源，实时预测、发布未来的交通路况，进而帮助导航引擎更精准的计算ETA和规划路线。

冀晨光介绍了一个模型预测突发拥堵的实例。下图里有上下两张图，分别是HSTGCN和此前学术界的代表性路况预测模型STGCN的预测结果。图的横轴是一天的全部时刻，纵轴是一条道路的旅行时间。蓝色曲线代表真实的路况，橙色曲线代表路况的历史均值，其他颜色的曲线对应模型提前5-15分钟的预测结果。可以看到，HSTGCN克服了上一代方法的不足，很好的解决了突发拥堵的预测问题。

此外，因为HSTGCN的预测是基于规划车流量的，而这个预测值又会影响到下一个时刻的路线规划，所以HSTGCN带来了动态分流、消解拥堵的能力。

应用前瞻：从“路况预测”到“交通调度”

今天，各大出行科技公司所做的路况预测主要是被动式的统计预测，而HSTGCN则为主动式的交通调动第一次提供了工业界可落地的、数据驱动的解决方案。

可以畅想一下未来的情景。路线规划引擎会从今天的单模态规划演变成多模态规划，综合考虑驾车、公交、骑行、步行等多种出行方式。HSTGCN利用规划引擎产出的路线及预估时间，推导出未来路网上的交通状况。接下来，智能调度模块，例如红绿灯相位调控引擎或是高速费调控引擎，基于预估的路况进行决策，决策的结果又反馈回路线规划引擎，干预路线推荐。