龍瓊，胡列格，張蕾，喻杰

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

路徑誘導系統(tǒng)(Route guidance system)是智能交通系統(tǒng)的核心組成部分之一[1?2]。路徑誘導系統(tǒng)通過誘導信息來改變出行者的出行行為，降低出行者對未知交通狀態(tài)的焦慮，為駕駛員找到從當前位置到目的地的最優(yōu)行駛路徑。但駕駛員對于最優(yōu)路徑的理解和要求因人而異，也會隨時間和旅行目的不同而變化，因此，最優(yōu)路徑的標準不是唯一和固定不變的。在當前的大多數(shù)路徑誘導系統(tǒng)中，其優(yōu)化目標一般表示為出行時間最短或出行距離最短[3?4]，而沒有深入考慮駕駛員的性格特點、交通狀況、出行目的等因素，所以，其“最優(yōu)”的含義是狹隘的，所獲得的最優(yōu)解也不一定能夠滿足駕駛員的期望[5?6]。因此，在路徑誘導過程中，引入駕駛員的個人偏好，體現(xiàn)路徑誘導系統(tǒng)的個性化特點，協(xié)調好各種選擇標準, 提出一種有效的最優(yōu)路徑誘導方法有重要意義。很多研究者嘗試利用模糊邏輯、人工智能、近似推理等理論來解決該問題，如Pang等[7]提出了一種基于模糊神經(jīng)網(wǎng)絡的路徑選擇方法。該方法利用模糊神經(jīng)網(wǎng)絡表達影響路徑選擇的各種因素的相關關系并最終根據(jù)駕駛員的偏好給出所有可行路徑的優(yōu)劣排序。但該方法需經(jīng)過多次運行訓練后才能比較有效，改變偏好信息的當次無法由系統(tǒng)提供滿足特殊要求的最優(yōu)路徑。孫燕等[5]基于層次分析法和灰色評價理論建立了一種根據(jù)駕駛員的偏好自適應選擇最優(yōu)路徑的方法，能夠在可行路徑集中搜索滿足駕駛員個人偏好的最優(yōu)路徑，但并沒有將這種路徑選擇方法引入路徑誘導過程，僅對可行路徑進行個性化選擇，因而存在一定的局限性。為此，本文作者針對智能交通系統(tǒng)中路徑誘導問題的特點，將駕駛員個人偏好量化為偏好函數(shù)，引入路徑誘導過程中，提出一種基于物理規(guī)劃的路徑誘導方法。該方法充分考慮了駕駛員的個性化需求，能夠滿足不同駕駛員的個性偏好，自適應地為駕駛員提供期望的最優(yōu)路徑。

1 物理規(guī)劃方法概述

1.1 基本思路

物理規(guī)劃是Messac于1995年提出的一種處理多目標優(yōu)化設計問題的有效方法。該方法將整個設計過程置于一個更加靈活、自然的框架中，以減輕計算負擔，便于實際應用。該方法能夠從本質上把握使用者的偏好，是處理多目標優(yōu)化問題的新框架。其基本思路是：引入偏好函數(shù)，將不同物理意義的各種設計目標轉換為具有相同數(shù)量級的無量綱的滿意度目標。通過對偏好函數(shù)的優(yōu)化，尋求對綜合目標滿意度最優(yōu)的設計點作為問題的最優(yōu)解。因此，建立偏好函數(shù)是物理規(guī)劃問題的關鍵，它反映設計者對各設計目標的偏好程度[7?10]。

1.2 偏好函數(shù)的數(shù)學描述

偏好函數(shù)是設計指標的函數(shù)，記第i個設計指標xi的偏好函數(shù)為ui(xi)。物理規(guī)劃中對設計指標的偏好分為以下4種類型：(1) Class1，設計指標越小越好；(2) Class2，設計指標越大越好；(3) Class 3，設計指標趨于某值最好；(4) Class4，設計指標在某取值范圍最好。偏好函數(shù)又分為軟、硬(S和H) 2種類型。軟型偏好函數(shù)是指偏好函數(shù)值在可行域內隨設計指標變化，體現(xiàn)對設計指標不同取值的不同偏好程度。對于硬型偏好函數(shù)，當設計指標在可行域內時函數(shù)值均取最小，表示只要設計指標可行即可。因此，偏好函數(shù)具有圖1所示的8種基本類型。在工程優(yōu)化問題中，一般采用軟偏好函數(shù)描述設計目標，硬偏好函數(shù)描述約束條件。

為更加具體、靈活地體現(xiàn)設計者的偏好，物理規(guī)劃將軟偏好函數(shù)的設計目標分為幾個連續(xù)的不同滿意程度的區(qū)間。以Class1-S型為例，對某一設計目標進行區(qū)間劃分：

