摘  要： 針對現(xiàn)存大多數(shù)動態(tài)路徑規(guī)劃算法目標(biāo)單一問題進(jìn)行研究，提出基于理想點(diǎn)的多屬性決策方法解決該問題，屬性的選取融合時間、路程及現(xiàn)代最為重視的安全因素，使得動態(tài)路徑規(guī)劃的結(jié)果更加均衡。同時在多屬性決策過程中引入優(yōu)先級這一概念，使得駕駛員可以根據(jù)自身的需求及駕駛技術(shù)對交通信息的重要度進(jìn)行排序，得到匹配度最高的駕駛方案。仿真結(jié)果表明，基于多屬性優(yōu)先級的動態(tài)路徑規(guī)劃算法既能夠起到多目標(biāo)均衡的路徑規(guī)劃效果，同時又能夠?qū)崿F(xiàn)個性化駕駛。

　　關(guān)鍵詞： 動態(tài)路徑規(guī)劃；多屬性決策；逼近理想點(diǎn)；優(yōu)先級

0 引言

　　車輛的動態(tài)路徑規(guī)劃是指車輛在不同地理位置根據(jù)當(dāng)前時刻的道路交通信息選擇駕駛路線的方法。根據(jù)實(shí)時交通信息作出的動態(tài)路徑規(guī)劃可以有效地避免擁堵路段、事故路段，提高行駛效率，在城市車輛規(guī)劃中有較大的應(yīng)用[1]。

　　近年來，隨著傳感網(wǎng)絡(luò)、通信技術(shù)等信息科技的發(fā)展，國內(nèi)外學(xué)者已對車輛的動態(tài)路徑規(guī)劃進(jìn)行了大量的研究，高峰、王明哲針對已有路徑選擇模型缺乏選擇決策過程的問題，提出了一種基于決策場理論的車輛路徑選擇過程框架，建立一種面向過程的車輛動態(tài)路徑選擇模型[2]。宋久元等人充分利用啟發(fā)式搜索具有方向性的啟發(fā)信息，對A*算法進(jìn)行了改進(jìn)，采用雙向的A*算法來避免過多的節(jié)點(diǎn)搜索和搜索過界的問題[3]。CHEN C L P、Zhou Jin和Zhao Wei利用基于三角模糊集的多屬性決策方法進(jìn)行動態(tài)導(dǎo)航，避免了大型傳感網(wǎng)絡(luò)中傳統(tǒng)的交通信息中心不能及時傳遞全球?qū)崟r交通信息這一問題[4]。朱東杰、崔剛等人設(shè)計了基于動態(tài)路徑規(guī)劃的車載自組網(wǎng)的車輛移動模型，并提出了一種基于Dijkstra的動態(tài)路徑規(guī)劃算法[5]。

　　然而上述研究中，仍存在一些問題：（1）現(xiàn)存動態(tài)路徑規(guī)劃算法大部分還是基于最短時間或者最短路徑，不能達(dá)到較好的平衡效果；（2）路徑規(guī)劃算法對信息的處理方式較單一，駕駛員不能進(jìn)行個性化設(shè)置。為了解決上述問題，本文將城市道路劃分為交叉路口集合和路段集合，將從出發(fā)點(diǎn)到目的地的長距離路徑規(guī)劃問題拆分成車輛在各個交叉路口時的路段選擇問題，簡化了路徑規(guī)劃過程中對全局路網(wǎng)的信息計算。路段選擇過程綜合考慮車輛速度、安全系數(shù)、預(yù)期路程3種較為重要的交通信息，利用多屬性決策法分析該問題，使得車輛的動態(tài)路徑規(guī)劃結(jié)果較為均衡。在多屬性決策過程中引入信息優(yōu)先級設(shè)置概念，按照個人偏好設(shè)置計算各交通信息的權(quán)重向量，以達(dá)到個性化駕駛的目的。

1 車輛移動模型

　　傳統(tǒng)的動態(tài)路徑規(guī)劃算法基于最短距離算法或最短時間算法進(jìn)行路徑規(guī)劃，當(dāng)車輛每次到達(dá)一個交叉路口時，通過收集到的實(shí)時交通信息檢測當(dāng)前的路徑規(guī)劃是否為最優(yōu)，若非最優(yōu)路徑，則重新規(guī)劃車輛從當(dāng)前位置到目的地的最優(yōu)路徑。該方法對當(dāng)前位置到目的地的全局路網(wǎng)進(jìn)行規(guī)劃時產(chǎn)生較大計算量，當(dāng)車輛移動速度較快時，很難起到良好的路徑規(guī)劃效果。

