基于GPS探测的贝叶斯路径规划装置及方法

摘要

本发明涉及一种基于GPS探测的贝叶斯路径规划装置及方法。本发明方法是采用先验知识推估后验信息的方法来模拟司机的一种先验找路方法；本装置利用贝叶斯分类器将司机的先验推断方法纳入到我们的路径规划装置中，其本身是基于分类器装置对路网做模式识别处理后而形成的路径规划方法。本发明利用这种司机对道路网络的实时交通状况的先验推断，构造了贝叶斯分类器来形成对道路网络的优先识别，基于这种优先识别而形成的一种路径规划装置及方法，它可以根据高峰期、非高峰期的先验知识在不同的交通时段中分别给出不同的最优路径。该装置及方法具有良好的实用性，并可以灵活的集成到各种基于道路交通的导航系统中。

权利要求

1.一种基于GPS探测的贝叶斯路径规划装置，其特征是：主要分为探测端和中心处理端两个部分，其中探测端选择一些熟悉道路交通状况的司机，将GPS探测器分布在这些司机的车辆上；所述的中心处理端包括接收器、中心控制器、路径筛选器、贝叶斯分类器和最优路径计算器几个模块：其中探测端：

GPS探测器，主要是用GPS采集器来对n个司机的行驶轨迹进行探测；

所述的中心处理端：

中心控制器，控制其它的模块之间的数据传送；

路径筛选器，主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；

贝叶斯分类器，根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；

最优路径计算器，根据形成的三种优选道路，实施最优路径搜索计算，得到最优路径结果；

路径存储器，存放路径筛选器建立的“好”路径集；

道路分类存储器，存放贝叶斯分类器分类后形成的三种道路集。

2.一种基于GPS探测的贝叶斯路径规划方法，其特征是包括以下步骤：（1）、探测端用GPS探测器来获取出行经验数据；

（2）、中心控制端从GPS探测器中得到的轨迹数据经过一系列处理而实现路径规划，包括以下步骤：（2.1）用路径筛选器来得到先验上的“好”的路径集：主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；

（2.2）根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；

（2.3）最优路径计算器中计算最优路径，中心控制器将上述三类优先道路集看成三层道路网络输入到最优路径计算器，得到最优路径结果。

3.根据权利要求2所述的基于GPS探测的贝叶斯路径规划方法，其特征是：所述的路径筛选器主要由比较控制器、匹配计算模块以及缓存器三部分组成：a）在匹配计算模块中，根据探测端采集得到的司机的GPS轨迹和记录的出发点和终止点，用地图匹配方法将其匹配到对应的道路路段，并根据相邻的道路路段相接得到每个出发点和终止点之间形成的路径，匹配计算模块得到的路径集输入到比较控制器中；

b）在比较控制器中，先根据每条路径的总长度和GPS记录的行程时间，可以得到其平均通行速度v，通过比较平均通行速度的关系，得到一条先验上“好”的路径，将其纳入”好”的路径集，并放入到路径存储器中。

4.根据权利要求2所述的基于GPS探测的贝叶斯路径规划方法，其特征是：所述的贝叶斯分类器主要由数据分割器、道路特征生成器、贝叶斯分类控制器、道路拓扑检测器和缓存器构成；

a）将“好”路径输入给数据分割器，数据分割器根据路径的时间属性，将其分为高峰期的“好”路径集T1和非高峰期的“好”路径集T2；

b）在道路特征生成器中，对所有的“好”路径集，将所有路径经过同一道路路段e的频次作统计；

c）在道路特征生成器中，计算道路网络上的所有节点对之间的最短路径，并由此得到道路路段e的中介中心性；

d）从道路网络数据中挑选一部分出来作为贝叶斯分类控制器的训练数据，利用贝叶斯分类控制器来对道路路段分类，得到优先道路集、次优道路集和一般道路集；

e）在道路拓扑检测器中，根据步骤d）得到的三个道路集，将其生成的这三类优先道路集放入到道路分类存储器中。

说明书

基于GPS探测的贝叶斯路径规划装置及方法

[0001] 技术领域：

[0002] 本发明涉及一种适合于在实际的交通出行状况下基于先验的推断而采用的一种路径规划装置及方法，特别涉及一种基于GPS探测的贝叶斯路径规划装置及方法。

[0003] 背景技术：

