大數(shù)據(jù)驅(qū)動下的新一代高速公路智慧誘導(dǎo)技術(shù)

孫金海

摘 要：為了解決高速公路出行路徑選擇問題，基于圖論模糊算法，提出了大數(shù)據(jù)下的智慧誘導(dǎo)技術(shù)。首先對高速路網(wǎng)在路徑誘導(dǎo)的實時性、線路規(guī)劃的精準(zhǔn)度和算法的適用性方面進(jìn)行優(yōu)化;其次通過利用貪心算法和整體尋優(yōu)算法，對經(jīng)典路徑誘導(dǎo)算法進(jìn)行研究和比選;最后針對高速路網(wǎng)提出基于大數(shù)據(jù)動態(tài)規(guī)劃的路徑誘導(dǎo)技術(shù)，采用大數(shù)據(jù)、內(nèi)存計算、圖計算和AI結(jié)合的方式來實現(xiàn)大數(shù)據(jù)的動態(tài)實時路徑誘導(dǎo)。研究結(jié)果表明，智慧誘導(dǎo)技術(shù)可主動為有不同訴求目標(biāo)的出行者提供實時最優(yōu)的方案選擇，解決復(fù)雜路網(wǎng)下動態(tài)路徑的合理誘導(dǎo)問題。所提出的方法可實現(xiàn)大數(shù)據(jù)驅(qū)動下的智慧誘導(dǎo)，對進(jìn)一步提升公路智能化和精細(xì)化管理水平具有借鑒意義。

關(guān)鍵詞：人工智能其他學(xué)科;大數(shù)據(jù);圖論;動態(tài)規(guī)劃;智慧誘導(dǎo)

中圖分類號：TP181?? 文獻(xiàn)標(biāo)志碼：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

公路出行需求的猛增致使路網(wǎng)交通擁堵頻繁發(fā)生，惡劣天氣或突發(fā)事件導(dǎo)致的路段癱瘓屢見不鮮，降低了公眾的出行體驗。近年來隨著路網(wǎng)規(guī)模的不斷擴(kuò)大，路網(wǎng)結(jié)構(gòu)日趨復(fù)雜，路網(wǎng)交通流分布出現(xiàn)不均衡的現(xiàn)象，造成了道路資源的浪費(fèi)[1]。在信息技術(shù)飛速發(fā)展的今天，如何從方便公眾出行、提高路網(wǎng)通行效率出發(fā)，利用先進(jìn)技術(shù)從大數(shù)據(jù)中挖掘有價值的信息，為公眾提供更加實時和精準(zhǔn)的在線誘導(dǎo)服務(wù)[2]，提升公路智能化服務(wù)水平[3-4]，是高速公路管理部門亟需解決的問題。

1 路徑誘導(dǎo)算法選擇綜述

圖論是路徑誘導(dǎo)算法的理論基礎(chǔ)，可以把高速網(wǎng)絡(luò)作為一個收費(fèi)站節(jié)點、服務(wù)區(qū)節(jié)點和道路（有向）邊組成的網(wǎng)絡(luò)圖來進(jìn)行研究。

高速路網(wǎng)參與者包括總體參與者（如路網(wǎng)管理人員）、局部參與者（如路段管理人員）和個體參與者（行駛車輛個體）等不同的角色。對于p個節(jié)點的圖G，每類角色對路徑誘導(dǎo)的需求都可以視作對G上p階最小支撐樹問題解的尋求計算。

路徑誘導(dǎo)算法是路徑誘導(dǎo)技術(shù)的核心，常見的經(jīng)典路徑誘導(dǎo)算法一般分為貪心算法和整體尋優(yōu)算法。

1.1 貪心算法

貪心算法（又稱貪婪算法）是指在求問題答案時，總是作出在當(dāng)前看來是最好的選擇。貪心算法不能得到所有問題整體的最優(yōu)結(jié)果，但對一定范圍的許多問題能產(chǎn)生整體最佳解或者是整體最優(yōu)答案相近解。

這一類算法有以下特點：

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

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

3） 在一定條件下得到可行解的集。

對于[WTBX]p個節(jié)點的圖G，貪心算法可以作為G上p階最小支撐樹的問題解。顯然，在w（T）的迭加過程中，w（e）是不能發(fā)生變化（處于靜態(tài)）的。