　　本文將城市路網(wǎng)看作交叉路口Pi與兩個相鄰交叉路口間連接路段Pi_j的集合，即G={P，R}，其中R為有向路段，即同一路徑的不同方向為不同路段。當(dāng)車輛每次行駛到交叉路口Pi時，車輛向交叉路口通信設(shè)備發(fā)送路徑規(guī)劃請求，Pi處的路口設(shè)備接收到請求信息后，發(fā)送反饋信息，將與Pi毗鄰路段的車輛速度、預(yù)期成本、安全系數(shù)等信息反饋給車載設(shè)備，車載設(shè)備根據(jù)道路屬性信息進(jìn)行多屬性決策，將最佳下一行駛方向反饋給駕駛員，重復(fù)該過程，直到車輛到達(dá)目的位置。

2 道路信息分類

　　假設(shè)交叉路口節(jié)點(diǎn)都建設(shè)有可以進(jìn)行無線通信、有線通信和信息存儲的路旁設(shè)備，路網(wǎng)中的每輛車都安裝通信設(shè)備、GPS和電子地圖。為了實(shí)現(xiàn)車輛在交叉路口的路段選擇，需要搜集3種道路交通信息：車輛速度、預(yù)期成本、安全系數(shù)。

　　2.1 車輛速度

　　車輛速度v表示路段上正在行駛的全部車輛的速度，由于路段上同時行駛的車輛速度不同，因此可以用區(qū)間數(shù)來表示該路段的車輛速度，即v=[vL，vU]。車輛速度越快，表明道路越暢通，因此該信息為效益型信息。

　　2.2 預(yù)期路程

　　預(yù)期路程s表示車輛從當(dāng)前位置到達(dá)目的地的預(yù)期路程，實(shí)際問題中該信息在一定范圍內(nèi)取值，因此用區(qū)間數(shù)表示s=sL，sU」。車輛行駛到交叉路口時，由于可能選擇不同路段導(dǎo)致不同預(yù)期路程，顯然預(yù)期路程越大，車輛行駛的開銷越大，因此該信息為成本型信息。

　　2.3 道路安全系數(shù)

　　道路安全系數(shù)b表示路段交通環(huán)境的安全程度，不同的路段寬度、路段坡度、路面行駛質(zhì)量、路面視認(rèn)性會對其數(shù)值產(chǎn)生較大影響[6]。路段的道路安全系數(shù)越高，發(fā)生交通事故的可能性就越小，因此該信息為效益型信息。

　　3 多屬性優(yōu)先級路徑?jīng)Q策

　　車輛行駛過程中與前方交叉路口設(shè)備建立通信，獲取到了其連接的不同路段的3種道路交通信息，但是其在決策中所占的權(quán)重并不清楚，因此本文采用逼近理想點(diǎn)法來解決權(quán)重模糊的多屬性決策問題。與傳統(tǒng)算法不同的是，本文所提出的算法中加入了優(yōu)先級的概念，即駕駛員可以根據(jù)個人駕駛需求、習(xí)慣等對道路交通信息設(shè)置不同的優(yōu)先級，選擇不同的決策模型進(jìn)行路徑規(guī)劃，從而達(dá)到個性化的動態(tài)路徑規(guī)劃目的。具體計算步驟如下：

　?。?）確定備選道路的信息集A=[aij]n×m。其中i表示前方路口所連接的道路編號，1≤n≤4；j表示同一路段不同道路信息，1≤m≤3。

　?。?）標(biāo)準(zhǔn)化信息集R=[rij]n×m。

　　為了消除不同物理量綱對路徑選擇的影響，將已知的信息數(shù)據(jù)標(biāo)準(zhǔn)化，標(biāo)準(zhǔn)化公式如下[7]：

　?。?）設(shè)置路段交通信息優(yōu)先級。

　　依據(jù)駕駛員的個人偏好確定3種交通信息重要度的優(yōu)先級，其中1為最高級，3為最低級，根據(jù)信息的優(yōu)先級將集合R中的數(shù)據(jù)重新排列為R′。

　?。?）確定正理想點(diǎn)r+和負(fù)理想點(diǎn)r-[8]。

　?。?）計算不同優(yōu)先級的交通信息與正負(fù)理想點(diǎn)偏差。

　　若交通信息優(yōu)先級為1，偏差計算公式為：

　?。?）計算屬性信息的權(quán)重向量。

　　為了使所有路徑選擇方案在所有路段交通信息作用下與正理想點(diǎn)偏差最小與負(fù)理想點(diǎn)偏差最大，?棕需滿足[8]：

　　d（rij，rj-）、d（rij，rj+）均為已知量，易根據(jù)式（8）計算得出精確的權(quán)重向量。

　?。?）代入權(quán)重向量?棕=[?棕1，?棕2，?棕3]計算每個方案與區(qū)間型理想點(diǎn)的相對貼近度di，di值越大表示相應(yīng)的方案越優(yōu)。

4 仿真比較