[0004] 当前，全球定位系统（Global Positioning System）已经广泛地在各种车辆上作为定位导航设备应用起来，比如车载导航系统，车辆的定位监控系统，交通部门的浮动车系统等等。另一方面，我们的各种导航系统中的路径优化方法得到的最优路径在实际使用中其规划出来的路径往往是在绝对的时间或者长度度量上的一种最短路径。然而，由于道路的实时交通路况的随机特性，这样在度量意义上的最优路径往往并不是那么符合司机的先验知识，这样的最优路径也往往不是我们真实世界的最优路径。

[0005] 专利（中国专利申请号200410103954.1）是将车辆的时间和速度融合入路径规划的一种方法，专利（中国专利申请号200610036181.9）是一种将路段权值设定为通行时间来实现的一种路径规划方法，从上面这几个专利申请书来看，目前已经有一些关于路径规划装置及方法的专利，现有的关于路径规划的专利仅仅是在度量（长度或者时间）上给出的一种路径最优化方法。这些方法都没有采用基于贝叶斯的先验推断方法来实现路径规划。

[0006] 《测绘学报》2010年8月39卷(404-409页)中公布了一篇文献《出租车经验知识建模与路径规划算法》，虽然有些考虑了出租车的经验信息，但是仅仅是把一些信息用下面的计算公式归算到了道路所属权值上，Wi（t）=[μ1•Ti（t）+μ2•Si]/μ3•Ci(t)[0007] 本质上来说，该公式是将时间和速度信息通过这个公式，将w权值设定到对应的路段上，最后通过传统的dijkstra方法计算最优路径。将经验信息归算到道路权值上做路径规划的方法，在具备实时交通信息的情况下，与传统的最优路径方法的问题是一样的，其无法回避实时交通信息的随机性。该方法并不是一种先验推断方法，因而和采用度量上的最优路径规划的计算在方法上区别并不大。因此，该文献并未形成一种司机的先验信息并根据贝叶斯推断来分类道路集，并据此进行路径规划。

[0008] 从上面分析的现有的路径规划的技术方法来看，这些将速度，长度，通行时间等某种经验信息归化到道路权值的度量上的最优路径方法，并未真正将对路网交通状况非常熟悉的司机的一种先验推断方法纳入到路径规划系统中。

[0009] 发明内容：

[0010] 本发明的目的就是针对现有技术存在的上述缺陷，提供一种基于GPS探测的贝叶斯路径规划装置及方法，本发明方法是采用先验知识推估后验信息的方法来模拟司机的一种先验找路方法；本装置利用贝叶斯分类器将司机的先验推断方法纳入到我们的路径规划装置中，其本身是基于分类器装置对路网做模式识别处理后而形成的路径规划方法。

[0011] 本发明的基于GPS探测的贝叶斯路径规划装置，主要分为探测端和中心处理端两个部分，其中探测端选择一些熟悉道路交通状况的司机，将GPS探测器分布在这些司机的车辆上；所述的中心处理端包括接收器、中心控制器、路径筛选器、贝叶斯分类器和最优路径计算器几个模块：

[0012] 其中探测端：GPS探测器，主要是用GPS采集器来对n个司机的行驶轨迹进行探测；

[0013] 所述的中心处理端：中心控制器，控制其它的模块之间的数据传送；路径筛选器，主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；贝叶斯分类器，根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；最优路径计算器，根据形成的三种优选道路，实施最优路径搜索计算，得到最优路径结果；路径存储器，存放路径筛选器建立的“好”路径集；道路分类存储器，存放贝叶斯分类器分类后形成的三种道路集。

[0014] 本发明的基于GPS探测的贝叶斯路径规划方法，包括以下步骤：

[0015] （1）、探测端用GPS探测器来获取出行经验数据；

[0016] （2）、中心控制端从GPS探测器中得到轨迹数据并通过一系列地处理而实现路径规划，包括以下步骤：

[0017] （2.1）用路径筛选器来得到先验上的“好”的路径集：主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；

[0018] （2.2）根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；

[0019] （2.3）最优路径计算器中计算最优路径，中心控制器将上述三类优先道路集看成三层道路网络输入到最优路径计算器，得到最优路径结果；

[0020] 上述的路径筛选器主要由比较控制器、匹配计算模块以及缓存器三部分组成：

