實時環境下多目標的路徑選擇模型

陳海鵬，劉陪，申鉉京，王玉,3

(1.吉林大學 計算機科學與技術學院,吉林 長春 130012; 2.吉林大學 符號計算與知識工程教育部重點實驗室,吉林 長春 130012； 3.吉林大學 應用技術學院,吉林 長春 130012)

實時環境下多目標的路徑選擇模型

陳海鵬1,2，劉陪1,2，申鉉京1,2，王玉1,2,3

(1.吉林大學 計算機科學與技術學院,吉林 長春 130012; 2.吉林大學 符號計算與知識工程教育部重點實驗室,吉林 長春 130012； 3.吉林大學 應用技術學院,吉林 長春 130012)

針對出行者出行需求多樣化的問題，本文從時間、費用角度出發，構建了實時環境下基于多目標的路徑選擇模型。采用加權求和函數對多維數據聚集得到組合權重，而權重系數可依據出行者需求或喜好設定。為驗證模型的實用價值，在仿真環境下，多目標模型與基于幾何距離最短的路徑選擇模型在時間、費用、距離等評價指標進行了對比。實驗結果證明實時環境下基于多目標的路徑選擇模型更具有實用價值。

智能交通系統； 動態路徑誘導系統； 多目標； 路徑選擇模型； 加權求和函數； 組合優化； 廣義自適應A*算法

智能交通系統(intelligent transportation system， ITS)是集信息、通信、控制及網絡等技術于一體的綜合研究學科，可以提供全方位、實時、準確以及高效的服務信息，ITS是有潛力的研究方向，進一步說將成為未來相關研究領域的熱點[1]。動態路徑誘導系統(dynamic route guidance system，DRGS)是ITS一個重要的分支，利用計算機、通信等現代技術，為出行者提供實時交通信息以及最優路徑。在DRGS中，路徑選擇模型可以確立DRGS的目標[2]。

路徑誘導模型分為靜態模型和動態模型，靜態模型以假設出行者獲知路網信息為前提，并以隨機期望效用理論或積累前景理論為基礎。而動態模型包含一些信息獲取和學習的過程，以隨機虛擬理論或增強學習理論作為指導[3]。目前，在國內路徑誘導模型的研究主要還是集中在靜態模型且取得了階段性的成果。基于期望效用理論的模型是在確定性框架下，以幾何路徑或者出行時間為效用值，以期望獲得效用最大化評價各備選方案的優劣。孟夢等針對不同的出行時間，提出了組合出行工具的路徑選擇模型，以組合出行工具的模式下為出行者提供最優路徑[4]。劉艷秋等構建了交通堵塞下基于實時交通信息的路徑選擇模型[5]。相反，積累前景理論是不確定性情況下的決策行為，決策者以財富的變化量而不是最終量作為參考依據進行決策[6]，針對交通信息不確定的特性，諸多學者以積累前景理論為基礎提出了路徑選擇模型[7-9]。但是，目前提出的模型大多僅針對路段行程時間構建的單目標路徑選擇模型[6]，顯然，與實際存在很大的偏差。在實時環境下，交通暢通、擁擠情形下路阻的產生形式有所差異，因此，分別以交通暢通、擁擠下的路阻構建了基于時間最短的路徑選擇模型， 進而提高了模型的可靠性。

Erel Avineri等提出時間是影響路徑抉擇最重要的因素，但不能確切地表述所有出行者的意愿[10]。由此可見，在實時環境下，路徑優化是多目標組合優化問題[11]，例如，時間、費用、環境等因素。因此，僅從時間上考慮構建路徑選擇模型并不合理而建立基于多目標的路徑選擇模型是有必要的。因此，分別從時間、費用兩個角度出發，構建了實時環境下基于多目標的路徑選擇模型。