　　為了證明本文提出算法的適用性及有效性，構(gòu)建一個7×9的路網(wǎng)對其進(jìn)行仿真，將本文提出的基于多屬性優(yōu)先級路徑規(guī)劃算法與最短距離路徑規(guī)劃法[9]、最短時間路徑規(guī)劃法[10]進(jìn)行對比。

　　仿真過程中，車輛從位置0出發(fā)，行駛目的地為位置9，假設(shè)0~9路段車輛速度較慢，10~19、20~29、30~39路段車輛速度中等，50~59路段車輛速度非?？?，其他路段車輛速度較快；0~9路段安全級別為較差，10~19、50~59路段安全級別為一般，30~39、40~49路段安全級別為非常好，其他路段安全級別為較好，詳細(xì)參數(shù)設(shè)置如表1所示。

　　按照上述設(shè)置對最短距離算法、最短時間算法、非個性化多屬性決策算法進(jìn)行仿真，得到3種算法的路徑規(guī)劃如圖1所示。根據(jù)路徑圖，可以通過加權(quán)平均的方式計算出不同路徑規(guī)劃算法下車輛的行駛路程、平均速度、行駛時間、平均安全系數(shù)等參數(shù)，如表2所示。

　　從表2可以看到，多屬性決策算法規(guī)劃的動態(tài)路徑各項指標(biāo)比較均衡，兼顧了多重交通信息，能夠使駕駛員得到更良好的駕駛體驗。

　　依據(jù)駕駛員的需求和駕駛技術(shù)，可以選擇多屬性優(yōu)先級的方法進(jìn)行路徑規(guī)劃，本文以下述3種優(yōu)先級方案為例仿真，得到路徑規(guī)劃結(jié)果如圖2所示。

　　方案1 ①安全②路程③時間。

　　方案2 ①時間②安全③路程。

　　方案3 ①路程②時間③安全。

　　根據(jù)圖2路徑圖，同樣可以計算得出車輛在多屬性決策算法的不同個性化設(shè)置下，車輛的行駛路程、平均速度、行駛時間、平均安全系數(shù)等參數(shù)，如表3所示。

　　仿真結(jié)果表明，使用多屬性優(yōu)先級的動態(tài)路徑規(guī)劃方法既綜合考慮各項交通信息對駕駛的影響，同時又能夠讓駕駛需求、駕駛技術(shù)不同的駕駛員有個性化的駕駛體驗。

5 結(jié)論

　　本文提出了一種基于多屬性優(yōu)先級的車輛動態(tài)路徑規(guī)劃方法，該算法改善了最短路徑算法、最短時間算法追求單一指標(biāo)最優(yōu)化的情況，得到均衡了時間、路程及道路安全狀況等因素的路徑規(guī)劃結(jié)果。同時在多屬性決策進(jìn)行路徑規(guī)劃的過程中，引入了優(yōu)先級設(shè)置方法，能夠區(qū)分不同交通信息的重要程度，方便駕駛員根據(jù)其需求設(shè)置，完成個性化駕駛的目的。

參考文獻(xiàn)

　　[1] 鄧向林.基于動態(tài)規(guī)劃算法的出租車合乘模式研究[J].微型機(jī)與應(yīng)用，2013，32（8）：79-81，84.

　　[2] 高峰，王明哲.面向決策過程的動態(tài)路徑選擇模型[J].交通運(yùn)輸系統(tǒng)工程與信息，2009，9（5）：96-102.

　　[3] 宋久元，滕國庫，胡麗霞.路徑規(guī)劃算法的改進(jìn)及在車載導(dǎo)航中的應(yīng)用[J].計算機(jī)與數(shù)字工程，2010，35（8）：95-98.

　　[4] CHEN C L P， Zhou Jin， Zhao Wei. A real-time vehicle navigation algorithm in sensor network environments[J]. IEEE Transaction on Intelligent Transportation Systems， 2012， 13 （4）： 1657-1666.

　　[5] 朱東杰，崔剛，傅忠傳.基于動態(tài)路徑規(guī)劃的VANET車輛移動模型研究[J].高技術(shù)通訊，2014，24（6）：573-580.

　　[6] 魏朗，高麗敏，余強(qiáng)，等.駕駛員道路安全感受模糊評判模型[J].交通運(yùn)輸工程學(xué)報，2004，4（1）：102-105.

　　[7] 達(dá)慶利，徐澤水.不確定多屬性決策的單目標(biāo)最優(yōu)化模型[J].系統(tǒng)工程學(xué)報，2002，17（1）：50-55.

　　[8] 和媛媛，周德群.區(qū)間數(shù)多屬性決策問題的逼近理想點(diǎn)方法[J].統(tǒng)計與決策，2009（24）：9-11.

　　[9] 樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)[J].武漢測繪科技大學(xué)學(xué)報，1999，24（3）：209-212.

　　[10] CHABINI I， LAN S. Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks[J]. IEEE Transaction on Intelligent Transportation Systems， 2002，5（3）：60-74.