(1) 很期望域(xi≤xi1)，設計者可以接受的范圍，且對該范圍內的目標值很期望；

(2) 期望域(xi1≤xi≤xi2)，設計者期望的可接受范圍；(3) 可忍受域(xi2≤xi≤xi3)，設計者可接受的范圍；(4) 不期望域(xi3≤xi≤xi4)，設計者可接受但不期望的范圍；

(5) 很不期望域(xi4≤xi≤xi5)，目標在該區(qū)間可接受但很不期望；

(6) 不可接受域(xi5≤xi)，目標在該范圍內不可接受。

其中：xi1～xi5是設計者根據(jù)其偏好給定的第i個設計目標的區(qū)間端點值，如圖2所示。

1.3 物理規(guī)劃問題的數(shù)學模型

文獻[11]取各設計目標的偏好函數(shù)平均值的常用對數(shù)作為綜合偏好函數(shù)，即

其中：n為偏好函數(shù)的個數(shù)?？梢姡锢硪?guī)劃問題可以表述為：綜合選擇合適的偏好函數(shù)變量xi(i=1，2，…，n)，使得綜合偏好函數(shù)值J最小，即J→min。在通常情況下，各偏好函數(shù)變量xi之間是相互耦合的，這將給規(guī)劃過程帶來了難度。

圖1 偏好函數(shù)的基本類型Fig.1 Fundamental type of Preference functions

圖2 偏好函數(shù)的區(qū)間劃分示意圖Fig.2 Interval differentiate schemes of preference functions

2 路徑誘導模型構建

式(1)建立了1個物理規(guī)劃問題的通用數(shù)學模型。從式(1)可以看出：該模型對各種與路徑選擇有關的因素(偏好函數(shù))同等看待，這將影響路徑誘導的靈活性，也難以反映駕駛員的個性化特點。事實上，不同駕駛員對于每個偏好函數(shù)的看重程度并不一定相同，在不同的情況下(如不同出現(xiàn)目的、不同天氣、不同時間)，即使是同一駕駛員，對每個偏好函數(shù)的看重程度也會存在差異。因此，在路徑誘導問題中，為了體現(xiàn)駕駛員的個性化偏好，有必要在綜合偏好函數(shù)中引入偏好系數(shù)λi。此外，考慮到常用對數(shù)是單調遞增函數(shù)，將其引入綜合偏好并無實質意義，所以，本文設計路徑誘導的優(yōu)化模型為其中：ui(j)表示在所經(jīng)歷道路序列中的第j條道路關于評價指標xi的偏好值；1/m是為了與路徑代價保持一致性而引入的加權因子。在一般情況下，設計評價指標的偏好函數(shù)僅為Class1-S型和Class2-S型，故

或

從式(2)可以看出：考慮駕駛員個人偏好的最優(yōu)路徑模型與其各項分類指標xi、偏好函數(shù)fi以及偏好系數(shù)λi緊密相關。因此，構建能夠反映駕駛員性格偏好的路徑誘導模型的關鍵在于：路徑評價指標體系的構建、誘導偏好函數(shù)的數(shù)學表達以及偏好系數(shù)的設計這3個方面。

2.1 路徑評價指標體系的構建

評價1條路徑的優(yōu)劣，僅僅考慮其行駛距離或者行駛時間是不夠的，還應該考慮可行路徑的特點、駕駛員的性格特點、特定出行的性質(如目的、預算)以及駕駛環(huán)境(如天氣、白天晚上)等因素，因此，路徑評價具有一定的主觀性，因人而異。本文綜合考慮駕駛員的個性化需求，參照文獻[4]，構建路徑評價指標體系如下的評價指標體系：

其中：x1為行駛距離，行駛距離越短，偏好函數(shù)值越小，期望度越高；x2為行駛速度，交通流誘導系統(tǒng)控制中心預先根據(jù)當前交通狀況估計每段道路上的平均行駛速度，行駛速度越高，偏好函數(shù)值越小，期望度越高；x3為擁擠程度，主要考慮道路上的車輛密度、排隊長度、紅燈等待時間等，擁擠程度越低，偏好函數(shù)值越小，期望度越高；x4為通行費用，針對高速公路、國道等收費道路。通行費用越少，偏好函數(shù)值越小，期望度越高；x5為行駛難度，主要考慮道路寬度、車道數(shù)、行人及非機動車數(shù)量等。行駛難度越小，偏好函數(shù)值越小，期望度越高；x6為沿途景觀，進行長途旅行時，沿途景觀有時也是1個需要考慮的因素。沿途景觀越好，偏好函數(shù)值越小，期望度越高。