在處理多準則優化問題時，一般采取單目標類和多目標類的策略[12]。單目標類將多目標優化問題轉化為單目標優化問題，轉化過程使用目標聚合或目標標準策略對其結果進行組合。而多目標類是以目標向量間的關系來定義決策向量之間的優劣關系，一般可獲得均勻分布的Pareto最優前端。但在高維度下，多標準Pareto最優路徑算法運行效率極低甚至無法運行[13]。然而，在實時信息下，對反應速度的要求卻十分苛刻，由此可見多目標類在動態實時路網中并不實用。評價函數中加權求和函數屬于單目標類，加權求和函數是解決多目標函數優化問題比較常見的方式之一。它采用目標聚合策略即將多維空間中的數據對象聚集轉化為單目標空間的優化問題。處理過程相對比較簡單，但組合權重的意義及結果的優劣至關重要。聚合過程中，由于不同的計量方式，各個目標函數間具有不同的值域。相應地，當映射到加權求和目標函數時，決策變量間具有不同的閾值。在這種情形下，閾值大的決策變量對組合函數的支配大，反之支配小[14]。所以，本文在使用加權求和函數前，對各個目標函數值進行了預處理，即對其進行類似的量值處理，從而保證支配能力的均衡即可獲取最優路徑。

1 基于多目標的路徑選擇模型設計

1.1 問題描述及分析

路徑優化問題相當于圖理論模型中最優路徑的查找問題，但又存在差異。在動態路徑誘導系統中含有靜態屬性和動態屬性[15]，靜態屬性是路網信息相對固定的部分，例如: 地理位置信息、路段間距以及路段的基本通行能力等。而動態屬性可以反映實時信息狀況，例如，車流量、行車速度等。所以，路網數據對象具有多樣、復雜以及實時的特性。以圖論為基礎，同時結合動態路網信息的特性，路徑優化問題的定義形式：

(1)

式中：G=(V，Rij)是靜態屬性，表示路網結構；V是從起始點到結束點間的結點集合；Rij是當前Sstart到Send所有無環路集合，其定義形式為

(2)

式中：Wij是體現了動態路徑誘導系統中的動態屬性，Wij對應(i，j)間的權重值，并以此為優化準則；Sstart是出發節點且隨著車輛的不斷行駛動態更新，Send表示目標節點。

1.2 基于時間最短的路徑選擇模型

在實時交通信息下，影響路阻的因素多樣化。例如：天氣、ITS系統故障、交通事故等偶然事件，也包含一些不確定因素，例如車速、車流量等。所以，僅以單一的車輛行程時間為路阻并不合理，交通暢通或者擁擠的情形下產生路阻的方式有所差異。在交通暢通情形下以行駛時間及交叉口轉向延誤產生的時間為路阻；而在交通擁擠的狀態下，產生路阻最主要的是延誤時間而行程時間可忽略不計。所以，基于時間最短的路徑選擇模型的定義形式為

(1-K)(dij+Dij)}(t)

(3)

其約束條件為

(4)

(5)

(6)

式中：(i，j)均屬于V集合且互異。式(4)是無環路控制。式(5)為道路飽和度[16]并約束路阻的計算方式，Qij表示當前路段交通量，Cij為路段基本通行能力，當Qij/Cij比值在[0,1]范圍時，道路屬于暢通狀態，而(2Cij-Qij/Cij)比值在(1,2)范圍內時，道路交通處于擁擠狀態。針對交通擁擠以及暢通情形下路阻計算方式的不同：式(3)中，在約束系數K為1時，tij及Dij表示車輛的行程時間和交叉口等待時間；在約束系數K為0時，dij及Dij代表車輛間相互影響產生的延誤時間及交叉口延誤時間。式(6)在道路暢通的情況下，交叉口有可能出現小范圍的等待紅燈時間。當在一個有效綠燈時長tn通過交叉口時，系數?=0，即等待時間為0；反之，則 ?=1，計算等待時間。

1.3 基于費用最低的路徑選擇模型

通常情況下，燃油費是最主要的費用，而在一些歐洲國家采用繳納擁擠稅的方式緩解擁擠地區的交通壓力，擁擠稅的計費方式是一天中僅第一次進入擁擠區域時收取費用，但多次或未進入時不計費用，基于費用最低的路徑選擇模型的定義形式為

(7)

式中：(i，j)均屬于V結點集合且互異；F(i，j) 表示(i，j)兩結點間的費用總和，費用的計算方式為