[0021] a）在匹配计算模块中，根据探测端采集得到的司机的GPS轨迹和记录的出发点和终止点，用地图匹配方法将其匹配到对应的道路路段，并根据相邻的道路路段相接得到每个出发点和终止点之间形成的路径，匹配计算模块得到的路径集输入到比较控制器中；

[0022] b）在比较控制器中，先根据每条路径的总长度和GPS记录的行程时间，可以得到单

[0023] 条路径上司机车辆行驶的平均通行速度v单，通过与所有路径通行速度的平均值V平均总体相比较，根据v单≥V平均总体可以得到一条先验上“好”的路径，将其纳入”好”的路径集，并放入到路径存储器中。

[0024] 上述的贝叶斯分类器主要由数据分割器、道路特征生成器、贝叶斯分类控制器、道路拓扑检测器和缓存器构成；

[0025] a）将“好”路径输入给数据分割器，数据分割器根据路径的时间属性，将其分为高峰期的“好”路径集T1和非高峰期的“好”路径集T2；

[0026] b）在道路特征生成器中，对所有的“好”路径集，将所有路径经过同一道路路段e的频次作统计；

[0027] c）在道路特征生成器中，计算道路网络上的所有节点对之间的最短路径，并由此得到道路路段e的中介中心性。

[0028] d）从道路网络数据中挑选一部分出来作为贝叶斯分类控制器的训练数据，利用贝叶斯分类控制器来对道路路段分类，得到优先道路集、次优道路集和一般道路集；

[0029] e）在道路拓扑检测器中，根据步骤d）得到的三个道路集，将其生成的这三类优先道路集放入到道路分类存储器中。

[0030] 本发明的有益效果是：本专利就是利用这种司机对道路网络的实时交通状况的先验推断，构造了贝叶斯分类器来形成对道路网络的优先识别，基于这种优先识别而形成的一种路径规划装置及方法，它可以根据高峰期、非高峰期的先验知识在不同的交通时段中分别给出不同的最优路径。该装置及方法具有良好的实用性，并可以灵活的集成到各种基于道路交通的导航系统中。

[0031] 附图说明：

[0032] 附图1是本发明的装置的原理示意图；

[0033] 附图2是本发明的路径筛选器的示意图；

[0034] 附图3是本发明的路径筛选器筛选“好”路径的流程图；

[0035] 附图4是本发明的贝叶斯分类器的示意图；

[0036] 附图5是本发明的道路集的贝叶斯分类流程示意图；

[0037] 附图6是本发明的最优路径计算流程图。

[0038] 具体实施方式：

[0039] 本装置的具体的实施方式如下：

[0040] 探测端的实施：

[0041] 用GPS探测器来获取出行经验数据。选择n个对需要做路径分析的区域道路网非常熟悉的司机，将GPS探测器装在这n个司机的车上，用GPS来记录其每天的出行数据，包[0042] 括其出行路径的出发点和终止点。这样累积记录他们的出行路径一段时间（比如一个月）后，根据这些对实时道路熟悉的司机车辆上的GPS探测器及其记录，得到n个经验司机的出行GPS轨迹数据。

[0043] 中心处理端实施步骤：

[0044] 整个中心处理端模块间的数据传输由中心控制器来控制，运行的步骤流程也由中心控制器来控制。下面按先后顺序给出中心处理端实现的贝叶斯路径规划方法。

[0045] 1 用路径筛选器来得到先验上的“好”的路径集，本模块主要由比较控制器、匹配计算模块以及缓存器三部分组成，其结构示意图见图2，其流程图见图3；

[0046] 中心控制器从GPS探测器中得到采集的GPS轨迹数据。

[0047] 1a ）在匹配计算模块中，根据探测端采集得到的司机的GPS轨迹和记录的出发点和终止点，用地图匹配方法将其匹配到对应的道路路段，并根据相邻的道路路段相接得到每个出发点和终止点之间形成的路径。匹配计算模块得到的路径集输入到比较控制器中。

