RBF神經(jīng)網(wǎng)絡的行車路徑代價函數(shù)建模

陳亮，何為，韓力群

(北京工商大學計算機與信息工程學院，北京 100048)

RBF神經(jīng)網(wǎng)絡的行車路徑代價函數(shù)建模

陳亮，何為，韓力群

(北京工商大學計算機與信息工程學院，北京 100048)

行車路線優(yōu)化是城市智能交通系統(tǒng)的研究熱點之一，對整個交通系統(tǒng)的優(yōu)化起著重要作用.分析了影響行車時間的各種因素，結(jié)合圖論中最短路徑算法，建立了基于RBF神經(jīng)網(wǎng)絡的路徑代價函數(shù)模型.基于該函數(shù)模型，可以計算出交通圖中任意給定兩地間的時間最優(yōu)路徑.將該模型應用于實際路況進行有效性驗證，得到了有實用價值的結(jié)果，說明了該模型的正確性和有效性.

智能交通;路徑代價函數(shù);行車路線優(yōu)化;RBF神經(jīng)網(wǎng)絡;圖論

在城市智能交通系統(tǒng)中，行車路線優(yōu)化對整個交通系統(tǒng)的優(yōu)化起著重要作用，選取最優(yōu)車輛行車路線，可以加快車流速度，減少擁堵發(fā)生，還能減少因為堵車而造成的交通車輛刮蹭等事故的概率，因此，該課題的研究具有重要的實用意義.

行車路線優(yōu)化屬于路徑優(yōu)化問題.目前關于路徑優(yōu)化的研究主要集中在如何找到最短路徑，其中常見的一類方法是采用圖論中的Dijkstra算法，具體實現(xiàn)算法有 A－star［1］、Bellman、Ford2Moore、Floyd 等［2］;另一類常用方法是基于蟻群算法的解決方法，如2007年Horoba等人提出的基于隨機過程的改進蟻群算法最短路徑尋優(yōu)［3］，2009年Punyaslok提出的多網(wǎng)絡流最優(yōu)化框架，2010年Zakzouk提出的基于蟻群算法利用模糊約束解決最短路徑問題［4］.

道路交通網(wǎng)絡的實際情況非常復雜，每個路段的行車時間除了與距離有關外，還與路寬、路況、氣候及行車時段等諸多因素相關，因此最短路徑并不意味著最短行車時間，不能簡單地用路徑長度計算路徑的代價值［5］.鑒于此，本文從實際情況出發(fā)，綜合考慮了各種影響行車時間的主要因素，建立了較為實用的路段代價函數(shù)模型并進行了實驗驗證.

1 路徑代價函數(shù)及其影響因素分析

圖論中每個弧段都可用其代價函數(shù)值表示，2個給定點之間的路徑代價函數(shù)值則可用構成該路徑的所有弧段的代價函數(shù)值之和表示.2個給定點間的最優(yōu)路徑即指所有可達路線中代價函數(shù)值最小的路徑［6］.

實際應用中，弧段對應于兩相鄰路口之間的路段，路徑對應于出發(fā)地到目的地之間的行車路線，代價函數(shù)值則對應于行車時間代價.實際道路中，很多因素都會影響車輛通過路段的時間，表1列出了可能影響車輛通過路段時間的主要因素［7］.

表1 車輛通行時間的影響因素Table 1 The influencing factors of vehicle travel time

在諸影響因素中，可進一步篩選出相互獨立的主要因素.經(jīng)過深入調(diào)研，本文確定了5個相互獨立的影響因素:實時交通路況、車道數(shù)(路寬)、道路長度、自助紅綠燈數(shù)量以及車輛轉(zhuǎn)向.

2 基于RBF網(wǎng)絡的路段代價函數(shù)建模

在實際道路中，車輛通過路段的時間與其影響因素之間存在著嚴重的非線性和不確定性，因此很難用解析式來表達.人工神經(jīng)網(wǎng)絡適于處理非線性問題，利用神經(jīng)網(wǎng)絡建立路徑代價函數(shù)模型，是一種可行的途徑［8］.適合擬合非線性關系的神經(jīng)網(wǎng)絡主要有BP網(wǎng)絡和RBF網(wǎng)絡，經(jīng)實驗對比，采用效果較好的RBF網(wǎng)絡進行建模［9］.

2.1 基于正交實驗的訓練集設計

