基于多屬性優(yōu)先級(jí)的動(dòng)態(tài)路徑規(guī)劃方法*

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

基于多屬性優(yōu)先級(jí)的動(dòng)態(tài)路徑規(guī)劃方法*

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

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

動(dòng)態(tài)路徑規(guī)劃；多屬性決策；逼近理想點(diǎn)；優(yōu)先級(jí)

0 引言

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

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

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

1 車輛移動(dòng)模型

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

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

2 道路信息分類

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

2.1 車輛速度

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

2.2 預(yù)期路程

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

2.3 道路安全系數(shù)

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

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

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

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

（2）標(biāo)準(zhǔn)化信息集R=［rij］n×m。

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

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

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

（4）確定正理想點(diǎn)r+和負(fù)理想點(diǎn)r-［8］。

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

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

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

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

（6）計(jì)算屬性信息的權(quán)重向量。

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

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

（7）代入權(quán)重向量ω=［ω1，ω2，ω3］計(jì)算每個(gè)方案與區(qū)間型理想點(diǎn)的相對(duì)貼近度 di，di值越大表示相應(yīng)的方案越優(yōu)。

4 仿真比較

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

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

表1 仿真參數(shù)設(shè)置

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

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

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

圖1 不同路徑規(guī)劃算法的仿真路徑圖

表2 不同路徑規(guī)劃算法的仿真結(jié)果

圖2 不同優(yōu)先級(jí)設(shè)置的多屬性決策方案路徑圖

方案1①安全②路程③時(shí)間。

方案2①時(shí)間②安全③路程。

方案3①路程②時(shí)間③安全。

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

表3 不同優(yōu)先級(jí)設(shè)置的多屬性決策方案對(duì)比結(jié)果

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

5 結(jié)論

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

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

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

［3］宋久元，滕國(guó)庫，胡麗霞.路徑規(guī)劃算法的改進(jìn)及在車載導(dǎo)航中的應(yīng)用［J］.計(jì)算機(jī)與數(shù)字工程，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］朱東杰，崔剛，傅忠傳.基于動(dòng)態(tài)路徑規(guī)劃的VANET車輛移動(dòng)模型研究［J］.高技術(shù)通訊，2014，24（6）：573-580.

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

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

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

［9］樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，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

李彤，李德敏，張光林，等.基于多屬性優(yōu)先級(jí)的動(dòng)態(tài)路徑規(guī)劃方法［J］.微型機(jī)與應(yīng)用，2015，34（18）：82-84，88.

2015-05-18）

李彤（1990-），女，碩士研究生，主要研究方向：車輛自組織網(wǎng)絡(luò)與應(yīng)用。

李德敏（1963-），男，博士，教授，博士生導(dǎo)師，主要研究方向：移動(dòng)計(jì)算網(wǎng)絡(luò)與應(yīng)用、自組織網(wǎng)絡(luò)與應(yīng)用。

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

國(guó)家自然科學(xué)基金（ 71171045 ， 61301118 ） ；上海市教科委創(chuàng)新項(xiàng)目（ 14YZ130 ） ；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)基金資助和東華大學(xué)“勵(lì)志計(jì)劃”基金