陳亮，何為，韓力群

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

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

陳亮，何為，韓力群

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

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

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

在城市智能交通系統(tǒng)中，行車路線優(yōu)化對整個交通系統(tǒng)的優(yōu)化起著重要作用，選取最優(yōu)車輛行車路線，可以加快車流速度，減少擁堵發(fā)生，還能減少因?yàn)槎萝嚩斐傻慕煌ㄜ囕v刮蹭等事故的概率，因此，該課題的研究具有重要的實(shí)用意義.

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

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

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

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

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

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

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

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

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

2.1 基于正交實(shí)驗(yàn)的訓(xùn)練集設(shè)計

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

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

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

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

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

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

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

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

2.3 模型驗(yàn)證

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

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

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

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

3 應(yīng)用實(shí)例

3.1 應(yīng)用實(shí)例概述

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

圖2 實(shí)際交通道路Fig.2 Actual traffic roads

可達(dá)路徑的搜索方法如下.

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

2)建立加權(quán)有向圖的鄰接矩陣.

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

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

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

圖3 加權(quán)有向圖Fig.3 Weighted directed graph

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

續(xù)表6

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

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

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

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

圖4 實(shí)時交通路況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 可達(dá)路線生成算法的改進(jìn)

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

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

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

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

3.4 有效性驗(yàn)證

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

4 結(jié)束語

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

［1］張渭軍，王華.城市道路最短路徑的Dijkstra算法優(yōu)化［J］.長安大學(xué)學(xué)報:自然科學(xué)版，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］姜桂艷，鄭祖舵.基于記憶機(jī)制的動態(tài)交通路徑優(yōu)化算法［J］.吉林大學(xué)學(xué)報:工學(xué)版，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］徐俊明.圖論及其應(yīng)用［M］.3版.合肥:中國科學(xué)技術(shù)大學(xué)出版社，2010:21－53.

［7］劉海燕.智能交通系統(tǒng)的車輛行駛最佳路徑算法［J］.北京工商大學(xué)學(xué)報:自然科學(xué)版，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)絡(luò)教程［M］.北京:北京郵電大學(xué)出版社，2006:127－143.

［9］馬君，劉曉東，孟穎.基于神經(jīng)網(wǎng)絡(luò)的城市交通流預(yù)測研究［J］.電子學(xué)報，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)絡(luò)中的路徑優(yōu)化研究［J］.山東大學(xué)學(xué)報:工學(xué)版，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)絡(luò)理論、設(shè)計及應(yīng)用［M］.2版.北京:化學(xué)工業(yè)出版社，2007:164－191.

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

［13］劉張雷，史忠科.城市動態(tài)時間最短路徑誘導(dǎo)系統(tǒng)實(shí)現(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)路徑搜索算法的研究與實(shí)現(xiàn)［J］.機(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］王海英，黃強(qiáng)，李傳濤，等.圖論算法及其MATLAB實(shí)現(xiàn)［M］.北京:北京航空航天大學(xué)出版社，2010:12－18.

［17］王曉麗，楊兆升，呂旭濤，等.平行四邊形限制最短路徑算法及其在交通網(wǎng)絡(luò)中的應(yīng)用［J］.吉林大學(xué)學(xué)報:工學(xué)版，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ìn)方法研究［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年生，碩士研究生，主要研究方向?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)、智能交通.

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

韓力群，女，1953年生，教授，中國人工智能學(xué)會副理事長.主要研究方向?yàn)橹悄苄畔⑻幚砼c圖像工程技術(shù)，主持各類科研項(xiàng)目30余項(xiàng)，獲國家發(fā)明專利3項(xiàng)、北京發(fā)明創(chuàng)新大賽銀獎1項(xiàng).發(fā)表學(xué)術(shù)論文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.