孙金海

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

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

中图分类号：TP181   文献标志码：A

Abstract：In order to solve the problem of freeway travel route selection， based on graph theory fuzzy algorithm， an intelligence induction technology driven by big data is proposed. Firstly， aiming at the real-time performance of route guidance， the accuracy of route planning and the applicability of the algorithm are improved. Secondly， the classical route guidance algorithms are researched and compared by using the greedy algorithm and the overall optimization algorithm; At last， a new route guidance technology based on large data dynamic programming is proposed for high-speed road network. The technology combines large data， memory computing， graph computing and AI to realize dynamic real-time route guidance based on large data. The result shows that the intelligence induction technology actively provides real-time optimal scheme selection for travelers with different demands， and solves the problem of reasonable route guidance under complex road network. The research method can be used for reference to realize the intelligent induction driven by big data and to further improve the level of highway intelligent and fine management.

Keywords：artificial intelligence other disciplines; big data; graph theory; dynamic programming; intelligence induction

公路出行需求的猛增致使路网交通拥堵频繁发生，恶劣天气或突发事件导致的路段瘫痪屡见不鲜，降低了公众的出行体验。近年来随着路网规模的不断扩大，路网结构日趋复杂，路网交通流分布出现不均衡的现象，造成了道路资源的浪费[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如何去产生正确的动作。

RLS对外部环境提供的信息依赖很少，必须靠自身的经历进行学习。通过这种方式，RLS在行动-评价的环境中获得知识，改进行动方案以适应环境。例如冬奥会前夕，可以事先通过模拟演练和试错获得路网上的权函数策略，结合路网实际状况计算冬奥会期间最佳的诱导路径。

2.2 基于大数据的动态实时路径诱导决策分析

动态实时路径诱导决策分析是为路网中实时发生的重大突发事件[11]产生的，如：在交通事故、交通拥堵等对路网通行能力造成影响的情况下，基于上述大数据的动态实时路径诱导计算框架，可以构建事故下路网影响分析模型。

在高速公路交通中，交通事件影响分析是一类重要的决策分析类型。主要包括两类事件：一类是突发交通事件，比如交通事故、突发恶劣天气等;一类是交通管制、道路养护等主动干预事件或预期发生事件（如节假日的影响）[12]。通常采用历史类似事件数据统计分析方法或交通仿真方法对事件的影响进行分析[13]。通过影响分析，得到相关路段、时段的交通事件的影响评估，包括影响的范围、影响程度等。

发生交通事故时段的路网影响分析模型如图2所示。

在事故影响分析模型中，通过大数据平台采集流量、路况、气象、事故等，以形成各类交通事件。基于这些历史事件，大数据平台进行事件影响的初步分析，并结合当前和未来预测的断面流量数据进行分析，获得交通事件的影响数据。

根据上述突发事件影响分析模型输出受影响路段的通行能力和拥挤程度结果，包括：受影响路段拥堵长度、拥堵时长、流量、平均速度、上游入口匝道流量、平均速度等，与设置的是否触发处置措施的阈值

相比较，小于阈值则不做任何处理，大于或等于阈值则根据具体值域范围，触发启动对应的交通诱导分析流程，实现在线的实时路径诱导分析，并通过最优路径算法找出所有可行路径中的最优路径，自动生成诱导建议，以便能够在对高速运营产生尽量小的影响下及时进行合理路径的诱导来疏散交通流[14]。

示例：某路段发生事故造成拥堵情况下的动态路径诱导决策分析模型如图3所示。

同时结合受影响范围内的交通诱导牌、服务区等设备设施的可用性，分级预告突发事件，给即将进入事发路段的车辆提供绕行路径、告知信息等，减少突发事件的不良影响[15]。

3 大数据驱动下的动态路径诱导技术应用

基于大数据动态规划的路径诱导技术研究，针对不同出行者的出行需求綜合考虑费用、时间、距离、天气、车流量以及路况等因素，从提高整个路网的通行效率和出行体验为出发点，采用强化学习技术实现基于大数据的实时诱导路径最佳方案的动态选择，既保证了路网最大限度的有效利用和畅通，实现了路网经济效益的最大化，又使得管理部门在平衡路网交通流的前提下，为公众提供更为精准和实时的诱导路线，使智慧诱导下的主动服务以及智能化管理成为了可能。图4是采用基于大数据动态规划的路径诱导技术实现交通诱导决策支持系统的应用结果展示示例。

4 结 语

基于大数据动态规划的路径诱导技术，实现了交通诱导决策支持系统，为不同的出行者提供了实时诱导路径最佳方案的动态选择，既保证了路网最大限度的有效利用和畅通，又使路网的经济效益最大化，进一步提升了公路智能化和精细化的管理水平。

由于路段信息采集手段有限，数据不尽完善，数据采集密度及精准度有待提高，给出行的精准服务带来一定的困难，如何利用ETC使这些问题得到逐步改善和加强，将是以后的研究方向。随着国家交通强国战略的实施，以及交通主管部门智慧公路政策的逐步落地，引导司乘人员实现智慧出行，实现更加智能化和精细化的交通管理是大数据时代下智慧高速公路建设的主旋律。

参考文献/References：

[1] 李朝衍. 探讨智慧交通信息诱导系统的关键技术. 通讯世界， 2017（22）：54-55.

[2] 李强， 刘晓峰. 智慧交通信息诱导系统关键技术的研究. 电视技术， 2014， 38（21）：73-75.

LI Qiang， LIU Xiaofeng. Research on key technologies for intelligent transportation information induction system. Video Engineering， 2014， 38（21）：73-75.

[3] 杨朋飞. 基于综合交通诱导的智能公共交通信息服务系统研究[D]. 青岛：青岛科技大学，2009.

YANG Pengfei. Research Into the Information Service System for Intelligent Public Transportation Based on Integrated Traffic Guidance[D].Qingdao：Qingdao University of  Science and Technology，2009.

[4] 崔倩倩. 一种基于众包地图的智能交通诱导数据模型及方案研究[D]. 北京：北京邮电大学， 2015.

CUI Qianqian. A Study on the Data Model and Scheme of Intelligent Traffic Guidance Based on Crowdsourcing Map[D].Beijing： Beijing University of Posts and Telecommunications，2015.

[5] KARPATY A， TODERICI G， SETTY S， et al. Large-scale video classification with convolutional neural networks[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. Washington DC： IEEE， 2014：1725-1732.

[6] SZEGEDY C， LIU W， IA Y Q， et al. Going deeper with convolutions[C]// 2015 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. Boston： IEEE， 2015：7298594.

[7] van ASSELT ， GUEZ A， SILVER D. Deep reinforcement learning with double Q-learning. Computer Science， 2015：1509.06461v3.

[8] 王少华， 卢浩， 黄骞， 等. 智慧交通系统关键技术研究. 测绘与空间地理信息， 2013（sup）：88-91.

WANG Shaohua， LU ao， UANG Qian，et al. Research on key technologies for smart transportation systems. Geomatics & Spatial Information Technology， 2013（sup）：88-91.

[9] DUAN Yan， CEN Xi， OUTOOFT R， et al. Benchmarking deep reinforcement learning for continuous control[C]//Proceedings of the 33rd International Conference on International Conference on Machine Learning.  New York：[s.n.]， 2016：1329-1338.

[10]苑宇坤， 張宇， 魏坦勇， 等. 智慧交通关键技术及应用综述. 电子技术应用， 2015，41（8）：9-12.

YUAN Yukun， ZANG Yu， WEI Tanyong， et al. Review of key technologies and applications of intelligent transportation.Application of Electronic Technique， 2015，41（8）：9-12.

[11]王涤宇， 付超贤. 交通2.0——智慧交通的关键. 中兴通讯技术， 2014， 20（4）：11-15.

WANG Diyu， FU Chaoxian. Transport 2.0： The key to smart transport. ZTE Technology ournal， 2014， 20（4）：11-15.

[12]韩直， 关雨嫣. 智慧交通构建研究. 公路交通技术， 2018， 34（6）：114-117.

AN Zhi， GUAN Yuyan. Research on intelligent transportation construction. Technology of ighway and Transport， 2018， 34（6）：114-117.

[13]陈宇轩， 王晓丹， 吕秋平. AI改变传统驾驶，智慧交通离我们还有多远？[EB/OL]. http：//www.kepuchina.cn/qykj/rgzn/201711/t20171123_284175.shtml，2017-11-23.

[14]蓝志军. 关于智慧交通系统的设计方法分析. 明日风尚， 2016（23）：17.

[15]张智鸿. 智慧交通中大数据应用面临的挑战与对策研究. 智能城市， 2018（9）：104-105.