基于多屬性優先級的動態路徑規劃方法*

李 彤，李德敏，張光林，吳思畏（1.東華大學 信息科學技術學院，上海 201620；2.教育部 數字化紡織服裝技術工程研究中心，上海 200000）

基于多屬性優先級的動態路徑規劃方法*

李 彤1，2，李德敏1，2，張光林1，2，吳思畏1，2
（1.東華大學 信息科學技術學院，上海 201620；2.教育部 數字化紡織服裝技術工程研究中心，上海 200000）

針對現存大多數動態路徑規劃算法目標單一問題進行研究，提出基于理想點的多屬性決策方法解決該問題，屬性的選取融合時間、路程及現代最為重視的安全因素，使得動態路徑規劃的結果更加均衡。同時在多屬性決策過程中引入優先級這一概念，使得駕駛員可以根據自身的需求及駕駛技術對交通信息的重要度進行排序，得到匹配度最高的駕駛方案。仿真結果表明，基于多屬性優先級的動態路徑規劃算法既能夠起到多目標均衡的路徑規劃效果，同時又能夠實現個性化駕駛。

動態路徑規劃；多屬性決策；逼近理想點；優先級

0 引言

車輛的動態路徑規劃是指車輛在不同地理位置根據當前時刻的道路交通信息選擇駕駛路線的方法。根據實時交通信息作出的動態路徑規劃可以有效地避免擁堵路段、事故路段，提高行駛效率，在城市車輛規劃中有較大的應用［1］。

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

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

1 車輛移動模型

傳統的動態路徑規劃算法基于最短距離算法或最短時間算法進行路徑規劃，當車輛每次到達一個交叉路口時，通過收集到的實時交通信息檢測當前的路徑規劃是否為最優，若非最優路徑，則重新規劃車輛從當前位置到目的地的最優路徑。該方法對當前位置到目的地的全局路網進行規劃時產生較大計算量，當車輛移動速度較快時，很難起到良好的路徑規劃效果。

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

2 道路信息分類

假設交叉路口節點都建設有可以進行無線通信、有線通信和信息存儲的路旁設備，路網中的每輛車都安裝通信設備、GPS和電子地圖。為了實現車輛在交叉路口的路段選擇，需要搜集3種道路交通信息：車輛速度、預期成本、安全系數。

2.1 車輛速度

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

2.2 預期路程

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

2.3 道路安全系數

道路安全系數b表示路段交通環境的安全程度，不同的路段寬度、路段坡度、路面行駛質量、路面視認性會對其數值產生較大影響［6］。路段的道路安全系數越高，發生交通事故的可能性就越小，因此該信息為效益型信息。

3 多屬性優先級路徑決策

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

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

（2）標準化信息集R=［rij］n×m。

為了消除不同物理量綱對路徑選擇的影響，將已知的信息數據標準化，標準化公式如下［7］：

（3）設置路段交通信息優先級。

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

（4）確定正理想點r+和負理想點r-［8］。

（5）計算不同優先級的交通信息與正負理想點偏差。

若交通信息優先級為1，偏差計算公式為：

若交通信息優先級為2，偏差計算公式為：

若交通信息優先級為3，偏差計算公式為：

（6）計算屬性信息的權重向量。

為了使所有路徑選擇方案在所有路段交通信息作用下與正理想點偏差最小與負理想點偏差最大，ω需滿足［8］：

d（rij，rj-）、d（rij，rj+）均為已知量，易根據式（8）計算得出精確的權重向量ω=［ω1，ω2，ω3］。

（7）代入權重向量ω=［ω1，ω2，ω3］計算每個方案與區間型理想點的相對貼近度 di，di值越大表示相應的方案越優。

4 仿真比較

為了證明本文提出算法的適用性及有效性，構建一個7×9的路網對其進行仿真，將本文提出的基于多屬性優先級路徑規劃算法與最短距離路徑規劃法［9］、最短時間路徑規劃法［10］進行對比。

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

表1 仿真參數設置

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

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

依據駕駛員的需求和駕駛技術，可以選擇多屬性優先級的方法進行路徑規劃，本文以下述3種優先級方案為例仿真，得到路徑規劃結果如圖2所示。

圖1 不同路徑規劃算法的仿真路徑圖

表2 不同路徑規劃算法的仿真結果

圖2 不同優先級設置的多屬性決策方案路徑圖

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

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

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

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

表3 不同優先級設置的多屬性決策方案對比結果

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

5 結論

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

［1］鄧向林.基于動態規劃算法的出租車合乘模式研究［J］.微型機與應用，2013，32（8）：79-81，84.

［2］高峰，王明哲.面向決策過程的動態路徑選擇模型［J］.交通運輸系統工程與信息，2009，9（5）：96-102.

［3］宋久元，滕國庫，胡麗霞.路徑規劃算法的改進及在車載導航中的應用［J］.計算機與數字工程，2010，35（8）：95-98.

［4］CHEN C L P，Zhou Jin，Zhao Wei.A real-time vehicle navigation algorithm in sensornetwork environments［J］.IEEE Transaction on IntelligentTransportation Systems，2012，13（4）：1657-1666.

［5］朱東杰，崔剛，傅忠傳.基于動態路徑規劃的VANET車輛移動模型研究［J］.高技術通訊，2014，24（6）：573-580.

［6］魏朗，高麗敏，余強，等.駕駛員道路安全感受模糊評判模型［J］.交通運輸工程學報，2004，4（1）：102-105.

［7］達慶利，徐澤水.不確定多屬性決策的單目標最優化模型［J］.系統工程學報，2002，17（1）：50-55.

［8］和媛媛，周德群.區間數多屬性決策問題的逼近理想點方法［J］.統計與決策，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 discretetime dynamic networks［J］.IEEE Transaction on Intelligent Transportation Systems，2002，5（3）：60-74.

Dynamic route planning method based on multi-attribute and priority

Li Tong1，2，Li Demin1，2，Zhang Guanglin1，2，Wu Siwei1，2
（1.College of Information Science and Technology，Donghua University，Shanghai 201620，China；2.Engineering Research Center of Digitized Textile ＆ Fashion Technology，Ministry of Education，Shanghai 200000，China）

Most dynamic route planning methods now existed only have a single target.In view of this circumstance，a method called MADM based on the ideal point is proposed to solve this problem.The attributes merge time，distance and safety together to make a balance routing result.It also introduces an idea of priority to sort the traffic information according to their requirement and road sense，and finally the traveler could get the best route navigation.The result of simulation shows the dynamic route planning method based on multi-attribute and priority can make multi-objective of route planning equilibrium，as well as can realize a personalized driven.

dynamic route planning；multi-attribute decision making；gain on ideal point；priority

TP391

A

1674-7720（2015）18-0082-03

李彤，李德敏，張光林，等.基于多屬性優先級的動態路徑規劃方法［J］.微型機與應用，2015，34（18）：82-84，88.

2015-05-18）

李彤（1990-），女，碩士研究生，主要研究方向：車輛自組織網絡與應用。

李德敏（1963-），男，博士，教授，博士生導師，主要研究方向：移動計算網絡與應用、自組織網絡與應用。

張光林（1981-），通信作者，男，博士，副教授，主要研究方向：無線網絡、車輛自組網。E-mail：glzhang@dhu.edu.cn。

國家自然科學基金（ 71171045 ， 61301118 ） ；上海市教科委創新項目（ 14YZ130 ） ；中央高校基本科研業務費專項基金資助和東華大學“勵志計劃”基金