基于层次式匹配的最佳路径匹配算法

[摘 要] 提出了以分段的轨迹数据为基础，结合时空数据挖掘技术，挖掘基于带时效的频繁模式。并基于这个频繁模式给出行者提供最佳的行车路线。同时，为了提高算法效率，提出了一种基于层次式模式匹配的思想，用分层的思想来过滤大量模式之间的匹配。

[关 键 词] 路径规划；交通控制；轨迹聚类

[中图分类号] G642 [文献标志码] A [文章编号] 2096-0603（2016）07-0129-01

一、引言

随着电子地图和导航系统的迅速普及，城市内出行变得越来越方便。但是现有导航系统的缺陷——单纯以几条固定路径的导航选择并不能让很多出行者绕开拥堵路段，而且还使得某些拥堵路段更加拥堵。另外，大量的定位系统使各个系统保存了大量的轨迹数据，如何从这些轨迹数据中挖掘有效信息，从而给不同爱好的出行者提供更加合适的出行线路是当前城市计算领域研究的热点之一。

路径优化是路径规划的核心问题，目前最有影响力的流行算法是Dijkstra在1959年提出的最短路径算法，Dijkstra算法，用于寻找两个点之间的最短路径。但是由于其算法的计算复杂度太高。很多学者对该算法进行了改进，提出了基于启发式搜索的A*算法以及基于记录历史路径的D*算法。因此，在城市内汽车保有量的不断剧增，以及影响交通情况的诸多因素影响下，上述研究方案在实际使用过程中并不能发挥很好的作用。

二、算法框架

本课题旨在以城市内的出租车定位轨迹数据为基础进行数据挖掘，挖掘城市内两个站点之间的最佳路径。为了实现这个目标，本文将从两个目标角度对出租车定位数据进行挖掘。首先，根据轨迹数据统计每个路段在不同时间段的进度和出度，并在此基础上计算基于信息熵的聚类分析，以构成整个城市的不同交通集中区域；接着，根据区域间的相连轨迹固定每个区域之间的最短距离，结合每个区域所在位置到区域出口之间的路径，就可以得出两个点之间的最佳路径规划。

为了提高检索效率，本文采用分层处理方式来提高检索速度，即按不同层次对整个城市进行逐层划分，从而使得整个城市的空间区域变成一个典型的树结构。按照上面的实现思想，本系统的实现流程如下：

（一）数据初始化

系统先将出租车轨迹数据（定位信息）按照每个路段划分成路径片段，即出租车经过每个路段的信息（路段编号，进入时间，离开时间），并导入公路网络信息。

（二）基于信息熵的区域划分算法

每个路段都有入度和出度（由于路段内有停车场或小区，单位时间内出度并不等于入度），如果将单位时间内每个路段的出入度之差作为该路段在该单位时间的信息熵，那么一些相邻路段之间的组合就是区域，如果将每个区域的向外的出入度之差作为该区域的信息熵，那么城市区域的划分就是将这些路段组合起来，使得整个系统的信息熵最低，就是我们所需要的区域划分。

（三）构建基于轨迹频繁模式挖掘和层次匹配的最佳路径模式库

按照传统的轨迹数据挖掘算法将出租车轨迹数据进行频繁模式挖掘，然后将挖掘获得频繁模式来构建两个点之间的最佳路径。其实现过程可以分为以下几个步骤：

1.按照上一个阶段获取的区域，结合历史轨迹数据，挖掘任何两个区域之间在不同时刻的最佳频繁路径，构建模式库；并确定每个区域连接其他区域的出入口，将其定义为关键点。

2.根据轨迹数据挖掘区域内不同时刻内、每个路段到每个关键点的最佳频繁路径模式。

3.上述两个模式集合构成整个最佳路径模式库。

（四）层次式最佳路径模式库的搜索

1.一旦用户输入起始位置和目标位置之后，系统会自动根据当前时间以及对应特征（比如周末、非周末等）进行路径频繁模式匹配。整个过程将以顶层为参数按照下面的流程递归调用。

2.将传入层作为当前层，系统按照输入的起始点和终点判断两个点是否处在同一个子区域。

3.如果两个点处在同一个子区域，且该区域已经没有子区域，那么直接对起始点和目标点进行匹配；如果匹配，则返回此两个点的匹配路径；如果还存在子区域，则递归进入下一层。

4.如果没有找到，则直接使用百度地图的路径导航。

随着电子地图、移动设备和定位技术的迅猛发展，越来越多的导航系统开始左右人们的出行。但是当前大多导航系统还停留在一些规定好的固定路径作为导航线路，这使一些拥堵路段变得更加拥堵。而本文则是采用历史轨迹数据挖掘，将大多数人采用的行走路径作为导航路径，这种方案给出行者提供更加灵活多变的优化路径。同时，为了提高历史路径的匹配效率，本文还采用层次式匹配思想来提高匹配效率，提供算法的实时性。

参考文献：

严德志，于凤芹.基于最佳路径组合搜索策略的匹配追逐算法[J].微计算机信息，2007（15）.