(8)

式中：Fh(i，j)表示燃油費用；Fc(i，j)代表擁擠區域繳納擁擠費，約束擁擠費的計算方式為

(9)

式(9)表示：當且僅當第一次進入擁擠區域時繳納擁擠費，即γ=1，否則γ=0。

1.4 組合優化函數模型

針對出行者出行需求的多樣化，采用加權求和最小化方法處理基于多目標的路徑選擇模型更加合理且易實現。出行者可以預設出行需求，例如設置費用最低、時間最短或自設權重大小。所以，本文以加權求和函數值作為優化準則，組合優化函數模型的定義形式為

(10)

式中：wz、wc分別代表路阻、費用的權重系數且和為1，Z(i，j) 和F(i，j)分別為(i，j)路段間的路阻及費用。為均衡各決策變量在組合權重函數中的控制權限，對Z(i，j)及F(i，j)均采用迭代取最高有效位的策略進行類似的量值處理，從而使各個決策變量的閾值限定在指定范圍內。

2 基于多目標的路徑選擇模型求解

在實時交通信息下，動態路徑優化中“動”主要體現在各路段中評價值會隨著時間的變化而發生變更，而最優路徑也會隨之發生變化，因此，動態地為出行者提供優化方案。針對交通信息的不可控性、隨機性以及不確定性等因素，顯然一步尋優與實時狀況相背離，而逐步尋優更加合理。換言之，動態路徑優化是一種逐步尋優的搜索過程，而最終目的是降低費用、減少污染或節省時間等。

為驗證實時環境下基于多目標的路徑選擇模型，采用廣義自適應A*算法[17]實現并獲取最優路徑及評價參數值。

2.1 采用廣義自適應A*算法的合理性分析

廣義自適應A*算法被認為是A*算法的迭代過程，同樣在算法中，采用open表保存所有已生成而未考察的節點，closed表存儲已訪問過的節點。但存在兩方面的差異，一方面每完成一次A*搜索后，修改closed表中所有狀態的h值，從而使啟發值更明智。另一方面，當發現某條邊的權重減少時，在搜索空間中需修改某些狀態h值，即重構h值的一致性。這兩點體現廣義自適應A*算法在動態環境中的適用性。

在動態路徑優化中，一方面，隨著距離目標越來越近，結點不斷減少，起始點Sstart在不斷的發生變化。因此，起始點Sstart需動態的調整；另一方面，在實時環境下，路段的權值動態的變化。本文以組合權重值Wij為算法的啟發式h值，實時環境下，決策變量路阻、時間在不斷發生變化，Wij有可能減小。在這種情形下，需重構Wij的一致性。重構后，調用A*算法進而得到當前信息下的最優路徑，重復此過程直到Sstart=Send算法結束。

2.2 算法應用過程

2.2.1 實現過程

在本文中，廣義自適應A*算法具體實現過程如圖1所示。

圖1 廣義自適應A*算法實現過程Fig.1 Generalized adaptive A* algorithm implementation process

1)初始化Sstart、Send，加載Sstart和Send間地圖的靜態數據并獲取當前實時動態信息，進而初始化組合權重Wij，執行步驟2。

2)若Sstart!=Send，首先調用A*算法，若不存在路徑，返回NULL程序結束；反之，則返回目標結點Send，進而轉向步驟3。

3)修改closed表中所有的啟發式值Wij，并以Send為參數構造Sstart與Send間的路徑，執行步驟4。

4)以當前路徑的下一結點為Sstart，并更新實時動態數據，重新檢測以Sstart的Wij啟發式值是否減小，若減小，則重構Wij的一致性，重構完成后，跳出步驟4，執行步驟2；若不變或增加，則繼續執行步驟4；若Sstart=Send時，跳出步驟4，執行步驟2。

2.2.2 控制策略