在此只針對最常用的Dijkstra算法和K-最短路徑算法進(jìn)行介紹。

1.1.1 Dijkstra算法

Dijkstra算法是典型最短路徑算法，是一種集中式的靜態(tài)算法，算法解決的是圖中目標(biāo)源點到其他頂點的最短路徑問題。Dijkstra算法既有優(yōu)點也有缺點。優(yōu)點是算法簡明、能得到局部最優(yōu)解，缺點是效率低、運(yùn)算中占用空間大。算法的計算復(fù)雜度為[WTBX]O（n2），如果邊數(shù)遠(yuǎn)小于n2，對此可以考慮用堆優(yōu)化把復(fù)雜度降為O（nlog（n））。

Dijkstra算法是一個真正意義上的快速（有效）算法，它不僅用于找出電腦網(wǎng)絡(luò)中一個節(jié)點到其他節(jié)點間的最短路徑，還可以解決一個網(wǎng)絡(luò)系統(tǒng)中的短圈問題（計算圖中的最短圈）[5]。

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

在計算實時性的大型交通網(wǎng)絡(luò)中，最常用K-最短路徑算法，該算法能滿足用戶出行，提供不同路徑進(jìn)行選擇，這是一種非確定性的復(fù)雜算法，結(jié)果往往是給出很多條比較接近的路徑，有可能存在重復(fù)路段，甚至產(chǎn)生環(huán)路。

1.2 整體尋優(yōu)算法（Floyd[6]算法）

這種算法能找到全局最優(yōu)答案，并且大量用于計算各種優(yōu)化問題。Floyd算法需要建立鄰接表或者是鄰接矩陣，計算復(fù)雜度為O（n3），存儲復(fù)雜度為O（n2），需要耗費(fèi)巨大的計算和存儲資源。

對于低階稠密圖，F(xiàn)loyd算法是有效的;對于高階稠密圖，F(xiàn)loyd算法的成本是巨大的，這也是全局最優(yōu)的代價。

但對于高階稀疏圖，F(xiàn)loyd算法的計算可以優(yōu)化到O（n2）甚至O（nlog（n））， 存儲復(fù)雜度也可以優(yōu)化到O（nlog（n））。

1.3 高速路網(wǎng)下的路徑誘導(dǎo)算法選擇

上述經(jīng)典算法對于靜態(tài)下的路網(wǎng)G是可以生效的，可有效用于網(wǎng)絡(luò)建設(shè)規(guī)劃、地圖導(dǎo)航等以出行距離最短作為最優(yōu)目標(biāo)的場景。針對高速路網(wǎng)，主要采用類Floyd的全局優(yōu)化算法進(jìn)行動態(tài)路徑規(guī)劃與尋優(yōu)。但由于高速路徑誘導(dǎo)涉及多方參與者，不同參與者有不同的目標(biāo)訴求，具體有以下幾種。

1）以個體/總體/局部出行距離最短作為最優(yōu)目標(biāo)，這類目標(biāo)比較直接、直觀和常見。

2）以個體/總體/局部出行時間最短作為最優(yōu)目標(biāo)，這類目標(biāo)在擁堵時期/時段比較常見。

3）以個體/總體/局部出行費(fèi)用（成本）最低作為最優(yōu)目標(biāo)，這類目標(biāo)和1類目標(biāo)關(guān)聯(lián)性很強(qiáng)，但出行成本并非僅僅包含通行費(fèi)用。常用于節(jié)假日、擁堵時段、重大事件/事故發(fā)生時，對于大車的誘導(dǎo)有積極效果。

4）以個體/總體/局部安全影響與事故概率作為最優(yōu)目標(biāo)，這類目標(biāo)在惡劣天氣、重大事件/事故發(fā)生時具有重要意義。

5）以路網(wǎng)費(fèi)用損失作為最優(yōu)目標(biāo)，這類目標(biāo)主要用于理論規(guī)劃和研究分析。

6）以客戶的安全快捷體驗作為最優(yōu)目標(biāo)，這類目標(biāo)在重大事件（如冬奧會出行保障）發(fā)生時比較常見。

