基于物理規劃的路徑誘導方法

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

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

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

1 物理規劃方法概述

1.1 基本思路

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

1.2 偏好函數的數學描述

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

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

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

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

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

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

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

1.3 物理規劃問題的數學模型

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

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

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

圖2 偏好函數的區間劃分示意圖Fig.2 Interval differentiate schemes of preference functions

2 路徑誘導模型構建

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

或

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

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

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

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

2.2 偏好函數的數學表達

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

2.3 偏好系數設計

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

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

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

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

3 路徑誘導方法

3.1 基本思路

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

3.2 路網數據庫構建

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

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

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

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

3.3 代價函數

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

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

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

3.4 算法描述

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

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

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

Step 3：最優路徑搜索。根據起點和目的點坐標，采用 A*算法在交通路網中搜索滿意度最高的最優路徑。

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

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

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

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

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

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

7) 遞增f，重排OPEN表。

8) 返回步驟3。

Step 4：輸出最優路徑。

4 仿真算例

圖3 交通路網示意圖Fig.3 Traffic network

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

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

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

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

或者

圖4 優化路徑示意圖1Fig.4 Optimization path of traffic network

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

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

通過規劃，得到最優結果為：

或者

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

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

表2 交通路網相關參數設置Table 2 Traffic network related parameters settings

5 結論

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

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

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

[1] 楊兆升. 城市交通流誘導系統理論與模型[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] 李威武, 王慧, 錢積新. 智能交通系統中路徑誘導算法研究進展[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] 孫燕, 陳森發, 黃鹍. 基于灰色評價理論的自適應最優路徑選擇[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] 雍恩米, 陳磊, 唐國金. 基于物理規劃的高超聲速飛行器滑翔式再入軌跡優化[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] 龍科軍, 王賽政, 肖向良. 面向駕駛員特性的路徑規劃算法[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.