路况是地图中最重要的功能之一。导航规划出来的路线上一般覆盖了不同的颜色，比如绿色、红色、黄色、代表了不同路段的拥堵级别，这样覆盖了颜色的路线我们称之为蚯蚓线。不同的颜色代表不同的拥堵级别，比如绿色代表畅通、黄色代表缓行、红色代表拥堵、紫色代表严重拥堵，我们称之为路况。那么路段的路况是怎么计算来的呢？
- 政府数据：政府可以通过摄像头等技术来监控道路的拥堵情况。
- 第三方服务商：比如四维这样的第三方，他们每分钟会提供所有路段的拥堵级别。当然四维内部的数据可能也是通过政府拿到数据的。
- 基于用户上报：地图服务商通过用户的位置上传信息，来预测路段的拥堵程度。
本文将着重介绍基于用户上报的路况预测方法。一般来说，导航规划出来的路线中包含有很多link（对应真实世界中的路段），一个link路段可以认为是地图处理的最小单位，这些link之间有连接关系（对应真实世界的道路连接）。为了画出蚯蚓线，我们需要预测所有link的路况。路况和通行速度呈直接关系，通行速度越快，代表路况通行越顺畅。所以最终问题变为怎么得到link路段的平均通行速度？
实时路况预测
实时路况是指当前时间的路况，一般以1分钟为一个时间段，实际中实时路况拿的是上一分钟的路况信息。因为用户导航时候需要不断的上传位置信息，位置信息中会包含有GPS位置、GPS速度等，所以地图服务商的后台每时每刻可以拿到大量用户上传的位置信息，然后根据GPS位置将其绑定到对应的link上，GPS速度就可以认为是该link的一个通行速度。如果一条link获得了多个GPS位置的绑定，可能会有多个通行速度，然后做平均就可以得到link的最终通行速度。
link的通行速度会每分钟根据上一分钟的数据做更新，同时需要过滤掉那些噪音数据（行人上传、停车上传等），处在导航行程中的数据最佳。
未来路况预测
有时候实时路况并不能满足需求，比如对于长距离导航（2小时）来说，有可能走到末尾link的时候实时路况早已发生了变化，这时候我们就需要去预测未来某个时刻某条link的路况。有以下几种方法：
- 历史数据拟合：如果该link历史上在该时刻都是拥堵的，那么未来在该时刻大概率也是拥堵的。所以可以对该link前几周在该时刻的通行速度做平均，平均数认为是该link的未来在该时刻的通行速度。当然也可以使用加权平均、加权平滑等手段。
- 通行速度预测：历史上该link在该时刻的通行速度认为是机器学习的特征，比如使用上周、上上周、上个月、上一年的通行速度，另外该link的一些静态属性也可以作为特征（长度、宽度、车道数等），模型使用xgbt或者fm的，损失函数使用MAPE（预测通行速度和真实通行速度的误差百分比），这样就可以训练出来一个预测通行速度的模型。
- 序列预测：历史数据可以看做是一个时间序列，进而我们可以使用RNN、LSTM等序列深度学习方法，或者TCN时间卷积网络来根据历史序列数据预测未来的通行速度。
- 空间特征：上面我们仅用到了历史上的数据，而实际上link和周围的link之间是有关系的，一般来说如果周围的link都拥堵了，该link大概率也会拥堵。所以可以将整个路网看成一张图，link是图中的节点，link之间的连接连接关系是图中的节点连接关系，进而我们就可以使用图神经网络的技术（GCN）来预测link的通行速度。
- 空间+时间：将空间特征和历史序列特征相结合，比如先使用GCN对link进行编码，然后再使用RNN等序列方法对link进行预测。