RBF網(wǎng)絡的輸入是影響車輛通行時間的因素，教師信號是車輛通過路段的實際時間.本文所確定的影響因素包括:實時路況x1、車道數(shù)量x2、行人自助式紅綠燈數(shù)量x3、路段長度x4、車輛在路口的轉(zhuǎn)向方式x5.

可以看出，上述影響因素既有語言變量，又有數(shù)值變量.首先，對各影響因素進行數(shù)值化和離散化.其中:x1為語言變量，根據(jù)北京市交通管理局現(xiàn)有標準劃分，共分為3種路況:“暢通”、“緩行”、“擁堵”，與3個語言值對應，x1取值分別為0、1、2;x2可直接采用實際車道數(shù)，分為1～2條、3條、4條3種情況，x2取值分別對應為0、1、2;行人自助式紅綠燈數(shù)量x3，可直接采用實際數(shù)量，取值分別為0、1、2.路段長度x4可離散為3個區(qū)間，分別為小于500 m、500 ～1 000 m、大于1 000 m，對應的x4取值為0、1、2;x5也是語言變量，可分為“直行”、“左轉(zhuǎn)、“右轉(zhuǎn)”3 種情況［10］，分別用 0、1、2 表示.按照上述規(guī)定，5種影響因素的完全搭配可產(chǎn)生243個樣本對，而每個樣本對中的教師信號必須來自與輸入條件相符的實際情況.為了減少工作量，采用正交實驗設計法來構造樣本集，其優(yōu)點是:正交表能在保證采集數(shù)據(jù)均勻分布的前提下，大大減少訓練網(wǎng)絡所需的樣本數(shù).本文將每個影響因素分成3個水平，如表2所示.表2給出了水平因素表，x1～x5是對道路通行時間不同的影響因素，再將每一個影響因素具有的3個水平填入表中.

采用的正交試驗如表3所示.將5個不同因素的不同水平分別排列組合得到的18種實驗組合情況.雖然只給出了18種實驗組合情況，但是用這個表設計的訓練集保證了實驗數(shù)據(jù)的代表性.

2.2 基于RBF網(wǎng)絡的路段代價函數(shù)建模

由于采集到的輸入輸出數(shù)據(jù)取值范圍差別很大，需進行歸一化處理，將輸入數(shù)據(jù)歸一化到［－1，1］區(qū)間，教師信號的時間單位采用小時，歸一化到(0，1］區(qū)間［11］.數(shù)據(jù)歸一化后的情況如表 4 所示.

表4 數(shù)據(jù)歸一化Table 4 Data normalization

表4根據(jù)x1～x5這5個影響行車時間因素的實際情況，依據(jù)表3，然后分別將其歸一化，如x1～x4歸一化的原則是本身對應的3個水平，將其歸一化至［－1，0，1］，x5是時間，將其歸一化至［0，1］.

RBF網(wǎng)絡的設計與訓練采用函數(shù)net=newrb(P，T，goal，spread)，其中，P 為 5 維輸入向量，T為網(wǎng)絡輸出的行車代價值，訓練誤差目標值goal設定為0.01，spread為徑向基函數(shù)的擴展系數(shù)，經(jīng)調(diào)試取為 1.5［12］.

2.3 模型驗證

由于特定路段的行車時間具有不確定性，采用上述方法建立的路段代價函數(shù)其輸出并非準確的行車時間，而是行車代價值，其作用是通過比較不同可達路線的行車代價從而確定最優(yōu)行車路線.本文用表5中的15組實際數(shù)據(jù)對模型進行驗證，結(jié)果如表5的第7列所示.

表5 仿真結(jié)果對比Table 5 Simulation results comparison

從表5可知，擁堵路段的網(wǎng)絡預測代價值要明顯大于暢通與緩行的值，說明實際道路路況是影響車輛行駛時間的主要因素，當其他因素相同時，轉(zhuǎn)向會影響所用的時間，如左轉(zhuǎn)比直行和右轉(zhuǎn)花費的時間都多，這與日常常識是相符的.5個影響因素中的x1、x3、x4都是正向關因素，即水平越高，所花費時間越長，網(wǎng)絡的預測值同樣也越大，而x2是反相關因素.仿真結(jié)果如圖1所示，同樣也可以看出，神經(jīng)網(wǎng)絡的仿真預測結(jié)果與實測結(jié)果趨勢一致，表明所設計的路段行車代價函數(shù)模型可靠.圖1中需要說明的是，實際行車路線是以秒為單位計時，而神經(jīng)網(wǎng)絡計算的行車代價值沒有單位，不表示實際消耗的時間，表示的是車輛行駛在不同的路段所耗費時間多少的橫向比較，并以此為依據(jù)，最終選擇出最優(yōu)路徑.

圖1 仿真值與實際測量值Fig.1 Simulation and test values

3 應用實例

3.1 應用實例概述

本文應用實例是利用路段代價函數(shù)模型確定特定路況條件下，從航天橋至西單路口的最優(yōu)路線，實際道路如圖2.具體步驟是:首先將交通網(wǎng)絡圖抽象成為加權有向圖［13］，找出連通起點和終點的所有可達路線，2個相鄰交通路口之間是一個路段，從而可將各可達路線表示為一個路段系列，其中每個路段的實際情況可用一個5維向量進行描述，代入路段代價函數(shù)模型后可計算出該路段的行車代價值，所有路段的代價值之和即為路徑的行車代價值，其中行車代價值最小的路徑為最優(yōu)路徑［14］.

圖2 實際交通道路Fig.2 Actual traffic roads

可達路徑的搜索方法如下.

1)將圖2中的交通圖抽象為加權有向圖，對不能提供實時路況信息的路段視為不可達，從而得到圖3.圖3中，1號節(jié)點為航天橋，15號節(jié)點為西單路口.

