龍瓊，曾革, ，張謹帆，張蕾

(1. 湖南城市學院 土木工程學院，湖南 益陽，413000；2. 長沙理工大學 交通運輸工程學院，湖南 長沙，410004)

動態(tài)路徑誘導研究的核心問題是：在動態(tài)的交通路網(wǎng)中，找出1條考慮駕駛員路徑選擇行為的最優(yōu)道路，從而使得駕駛員順利地從起點到達終點[1-4]。在傳統(tǒng)的路徑誘導方法研究中，一般以出行時間最短或出行距離最短作為優(yōu)化目標。這種方法雖然降低了最優(yōu)路徑搜索問題的難度，但是，由于忽略了駕駛員的個性化需求，誘導系統(tǒng)向不同駕駛員提供的最優(yōu)路徑是一樣的，這將引起出行者的過度反應或集聚效應，從而導致?lián)頂D漂移現(xiàn)象。擁擠漂移現(xiàn)象的產(chǎn)生會使得路網(wǎng)中的交通流處于失衡狀態(tài)，同時，這會大大增加駕駛員對交通誘導系統(tǒng)的不信任度，從而對交通流誘導技術(shù)的應用與推廣產(chǎn)生較大的負面影響。鑒于此，一些學者提出采用k-最短路算法來同時求取多條候選路徑供駕駛員選擇，將最后的決策權(quán)留給駕駛員[5-8]。此種方法能有效分散交通流，緩解擁擠漂移問題，但同時帶來了需要駕駛員對各條路徑的進行個性化評價的問題。孫燕等[9-12]利用灰色理論、模糊數(shù)學、神經(jīng)網(wǎng)絡等方法探討了該問題。但在通常情況下，這些路徑搜索與路徑評價相互獨立：路徑搜索基于傳統(tǒng)的靜態(tài)交通路網(wǎng)即可完成；而在路徑評價過程中需要能夠反映駕駛員個性化需求的交通信息，兩者對交通路網(wǎng)的信息需求的不一致性，給實際應用帶來了一定的難度。駕駛員對于路徑選擇的行為特征較復雜，不同駕駛員選擇最優(yōu)路徑的標準不是固定不變的。為此，本文作者在分析個性化動態(tài)路徑誘導問題的基礎(chǔ)上，提出一種面向駕駛員個性化需求的動態(tài)路徑誘導方法。首先，構(gòu)建路段交通阻抗評價指標體系，基于物理規(guī)劃的思想，動態(tài)確定相應的路網(wǎng)搜索空間；其次，引入駕駛員偏好因子，對搜索空間各路段進行實時綜合評價，得到反映駕駛員個性化需求的各路段綜合交通阻抗；而后利用Dijkstra算法實現(xiàn)最優(yōu)路徑搜索, 由此獲得的最優(yōu)路徑既考慮了各出行影響因素, 又充分體現(xiàn)了不同駕駛員的出行意愿。

1 個性化動態(tài)路徑誘導問題

將交通路網(wǎng)表達為G(V,A,T)。其中：V為路網(wǎng)所有節(jié)點vi的集合；A為所有路段Ai,j的集合；下標i和j為路網(wǎng)節(jié)點標識；T∈[t0,tm]為路阻變化可獲知或預測的時間段。設(shè)路段Ai,j的阻抗為fi,j(x1,x2,· · ·,xm)，表示從節(jié)點vi出發(fā)到節(jié)點vj的交通阻抗函數(shù)；X= ｛xi|i= 1 ,2,···m｝ ，為交通阻抗評價指標，則個性化動態(tài)路徑誘導問題可以描述為：基于能夠全面反映路網(wǎng)特征的評價指標體系X，引入駕駛員的個性化偏好因子，構(gòu)建能夠反映駕駛員個性化特征的交通路網(wǎng)G(V,A,T)，并從中尋找1條從t0時刻出發(fā)、自起始點v0到目標點vN的最能夠滿足駕駛員個性化需求的路徑∏｛v0,v1,· · ·,vN｝ ，并使得目標函數(shù)最小。因此，構(gòu)建合適的評價指標體系，將駕駛員的個性化偏好實時地表達在交通路網(wǎng)G(V,A,T)中是本文研究的重點。