實際應(yīng)用中常根據(jù)受眾的不同設(shè)置不同的目標(biāo)，組合2個或多個目標(biāo)來進(jìn)行尋優(yōu)，并結(jié)合時間周期考慮短期/長期目標(biāo)等等。這些路徑上的權(quán)函數(shù)其實是非常復(fù)雜的，給經(jīng)典算法帶來很大的挑戰(zhàn)，通過對路徑的評估計算進(jìn)行動態(tài)學(xué)習(xí)而采用的人工智能技術(shù)應(yīng)運(yùn)而生。

高速網(wǎng)絡(luò)作為一個收費(fèi)站節(jié)點、服務(wù)區(qū)節(jié)點和道路（有向）邊組成的網(wǎng)絡(luò)圖，由于高速公路的封閉性和有向性，可以看作一個[WTBX]p階稀疏圖（p值在1 000左右）。采用高階稀疏優(yōu)化的Floyd算法，計算和存儲復(fù)雜度可以優(yōu)化到O（nlog（n））[7]。

2 基于大數(shù)據(jù)動態(tài)規(guī)劃的路徑誘導(dǎo)技術(shù)實現(xiàn)

2.1 基于大數(shù)據(jù)的動態(tài)實時路徑誘導(dǎo)計算框架

根據(jù)高速路網(wǎng)的有限階數(shù)和稀疏特點，采用Floyd的全局優(yōu)化算法進(jìn)行動態(tài)路徑規(guī)劃與尋優(yōu)。在實際應(yīng)用中，由于要保障數(shù)據(jù)處理的準(zhǔn)確性、實時性和可用性，采用大數(shù)據(jù)+內(nèi)存計算+圖計算+AI的方式來實現(xiàn)基于大數(shù)據(jù)的動態(tài)實時路徑誘導(dǎo)。

基于大數(shù)據(jù)的動態(tài)實時路徑誘導(dǎo)計算框架如圖1所示。

底層是大數(shù)據(jù)平臺基礎(chǔ)設(shè)施adoop DFS數(shù)據(jù)庫及關(guān)系數(shù)據(jù)庫管理系統(tǒng)（RDBMS）和Spark，之上是GraphX和MLlib，Tensorflow計算引擎。

通過誘導(dǎo)路徑計算模塊來實現(xiàn)路網(wǎng)整體/局部/個體的實時誘導(dǎo)計算。由于p的有限性，通過采用高階稀疏優(yōu)化的Floyd算法[8]，把全路網(wǎng)裝入Spark RDD成為可能，這一空間換時間的策略大大降低了計算復(fù)雜度，使得車主通過APP/網(wǎng)站/微信/96122等實時獲得最優(yōu)路徑成為可能。

誘導(dǎo)路徑計算模塊的效果取決于圖論的模型，[WTBX]w（t）權(quán)函數(shù)/組是模型的重要構(gòu)成元素。w（t）權(quán)函數(shù)組并不一定都采用簡單的帶權(quán)加法復(fù)合模式，其復(fù)合特征可能是復(fù)雜的，還可能受到不同時間、不同區(qū)域、不同事件的影響。采用RLS（reinforcement learning system）強(qiáng)化學(xué)習(xí)技術(shù)計算學(xué)習(xí)不同時間、不同路段、不同路況下的函數(shù)組，并以5 min為周期進(jìn)行不斷地迭代計算、更新、評估與學(xué)習(xí)。

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個領(lǐng)域，強(qiáng)調(diào)如何基于環(huán)境而行動，以取得最大化的預(yù)期利益。其靈感來源于心理學(xué)的行為主義理論，即有機(jī)體如何在環(huán)境給予的獎勵或懲罰的刺激下，逐步形成對刺激的預(yù)期，產(chǎn)生能獲得最大利益的習(xí)慣性行為。這個方法具有普適性，因此在其他許多領(lǐng)域都有研究，例如博弈論、控制論、運(yùn)籌學(xué)、信息論、仿真優(yōu)化、多主體系統(tǒng)學(xué)習(xí)、群體智能、統(tǒng)計學(xué)以及遺傳算法。在運(yùn)籌學(xué)和控制理論研究的語境下，強(qiáng)化學(xué)習(xí)被稱作“近似動態(tài)規(guī)劃”（approximate dynamic programming，ADP）[9]，在最優(yōu)控制理論中也有較廣泛的應(yīng)用。