2)建立加權有向圖的鄰接矩陣.

3)根據(jù)鄰接矩陣，從起始點開始找出下一節(jié)點;若下一個節(jié)點等于目標點，則返回2).

4)將起點到終點經(jīng)過的全部節(jié)點串連起來，形成完整路徑，將路徑中經(jīng)過點的權值相加，得到整條路徑的權值［15］.

根據(jù)上述算法共得到92條可達路線［16］，略去情況近似的路徑，選出差別較大的20條路徑，根據(jù)距離長短對可達路線編號，如表6所示.

圖3 加權有向圖Fig.3 Weighted directed graph

表6 均勻抽出20條可達路線Table 6 Uniform extraction 20 paths

續(xù)表6

表6為所有可達路徑中均勻抽取出的20條可達路徑，按實際距離從小到大排序，可知，最短可達路線的距離為6.55 km，最長可達路線的距離為14.45 km.

3.2 確定最優(yōu)行車路線

圖4給出了早上7:00時上述路段的實時路況交通圖，其中細線路段為暢通，粗線路段為緩行，粗虛線路段為擁堵.

結(jié)合圖4中實際的交通路況，并利用路段行車代價函數(shù)模型計算表6中各可達路線的行車代價值，將得到的行車代價值從小到大排序，結(jié)果如表7所示.

圖4 實時交通路況Fig.4 Real time traffic

表7 最優(yōu)路徑排序Table 7 Optimal paths sort

從表7中可以看出，根據(jù)行車代價函數(shù)模型選出的最優(yōu)路徑R3并非距離最短的路徑R1，雖然多走了500 m的路，但卻有效地避開了擁堵路段，節(jié)約的時間大于繞路的時間代價.

3.3 可達路線生成算法的改進

根據(jù)上述算法共得到92條可達路線，其中很多“繞路”的情況不符合常識，如表7中的R20.一種改進的思路是，在計算可達路線時增加約束條件［17］.例如，按照“不走回頭路”的要求，每個節(jié)點的選擇方向必須與終點的2個方向分量一致，按照這樣的條件，本例共選出9條長度近似的可達路線［18］，表8中列出了這9條可達路線的行車代價預測值.

表8 改進算法后的最優(yōu)路徑Table 8 Optimal paths by the improved algorithm

從表8可以看出，附加限制條件后，選出的可達路線即距離最短的前9條路徑，當加上約束條件對最優(yōu)路徑的選擇會產(chǎn)生一定影響，但卻大大提高了計算效率，并能保證行車時間和距離雙優(yōu)化.可以看出，表8中的改進路徑IR9和表7中的路徑R3相同.