1)擁擠區域控制策略：調用A*算法過程中，采用K約束設置open表優先級的策略，即當K=1時的優先級高于K=0時的優先級，從而可以優先擴展暢通區域的結點。設定open表優先級過程：首先將open表定義以Wij為優先的隊列；進而，判斷K值，若K=0，則該結點插入臨時優先隊列，否則插入open表；優先擴展暢通區域的結點，當open表為空且未找到目標節點時，進而擴展臨時優先隊列。在道路擁擠的情形下，有效避免進入擁擠區域，從而節省時間、減少費用也可以緩解擁擠區域的交通壓力。

2)組合優化函數中各決策變量的控制策略：采用迭代循環將各決策變量的閾值限定在(0,0.1)內。因此，有效保證各個決策變量在組合優化函數模型中的均衡支配。從而，使得組合權重與優化結果的映射保持一致性。

3 實驗仿真及結果分析

為驗證在實時環境下基于多目標的路徑選擇模型的合理性及有效性，采用C++編程仿真實驗環境。以隨機讀入文本的形式模擬實時環境，即車流量以文本流的形式更新。

3.1 參數設置

在交通信息中，車流量是實時變化的，車流量Qij與密度kij間存在函數關系：

(11)

式中：vf、kf分別為暢通速度及阻塞密度，參考城市道路函數模型，在實驗中設置vf=77.4，kf=124。

行駛時間以BPR函數計算，路阻系數α和β采用交通流分配程序中的取值，即α=0.15，β=4。由于速度的隨機性、不可控性，在不考慮人為主觀因素的前提下，同時考慮城市道路限速。本文將其理想化處理，即假設路段(i，j)以均速行駛。由車流量、密度、速度三者間的關系確定速度：

(12)

在交通擁擠情形下，車輛間相互影響產生延遲時間的計算方式[5]為

(13)

式中：θij代表單位小時內當前路段車輛的時間密集度，Lij表示當前路段長度，Lc為有效檢測器長度與平均車長的距離之和。

形式化交叉口等待時間為

(14)

式(14)表示道路暢通及擁擠的情形下，交叉口的等待時間Dij的計算方式。在實驗中，n設置為1，即在交通暢通下，出行者可接受在交叉口的延遲為一個有效紅綠燈的時間，λ為綠信比。

影響燃油費用Fh(i，j)與車輛運行相關的外部因素多樣化，例如平均速度、加速度、車輛行駛工況等[18]。為簡化及理想化處理，本文僅從平均速度上考慮燃油費。計算方法采用隗海林等構建的平峰期和高峰期車速-油耗的模型[19]，其計算形式為

(15)

(16)

式中：cost表示當車輛第一次(γ=1)進入擁擠區域時繳納擁擠稅，否則，無需繳納擁擠稅。

3.2 實驗仿真數據

利用某城市實際道路網絡結構進行路徑尋優仿真實驗，VISSIM仿真將真實地圖映射為如圖2所示的路網結構。

圖2 VISSIM仿真圖Fig.2 Map using VISSIM simulation

在圖2中有101個測試結點和291條測試路段，實驗數據以VISSIM仿真數據并結合實際進行了合理假設。車流量采用VISSIM仿真數據并以文本的形式實時讀入。速度、燃油費、時間等結合實際道路情況進行了合理的設定和計算。

3.3 評價指標

到目前為止，針對路徑選擇模型的評價沒有統一的標準。而目前普通汽車上安裝的商用導航系數大多是基于幾何最短路徑或可通達路徑的靜態路徑為優化路徑。為驗證模型的合理性及實用價值，與基于幾何距離最短的路徑選擇模型分別以時間、費用、距離等參數進行了對比實驗。實驗結果證明了在實時環境下，幾何最短路徑并非最優路徑，而基于多目標的路徑選擇模型更加合理且具有一定的實用價值。

3.4 實例及結果分析

本文在仿真實時環境下進行了多組實驗，分別從道路暢通及擁擠情形下，以基于幾何最短路徑與本文模型進行了對比實驗。為形象地顯示實驗結果，本文分別以最優路徑對比圖以及評價參數的對比結果加以詮釋。

3.4.1 道路暢通情形下的對比實驗

