大数据驱动下的新一代高速公路智慧诱导技术

来源：核心期刊咨询网时间：2019-12-14 11:2612

摘要：摘 要：为了解决高速公路出行路径选择问题，基于图论模糊算法，提出了大数据下的智慧诱导技术。首先对高速路网在路径诱导的实时性、线路规划的精准度和算法的适用性方面进行优化;其次通过利用貪心算法和整体寻优算法，对经典路径诱导算法进行研究和比选;最后

　　摘 要：为了解决高速公路出行路径选择问题，基于图论模糊算法，提出了大数据下的智慧诱导技术。首先对高速路网在路径诱导的实时性、线路规划的精准度和算法的适用性方面进行优化;其次通过利用貪心算法和整体寻优算法，对经典路径诱导算法进行研究和比选;最后针对高速路网提出基于大数据动态规划的路径诱导技术，采用大数据、内存计算、图计算和AI结合的方式来实现大数据的动态实时路径诱导。研究结果表明，智慧诱导技术可主动为有不同诉求目标的出行者提供实时最优的方案选择，解决复杂路网下动态路径的合理诱导问题。所提出的方法可实现大数据驱动下的智慧诱导，对进一步提升公路智能化和精细化管理水平具有借鉴意义。

　　关键词：人工智能其他学科;大数据;图论;动态规划;智慧诱导
 

　　《大数据时代》(月刊)创刊于2016年，杂志是经国家新闻出版广电总局特别批准，落户“中国数谷”的国内首批大数据专业期刊。

　　公路出行需求的猛增致使路网交通拥堵频繁发生，恶劣天气或突发事件导致的路段瘫痪屡见不鲜，降低了公众的出行体验。近年来随着路网规模的不断扩大，路网结构日趋复杂，路网交通流分布出现不均衡的现象，造成了道路资源的浪费[1]。在信息技术飞速发展的今天，如何从方便公众出行、提高路网通行效率出发，利用先进技术从大数据中挖掘有价值的信息，为公众提供更加实时和精准的在线诱导服务[2]，提升公路智能化服务水平[3-4]，是高速公路管理部门亟需解决的问题。

　　1 路径诱导算法选择综述

　　图论是路径诱导算法的理论基础，可以把高速网络作为一个收费站节点、服务区节点和道路(有向)边组成的网络图来进行研究。

　　高速路网参与者包括总体参与者(如路网管理人员)、局部参与者(如路段管理人员)和个体参与者(行驶车辆个体)等不同的角色。对于p个节点的图G，每类角色对路径诱导的需求都可以视作对G上p阶最小支撑树问题解的寻求计算。

　　路径诱导算法是路径诱导技术的核心，常见的经典路径诱导算法一般分为贪心算法和整体寻优算法。

　　1.1 贪心算法

　　贪心算法(又称贪婪算法)是指在求问题答案时，总是作出在当前看来是最好的选择。贪心算法不能得到所有问题整体的最优结果，但对一定范围的许多问题能产生整体最佳解或者是整体最优答案相近解。

　　这一类算法有以下特点：

　　1) 可能最后答案不是最佳;

　　2) 得不到最大或最小解答案;

　　3) 在一定条件下得到可行解的集。

　　对于[WTBX]p个节点的图G，贪心算法可以作为G上p阶最小支撑树的问题解。显然，在w(T)的迭加过程中，w(e)是不能发生变化(处于静态)的。

　　在此只针对最常用的Dijkstra算法和K-最短路径算法进行介绍。

　　1.1.1 Dijkstra算法

　　Dijkstra算法是典型最短路径算法，是一种集中式的静态算法，算法解决的是图中目标源点到其他顶点的最短路径问题。Dijkstra算法既有优点也有缺点。优点是算法简明、能得到局部最优解，缺点是效率低、运算中占用空间大。算法的计算复杂度为[WTBX]O(n2)，如果边数远小于n2，对此可以考虑用堆优化把复杂度降为O(nlog(n))。

　　Dijkstra算法是一个真正意义上的快速(有效)算法，它不仅用于找出电脑网络中一个节点到其他节点间的最短路径，还可以解决一个网络系统中的短圈问题(计算图中的最短圈)[5]。

　　1.1.2 [WTBX]K-最短路径算法

　　在计算实时性的大型交通网络中，最常用K-最短路径算法，该算法能满足用户出行，提供不同路径进行选择，这是一种非确定性的复杂算法，结果往往是给出很多条比较接近的路径，有可能存在重复路段，甚至产生环路。

　　1.2 整体寻优算法(Floyd[6]算法)

　　这种算法能找到全局最优答案，并且大量用于计算各种优化问题。Floyd算法需要建立邻接表或者是邻接矩阵，计算复杂度为O(n3)，存储复杂度为O(n2)，需要耗费巨大的计算和存储资源。