2 評價指標體系構(gòu)建

評價某條路段的優(yōu)劣時，僅僅考慮其行程距離或者行程時間是不夠的，還應該考慮可行路段的特點、駕駛員的個性需求、特定出行的性質(zhì)(如目的、預算)以及駕駛環(huán)境(如天氣、白天晚上)等因素，因此，路段評價具有一定的主觀性，因人而異。從駕駛員的角度考慮，理想最優(yōu)路徑的確定過程應綜合考慮各主要出行影響因素并充分體現(xiàn)駕駛員的主動性[13]。本文綜合考慮駕駛員的個性化需求，構(gòu)建路段綜合交通阻抗評價指標體系如下：

其中：x1為路段行程距離；x2為路段每公里行程時間；x3為舒適度，綜合考慮路段的擁擠程度、車道數(shù)、道路質(zhì)量等級、行人及非機動車數(shù)量等因素的影響而獲得的路段評價指標；x4為安全度，根據(jù)路段交通事故率來度量；x5為路段每公里行程費用，主要考慮路段收費和油耗；x6為路段沿途景觀，戶外游玩時，沿途景觀往往是1個需要考慮的因素。值得說明的是，x2為路段每公里行程時間，實際等價于對路段行駛速度的評價。

這些指標從總體上可分為定性指標和定量指標。定性化指標無量綱包括舒適度和沿途景觀，本文采用定性等級評分法來描述各指標；定量化指標可以通過測算、建模等方法來獲得，如行程距離、行程時間、安全度和行程費用，但各指標之間的量綱不同。具體地說，建立評價指標的度量標準如表1所示。

表1 評價指標度量標準Table 1 Metrics of evaluation

從表1可以看出：對于每條道路，其每公里行程時間、舒適度、安全度、行程費用和沿途景觀等指標的行駛代價均與路段行程距離直接相關(guān)，即當路段越長時，因行程時間、舒適度、安全度、行程費用、沿途景觀產(chǎn)生的路阻代價將越大。

3 基于物理規(guī)劃的個性化動態(tài)路徑誘導

3.1 物理規(guī)劃的基本思路

物理規(guī)劃是一種處理多目標優(yōu)化設(shè)計問題的有效方法。該方法能夠從本質(zhì)上把握使用者的偏好，是處理多目標優(yōu)化問題的新框架。其基本思路是[14-15]：引入偏好函數(shù)，描述評價主體對某一評價指標的個性化需求；引入偏好因子，將不同物理意義的各種評價指標轉(zhuǎn)換為具有相同數(shù)量級的無量綱的滿意度目標；通過優(yōu)化，尋求對綜合目標的滿意度最優(yōu)解作為問題解。在一般情況下，設(shè)計評價指標的偏好函數(shù)僅為Class1-S型(設(shè)計指標越小越好)和Class2-S型(設(shè)計指標越大越好)，以Class1-S型為例(見圖1)，對某一設(shè)計指標進行區(qū)間劃分，其中xi1～xi5是設(shè)計者根據(jù)其偏好給定的評價指標xi的區(qū)間端點值。

圖1 駕駛員對道路評價指標的偏好函數(shù)Fig.1 Preference function of drivers on road evaluation index

從圖1可以看出：加駕駛員對路徑的個性化選擇過程可以描述為：在各項路徑評價指標均可接受的范圍內(nèi)，通過在動態(tài)交通路網(wǎng)中合理表達自身的個性化需要，自動搜索獲得最符合個性化需求的行車路徑。因此，綜合考慮路徑誘導的特點，駕駛員的個性化需求可分為以下3個層次。