高速路網(wǎng)下，路段和車輛都可以類似智能體（Agent）“試錯”的方式進(jìn)行學(xué)習(xí)，通過與環(huán)境進(jìn)行交互獲得獎賞（價值目標(biāo)）指導(dǎo)行為[10]。強(qiáng)化學(xué)習(xí)不同于連接主義學(xué)習(xí)中的監(jiān)督學(xué)習(xí)，主要表現(xiàn)在強(qiáng)化信號上，強(qiáng)化學(xué)習(xí)中由環(huán)境提供的強(qiáng)化信號是對產(chǎn)生動作的好壞作一種評價（通常為標(biāo)量信號），而不是告訴強(qiáng)化學(xué)習(xí)系統(tǒng)RLS如何去產(chǎn)生正確的動作。

RLS對外部環(huán)境提供的信息依賴很少，必須靠自身的經(jīng)歷進(jìn)行學(xué)習(xí)。通過這種方式，RLS在行動-評價的環(huán)境中獲得知識，改進(jìn)行動方案以適應(yīng)環(huán)境。例如冬奧會前夕，可以事先通過模擬演練和試錯獲得路網(wǎng)上的權(quán)函數(shù)策略，結(jié)合路網(wǎng)實際狀況計算冬奧會期間最佳的誘導(dǎo)路徑。

2.2 基于大數(shù)據(jù)的動態(tài)實時路徑誘導(dǎo)決策分析

動態(tài)實時路徑誘導(dǎo)決策分析是為路網(wǎng)中實時發(fā)生的重大突發(fā)事件[11]產(chǎn)生的，如：在交通事故、交通擁堵等對路網(wǎng)通行能力造成影響的情況下，基于上述大數(shù)據(jù)的動態(tài)實時路徑誘導(dǎo)計算框架，可以構(gòu)建事故下路網(wǎng)影響分析模型。

在高速公路交通中，交通事件影響分析是一類重要的決策分析類型。主要包括兩類事件：一類是突發(fā)交通事件，比如交通事故、突發(fā)惡劣天氣等;一類是交通管制、道路養(yǎng)護(hù)等主動干預(yù)事件或預(yù)期發(fā)生事件（如節(jié)假日的影響）[12]。通常采用歷史類似事件數(shù)據(jù)統(tǒng)計分析方法或交通仿真方法對事件的影響進(jìn)行分析[13]。通過影響分析，得到相關(guān)路段、時段的交通事件的影響評估，包括影響的范圍、影響程度等。

發(fā)生交通事故時段的路網(wǎng)影響分析模型如圖2所示。

在事故影響分析模型中，通過大數(shù)據(jù)平臺采集流量、路況、氣象、事故等，以形成各類交通事件。基于這些歷史事件，大數(shù)據(jù)平臺進(jìn)行事件影響的初步分析，并結(jié)合當(dāng)前和未來預(yù)測的斷面流量數(shù)據(jù)進(jìn)行分析，獲得交通事件的影響數(shù)據(jù)。

根據(jù)上述突發(fā)事件影響分析模型輸出受影響路段的通行能力和擁擠程度結(jié)果，包括：受影響路段擁堵長度、擁堵時長、流量、平均速度、上游入口匝道流量、平均速度等，與設(shè)置的是否觸發(fā)處置措施的閾值

相比較，小于閾值則不做任何處理，大于或等于閾值則根據(jù)具體值域范圍，觸發(fā)啟動對應(yīng)的交通誘導(dǎo)分析流程，實現(xiàn)在線的實時路徑誘導(dǎo)分析，并通過最優(yōu)路徑算法找出所有可行路徑中的最優(yōu)路徑，自動生成誘導(dǎo)建議，以便能夠在對高速運(yùn)營產(chǎn)生盡量小的影響下及時進(jìn)行合理路徑的誘導(dǎo)來疏散交通流[14]。

示例：某路段發(fā)生事故造成擁堵情況下的動態(tài)路徑誘導(dǎo)決策分析模型如圖3所示。

同時結(jié)合受影響范圍內(nèi)的交通誘導(dǎo)牌、服務(wù)區(qū)等設(shè)備設(shè)施的可用性，分級預(yù)告突發(fā)事件，給即將進(jìn)入事發(fā)路段的車輛提供繞行路徑、告知信息等，減少突發(fā)事件的不良影響[15]。