在交通暢通的情形下，以結點1～100為一組實例進行分析。為驗證本文組合優化函數模型的有效性，基于該實例下，以同等實驗環境，時間權重系數wz分別在0～1以0.1為間隔取值。在不同wz下，最優路徑所對應的時間、費用以及兩者比值(費用/時間)如圖3所示，體現了組合權重與優化結果間的映射關系。

圖3 道路暢通情形下組合權重與優化結果映射關系Fig.3 The mapping relationship between combination weights and the optimization results under the smoother of road traffic

由圖3可知，隨著時間權重系數增加，時間逐漸減少，而費用越來越大。由于wz的增加，時間決策變量在組合優化函數中的支配力越來越大，與此同時，費用決策變量的支配力變小。所以，優化結果趨向于時間越來越少而費用逐漸變大。在圖3中，費用與時間比值逐漸增大但在某些相鄰點間的比值相同，例如：時間權重系數分別為0、0.1、0.2時。這種情況下，由不同的權重系數得到相同的優化結果屬于結果重合，結果重合的意義在于當前最優路徑唯一化。進一步分析圖3可知，曲線為上升趨勢，優化結果符合加權求和函數的一般規律，即組合權重與優化結果間的映射具有一致性。因此，可以證明本文的組合優化函數模型的合理性及有效性。而且在不同權重系數下存在不同的優化結果，則最優路徑的結果集合具有多樣性的特點，從而可以滿足出行者多樣化的需求。

為進一步驗證本模型的優勢，在同等實驗環境下，本文模型分別以不同時間權重系數下的最優路徑與基于幾何最短的最優路徑進行了對比實驗，如圖4～6中圖例所示。其中，圖4為幾何最短路徑示意圖，圖5、6是時間權重系數分別為1和0.5的最優路徑。

圖4 道路暢通情形下的幾何最短路徑Fig.4 Geometric shortest path under the smoother of road traffic

圖5 道路暢通情形下wz=1的基于多目標的路徑選擇模型的最優路徑Fig.5 The optimal path of wz =1 based on multi-objective under smoother of road traffic

圖6 道路暢通情形下wz=0.5的基于多目標的路徑選擇模型的最優路徑Fig.6 The optimal path of wz=0.5 based on multi-objective under smoother of road traffic

由圖4～6可知，幾何最短路徑的距離明顯優于多目標模型。為進一步說明上述結果，本文分別從距離、時間、費用等參數進行了對比實驗，其結果如表1所示。

表1 道路暢通情形下的對比實驗

對比表1列出的基于兩種模型下最優路徑的距離，可以進一步驗證上述圖4～6結果。針對基于幾何距離最短的路徑選擇模型而言，優化是以距離最短為目標。所以，基于幾何距離最短的模型下，最優路徑的距離最短。

盡管基于幾何距離最短的路徑選擇模型在距離上占優多目標模型，但由表1中時間、費用等參數可以看出，多目標模型在時間、費用上均優于對比模型。其原因是由于影響路阻的因素多樣化，如行駛時間、交叉口等待時間等。在道路暢通但未達到擁擠如交通密度達到臨界的情形下，在交叉口等紅燈的幾率明顯增加，相應的延誤時間就會增加，而行駛速度相對較慢導致行駛時間增加，因而路阻增加。而且，燃油費用與距離、速度密切相關，其距離與速度間存在正相關的特性，因此費用也增加。所以，在實時環境下，當圖4所示的最優路徑上的車流量增加時，車輛在交叉口的等待時間及行駛時間均增加，而行駛速度減小導致費用的增加。由此可見，在實時環境下，以最短距離作為優化目標并不合理，而建立基于多目標的路徑選擇模型具有更高的實用價值。

為進一步驗證組合優化函數模型的有效性，在本實例中，分別以時間權重系數為1(如圖5)和0.5(如圖6)對比實驗。圖5的距離大于圖6的距離且與實例結果如表1相一致，但由表1中可以看出隨著時間權重系數的減少，費用權重系數的增加，權重系數為1的最優路徑的路阻占優于圖6所示的路徑，但費用劣于時間權重系數為0.5的最優路徑。由于各權重系數的變化產生不同的優化結果是組合權重的目的，因此，實驗結果符合加權求和函數的意義。從而，進一步證明了本文的組合權重函數模型的合理性、易實現性以及在實時環境下可滿足出行者需求的多樣化。

