批量

随着城市规模的不断扩大和便民业务的发展，行车导航、共享汽车和物流派送等应用已经深入人们日常生活之中。这些应用都不可避免地需要使用GPS、北斗等定位系统，进而产生了大量的轨迹数据。然而，普通民用GPS定位系统上传的位置数据会由于许多缘故发生与物体的实际地理位置不同的现象，产生了米级别的误差，一般在10米以内。此外，在数据传输、存储和耗电的条件限制下，导致轨迹点采样频率不宜过高。因此，以上因素导致采集到的移动对象位置与其实际所在道路之间有一定距离偏差。为了使接收到的位置数据可以真实反映移动对象的运行轨迹，需要进行轨迹的各种预处理工作，其中地图匹配是一项十分重要的工作。 一、地图匹配 地图匹配是将存在误差或漂移的GPS观测点匹配至路网上的算法，它常用于还原观测点的真实位置和移动物体的运动轨迹。如图1，地图匹配算法将采集到点1、2、3映射到路段上。地图匹配可分为离线和实时两种处理方式：离线方式接收过去一段时间观测到的批量轨迹数据，并计算输出全量轨迹的最优匹配结果。其优势在于准确度高。然而，它的处理过程十分耗时，因此，面对监测和追踪等需要实时返回计算结果的场景难免力有不逮；实时地图匹配则可以很好地弥补离线处理时延大的缺陷。目前，基于HMM的实时地图匹配算法[2]被广泛使用于很多业务场景中,如公交车实时位置播报、快递员配送位置跟踪。以危化品运输车辆的监管为例，危化品运输车若偏离原报备路线，通过实时的地图匹配可以在第一时间获取其异常行为及最新位置，实现了对危化品车辆行驶路线的实时监测。barefoot [1]是一个开源项目，它基于实时地图匹配算法提供了实时地图匹配服务。本文接下来主要从算法思想和实现思路两方面介绍开源项目barefoot中的实时地图匹配服务。 图1 地图匹配示意图 二、算法思想 Barefoot 是一个开源的Java项目，它提供了离线/实时地图匹配及空间分析等服务，其中实时地图匹配的实现思路以Goh[2] 提出的算法作为参考。如图2所示，Barefoot提供的实时地图匹配演示图。 图2 实时地图匹配演示图 Goh[2]提出的算法基于隐马尔可夫模型(HMM)，并采用可变滑动窗口进行回溯计算，实现了高精度低延时的实时地图匹配。 其主要流程大体分成三步， 1）寻找候选路网点，2）计算发射和转移概率，3）获取计算结果。 1）寻找候选路网点 寻找候选路网点是指，针对每一个轨迹点z_t，找到距离z_t指定距离(默认为50m)的路段，计算每条路段上距离z_t最近的位置，即为候选路网点。候选路网点通常为轨迹点z_t在对应路段的垂直投影点或路段的端点。 2）计算发射和转移概率 获取到轨迹点z_t对应的候选路网点集合S_t后，以z_t到每一个候选路网点的距离和GPS定位误差为参数，计算候选路网点的发射概率P(z_t |s_t)；再针对上一时刻的候选路网点集合S_(t-1)与本次集合S_t中的每一组候选点，以两个候选点之间最短路径的长度作为主要参数计算这两点之间的转移概率。 3）获取计算结果 概率计算完成后，通过在线Viterbi算法检验是否存在结果点，并返回到达该点的最优路径。 图3 HMM算法 在HMM基础之上，barefoot扩展了两种概率模型：过滤概率和序列概率。其中，过滤概率 用以计算在已观测到轨迹点序列 的条件下，最可能符合真实情况的路网点 序列概率 则在已观测到轨迹点序列 的条件下， 计算在路网上到达点 最可能的路径。 需要注意的是，在转移概率和序列概率的计算过程中，需要使用历史轨迹点对应的候选路网点集合作为参数。因此，barefoot采用了可变滑动窗口来保存历史状态。可变滑动窗口指的是窗口中可容纳的路网点集合数固定，而总路网点数量取决于每个路网点集中的点数，是可变的值。当接收到一个新轨迹点时，可变滑动窗口向前扩展一位，同时根据配置中的窗口上限参数来判断是否需要清除当前窗口中的历史路网点集。Barefoot 提供了状态更新TTL、路网点集合数量上限k和时间段上限τ 三个窗口配置参数用于配置路网点集合数。 三、实现思路 Barefoot通过启动tracker server接收轨迹点，并发布计算结果。tracker server根据配置文件中的参数初始化指定容积的线程池开源地图，并为每一个发送数据的客户端分配一个处理线程T。T会持续接收客户端发送的轨迹数据，并将计算结果发送回客户端。当客户端长时间没有向tracker server发送消息时，对应的连接将被中断。在以上流程中，耗时较长的计算部分由处理线程T决定是否进行异步计算。 为实现以上计算步骤中的空间范围查询和最短路径规划，barefoot需要在内存中维护路网结构。它使用的方法是通过查询读取数据库中的路网表，并根据道路线的属性值构建路网有向图和带有道路线空间范围的四叉树索引来实现最短路径规划。在空间查询获取候选路网点时，使用索引获取空间范围内的道路线id，并在道路线上通过插值计算出与轨迹点距离最近的候选路网点的坐标。 图4 候选点 针对每个轨迹点，barefoot将其对应的候选路网点集合保存至时间窗内。时间窗使用优先队列(PriorityBlockingQueue)实现，在提供超时清理和新增入队功能的基础上，起到保证线程安全的作用。时间窗内的候选路网点集合通过链表相连，方便获取到每个路网点在上一状态中的关联点，以及本集合中最可能为真的目标路网点(如图4中加粗的点)。本次候选路网点集合更新的同时，历史点集合中既不是目标点又与后继路网点无关联的点将被移除。 四、测试结果 Barefoot...