[0048] 1b）在比较控制器中，先根据每条路径的总长度 L 和该路径从出发点到终止点之间的行程时间⊿t，由v单=L/⊿t，可以得到单条路径的平均通行速度v单。然后计算某一时段T内GPS的所有行驶速度，根据该时段内所有路径的通行速度的均值V平均总体设定一个阈值。比较v单与V平均总体的关系。如果v单≥V平均总体，则认为该路径为一条先验上“好”的路径，将其纳入”好”的路径集，并放入到路径存储器中；如果v单﹤V平均总体，则认为该路径不是一条先验上“好”的路径，将其舍弃。最后形成完了“好”的路径集后，通知中心控制器将这些“好”的路径集存入路径存储器中。

[0049] 2 用贝叶斯分类器对道路网络做分类，得到三种优选道路集。贝叶斯分类器主要由数据分割器、道路特征生成器、贝叶斯分类控制器、道路拓扑检测器和缓存器这几部分构成，其结构如图4所示，其流程如图5所示。

[0050] 中心控制器从路径存储器中得到的“好”路径集输入到贝叶斯分类器。

[0051] 2a）将“好”路径输入给数据分割器，数据分割器根据路径的时间属性，将其分为高峰期的“好”路径集T1和非高峰期的“好”路径集T2。下面的步骤2b--2e分别对T1和T2实施，得到高峰期和非高峰期不同的三类优先道路集。

[0052] 2b）在道路特征生成器中，对所有的“好”路径集，将所有路径经过同一道路路段e的频次作统计，即不同的路径每经过一次相同的道路路段，其频次属性f(e)加1，f(e)初始值为0。根据所有“好”路径经过道路路段的速度做平均，记为v(e) 。

[0053] 2c）在道路特征生成器中，计算道路网络上的所有节点对之间的最短路径，所有最短路径的总数为N。根据所有的最短路径经过每一个道路路段e的次数c(e)，计算路段e的中介中心性B(e)= c(e)/N。

[0054] 2d）从道路网络数据中挑选一部分出来作为贝叶斯分类控制器的训练数据。按照2b）和2c）中得到的道路e的特征f(e)、v(e)和B(e)来估计贝叶斯分类控制器的参数。确定好了贝叶斯分类控制器参数以后，将所有的道路根据其特征f(e)、v(e)和B(e)利用贝叶斯分类控制器来对道路路段分类，得到优先道路集E1、次优道路集E2和一般道路集E3。

[0055] 2e）在道路拓扑检测器中，根据步骤2d）得到的三个道路集，从E1开始，计算得到E1的最大强连通子网C1。将E1中不在C1的道路重新加入到E2中，计算得到E2的最大强连通子网C2。这样，我们令G1=C1作为优先道路集，令G2=C1+C2作为次优道路集，G3为全部道路网络作为全体道路集。这样，我们就得到由G1、G2、G3形成的三类优先道路集。

[0056] 中心控制器在贝叶斯分类器的步骤完成后将其生成的这三类优先道路集放入到道路分类存储器中。

[0057] 3 根据步骤2中形成的针对高峰期T1和非高峰期T2的分类优先道路集，分别在最优路径计算器中计算最优路径。由于对于T1和T2的道路集，其计算步骤都是一样的，这样，在下面的描述中对T1和T2不作区分。其流程见图6。

[0058] 中心控制器将三类优先道路集看成三层道路网络输入到最优路径计算器。确定待确定的最优路径在路网中的起始点和终止点。在最优路径计算器中实施下面几个步骤：

[0059] 3a)从在第Gi层中分别从起始和终止点处开始正向和逆向搜索最优路径；

[0060] 3b)如果在Gi层正向和逆向搜索中，最优子路径上的节点也存在于对应的Gi-1层中，分别记为Si-1、Ti-1，那么就跳回到步骤3a)，并且i减1，即在第Gi-1中执行步骤3a）。如果在正向与逆向搜索中，最优子路径上没有这样的节点，那么就执行步骤3c）；

[0061] 3c）如果正向搜索的子路径和逆向搜索的子路径不能汇合于同一点，那么继续执行步骤3b），如果可以汇合于一点，那么执行步骤3d）；

[0062] 3d）汇合每层计算的子路径形成最后的经验最优路径。

[0063] 本装置中，探测端设备GPS探测器以硬件的形式装配在所选择的司机车辆上，并可以保存其车辆的GPS轨迹数据。中心处理端装置可以在任何的操作系统平台下，利用任何一种编程语言，利用软件方式来实现，也可以采用合适的硬件来实现，具有良好的实用性，并可以灵活的集成到各种基于道路交通的导航系统中。