摘 要： 針對現存大多數動態(tài)路徑規(guī)劃算法目標單一問題進行研究，提出基于理想點的多屬性決策方法解決該問題，屬性的選取融合時間、路程及現代最為重視的安全因素，使得動態(tài)路徑規(guī)劃的結果更加均衡。同時在多屬性決策過程中引入優(yōu)先級這一概念，使得駕駛員可以根據自身的需求及駕駛技術對交通信息的重要度進行排序，得到匹配度最高的駕駛方案。仿真結果表明，基于多屬性優(yōu)先級的動態(tài)路徑規(guī)劃算法既能夠起到多目標均衡的路徑規(guī)劃效果，同時又能夠實現個性化駕駛。
關鍵詞： 動態(tài)路徑規(guī)劃；多屬性決策；逼近理想點；優(yōu)先級
0 引言
車輛的動態(tài)路徑規(guī)劃是指車輛在不同地理位置根據當前時刻的道路交通信息選擇駕駛路線的方法。根據實時交通信息作出的動態(tài)路徑規(guī)劃可以有效地避免擁堵路段、事故路段，提高行駛效率，在城市車輛規(guī)劃中有較大的應用[1]。
近年來，隨著傳感網絡、通信技術等信息科技的發(fā)展，國內外學者已對車輛的動態(tài)路徑規(guī)劃進行了大量的研究，高峰、王明哲針對已有路徑選擇模型缺乏選擇決策過程的問題，提出了一種基于決策場理論的車輛路徑選擇過程框架，建立一種面向過程的車輛動態(tài)路徑選擇模型[2]。宋久元等人充分利用啟發(fā)式搜索具有方向性的啟發(fā)信息，對A*算法進行了改進，采用雙向的A*算法來避免過多的節(jié)點搜索和搜索過界的問題[3]。CHEN C L P、Zhou Jin和Zhao Wei利用基于三角模糊集的多屬性決策方法進行動態(tài)導航，避免了大型傳感網絡中傳統(tǒng)的交通信息中心不能及時傳遞全球實時交通信息這一問題[4]。朱東杰、崔剛等人設計了基于動態(tài)路徑規(guī)劃的車載自組網的車輛移動模型，并提出了一種基于Dijkstra的動態(tài)路徑規(guī)劃算法[5]。
然而上述研究中，仍存在一些問題：（1）現存動態(tài)路徑規(guī)劃算法大部分還是基于最短時間或者最短路徑，不能達到較好的平衡效果；（2）路徑規(guī)劃算法對信息的處理方式較單一，駕駛員不能進行個性化設置。為了解決上述問題，本文將城市道路劃分為交叉路口集合和路段集合，將從出發(fā)點到目的地的長距離路徑規(guī)劃問題拆分成車輛在各個交叉路口時的路段選擇問題，簡化了路徑規(guī)劃過程中對全局路網的信息計算。路段選擇過程綜合考慮車輛速度、安全系數、預期路程3種較為重要的交通信息，利用多屬性決策法分析該問題，使得車輛的動態(tài)路徑規(guī)劃結果較為均衡。在多屬性決策過程中引入信息優(yōu)先級設置概念，按照個人偏好設置計算各交通信息的權重向量，以達到個性化駕駛的目的。
1 車輛移動模型
傳統(tǒng)的動態(tài)路徑規(guī)劃算法基于最短距離算法或最短時間算法進行路徑規(guī)劃，當車輛每次到達一個交叉路口時，通過收集到的實時交通信息檢測當前的路徑規(guī)劃是否為最優(yōu)，若非最優(yōu)路徑，則重新規(guī)劃車輛從當前位置到目的地的最優(yōu)路徑。該方法對當前位置到目的地的全局路網進行規(guī)劃時產生較大計算量，當車輛移動速度較快時，很難起到良好的路徑規(guī)劃效果。
本文將城市路網看作交叉路口Pi與兩個相鄰交叉路口間連接路段Pi_j的集合，即G={P，R}，其中R為有向路段，即同一路徑的不同方向為不同路段。當車輛每次行駛到交叉路口Pi時，車輛向交叉路口通信設備發(fā)送路徑規(guī)劃請求，Pi處的路口設備接收到請求信息后，發(fā)送反饋信息，將與Pi毗鄰路段的車輛速度、預期成本、安全系數等信息反饋給車載設備，車載設備根據道路屬性信息進行多屬性決策，將最佳下一行駛方向反饋給駕駛員，重復該過程，直到車輛到達目的位置。
2 道路信息分類
假設交叉路口節(jié)點都建設有可以進行無線通信、有線通信和信息存儲的路旁設備，路網中的每輛車都安裝通信設備、GPS和電子地圖。為了實現車輛在交叉路口的路段選擇，需要搜集3種道路交通信息：車輛速度、預期成本、安全系數。
2.1 車輛速度
車輛速度v表示路段上正在行駛的全部車輛的速度，由于路段上同時行駛的車輛速度不同，因此可以用區(qū)間數來表示該路段的車輛速度，即v=[vL，vU]。車輛速度越快，表明道路越暢通，因此該信息為效益型信息。
2.2 預期路程
預期路程s表示車輛從當前位置到達目的地的預期路程，實際問題中該信息在一定范圍內取值，因此用區(qū)間數表示s=sL，sU」。車輛行駛到交叉路口時，由于可能選擇不同路段導致不同預期路程，顯然預期路程越大，車輛行駛的開銷越大，因此該信息為成本型信息。
2.3 道路安全系數
道路安全系數b表示路段交通環(huán)境的安全程度，不同的路段寬度、路段坡度、路面行駛質量、路面視認性會對其數值產生較大影響[6]。路段的道路安全系數越高，發(fā)生交通事故的可能性就越小，因此該信息為效益型信息。
3 多屬性優(yōu)先級路徑決策
車輛行駛過程中與前方交叉路口設備建立通信，獲取到了其連接的不同路段的3種道路交通信息，但是其在決策中所占的權重并不清楚，因此本文采用逼近理想點法來解決權重模糊的多屬性決策問題。與傳統(tǒng)算法不同的是，本文所提出的算法中加入了優(yōu)先級的概念，即駕駛員可以根據個人駕駛需求、習慣等對道路交通信息設置不同的優(yōu)先級，選擇不同的決策模型進行路徑規(guī)劃，從而達到個性化的動態(tài)路徑規(guī)劃目的。具體計算步驟如下：
?。?）確定備選道路的信息集A=[aij]n×m。其中i表示前方路口所連接的道路編號，1≤n≤4；j表示同一路段不同道路信息，1≤m≤3。
?。?）標準化信息集R=[rij]n×m。
為了消除不同物理量綱對路徑選擇的影響，將已知的信息數據標準化，標準化公式如下[7]：
?。?）設置路段交通信息優(yōu)先級。
依據駕駛員的個人偏好確定3種交通信息重要度的優(yōu)先級，其中1為最高級，3為最低級，根據信息的優(yōu)先級將集合R中的數據重新排列為R′。
?。?）確定正理想點r+和負理想點r-[8]。
（5）計算不同優(yōu)先級的交通信息與正負理想點偏差。
若交通信息優(yōu)先級為1，偏差計算公式為：
（6）計算屬性信息的權重向量。
為了使所有路徑選擇方案在所有路段交通信息作用下與正理想點偏差最小與負理想點偏差最大，?棕需滿足[8]：
d（rij，rj-）、d（rij，rj+）均為已知量，易根據式（8）計算得出精確的權重向量。
（7）代入權重向量?棕=[?棕1，?棕2，?棕3]計算每個方案與區(qū)間型理想點的相對貼近度di，di值越大表示相應的方案越優(yōu)。
4 仿真比較
為了證明本文提出算法的適用性及有效性，構建一個7×9的路網對其進行仿真，將本文提出的基于多屬性優(yōu)先級路徑規(guī)劃算法與最短距離路徑規(guī)劃法[9]、最短時間路徑規(guī)劃法[10]進行對比。
仿真過程中，車輛從位置0出發(fā)，行駛目的地為位置9，假設0~9路段車輛速度較慢，10~19、20~29、30~39路段車輛速度中等，50~59路段車輛速度非常快，其他路段車輛速度較快；0~9路段安全級別為較差，10~19、50~59路段安全級別為一般，30~39、40~49路段安全級別為非常好，其他路段安全級別為較好，詳細參數設置如表1所示。
按照上述設置對最短距離算法、最短時間算法、非個性化多屬性決策算法進行仿真，得到3種算法的路徑規(guī)劃如圖1所示。根據路徑圖，可以通過加權平均的方式計算出不同路徑規(guī)劃算法下車輛的行駛路程、平均速度、行駛時間、平均安全系數等參數，如表2所示。
從表2可以看到，多屬性決策算法規(guī)劃的動態(tài)路徑各項指標比較均衡，兼顧了多重交通信息，能夠使駕駛員得到更良好的駕駛體驗。
依據駕駛員的需求和駕駛技術，可以選擇多屬性優(yōu)先級的方法進行路徑規(guī)劃，本文以下述3種優(yōu)先級方案為例仿真，得到路徑規(guī)劃結果如圖2所示。
方案1 ①安全②路程③時間。
方案2 ①時間②安全③路程。
方案3 ①路程②時間③安全。
根據圖2路徑圖，同樣可以計算得出車輛在多屬性決策算法的不同個性化設置下，車輛的行駛路程、平均速度、行駛時間、平均安全系數等參數，如表3所示。
仿真結果表明，使用多屬性優(yōu)先級的動態(tài)路徑規(guī)劃方法既綜合考慮各項交通信息對駕駛的影響，同時又能夠讓駕駛需求、駕駛技術不同的駕駛員有個性化的駕駛體驗。
5 結論
本文提出了一種基于多屬性優(yōu)先級的車輛動態(tài)路徑規(guī)劃方法，該算法改善了最短路徑算法、最短時間算法追求單一指標最優(yōu)化的情況，得到均衡了時間、路程及道路安全狀況等因素的路徑規(guī)劃結果。同時在多屬性決策進行路徑規(guī)劃的過程中，引入了優(yōu)先級設置方法，能夠區(qū)分不同交通信息的重要程度，方便駕駛員根據其需求設置，完成個性化駕駛的目的。
參考文獻
[1] 鄧向林.基于動態(tài)規(guī)劃算法的出租車合乘模式研究[J].微型機與應用，2013，32（8）：79-81，84.
[2] 高峰，王明哲.面向決策過程的動態(tài)路徑選擇模型[J].交通運輸系統(tǒng)工程與信息，2009，9（5）：96-102.
[3] 宋久元，滕國庫，胡麗霞.路徑規(guī)劃算法的改進及在車載導航中的應用[J].計算機與數字工程，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].高技術通訊，2014，24（6）：573-580.
[6] 魏朗，高麗敏，余強，等.駕駛員道路安全感受模糊評判模型[J].交通運輸工程學報，2004，4（1）：102-105.
[7] 達慶利，徐澤水.不確定多屬性決策的單目標最優(yōu)化模型[J].系統(tǒng)工程學報，2002，17（1）：50-55.
[8] 和媛媛，周德群.區(qū)間數多屬性決策問題的逼近理想點方法[J].統(tǒng)計與決策，2009（24）：9-11.
[9] 樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實現[J].武漢測繪科技大學學報，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.