在根據(jù)常識設計約束條件時，也可考慮允許在某一個方向上“繞行”.例如，起點到終點在東西方向上的距離比南北方向的距離長，通常人們會選擇在東西方向少走回頭路，在南北方向上可視路況適當繞行，反之亦然.本例中，東西方向距離比南北方向距離長，當設定禁止向西行駛的約束條件時，得到的可達路線數(shù)為72;若附加條件為禁止向北行駛，則可達路線數(shù)為12.

3.4 有效性驗證

本文從表7中選取R1、R3和R9 3條路徑，請3位志愿者同時開車從航天橋出發(fā)，分別按照規(guī)定的路徑前往西單，并記下行程時間.結(jié)果是:R9的行車時間為41 min，R1的行車時間為52 min，R3的行車時間為66 min.可以得出，RBF行車代價函數(shù)模型給出的行車路線排序與實際情況相同.

4 結(jié)束語

本文的特點是利用RBF神經(jīng)網(wǎng)絡建立最優(yōu)路徑代價函數(shù)模型，通過圖論中的算法找到起點和終點的時間最優(yōu)路徑.在設計神經(jīng)網(wǎng)絡模型過程中，訓練集的設計由正交實驗法給出，訓練出的網(wǎng)絡模型測試結(jié)果較好，最后將模型應用到實例中，從最優(yōu)路徑代價函數(shù)模型給出的最優(yōu)路徑排序中選取差異較大的3條路徑，經(jīng)實際驗證取得了較好結(jié)果.本次研究的不足在于，諸如天氣因素(風、雨、雪、霧4類天氣)并沒有加入到網(wǎng)絡的訓練集中，原因在于這些因素在研究過程中較難采集，在以后的時間范圍內(nèi)將繼續(xù)觀察采集并加入這些因素的數(shù)據(jù)，將神經(jīng)網(wǎng)絡的訓練集豐富完善，使其能夠更加真實地反映出交通網(wǎng)絡路徑的代價函數(shù)值，更加貼近實際情況.

［1］張渭軍，王華.城市道路最短路徑的Dijkstra算法優(yōu)化［J］.長安大學學報:自然科學版，2005，25(6):62－65.

ZHANG Weijun，WANG Hua.Optimation Dijkstra arithmetic for shortest path of urban traffic net［J］.Journal of Chang’an University:Natural Science Edition，2005，25(6):62－65.

［2］姜桂艷，鄭祖舵.基于記憶機制的動態(tài)交通路徑優(yōu)化算法［J］.吉林大學學報:工學版，2007，37(5):1043－1048.

JIANG Guiyan，ZHENG Zuduo.Dynamic traffic path optimization algorithm based on mnemonic mechanism［J］.Journal of Jilin University:Engineering and Technology Edition，2007，37(5):1043－1048.

［3］HOROBA C，SUDHOLT D.Ant colony optimization for stochastic shortest path problems［C］//Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference.New York，USA:ACM，2008:1465－1472.

［4］ZAKZOUK A A A，ZAHER H M，EL－DEEN R A Z.An ant colony optimization approach for solving shortest path problem with fuzzy constraints［C］//2010 The 7th International Conference on Informatics and Systems.Cairo，E－gypt，2010:1201－1208.

［5］王泉嘯，蔡先華.動態(tài)最佳路徑算法研究［J］.城市勘測，2009，73(1):73－75.

WANG Quanxiao，CAI Xianhua.Study on the algorithm of dynamic optimal route［J］.Urban Geotechnical Investigation＆ Surveying，2009，73(1):73－75.

［6］徐俊明.圖論及其應用［M］.3版.合肥:中國科學技術大學出版社，2010:21－53.

［7］劉海燕.智能交通系統(tǒng)的車輛行駛最佳路徑算法［J］.北京工商大學學報:自然科學版，2006，24(1):53－55.

LIU Haiyan.Best running path arithmetic of vehicles in intelligent transport system［J］.Journal of Beijing Technology and Business University:Natural Science Edition，2006，24(1):53－55.

［8］韓力群.人工神經(jīng)網(wǎng)絡教程［M］.北京:北京郵電大學出版社，2006:127－143.

［9］馬君，劉曉東，孟穎.基于神經(jīng)網(wǎng)絡的城市交通流預測研究［J］.電子學報，2009，37(5):1092－1094.

MA Jun，LIU Xiaodong，MENG Ying.Research of urban traffic flow forecasting based on neural network［J］.Acta Electronica Sinica，2009，37(5):1092－1094.