　　对于低阶稠密图，Floyd算法是有效的;对于高阶稠密图，Floyd算法的成本是巨大的，这也是全局最优的代价。

　　但对于高阶稀疏图，Floyd算法的计算可以优化到O(n2)甚至O(nlog(n))， 存储复杂度也可以优化到O(nlog(n))。

　　1.3 高速路网下的路径诱导算法选择

　　上述经典算法对于静态下的路网G是可以生效的，可有效用于网络建设规划、地图导航等以出行距离最短作为最优目标的场景。针对高速路网，主要采用类Floyd的全局优化算法进行动态路径规划与寻优。但由于高速路径诱导涉及多方参与者，不同参与者有不同的目标诉求，具体有以下几种。

　　1)以个体/总体/局部出行距离最短作为最优目标，这类目标比较直接、直观和常见。

　　2)以个体/总体/局部出行时间最短作为最优目标，这类目标在拥堵时期/时段比较常见。

　　3)以个体/总体/局部出行费用(成本)最低作为最优目标，这类目标和1类目标关联性很强，但出行成本并非仅仅包含通行費用。常用于节假日、拥堵时段、重大事件/事故发生时，对于大车的诱导有积极效果。

　　4)以个体/总体/局部安全影响与事故概率作为最优目标，这类目标在恶劣天气、重大事件/事故发生时具有重要意义。

　　5)以路网费用损失作为最优目标，这类目标主要用于理论规划和研究分析。

　　6)以客户的安全快捷体验作为最优目标，这类目标在重大事件(如冬奥会出行保障)发生时比较常见。

　　实际应用中常根据受众的不同设置不同的目标，组合2个或多个目标来进行寻优，并结合时间周期考虑短期/长期目标等等。这些路径上的权函数其实是非常复杂的，给经典算法带来很大的挑战，通过对路径的评估计算进行动态学习而采用的人工智能技术应运而生。

　　高速网络作为一个收费站节点、服务区节点和道路(有向)边组成的网络图，由于高速公路的封闭性和有向性，可以看作一个[WTBX]p阶稀疏图(p值在1 000左右)。采用高阶稀疏优化的Floyd算法，计算和存储复杂度可以优化到O(nlog(n))[7]。

　　2 基于大数据动态规划的路径诱导技术实现

　　2.1 基于大数据的动态实时路径诱导计算框架

　　根据高速路网的有限阶数和稀疏特点，采用Floyd的全局优化算法进行动态路径规划与寻优。在实际应用中，由于要保障数据处理的准确性、实时性和可用性，采用大数据+内存计算+图计算+AI的方式来实现基于大数据的动态实时路径诱导。

　　基于大数据的动态实时路径诱导计算框架如图1所示。

　　底层是大数据平台基础设施adoop DFS数据库及关系数据库管理系统(RDBMS)和Spark，之上是GraphX和MLlib，Tensorflow计算引擎。

　　通过诱导路径计算模块来实现路网整体/局部/个体的实时诱导计算。由于p的有限性，通过采用高阶稀疏优化的Floyd算法[8]，把全路网装入Spark RDD成为可能，这一空间换时间的策略大大降低了计算复杂度，使得车主通过APP/网站/微信/96122等实时获得最优路径成为可能。

　　诱导路径计算模块的效果取决于图论的模型，[WTBX]w(t)权函数/组是模型的重要构成元素。w(t)权函数组并不一定都采用简单的带权加法复合模式，其复合特征可能是复杂的，还可能受到不同时间、不同区域、不同事件的影响。采用RLS(reinforcement learning system)强化学习技术计算学习不同时间、不同路段、不同路况下的函数组，并以5 min为周期进行不断地迭代计算、更新、评估与学习。

　　强化学习是机器学习的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。其灵感来源于心理学的行为主义理论，即有机体如何在环境给予的奖励或惩罚的刺激下，逐步形成对刺激的预期，产生能获得最大利益的习惯性行为。这个方法具有普适性，因此在其他许多领域都有研究，例如博弈论、控制论、运筹学、信息论、仿真优化、多主体系统学习、群体智能、统计学以及遗传算法。在运筹学和控制理论研究的语境下，强化学习被称作“近似动态规划”(approximate dynamic programming，ADP)[9]，在最优控制理论中也有较广泛的应用。

　　高速路网下，路段和车辆都可以类似智能体(Agent)“试错”的方式进行学习，通过与环境进行交互获得奖赏(价值目标)指导行为[10]。强化学习不同于连接主义学习中的监督学习，主要表现在强化信号上，强化学习中由环境提供的强化信号是对产生动作的好坏作一种评价(通常为标量信号)，而不是告诉强化学习系统RLS如何去产生正确的动作。

转载请注明来自：http://www.qikan2017.com/lunwen/lig/15022.html