第1層次為“可行性”需求，即路徑誘導結(jié)果必須滿足駕駛員的基本要求，如道路駕駛舒適度指標必須大于或等于某值。

第2層次為“偏好性”需求，即駕駛員對各指標的偏好程度，如一般情況下，與行程時間指標相比，駕駛新手更注重道路的安全性指標。

第3層次為“最優(yōu)性”需求，即路徑誘導在滿足駕駛員“可行性”需求的基礎(chǔ)上，根據(jù)其“偏好性”需求，盡可能使各評價指標達到綜合最佳值。

因此，基于物理規(guī)劃思想的個性化動態(tài)路徑誘導的基本思路是：首先，面向駕駛員對道路的“可行性”需求，根據(jù)車輛當前位置和目的地位置，動態(tài)確定交通路網(wǎng)搜索的幾何空間；其次，面向駕駛員對道路的“偏好性”需求，引入駕駛員選路過程中的偏好因子，對幾何空間內(nèi)的交通路網(wǎng)阻抗進行個性化評價，得到路段交通綜合阻抗；最后，面向駕駛員對道路的“最優(yōu)性”需求，基于 Dijkstra算法在動態(tài)確定的交通路網(wǎng)中搜索最優(yōu)路徑，實時輸出當前路網(wǎng)阻抗狀態(tài)下的最優(yōu)路徑。當路網(wǎng)中的交通阻抗發(fā)生變化或駕駛員行駛途中變更個性需求時，及時更新路網(wǎng)信息，按照前述基本思路，重新搜索從車輛當前位置到目的地的最優(yōu)路徑。

3.2 面向駕駛員“可行性”需求的交通路網(wǎng)空間動態(tài)確定

為了提高算法執(zhí)行效率，在大規(guī)模路網(wǎng)下需要對算法的搜索區(qū)域進行有效限制?？紤]到駕駛員對道路指標的“可行性”需求，通過如下方式確定搜索交通路網(wǎng)幾何空間。

Step 1“可行性指標”設(shè)定。在規(guī)劃之前，按照交互方式，確定駕駛員對道路的評價指標的可行性指標值xk5(見圖1，k=1, 2, …, 6)。值得注意的是：對于行程距離指標，駕駛員關(guān)心的是行駛總路程，所以，將x15設(shè)置為某個大于1的常數(shù)，當駕駛員的行駛總路程為車輛當前位置與目標點位置距離的x15倍時，則認為是不可行的；其他指標x25～x65則按照單條道路進行可行性指標進行設(shè)定。

Step 2交通路網(wǎng)幾何空間限定。假設(shè)車輛當前位置到目標點的直線距離為lod，令a=x15lod/2，以車輛當前位置與目標點位置為橢圓焦點，以a為橢圓長軸作橢圓，則橢圓限定的區(qū)域為交通路網(wǎng)搜索的可行幾何空間。

Step 3可行幾何空間的個性化裁剪。根據(jù)x25～x65，對橢圓限定區(qū)域的搜索空間進行裁剪，以滿足駕駛員對行駛途中的每公里行駛時間、舒適度、安全度、綜合費用和沿途景觀的“可行性”需求。

由此，動態(tài)確定了能夠滿足駕駛員“可行性”需求的交通路網(wǎng)空間。

3.3 面向駕駛員“偏好性”需求的路網(wǎng)交通阻抗綜合評價

從交通路網(wǎng)評價指標體系可以看出：各路段的行程時間、舒適度、安全度、行程費用和沿途景觀等行駛代價均與路段行程距離直接相關(guān)，從路阻代價的角度考慮，當路段行程距離越長時，因行程時間、舒適度、安全度、行程費用、沿途景觀產(chǎn)生的路阻代價將越大。據(jù)此，設(shè)計路阻函數(shù)如下：