2.2 偏好函數(shù)的數(shù)學表達

偏好函數(shù)取值沒有嚴格限定，只需能反映出在不同偏好區(qū)間中設計者對目標值的滿意度即可[5]。本文設計偏好函數(shù)曲線為自然對數(shù)曲線(以Class1-S為例)，表達式如下：其中：e為自然對數(shù)的底數(shù)。

2.3 偏好系數(shù)設計

對于同一路徑評價指標，每個駕駛員對其注重程度不一定一致。例如，當急于趕時間時，駕駛員通常注重的是行駛距離和行駛速度；當駕駛技術比較生疏時，駕駛員通常需要考慮道路的行駛難度；外出旅行時，駕駛員通常會選擇具有較好沿途景觀道路。因此，為了體現(xiàn)駕駛員的個性化需求，有必要設計對不同路徑評價指標的偏好系數(shù)。

按照偏好程度逐漸下降的順序，本文將偏好系數(shù)分為6個等級：“極重要”、“很重要”、“重要”、“稍重要”、“不重要”、“不關心”，如表1所示。

將表格中“不關心”的偏好指標對應的偏好系數(shù)置0，其他偏好系數(shù)按照主觀賦權法設置相應的值，即

表1 路徑選擇因素的偏好程度界面Table 1 Interface of preference of path selection factors

3 路徑誘導方法

3.1 基本思路

基于A*算法[11]進行路徑搜索，其基本思路如下：在構建交通路網(wǎng)數(shù)據(jù)庫的基礎上，基于前面構建的路徑誘導模型，設計合適的代價函數(shù)，從駕駛起點出發(fā)，基于A*算法在交通路網(wǎng)中依次擴展相應的路徑節(jié)點，直到擴展至目標節(jié)點結束，從而從目標節(jié)點回溯至起點，最終得到一條能夠反映駕駛員個人偏好的最優(yōu)路徑。

3.2 路網(wǎng)數(shù)據(jù)庫構建

當考慮用戶偏好時，路網(wǎng)數(shù)據(jù)庫的構建不僅要包含交通路網(wǎng)中每條道路的長度，而且要考慮每條可行道路上的行駛速度、擁擠程度、通行費用、行車難度、沿途景觀等因素，所以，構建對每條道路描述的數(shù)據(jù)結構如下：

式中：long為道路長度，velo,crowd,fee,difficulty和landscape依次為對該條道路上的行駛速度、擁擠程度、通行費用、行車難度、沿途景觀的評價。需說明的是：對于駕駛員而言，其關心的是行駛總路程，所以，對于單條道路的長度評價是沒有意義的。因此，在數(shù)據(jù)庫構建階段，只需保留長度，而無需對其進行數(shù)值上的評價。為了避免主觀標準的不同而導致路徑評價的隨意性，在此采用統(tǒng)計法對這些參數(shù)進行評判，從而得到一個較客觀的評價數(shù)值。

以對某條道路上的行駛速度評價為例，首先，根據(jù)經(jīng)驗確定速度評價的區(qū)間劃分參數(shù)，從小到大依次為v1，v2，v3，v4和v5；然后，交通流誘導系統(tǒng)控制中心實時測算該條道路上的平均時速；最后，參照式(4)，確定該條道路上行駛速度的數(shù)值評價(偏好函數(shù)值)：

其他參數(shù)的數(shù)值評價方法與行駛速度評價類似。將數(shù)值評價結果由交通流誘導系統(tǒng)控制中心統(tǒng)一管理，從而構建了交通路網(wǎng)數(shù)據(jù)庫，為后繼的路徑誘導過程提供數(shù)據(jù)支持。

3.3 代價函數(shù)

從路徑誘導模型(式(2))可以看出：考慮駕駛員個性偏好的路徑誘導是一個多目標優(yōu)化問題。為了提高搜索效率，保證搜索的最優(yōu)路徑能夠滿足駕駛員的個性偏好，同時考慮到駕駛員關心的是行駛總路程，對單條道路長度進行評價是沒有意義的，而其他評價指標均是針對單條道路進行評價的，為此，本文將代價函數(shù)分為2部分，即針對行駛總路程評價的代價函數(shù)和針對其他評價指標的綜合代價函數(shù)。分別基于 A*算法的思想進行路徑搜索[12]，代價函數(shù)如下：

其中：f1(k)為針對行駛總路程x1的評價代價函數(shù)，