3 大數(shù)據(jù)驅(qū)動下的動態(tài)路徑誘導(dǎo)技術(shù)應(yīng)用

基于大數(shù)據(jù)動態(tài)規(guī)劃的路徑誘導(dǎo)技術(shù)研究，針對不同出行者的出行需求綜合考慮費(fèi)用、時間、距離、天氣、車流量以及路況等因素，從提高整個路網(wǎng)的通行效率和出行體驗為出發(fā)點，采用強(qiáng)化學(xué)習(xí)技術(shù)實現(xiàn)基于大數(shù)據(jù)的實時誘導(dǎo)路徑最佳方案的動態(tài)選擇，既保證了路網(wǎng)最大限度的有效利用和暢通，實現(xiàn)了路網(wǎng)經(jīng)濟(jì)效益的最大化，又使得管理部門在平衡路網(wǎng)交通流的前提下，為公眾提供更為精準(zhǔn)和實時的誘導(dǎo)路線，使智慧誘導(dǎo)下的主動服務(wù)以及智能化管理成為了可能。圖4是采用基于大數(shù)據(jù)動態(tài)規(guī)劃的路徑誘導(dǎo)技術(shù)實現(xiàn)交通誘導(dǎo)決策支持系統(tǒng)的應(yīng)用結(jié)果展示示例。

4 結(jié) 語

基于大數(shù)據(jù)動態(tài)規(guī)劃的路徑誘導(dǎo)技術(shù)，實現(xiàn)了交通誘導(dǎo)決策支持系統(tǒng)，為不同的出行者提供了實時誘導(dǎo)路徑最佳方案的動態(tài)選擇，既保證了路網(wǎng)最大限度的有效利用和暢通，又使路網(wǎng)的經(jīng)濟(jì)效益最大化，進(jìn)一步提升了公路智能化和精細(xì)化的管理水平。

由于路段信息采集手段有限，數(shù)據(jù)不盡完善，數(shù)據(jù)采集密度及精準(zhǔn)度有待提高，給出行的精準(zhǔn)服務(wù)帶來一定的困難，如何利用ETC使這些問題得到逐步改善和加強(qiáng)，將是以后的研究方向。隨著國家交通強(qiáng)國戰(zhàn)略的實施，以及交通主管部門智慧公路政策的逐步落地，引導(dǎo)司乘人員實現(xiàn)智慧出行，實現(xiàn)更加智能化和精細(xì)化的交通管理是大數(shù)據(jù)時代下智慧高速公路建設(shè)的主旋律。

參考文獻(xiàn)/References：

[1] 李朝衍. 探討智慧交通信息誘導(dǎo)系統(tǒng)的關(guān)鍵技術(shù). 通訊世界， 2017（22）：54-55.

[2] 李強(qiáng)， 劉曉峰. 智慧交通信息誘導(dǎo)系統(tǒng)關(guān)鍵技術(shù)的研究. 電視技術(shù)， 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ǎo)的智能公共交通信息服務(wù)系統(tǒng)研究[D]. 青島：青島科技大學(xué)，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ǎo)數(shù)據(jù)模型及方案研究[D]. 北京：北京郵電大學(xué)， 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] 王少華， 盧浩， 黃騫， 等. 智慧交通系統(tǒng)關(guān)鍵技術(shù)研究. 測繪與空間地理信息， 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]苑宇坤， 張宇， 魏坦勇， 等. 智慧交通關(guān)鍵技術(shù)及應(yīng)用綜述. 電子技術(shù)應(yīng)用， 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——智慧交通的關(guān)鍵. 中興通訊技術(shù)， 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]韓直， 關(guān)雨嫣. 智慧交通構(gòu)建研究. 公路交通技術(shù)， 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改變傳統(tǒng)駕駛，智慧交通離我們還有多遠(yuǎn)？[EB/OL]. http：//www.kepuchina.cn/qykj/rgzn/201711/t20171123_284175.shtml，2017-11-23.

[14]藍(lán)志軍. 關(guān)于智慧交通系統(tǒng)的設(shè)計方法分析. 明日風(fēng)尚， 2016（23）：17.

[15]張智鴻. 智慧交通中大數(shù)據(jù)應(yīng)用面臨的挑戰(zhàn)與對策研究. 智能城市， 2018（9）：104-105.