其中：為路段行程距離的測量值；, · ··,分別為不同物理意義的各種評價指標x2,···,x6轉(zhuǎn)換為[0,1]區(qū)間的無量綱滿意度評價指標，本文統(tǒng)一將其轉(zhuǎn)換為Class1-S型(設(shè)計指標越小越好)，即

xk-max和xk-min分別為對應指標xk的最大值和最小值；λk為駕駛員在選路過程中對于不同指標的偏好因子。

偏好因子λi的引入體現(xiàn)了駕駛員的對路徑誘導的偏好性需求，簡化了駕駛員判斷指標相對重要性的復雜程度，解決了優(yōu)化排序過程中的一致性問題。評價指標框架如圖2所示。

圖2 層次化交通阻抗綜合評價體系Fig.2 Comprehensive evaluation system of hierarchical traffic impedance

為了體現(xiàn)駕駛員的個性化偏好，按照偏好程度逐漸下降的順序，將其分為6個等級：“極重要”、“很重要”、“重要”、“稍重要”、“不重要”、“不關(guān)心”， 并按照主觀賦權(quán)法設(shè)置相應的值，分別為：9，7，5，3，1和0，通過歸一法確定相應的偏好系數(shù)iλ。

3.4 面向駕駛員“最優(yōu)性”需求的動態(tài)最優(yōu)路徑搜索

基于Dijkstra算法[9]動態(tài)求解最優(yōu)路徑。由于在路網(wǎng)動態(tài)確定和交通阻抗綜合評價的過程中已經(jīng)充分考慮了駕駛員的“可行性需求”和“偏好性”需求，因此，誘導路徑是符合駕駛員的個性特點的，而考慮到路網(wǎng)交通阻抗的特點，在此進行最優(yōu)路徑搜索時采

用如下目標函數(shù)：

其中：fij表示路Ai,j的阻抗。當fij=∞時，節(jié)點vi和vj不連通。

首先，根據(jù)路網(wǎng)交通拓撲圖構(gòu)建聯(lián)接矩陣F：

然后，利用 Dijkstra算法，從起始車輛當前位置出發(fā)，逐步搜索到目標點，并記錄相應的代價，最終得到代價最優(yōu)的可行路徑。

在車輛行駛過程中，當路網(wǎng)中的交通阻抗變化超過一定閾值或駕駛員個性需求變更時，及時更新路網(wǎng)信息，按照前述基本思路，重新搜索從車輛當前位置到目的地的最優(yōu)路徑。

4 仿真算例

為了驗證本文方法的有效性，以長沙城區(qū)路徑誘導為背景進行仿真驗證，交通網(wǎng)絡如圖3所示。

圖3 長沙城區(qū)交通網(wǎng)絡Fig.3 Traffic network of Changsha

作為路徑誘導的基礎(chǔ)，路段交通阻抗屬性表的建立非常重要，基于路段評價指標體系，本文構(gòu)建對路段描述的數(shù)據(jù)結(jié)構(gòu)為

道路={長度，時間，合適度，安全性，費用，風景}

其中：時間、舒適度、安全性、費用、風景均存儲各路段具有相同數(shù)量級的無量綱滿意度評價指標值，以圖3中所示路段A1～A4為例，其路段阻抗如表2所示。表2中：A1為繞城高速路段，時間代價很小而費用代價最高(高速收費)；A2為環(huán)線路段，路況較好，時間代價較小，但存在車輛多、超速現(xiàn)象嚴重等問題，導致安全代價較大；A3為沿江大道，車道寬敞，行車流暢，舒適度代價最低，沿江風光帶風景宜人，與橘子洲遙遙相望，沿途景觀代價近似為 0；A4為繁華商業(yè)街區(qū)，車多擁擠，行駛緩慢，施工頗多，各種指標代價都很大。

表2 路段交通阻抗示例Table 2 Sample of road traffic impedance

假設(shè)一駕駛員從S點出發(fā)，到達目標T點，按照傳統(tǒng)的路徑誘導算法，搜索得到最優(yōu)路徑如圖4所示(其中：line1為最少時間路徑，line2為最短距離路徑。)

