(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201611045462.0
(22)申请日 2016.11.24
(71)申请人 广东顺德中山大学卡内基梅隆大学
国际联合研究院
地址 528300 广东省佛山市顺德区大良街
道办广东顺德中山大学卡内基梅隆大
学国际联合研究院
申请人 中山大学　广东药科大学
(72)发明人 邹小勇　王洋　李占潮　戴宗　
(74)专利代理机构 广州粤高专利商标代理有限
公司 44102
代理人 林丽明
(51)Int.Cl.
G08G  1/01(2006.01)
(54)发明名称
一种基于交通指数的随机动态网络交通规
划方法
(57)摘要
本发明公开一种基于交通指数的随机动态
网络交通规划方法，以二叉树结构构建交通网络
模型，用以表示某地区真实的道路情况，统计出
当前交通指数下从起点到目的地的每一条路径
被选择的概率值，每一条路径被选择的概率值为
该路径上各个路段的概率值之积，
然后挑选出最优的路径。本方法提出的随机寻径算法，在交通
网络概率模型中为交通规划提供快速准确的策
略，采用二叉树作为概率模型的逻辑结构，简单
可靠，可以在不同的移动设备和终端上部署，可
移植性强，应用广泛。利用交通指数判断路径状
况，有别于传统的基于图搜索的GPS导航方法，提
供更准确的路况情况。采用了概率方法，为用户
的体规划带来多元化的结果，有效解决了交通
拥堵问题。权利要求书1页  说明书9页  附图6页CN 106530702 A 2017.03.22
C N  106530702
A
1.一种基于交通指数的随机动态网络交通规划方法，其特征在于，包括以下步骤：
S1：以二叉树结构构建交通网络模型，用以表示某地区真实的道路情况，树根节点对应交通网络中的起点，中间节点对应网络范围内的各个位置，叶子节点表示目的地，节点与它的子节点之间为一个路段，从起点到目的地包括一条或多条不同的路径，每条路径包括一个或多个路段，每个路段根据其交通指数设定其被选择的概率值；
S2：统计出当前交通指数下从起点到目的地的每一条路径被选择的概率值，每一条路径被选择的概率值为该路径上各个路段的概率值之积，然后挑选出最优的路径。
2.根据权利要求1所述的基于交通指数的随机动态网络交通规划方法，其特征在于，步骤S1中，通过公式：
P min (a ,b)＝(Max(a ,b)-Min(a ,b))/INT(Min(a ,b))
计算二叉树两个子树的分支的概率值，其中a和b是代表二叉树中两个分支的交通指数，Max(a ,b)函数取a和b中的最大值，Min(a ,b)函数取a ,b中的最小值，INT(a ,b)函数为向下取整函数。
3.根据权利要求1所述的基于交通指数的随机动态网络交通规划方法，其特征在于，所述交通指数在0～5之间。
4.根据权利要求1所述的基于交通指数的随机动态网络交通规划方法，其特征在于，每个路段被选择的概率值在0～1之间。
5.根据权利要求1-4任一项权利要求所述的基于交通指数的随机动态网络交通规划方法，其特征在于，步骤S2中，具体过程为：
S2.1：初始化节点信息，载入交通指数并计算各路段相应的概率值；
S2.2：从根节点开始，根据左右子树的概率值进行随机寻径，选择一条子树作为结果；S2.3：如果计算
到叶子节点，则计算这条路径上的各个路段的概率积，并与最优解进行对比，如果当前路径的概率积比最优解的概率值更高，则将当前路径的数据更新到最优解中；
S2.4：重复步骤S2.1-S2.3，累计达到预设的迭代上限次数时，输出最优解的路径数据。
权　利　要　求　书1/1页CN 106530702 A
一种基于交通指数的随机动态网络交通规划方法
技术领域
[0001]本发明涉及交通规划领域，更具体地，涉及一种基于交通指数的随机动态网络交通规划方法。
背景技术
[0002]城市的交通规划是建立完善综合运输系统的重要保障，对社会的发展和生活质量的提高有重要的作用。为了提高交通效率，各国政府和机构展开了大量的研究工作，美、欧、日等国家已不局限于解决交通拥堵、交通事故、交通污染等问题，而是转向建立更综合的智能交通系统(Intelligent Transportation System，简称ITS)，并在重点发展领域大规模应用。近年来我国在交通规划上的研究和进展保持了高速增长态势，包含智能公交、电子警察、交通信号控制、卡口、交通视频监控、出租车信息服务管理、城
市客运枢纽信息化、GPS与警用系统、交通信息采集与发布和交通指挥类平台等10个细分行业，以获取更精准和有效的数据。
[0003]交通部门发布的信息如图1所示，提供了不同区域的交通指数，以及当前区域的平均车速。交通指数是表征当前及未来一段时间内道路情况的系数，由全市各个路口的信息采集设备(雷达，摄像头，红外和环形感应线圈，以及新一代为安装有全球卫星定位系统和无线通信装置的车辆提供的浮动车交通信息采集方法等)，并通过数据统计和综合分析得到，具有时序性强，动态性高等特点。一般的导航设备是基于GPS制导，会导致所有用户的路线规划都是相同和相似的最优路线，因此无法从根本上避免交通堵塞的发生。
发明内容
[0004]本发明为克服上述现有技术所述的至少一种缺陷，提供一种基于交通指数的随机动态网络交通规划方法，采用二叉树作为概率模型的逻辑结构，简单可靠，可以在不同的移动设备和终端上部署，可移植性强，应用广泛。
[0005]为解决上述技术问题，本发明的技术方案如下：
[0006]一种基于交通指数的随机动态网络交通规划方法，包括以下步骤：
[0007]S1：以二叉树结构构建交通网络模型，用以表示某地区真实的道路情况，树根节点对应交通网络中的起点，中间节点对应网络范围内的各个位置，叶子节点表示目的地，节点与它的子节点之间为一个路段，从起点到目的地包括一条或多条不同的路径，每条路径包括一个或多个路段，每个路段根据其交通指数设定其被选择的概率值；
[0008]S2：统计出当前交通指数下从起点到目的地的每一条路径被选择的概率值，每一条路径被选择的概率值为该路径上各个路段的概率值之积，然后挑选出最优的路径。[0009]在一种优选的方案中步骤S1中，通过公式：
[0010]P min(a,b)＝(Max(a,b)-Min(a,b))/INT(Min(a,b))
[0011]计算二叉树两个子树的分支的概率值，其中a和b是代表二叉树中两个分支的交通指数，Max(a,b)函数取a和b中的最大值，Min(a,b)函数取a,b中的最小值，INT(a,b)函数为
向下取整函数。
[0012]在一种优选的方案中，所述交通指数在0～5之间。
[0013]在一种优选的方案中，每个路段被选择的概率值在0～1之间。
[0014]在一种优选的方案中，步骤S2中，具体过程为：
[0015]S2.1：初始化节点信息，载入交通指数并计算各路段相应的概率值；
[0016]S2.2：从根节点开始，根据左右子树的概率值进行随机寻径，选择一条子树作为结果；
[0017]S2.3：如果计算到叶子节点，则计算这条路径上的各个路段的概率积，并与最优解进行对比，如果当前路径的概率积比最优解的概率值更高，则将当前路径的数据更新到最优解中；
[0018]S2.4：重复步骤S2.1-S2.3，累计达到预设的迭代上限次数时，输出最优解的路径数据。
[0019]与现有技术相比，本发明技术方案的有益效果是：本发明公开一种基于交通指数的随机动态网络交通规划方法，以二叉树结构构建交通网络模型，用以表示某地区真实的道路情况，统计出当前交通指数下从起点到目的地的每一条路径被选择的概率值，每一条路径被选择的概率值为该路径上各个路段的概率值之积，然后挑选出最优的路径。本方法提出的随机寻径算法，在交通网络概率模型中为交通规划提供快速准确的策略，采用二叉树作为概率模型的逻辑结构，简单可靠，可以在不同的移动设备和终端上部署，可移植性强，应用广泛。利用交通指数判断路径状况，有别于传统的基于图搜索的GPS导航方法，提供更准确的路况情况。采用了概率方法，为用户的体规划带来多元化的结果，有效解决了交通拥堵问题。
[0020]本技术根据深层概率模型的计算性质，将交通指数转化为对道路情况判断分析的概率值，并在不
同的网络范围(对应实际的交通距离)内提供不同置信度的结果。为了解决体用户得到的局部最优解相似的问题，构建概率模型为整个网络中所有用户提供避免交通堵塞的全局最优解。本方法采用的交通指数概念源于深圳市交通局发布的指数体系，利用现有的道路信息采集实时或周期路况，然后经过数据分析处理得到的衡量当前路况的综合性数据，可以对区域内的道理情况进行判断和预测。但是由于城市交通网络的规模十分巨大，而且网络细节众多，时序性很强，如何在较短的时间内提供准确有效的分析结果是现阶段工作的难点。
附图说明
[0021]图1为交通部门发布的信息图。
[0022]图2为某地区真实的道路情况图。完全二叉树算法
[0023]图3为图2交通网络的抽象表示图。
[0024]图4为图3中某一个区域的细节描述。
[0025]图5为图3区域的二叉树化表示图。
[0026]图6为随机寻径算法的流程图。
[0027]图7为随机寻径实验的迭代性能分布图。
[0028]图8为不同期望系数分组实验的准确率图。
[0029]图9为不同期望系数分组实验的耗时图。
[0030]图10为不同分组实验的准确率图。
具体实施方式
[0031]附图仅用于示例性说明，不能理解为对本专利的限制；
[0032]下面结合附图和实施例对本发明的技术方案做进一步的说明。
[0033]实施例1
[0034]1、交通网络模型构建
[0035]构建概率模型需要选择合适的图模型，而二叉树作为一个连通的无环图，有着简单的逻辑结构和优秀的表示能力，在表征地图网络时有着强大的处理能力。在计算机科学中，二叉树是每个节点最多有两个子树的树结构，如图2-5所示。图2为某地区真实的道路情况；图3为对该交通网络的抽象表示，用
于转化为计算机可以处理的数据结构；图4对图3中某一个区域的细节描述；图5为对这个区域的二叉树化表示。在图3中的抽象网络出现了不同的路口分道情况(例如岔道口和十字路口)，可以通过线性转换将其转换为统一的结构图4。
[0036]另外，由于每个路口(对应图中节点)在计算机中都使用邻接表存放相关信息，因此为了避免冗余的计算，在图5中将重复出现的路段使用带颜的方框标记(区别于没有重复的圆圈)出来，除终点外其余方框都使用一条线，代表后续的计算与前面的计算重复，直接使用之前计算的结果即可。
[0037]在图4所示的结构中，边上标注的概率值源于模拟的交通指数，仿照交通指数的发布形式随机在0～5之间赋值作为模拟生成的交通指数，并通过公式：
[0038]P min(a,b)＝(Max(a,b)-Min(a,b))/INT(Min(a,b))
[0039]计算出二叉树两个子树中路况较好(交通指数更大)的分支的概率值，其中a和b是代表二叉树中两个分支的交通指数，Max(a,b)函数取a和b中的最大值，Min(a,b)函数取a,b 中的最小值，INT()函数为向下取整函数。例如当(C)中A->B的交通指数是3.6，A->C的交通指数是2.1，则有：
[0040]
[0041]P(A→B)＝1-P(A→C)＝25％
[0042]图5是由图4转化得到的二叉树，树根(A节点)对应交通网络中的起点，中间节点(B ～H)对应网络范围内的各个位置，叶子节点(I)表示目的地。通过随机寻径算法(RRM)可以统计出当前交通指数下每一条路径被选择的概率值，然后挑选出最优的路径。由于一条路径是由不同的路段组成的，不能根据某一段路程的拥堵情况而将其视为该路段的整体情况，因此对于一条路径来说该路径上所有的路段都要考虑。可以看到在图4中，从A节点到I 节点可以有很多条不同的路径，例如：
[0043]
[0044]选择不同路段的组合会导致不同的路径长度和时间消耗。而通过交通指数计算得

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。