3.4.2 道路擁擠情形下的對比實驗

為進一步驗證基于多目標的路徑選擇模型的性能，在道路阻塞的情形下，對多目標模型進行了對比實驗。在反復多組實驗的基礎上，選取結點1～39為一組實例進行實驗分析。為驗證組合優化函數的有效性，在本實例下，同樣地，時間權重系數wz以0.1為間隔在0～1取值。在相同的實驗環境下，組合權重與優化結果的映射關系(以費用與時間的比值為優化結果)如圖7所示。

由圖7中可知，權重系數在0～0.9的費用、時間以及兩者比值持平，僅在0.9～1間費用及兩者比值處于上升趨勢而時間略有減少。由于K系數的約束控制，優先擴展暢通區域而擁擠區域結點被保存在臨時隊列中。因此，與道路暢通情形下相比，其可擴展的區域明顯減小，從而導致結果重合的概率增大。解集的多樣性受到影響，但有效避免進入擁擠區域，從而提高出行的可靠性，緩解交通壓力以及減少環境污染。但在圖7中，費用與時間的比值整體是上升趨勢，符合加權求和函數的一般規律。因此，在擁擠情形下，組合優化函數模型符合加權求和函數的意義。

圖7 道路擁擠情形下組合權重與優化結果映射關系Fig.7 The mapping relationship between combination weights and the optimization results under congestion of road traffic

為進一步詮釋本模型的合理性，在相同實驗環境下，基于多目標的路徑選擇模型分別以時間權重系數為0.8和0的最優路徑如圖8、9所示與幾何最短路徑如圖10進行了對比實驗。圖示中黑色加重為最優路徑，矩形標注為擁擠區域。

圖8 擁擠情形下wz=0.8基于多目標的路徑選擇模型的最優路徑Fig.8 The optimal path of wz=0.8 based on multi-objective under congestion of road traffic

在道路擁擠的情形下，采用約束系數K的控制策略，基于多目標的路徑選擇模型得到的最優路徑均有效避免擁擠區域，但距離略長于基于幾何距離的路徑選擇模型。而當權重系數分別為0.8和0時，圖8、9的最優路徑相同。當各權重系數不同而結果相同時，產生原因有兩種：一種是各決策變量的閾值相差大，組合權重函數對權重系數不敏感；而另一種就是當前最優路徑是唯一的，即不同權重系數的組合產生了同樣的結果。在求解算法中，針對各決策變量的閾值進行了預處理且已證明其有效性，所以原因歸結于結果重合。為更充分地說明問題，以距離、時間、費用等為參數進行了對比實驗，其結果如表2所示。

圖9 擁擠情形下wz=0基于多目標的路徑選擇模型的最優路徑Fig.9 The optimal path of wz=0 based on multi-objective under congestion of road traffic

圖10 道路擁擠情形下的幾何最短路徑Fig.10 Geometric shortest path under the congestion of road traffic

Table 2 Contrast experiment under the congestion of road traffic

模型距離/m時間/s費用/元最短路徑10169579476192401本文wz=081064423768647061本文wz=01064423768647061

由表2中同時列出的基于兩種不同模型給出的最優路徑的距離、時間以及費用等指標。實驗結果表明，基于幾何路徑最短的模型下的最優路徑距離最短，但基于多目標的路徑選擇模型在時間、費用上均甚優于最短距離。由于在交通擁擠的情形下，車輛間的相互延誤導致行駛速度緩慢，尤其，當交通達到堵塞時，交通滯留導致行駛速度為0。因此，當最短路徑在擁擠區域時，延誤時間增加導致路阻明顯增加；速度遲緩也導致燃油費增加，且當處于擁擠區內時擁擠費增加，從而導致費用的明顯增加。而多目標模型在系數K的約束控制下，有效避免了進入擁擠區域，從而時間、費用均明顯占優于最短路徑。但若目標結點處于擁擠區域時，由于本文以組合權重為優化目標，即以時間和費用組合的權重為誘導因素，且在求解中采用臨時優先隊列保存擁擠區域結點的策略。所以，基于多目標的模型得到的最優路徑在時間、費用上均占優于最短路徑。因此，可得到以下結論：在道路擁擠的情形下，基于多目標的路徑選擇模型比基于幾何最短的路徑選擇模型更具有實用價值。