顯然，上述路徑僅僅針對是單一指標的優(yōu)化結(jié)果，當駕駛員需要對行程中的安全性、舒適性等其他指標有要求時，該結(jié)果顯然難以滿足其個性化需求。下面通過2個算例來驗證本文方法的有效性。

圖4 傳統(tǒng)誘導方法搜索結(jié)果Fig.4 Search results of traditional induction method

4.1 算例1

為了體現(xiàn)駕駛員的個性化需求，通過人機交互的方式，確定駕駛員的“可行性”需求，確定相應的搜索空間；假設(shè)該駕駛員對行程中的風景和安全性能非常關(guān)心，偏好設(shè)置為：行程時間“不重要”，舒適度“重要”，安全度“極重要”，行程費用“稍重要”，沿途景觀“極重要”。根據(jù)主觀賦值法進行賦值，并進行歸一化，可得行程時間、舒適度、安全性、費用、風景相應 的 偏 好 系 數(shù)λ2～λ6：λ2≈ 0.037，λ3≈ 0.185，λ4≈ 0.333，λ5≈ 0.111，λ6≈ 0.333。從而得到相應的搜索路徑如圖5所示。

圖5 情況1的個性化路徑誘導結(jié)果Fig.5 Results of personalized route guidance for Case 1

從圖5可以看出：所選路徑避開了城市中心，道路寬敞、車流量較少，行車通暢，保證了駕駛員的安全性需求；同時，該路徑大部分經(jīng)歷沿江風光帶，能夠飽覽橘子洲和岳麓山畔的自然風光，符合駕駛員的沿途景觀需求。

4.2 算例2

假設(shè)另一駕駛員從同一起點出發(fā)，到達同一目的點，其個性化偏好為：行程時間“很重要”，舒適度“稍重要”，安全度“稍重要”，行程費用“極重要”，沿途景觀“不關(guān)心”。依據(jù)本文誘導方法得到結(jié)果如圖 6所示。

從圖6可以看出：所選路徑以環(huán)線行駛為主，路徑較短、車道寬敞、紅綠燈較少、車行通暢，能夠保證行程時間“很重要”的個性化需求；同時，該路徑避開了沿環(huán)城高速行駛帶來的行程費用代價，符合駕駛員的期望需求。

圖6 情況2的個性化路徑誘導結(jié)果Fig.6 Results of personalized route guidance for Case 2

5 結(jié)論

(1) 基于物理規(guī)劃的思想，提出了一種個性化動態(tài)路徑誘導方法。該方法充分考慮駕駛員對路徑誘導的個性需求，體現(xiàn)駕駛員選擇路徑的主動性。

(2) 通過駕駛員個性化需求在路徑誘導過程中的實時表達，在一定程度上避免了分布式動態(tài)導航系統(tǒng)中的擁擠漂移現(xiàn)象，提高了整個交通系統(tǒng)運行效率。

(3) 以長沙城區(qū)路徑誘導為背景進行仿真，并與傳統(tǒng)的最少時間/最短路徑誘導算法結(jié)果進行對比，驗證了本文方法的有效性和可行性，獲得的最優(yōu)路徑既考慮了各種因素對出行的影響, 又充分體現(xiàn)了不同駕駛員的出行意愿。

[1] 楊群, 關(guān)偉, 張國伍. 基于合理多路徑的路徑選擇方法的研究[J]. 管理工程學報, 2002, 16(4): 42-45.

YANG Qun, GUAN Wei, ZHANG Guowu. Study on multi-path based route choice approach[J]. Journal of Management Sciences in China, 2002, 16(4): 42-45.

[2] Lee C K. A multiple path routing strategy for vehicle route guidance systems[J]. Transportation Research, 1994, 2(3):185-195.