［10］朱文興，賈磊，丁緒東，等.城市交通網(wǎng)絡中的路徑優(yōu)化研究［J］.山東大學學報:工學版，2005，35(1):74－77.

ZHU Wenxing，JIA Lei，DING Xudong，et al.Research on the route optimization in urban traffic network［J］.Journal of Shandong University: Engineering Science，2005，35(1):74－77.

［11］韓力群.人工神經(jīng)網(wǎng)絡理論、設計及應用［M］.2版.北京:化學工業(yè)出版社，2007:164－191.

［12］傅薈璇，趙紅.MATLAB神經(jīng)網(wǎng)絡應用設計［M］.北京:機械工業(yè)出版社，2010:62－63.

［13］劉張雷，史忠科.城市動態(tài)時間最短路徑誘導系統(tǒng)實現(xiàn)研究［J］.控制工程，2010，17(3):351－355.

LIU Zhanglei，SHI Zhongke.Implementation of urban tmie－dependent shortest route guidance system［J］.Control Engineering of China，2010，17(3):351－355.

［14］羅嵩，王堅.智能交通系統(tǒng)的最優(yōu)路徑搜索算法的研究與實現(xiàn)［J］.機電產(chǎn)品開發(fā)與創(chuàng)新，2008，21(2):10－12.

LUO Song，WANG Jian.Optimal path search study and practice based on the intelligent transportation systems［J］.Development and Innovation of Machinery and Electrical Products，2008，21(2):10－12.

［15］PETTIE S，RAMACHANDRA V.A shortest path algorithm for real－weighted undirected graphs［J］.SIAM Journal of Computing，2005，34(6):1398－1427.

［16］王海英，黃強，李傳濤，等.圖論算法及其MATLAB實現(xiàn)［M］.北京:北京航空航天大學出版社，2010:12－18.

［17］王曉麗，楊兆升，呂旭濤，等.平行四邊形限制最短路徑算法及其在交通網(wǎng)絡中的應用［J］.吉林大學學報:工學版，2006，36(1):123－127.

WANG Xiaoli，YANG Zhaosheng，LV Xutao.Shortest path algorithm based on limiting parallelogram［J］.Journal of Jilin University:Engineering and Technology Edition，2006，36(1):123－127.

［18］魏二虎，賈滿，李林燕.最短路徑算法的改進方法研究［J］.測繪信息與工程，2007，32(4):40－42.

WEI Erhu，JIA Man，LI Linyan.On improvements for shortest path algorithm［J］.Journal of Geomatics，2007，32(4):40－42.

陳亮，男，1986年生，碩士研究生，主要研究方向為人工神經(jīng)網(wǎng)絡、智能交通.

何為，男，1953年生，高級工程師，IEEE會員，中國人工智能學會理事、智能產(chǎn)品與產(chǎn)業(yè)工作委員會秘書長，中國計量測試學會高級會員.主要研究方向為非電量檢測技術、計算機測控技術、嵌入式技術應用，主持或參與國家科技攻關、火炬計劃、省部級、橫向等各類科研項目30余項，發(fā)表學術論文30余篇，獲國家發(fā)明專利3項.

韓力群，女，1953年生，教授，中國人工智能學會副理事長.主要研究方向為智能信息處理與圖像工程技術，主持各類科研項目30余項，獲國家發(fā)明專利3項、北京發(fā)明創(chuàng)新大賽銀獎1項.發(fā)表學術論文120余篇，出版專著10部.

Radial basis function neural network modeling of the traffic path cost function

CHEN Liang，HE Wei，HAN Liqun
(College of Computer and Information Engineering，Beijing Commercial and Industrial University，Beijing 100048，China)

Vehicle route optimization is one of the hot topics in research on urban intelligent transportation systems(ITS)，and it plays an important role in the optimization of the entire transportation system.This paper analyzed various factors that affect the travel time and established a path cost function model with an radial basis function neural network，based on the shortest paths algorithms in graph theory.By this function model，the time－oriented optimal path between any two given places on a traffic map can be calculated.The model was applied to actual traffic to validate the effectiveness，and its results are of practical value，showing the correctness and validity of the model.

intelligent transportation;path cost function;vehicle route optimization;radial basis function neural network;graph theory

TP391.4

A

1673－4785(2011)05－0424－08

10.3969/j.issn.1673－4785.2011.05.006

2011－04－22.

陳亮.E－mail:newboy_01@163.com.