4 結論

1)采用迭代取最高位的策略，對組合優化函數中的決策變量進行類似的量值處理后，組合權重與最優解之間的映射更符合要求且結果優于未預處理的解。所以，基于多目標的路徑選擇模型能滿足出行者多樣化的需求。

2)在道路暢通的情形下，基于多目標的路徑選擇模型的路徑在時間、費用上均優于基于幾何最短模型的路徑。

3)在道路擁擠的情形下，由于K系數的約束可以有效避免車輛進入擁擠區域。所以，基于本文模型的最優路徑在時間、費用上均明顯甚優于幾何最短距離。

總之，基于多目標的路徑選擇模型比基于幾何最短的路徑選擇模型更具有實用價值。

[1]KIM G, ONG Y S, HENG C K, et al. City vehicle routing problem (city vrp): A review[J]. IEEE transactions on intelligent transportation systems, 2015, 16(4): 1654-1666.

[2]鄭祖舵. 動態路徑優化關鍵技術研究[D]. 長春: 吉林大學, 2006: 5-7. ZHENG Zuduo. Research on key technologies of the dynamic route optimization[D]. Changchun: Jilin University, 2016: 5-7.

[3]AVINERI E, PRASHKER J N. Sensitivity to travel time variability: travelers′ learning perspective[J]. Transportation research part C: emerging technologies, 2005, 13(2): 157-183.

[4]孟夢, 邵春福, 曾靖靜, 等.考慮出發時間的組合出行動態路徑選擇模型[J].中南大學學報:自然科學版, 2014, 45(10): 3676-3684. MENG Meng, SHAO Chunfu, ZENG Jingjing, et al. Dynamic route choice model with departure time in combined trip[J]. Journal of Central South University: science and technology, 2014, 45(10): 3676-3684.

[5]劉艷秋, 劉博. 交通擁堵下基于實時交通信息的路徑選擇模型[J]. 沈陽工業大學學報, 2014, 36(4): 426-430. LIU Yanqiu, LIU Bo. Route selection model based onreal-time traffic information under traffic congestion[J]. Journal of Shenyang University of Technology, 2014, 36(4): 426-430.

[6]吳磊. 車輛自組織網絡環境下動態路徑誘導系統的建模與優化策略研究[D].濟南：山東大學, 2014: 22-24. WU Lei. Modeling and optimization of dynamic route guidance system under vehicular Ad-Hoc networks[D]. Jinan: Shandong University, 2014: 22-24.

[7]劉玉印, 劉偉銘, 吳建偉. 基于累積前景理論的出行者路徑選擇模型[J]. 華南理工大學學報: 自然科學版, 2010, 38(7): 84-89. LIU Yuyin, LIU Weiming, WU Jianwei. A route selection model based on cumulative prospect theory[J]. Journal of South China University of Technology: natural science edition, 2010, 38(7): 84-89.

[8]吳磊, 楊立才. 基于前景理論的實時路徑選擇模型[J]. 控制理論與應用, 2013, 30(7):916-921. WU Lei,YANG Licai. Prospect theory-based route choice model in dynamic route guidance system[J]. Control theory & applications, 2013, 30(7): 916-921.

[9]張波, 雋志才, 林徐勛. 基于累積前景理論的隨機用戶均衡交通分配模型[J]. 西南交通大學學報, 2011, 46(5): 868-874. ZHANG Bo,JUN Zhicai,LIN Xuxun. Stochastic user equilibrium model based on cumulative prospect theory[J]. Journal of Southwest Jiaotong University, 2011, 46(5): 868-874.[10]AVINERI E, PRASHKER J N. Sensitivity to travel time variability: travelers′ learning perspective[J]. Transportation research part C: emerging technologies, 2005, 13(2): 157-183.