[3] YANG Qun, ZHAO Yanan. A fuzzy logic-based frame work for route choice in vehicle navigation systems[J]. Journal of Systems Science and Systems Engineering, 2000, 9(4): 467-474.

[4] 楊兆升, 初連禹. 動態(tài)路徑誘導系統(tǒng)的研究進展[J]. 公路交通科技, 2000, 17(1): 34-38.

YANG Zhaosheng, CHU Lianyu. Study on the development of the dynamic route guidance systems (DRGS)[J]. Journal of Highway and Transportation Research and Development, 2000,17(1): 34-38.

[5] 于德新, 楊兆升, 高鵬. 動態(tài)限制搜索區(qū)域的帶約束K則最優(yōu)路徑算法[J]. 吉林大學學報: 工學版, 2009, 39(增2): 172-176.

YU Dexin, YANG Zhaosheng, GAO Peng. ConstrainedK-shortest paths algorithm within dynamic restricted searching area[J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(S2): 172-176.

[6] Yen J Y. Finding theKshortest loopless paths in a network[J].Management Science, 1971, 17(11): 716-721.

[7] Lawler E. Combinatorial optimization: Networks and matroids[M]. New York: Courier Dover Publications, 1976:92-104.

[8] 王媛, 楊兆升, 高鵬. 預防擁擠漂移的帶約束K則最優(yōu)路徑算法[J]. 北京工業(yè)大學學報, 2009, 35(3): 345-349.

WANG Yuan, YANG Zhaosheng, GAO Peng. ConstrainedK-shortest paths algorithm to prevent the congestion shifting problem[J]. Journal of Beijing University of Technology, 2009,35(3): 345-349.

[9] 孫燕, 陳森發(fā), 黃鹍. 基于灰色評價理論的自適應最優(yōu)路徑選擇[J]. 中國公路學報, 2003, 16(4): 87-90.

SUN Yan, CHEN Senfa, HUANG Kun. Adaptive optimal route selection based on gray evaluation theory[J]. China Journal of Highway and Transport, 2003, 16(4): 87-90.

[10] 孫燕, 陳森發(fā), 亓霞, 等. 基于灰色系統(tǒng)理論的最優(yōu)路徑選擇方法[J]. 土木工程學報, 2003, 36(1): 94-98.

SUN Yan, CHEN Senfa, QI Xia, et al. Optimal route selection method based on gray system theory[J]. China Civil Engineering Journal, 2003, 36(1): 94-98.

[11] Pang K H, Cran T. Adaptive route selection for dynamic route guidance system based on fuzzy neural approaches[J]. IEEE Transactions on Vehicular Technology, 1999, 48(6): 2028-2041.

[12] 楊兆升, 姜桂艷, 溫慧敏. 流體神經(jīng)網(wǎng)絡在交通網(wǎng)用戶最優(yōu)路徑選擇中的應用研究[J]. 中國公路學報, 1999, 12(增刊):76-87.

YANG Zhaosheng, JIANG Guiyan, WEN Huimin. Application of fluid neuron network on route choice based on user optimum in traffic network[J]. China Journal of Highway and Transport,1999, 12(Suppl): 76-87.

[13] 馬永鋒, 陸鍵, 項喬君, 等. 基于出行決策的公路網(wǎng)多目標最優(yōu)路徑算法[J]. 交通運輸工程學報, 2007, 7(3): 100-105.

MA Yongfeng, LU Jian, XIANG Qiaojun. Optimal route arithmetic with multigoals in highway network based on travel decision-making[J]. Journal of Traffic and Transportation Engineering, 2007, 7(3): 100-105.

[14] McAllister C D, Smpson T W, Kemper L, et al. Robust multiobjective optimization through collaborative optimization and linear physical programming[C]//10th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference.Albany, New York, 2004: 1-16.

[15] Achill M, CHEN Xuan. Visualizing the optimization process in real-time using physical programming[J]. Engineering Optimization, 2000, 32(6): 721-747.