式中：g1(k)為駕駛員從起始位置到當前路網(wǎng)節(jié)點的實際路徑代價；h1(k)為從當前路網(wǎng)節(jié)點到達終點位置的啟發(fā)路徑代價，可取h1(k)為當前路網(wǎng)節(jié)點至終點的直線距離；u1(·)為路徑長度評價函數(shù)；f2(k)為針對其他評價指標x2～5的綜合代價函數(shù)，gi(k)為駕駛員從起始位置到當前路網(wǎng)節(jié)點的針對評價參數(shù)xi的實際評價代價；hi(k)為從當前路網(wǎng)節(jié)點到達終點位置的啟發(fā)評價代價。由于在通常情況下，hi(k)難以預估，為了研究方便，本文僅以路徑代價進行啟發(fā)搜索，即?。?/p>

3.4 算法描述

基于物理規(guī)劃的路徑誘導算法具體步驟如下。

Step 1：初始化。確定行駛起點和目的點，載入相應的交通路網(wǎng)，根據(jù)當前的交通狀況，智能交通系統(tǒng)自動對每條道路進行數(shù)值評價，確定其偏好函數(shù)值(注：對于通行費用、行車難度、沿途景觀等，可以在交通路網(wǎng)數(shù)據(jù)庫構建的初期進行評價；而對于擁堵行駛速度、擁擠程度等，則需要實時進行更新)。

Step 2：個性化選擇。駕駛員根據(jù)在終端系統(tǒng)中輸入個人偏好，如表1所示。

Step 3：最優(yōu)路徑搜索。根據(jù)起點和目的點坐標，采用 A*算法在交通路網(wǎng)中搜索滿意度最高的最優(yōu)路徑。

1) 生成1個只包含起始節(jié)點的搜索圖G，把起始節(jié)點插入OPEN表中，將CLOSED表置空。

2) 若OPEN表為空，則失敗退出。

3) 選擇OPEN表中的第1個節(jié)點，把它從OPEN表中移入CLOSED表中。

4) 若當前節(jié)點為目標節(jié)點，則將目標節(jié)點的父節(jié)點指針指向當前節(jié)點，路徑搜索過程結束。從目標點開始向上回溯直到起始位置，得到從起始到目標的最小代價路徑。

5) 基于交通路網(wǎng)圖，擴展當前路徑節(jié)點。生成其后繼節(jié)點集M，注意當前節(jié)點的祖先不在M中，在G中安置M的成員，使之成為當前節(jié)點的后繼。

6) 從M的每一個不在G中的成員建立一個指向當前節(jié)點的指針。把M的這些成員加到OPEN中，對M的每一個已在OPEN中或CLOSED中的成員m。若到目前位置找到的到達m的最好路徑通過當前節(jié)點，就把它的指針指向當前節(jié)點。對于已在CLOSED中的M的每一個成員，重新定性它在G中的每一個后繼，以使他們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。

7) 遞增f，重排OPEN表。

8) 返回步驟3。

Step 4：輸出最優(yōu)路徑。

4 仿真算例

圖3 交通路網(wǎng)示意圖Fig.3 Traffic network

為了驗證本文方法的有效性，在如圖3所示的給定的城市交通路網(wǎng)圖中進行路徑誘導仿真。圖3中：O為城市中心；E1—F1—G1—H1—E1包含的區(qū)域為“城內”，其他區(qū)域為“城外”；A1—B1—C1—D1—A1為繞城高速；A3—B3—C3—D3—A3，A3—C3和B3—D3為城區(qū)主道；A1—C1和B1—D1為正在維修中的街道；其他為一般的城市街道。交通路網(wǎng)中每一單元網(wǎng)格的邊長均為1(如A1—D4)，則其對角邊長為(如A1—E1)。