[11]WAHLE J, ANNEN O, SCHUSTER C, et al. A dynamic route guidance system based on real traffic data[J]. European journal of operational research, 2001, 131(2): 302-308.

[12]徐鶴鳴. 多目標粒子群優化算法的研究[D]. 上海: 上海交通大學, 2013: 45-46. XU Heming. Research on Multi-objective particle swarm optimization algorithms[D]. ShangHai: Shanghai Jiao Tong University, 2013: 45-46.

[13]楊雅君, 高宏, 李建中. 多維代價圖模型上最優路徑查詢問題的研究[J]. 計算機學報, 2012, 35(10): 2147-2158. YANG Yajun,GAO Hong,LI Jianzhong.Optimal path query based on cost function over multi-cost graphs. Chinese journal of computers, 2012, 35(10): 2147-2158.

[14]MARLER R T, ARORA J S. The weighted sum method for multi-objective optimization: new insights[J]. Structural and multidisciplinary optimization, 2010, 41(6): 853-862.

[15]WAHLE J, ANNEN O, SCHUSTER C, et al. A dynamic route guidance system based on real traffic data[J]. European journal of operational research, 2001, 131(2): 302-308.

[16]王素欣, 王雷震, 高利,等. BPR路阻函數的改進研究[J]. 武漢理工大學學報:交通科學與工程版, 2009, 33(3): 446-449. WANG Suxin, WANG Leizhen, et al. Improvement of BPR path resistance function[J]. Journal of Wuhan University of Technology: transportation science & engineering, 2009, 33(3): 446-449.

[17]SUN X, KOENIG S, YEOH W. Generalized adaptive A*[C]//Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 2008: 469-476.

[18]馮雨芹. 基于交通流狀態的城市道路燃油經濟性模型研究[D]. 哈爾濱: 哈爾濱工業大學, 2011: 31-32. FENG Yuqin. Research on fuel economy model of urban road based on traffic flow status[D]. Harbin: Harbin Institute of Technology, 2011: 31-32.

[19]隗海林, 王勁松, 王云鵬,等. 基于城市道路工況的汽車燃油消耗模型[J]. 吉林大學學報: 工學版, 2009, 39(5): 1146-1150. KUI Hailin，WANG Jinsong，WANG Yunpeng, et al. Vehicle fuel consumption model based on urban road operations[J]. Journal of Jilin University: engineering and technology edition, 2009, 39(5): 1146-1150.

本文引用格式：

陳海鵬，劉陪，申鉉京，等. 實時環境下多目標的路徑選擇模型[J]. 哈爾濱工程大學學報， 2017， 38(8): 1285-1292.

CHEN Haipeng, LIU Pei, SHEN Xuanjing, et al. Route choice model based on multi-objective in a real-time environment[J]. Journal of Harbin Engineering University， 2017， 38(8): 1285-1292.

Route choice model based on multi-objective in a real-time environment

CHEN Haipeng1,2, LIU Pei1,2, SHEN Xuanjing1,2, WANG Yu1,2,3

(1.College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China； 3.Applied Technology College, Jilin University, Changchun 130012, China)

In view of this situation, a route choice model based on multi-objective was constructed and considered from the angles of cost and time in this paper. The weighted sum method was used to aggregate multi-target data objects to obtain the composite weight value, and the weight coefficient can be set based on travelers′ needs or preferences. To verify the practical value of the model, the multi-objective-based model was compared with the route choice model on the basis of the shortest geometric distance in terms of time, cost, and distance. Experimental results show that the path of the multi-objective optimal route choice mode has more practical value based on a real-time environment.

intelligent transportation system; dynamic route guidance system; multi objective; route choice models; weighted sum method; combinatorial optimizing; generalized adaptive A*algorithm

2016-04-26.

日期：2017-04-27.

國家青年科學基金項目(61305046)；吉林省自然科學基金項目(20140101193JC， 20150101055JC).

陳海鵬(1978-)，男，副教授； 王玉(1983-)，男，講師.

王玉，E-mail:wangyu001@jlu.edu.cn.

10.11990/jheu.201604080

TP399

A

1006-7043(2017)08-1285-08

網絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170427.1510.076.html