對于總路程的評價，取總路程與始末兩點直線距離的比值μ作為評價參數(shù)。區(qū)間劃分為： )2.1,1[ ，對應的平均值依次為：0.5，(e+1)/2，e(e+1)/2，e2(e+1)/2，e3(e+1)/2和∞。其他相關參數(shù)設置如表2所示。

假設駕駛員從A1出發(fā)，要抵達終點C1，求在不同需求情況下的最優(yōu)路徑。

(1) 情況1：駕駛員有緊急事情，希望以很短的時間抵達終點C1，但駕駛員處于實習期間，駕駛技術不太熟練，希望道路上車流量較小，路況較好。該駕駛員將行駛距離和行駛速度設置為“極重要”，擁擠程度和行車難度設為“重要”，其他指標設置為“不關心”。按照第3節(jié)的方法和步驟進行路徑規(guī)劃，得到最優(yōu)結果為(圖4所示)。

或者

圖4 優(yōu)化路徑示意圖1Fig.4 Optimization path of traffic network

從搜索結果可以看出：基于物理規(guī)劃的搜索結果行駛行駛距離不太大，行駛速度整體較高，因而能夠以很短的時間抵達終點；同時，所選擇的道路擁擠程度較低，行車難度較小，符合駕駛員的主觀期望。

(2) 情況2：駕駛員外出游玩，希望在不產(chǎn)生較大費用的情況下好好體驗沿途的風景，不大注重行駛距離和行駛速度；同時，該駕駛員技術熟練，對交通狀況和路況寬窄情況不大在乎。該駕駛員將行駛距離和行駛速度設置為“稍重要”，擁擠程度和行駛難度設置為“稍重要”，通行費用設置為“重要”，沿途景觀設置為“極重要”。

通過規(guī)劃，得到最優(yōu)結果為：

或者

該搜索結果體現(xiàn)了低通行費用和好沿途景觀的特點，較好反映了駕駛員的個性化偏好。

以上2個仿真算例表明：由于偏好函數(shù)的引入，基于物理規(guī)劃的路徑誘導方法符合駕駛員進行路徑選擇的決策行為特征，能夠滿足不同駕駛員的出行需求。

表2 交通路網(wǎng)相關參數(shù)設置Table 2 Traffic network related parameters settings

5 結論

(1) 基于物理規(guī)劃理論，引入偏好函數(shù)，提出了一種能夠反映駕駛員偏好的路徑誘導方法。仿真算例表明，路徑誘導結果符合駕駛員的個性化選擇。

(2) 該方法能夠有效協(xié)調好各種路徑選擇標準，體現(xiàn)了路徑誘導系統(tǒng)的個性化特點，能夠滿足不同駕駛員的個性偏好，自適應地為駕駛員提供期望的最優(yōu)路徑。

(3) 該方法克服了以往規(guī)劃方法目標單一的缺點，為智能交通系統(tǒng)的研究提供了一定的借鑒意義；需說明的是：該方法將路網(wǎng)交通信息進行量化，在此基礎上進行最優(yōu)路徑的搜索，該方法實際上是一種靜態(tài)的路徑誘導方法。而事實上，路網(wǎng)交通信息是實時變化的，因此，有必要基于動態(tài)的路網(wǎng)環(huán)境對個性化路徑誘導策略進行研究。

[1] 楊兆升. 城市交通流誘導系統(tǒng)理論與模型[M]. 北京: 人民交通出版社, 2000: 14?29.YANG Zhao-shen. The urban traffic flow guidance system theory and model[M]. Beijing: China Communications Press,2000: 14?29.

[2] 李威武, 王慧, 錢積新. 智能交通系統(tǒng)中路徑誘導算法研究進展[J]. 浙江大學學報: 工學版, 2005, 39(6): 819?825.LI Wei-wu, WANG Hui, QIAN Ji-xin. New trends in route guidance algorithm research of intelligent transportation system[J]. Journal of Zhejiang University: Engineering Science,2005, 39(6): 819?825.

[3] WANG Hui. Transportation shortest path search area model[R].ProQuest Information and Learning Company, 2003: 119?121.

[4] Younes H, Patrice M S N. A strategic model for dynamic traffic assignment[J]. Networks and Spatial Economics, 2004, 4(2):291?315.

[5] 孫燕, 陳森發(fā), 黃鹍. 基于灰色評價理論的自適應最優(yōu)路徑選擇[J]. 中國公路學報, 2003, 16(4): 87?90.SUN Yan, CHEN Sen-fa, HUANG Kun. Adaptive optimal route selection based on gray evaluation theory[J]. China Journal of Highway and Transport, 2003, 16(4): 87?90.

[6] Jeffer L A, Goutam S P, Vikram M, et al. A multi-agent approach to cooperative traffic management and route guidance[J]. TransPortion Reasearch Part B, 2005, 39(4):297?318.

[7] 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.[8] McAllister C D, Simpson 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.

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

[10] 雍恩米, 陳磊, 唐國金. 基于物理規(guī)劃的高超聲速飛行器滑翔式再入軌跡優(yōu)化[J]. 航空學報，2008, 29(5): 1091?1097.YONG En-mi, CHEN Lei, TANG Guo-jin. Trajectory optimization of hypersonic gliding reentry vehicle based on the physical programming[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(5): 1091?1097.

[11] 龍科軍, 王賽政, 肖向良. 面向駕駛員特性的路徑規(guī)劃算法[J]. 計算機工程, 2011, 37(5): 264?265.LONG Ke-jun, WANG Sai-zheng, XIAO Xiang-liang. Driver character-oriented algorithm for route planning[J]. Computer Engineering, 2011, 37(5): 264?265.