實(shí)時(shí)環(huán)境下多目標(biāo)的路徑選擇模型

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

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長(zhǎng)春 130012; 2.吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,吉林 長(zhǎng)春 130012； 3.吉林大學(xué) 應(yīng)用技術(shù)學(xué)院,吉林 長(zhǎng)春 130012)

實(shí)時(shí)環(huán)境下多目標(biāo)的路徑選擇模型

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

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長(zhǎng)春 130012; 2.吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,吉林 長(zhǎng)春 130012； 3.吉林大學(xué) 應(yīng)用技術(shù)學(xué)院,吉林 長(zhǎng)春 130012)

針對(duì)出行者出行需求多樣化的問(wèn)題，本文從時(shí)間、費(fèi)用角度出發(fā)，構(gòu)建了實(shí)時(shí)環(huán)境下基于多目標(biāo)的路徑選擇模型。采用加權(quán)求和函數(shù)對(duì)多維數(shù)據(jù)聚集得到組合權(quán)重，而權(quán)重系數(shù)可依據(jù)出行者需求或喜好設(shè)定。為驗(yàn)證模型的實(shí)用價(jià)值，在仿真環(huán)境下，多目標(biāo)模型與基于幾何距離最短的路徑選擇模型在時(shí)間、費(fèi)用、距離等評(píng)價(jià)指標(biāo)進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果證明實(shí)時(shí)環(huán)境下基于多目標(biāo)的路徑選擇模型更具有實(shí)用價(jià)值。

智能交通系統(tǒng)； 動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)； 多目標(biāo)； 路徑選擇模型； 加權(quán)求和函數(shù)； 組合優(yōu)化； 廣義自適應(yīng)A*算法

智能交通系統(tǒng)(intelligent transportation system， ITS)是集信息、通信、控制及網(wǎng)絡(luò)等技術(shù)于一體的綜合研究學(xué)科，可以提供全方位、實(shí)時(shí)、準(zhǔn)確以及高效的服務(wù)信息，ITS是有潛力的研究方向，進(jìn)一步說(shuō)將成為未來(lái)相關(guān)研究領(lǐng)域的熱點(diǎn)[1]。動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)(dynamic route guidance system，DRGS)是ITS一個(gè)重要的分支，利用計(jì)算機(jī)、通信等現(xiàn)代技術(shù)，為出行者提供實(shí)時(shí)交通信息以及最優(yōu)路徑。在DRGS中，路徑選擇模型可以確立DRGS的目標(biāo)[2]。

路徑誘導(dǎo)模型分為靜態(tài)模型和動(dòng)態(tài)模型，靜態(tài)模型以假設(shè)出行者獲知路網(wǎng)信息為前提，并以隨機(jī)期望效用理論或積累前景理論為基礎(chǔ)。而動(dòng)態(tài)模型包含一些信息獲取和學(xué)習(xí)的過(guò)程，以隨機(jī)虛擬理論或增強(qiáng)學(xué)習(xí)理論作為指導(dǎo)[3]。目前，在國(guó)內(nèi)路徑誘導(dǎo)模型的研究主要還是集中在靜態(tài)模型且取得了階段性的成果?；谄谕в美碚摰哪Ｐ褪窃诖_定性框架下，以幾何路徑或者出行時(shí)間為效用值，以期望獲得效用最大化評(píng)價(jià)各備選方案的優(yōu)劣。孟夢(mèng)等針對(duì)不同的出行時(shí)間，提出了組合出行工具的路徑選擇模型，以組合出行工具的模式下為出行者提供最優(yōu)路徑[4]。劉艷秋等構(gòu)建了交通堵塞下基于實(shí)時(shí)交通信息的路徑選擇模型[5]。相反，積累前景理論是不確定性情況下的決策行為，決策者以財(cái)富的變化量而不是最終量作為參考依據(jù)進(jìn)行決策[6]，針對(duì)交通信息不確定的特性，諸多學(xué)者以積累前景理論為基礎(chǔ)提出了路徑選擇模型[7-9]。但是，目前提出的模型大多僅針對(duì)路段行程時(shí)間構(gòu)建的單目標(biāo)路徑選擇模型[6]，顯然，與實(shí)際存在很大的偏差。在實(shí)時(shí)環(huán)境下，交通暢通、擁擠情形下路阻的產(chǎn)生形式有所差異，因此，分別以交通暢通、擁擠下的路阻構(gòu)建了基于時(shí)間最短的路徑選擇模型， 進(jìn)而提高了模型的可靠性。

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

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

1 基于多目標(biāo)的路徑選擇模型設(shè)計(jì)

1.1 問(wèn)題描述及分析

路徑優(yōu)化問(wèn)題相當(dāng)于圖理論模型中最優(yōu)路徑的查找問(wèn)題，但又存在差異。在動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中含有靜態(tài)屬性和動(dòng)態(tài)屬性[15]，靜態(tài)屬性是路網(wǎng)信息相對(duì)固定的部分，例如: 地理位置信息、路段間距以及路段的基本通行能力等。而動(dòng)態(tài)屬性可以反映實(shí)時(shí)信息狀況，例如，車(chē)流量、行車(chē)速度等。所以，路網(wǎng)數(shù)據(jù)對(duì)象具有多樣、復(fù)雜以及實(shí)時(shí)的特性。以圖論為基礎(chǔ)，同時(shí)結(jié)合動(dòng)態(tài)路網(wǎng)信息的特性，路徑優(yōu)化問(wèn)題的定義形式：

(1)

式中：G=(V，Rij)是靜態(tài)屬性，表示路網(wǎng)結(jié)構(gòu)；V是從起始點(diǎn)到結(jié)束點(diǎn)間的結(jié)點(diǎn)集合；Rij是當(dāng)前Sstart到Send所有無(wú)環(huán)路集合，其定義形式為

(2)

式中：Wij是體現(xiàn)了動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中的動(dòng)態(tài)屬性，Wij對(duì)應(yīng)(i，j)間的權(quán)重值，并以此為優(yōu)化準(zhǔn)則；Sstart是出發(fā)節(jié)點(diǎn)且隨著車(chē)輛的不斷行駛動(dòng)態(tài)更新，Send表示目標(biāo)節(jié)點(diǎn)。

1.2 基于時(shí)間最短的路徑選擇模型

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

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

(3)

其約束條件為

(4)

(5)

(6)

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

1.3 基于費(fèi)用最低的路徑選擇模型

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

(7)

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

(8)

式中：Fh(i，j)表示燃油費(fèi)用；Fc(i，j)代表?yè)頂D區(qū)域繳納擁擠費(fèi)，約束擁擠費(fèi)的計(jì)算方式為

(9)

式(9)表示：當(dāng)且僅當(dāng)?shù)谝淮芜M(jìn)入擁擠區(qū)域時(shí)繳納擁擠費(fèi)，即γ=1，否則γ=0。

1.4 組合優(yōu)化函數(shù)模型

針對(duì)出行者出行需求的多樣化，采用加權(quán)求和最小化方法處理基于多目標(biāo)的路徑選擇模型更加合理且易實(shí)現(xiàn)。出行者可以預(yù)設(shè)出行需求，例如設(shè)置費(fèi)用最低、時(shí)間最短或自設(shè)權(quán)重大小。所以，本文以加權(quán)求和函數(shù)值作為優(yōu)化準(zhǔn)則，組合優(yōu)化函數(shù)模型的定義形式為

(10)

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

2 基于多目標(biāo)的路徑選擇模型求解

在實(shí)時(shí)交通信息下，動(dòng)態(tài)路徑優(yōu)化中“動(dòng)”主要體現(xiàn)在各路段中評(píng)價(jià)值會(huì)隨著時(shí)間的變化而發(fā)生變更，而最優(yōu)路徑也會(huì)隨之發(fā)生變化，因此，動(dòng)態(tài)地為出行者提供優(yōu)化方案。針對(duì)交通信息的不可控性、隨機(jī)性以及不確定性等因素，顯然一步尋優(yōu)與實(shí)時(shí)狀況相背離，而逐步尋優(yōu)更加合理。換言之，動(dòng)態(tài)路徑優(yōu)化是一種逐步尋優(yōu)的搜索過(guò)程，而最終目的是降低費(fèi)用、減少污染或節(jié)省時(shí)間等。

為驗(yàn)證實(shí)時(shí)環(huán)境下基于多目標(biāo)的路徑選擇模型，采用廣義自適應(yīng)A*算法[17]實(shí)現(xiàn)并獲取最優(yōu)路徑及評(píng)價(jià)參數(shù)值。

2.1 采用廣義自適應(yīng)A*算法的合理性分析

廣義自適應(yīng)A*算法被認(rèn)為是A*算法的迭代過(guò)程，同樣在算法中，采用open表保存所有已生成而未考察的節(jié)點(diǎn)，closed表存儲(chǔ)已訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)。但存在兩方面的差異，一方面每完成一次A*搜索后，修改closed表中所有狀態(tài)的h值，從而使啟發(fā)值更明智。另一方面，當(dāng)發(fā)現(xiàn)某條邊的權(quán)重減少時(shí)，在搜索空間中需修改某些狀態(tài)h值，即重構(gòu)h值的一致性。這兩點(diǎn)體現(xiàn)廣義自適應(yīng)A*算法在動(dòng)態(tài)環(huán)境中的適用性。

在動(dòng)態(tài)路徑優(yōu)化中，一方面，隨著距離目標(biāo)越來(lái)越近，結(jié)點(diǎn)不斷減少，起始點(diǎn)Sstart在不斷的發(fā)生變化。因此，起始點(diǎn)Sstart需動(dòng)態(tài)的調(diào)整；另一方面，在實(shí)時(shí)環(huán)境下，路段的權(quán)值動(dòng)態(tài)的變化。本文以組合權(quán)重值Wij為算法的啟發(fā)式h值，實(shí)時(shí)環(huán)境下，決策變量路阻、時(shí)間在不斷發(fā)生變化，Wij有可能減小。在這種情形下，需重構(gòu)Wij的一致性。重構(gòu)后，調(diào)用A*算法進(jìn)而得到當(dāng)前信息下的最優(yōu)路徑，重復(fù)此過(guò)程直到Sstart=Send算法結(jié)束。

2.2 算法應(yīng)用過(guò)程

2.2.1 實(shí)現(xiàn)過(guò)程

在本文中，廣義自適應(yīng)A*算法具體實(shí)現(xiàn)過(guò)程如圖1所示。

圖1 廣義自適應(yīng)A*算法實(shí)現(xiàn)過(guò)程Fig.1 Generalized adaptive A* algorithm implementation process

1)初始化Sstart、Send，加載Sstart和Send間地圖的靜態(tài)數(shù)據(jù)并獲取當(dāng)前實(shí)時(shí)動(dòng)態(tài)信息，進(jìn)而初始化組合權(quán)重Wij，執(zhí)行步驟2。

2)若Sstart!=Send，首先調(diào)用A*算法，若不存在路徑，返回NULL程序結(jié)束；反之，則返回目標(biāo)結(jié)點(diǎn)Send，進(jìn)而轉(zhuǎn)向步驟3。

3)修改closed表中所有的啟發(fā)式值Wij，并以Send為參數(shù)構(gòu)造Sstart與Send間的路徑，執(zhí)行步驟4。

4)以當(dāng)前路徑的下一結(jié)點(diǎn)為Sstart，并更新實(shí)時(shí)動(dòng)態(tài)數(shù)據(jù)，重新檢測(cè)以Sstart的Wij啟發(fā)式值是否減小，若減小，則重構(gòu)Wij的一致性，重構(gòu)完成后，跳出步驟4，執(zhí)行步驟2；若不變或增加，則繼續(xù)執(zhí)行步驟4；若Sstart=Send時(shí)，跳出步驟4，執(zhí)行步驟2。

2.2.2 控制策略

1)擁擠區(qū)域控制策略：調(diào)用A*算法過(guò)程中，采用K約束設(shè)置open表優(yōu)先級(jí)的策略，即當(dāng)K=1時(shí)的優(yōu)先級(jí)高于K=0時(shí)的優(yōu)先級(jí)，從而可以?xún)?yōu)先擴(kuò)展暢通區(qū)域的結(jié)點(diǎn)。設(shè)定open表優(yōu)先級(jí)過(guò)程：首先將open表定義以Wij為優(yōu)先的隊(duì)列；進(jìn)而，判斷K值，若K=0，則該結(jié)點(diǎn)插入臨時(shí)優(yōu)先隊(duì)列，否則插入open表；優(yōu)先擴(kuò)展暢通區(qū)域的結(jié)點(diǎn)，當(dāng)open表為空且未找到目標(biāo)節(jié)點(diǎn)時(shí)，進(jìn)而擴(kuò)展臨時(shí)優(yōu)先隊(duì)列。在道路擁擠的情形下，有效避免進(jìn)入擁擠區(qū)域，從而節(jié)省時(shí)間、減少費(fèi)用也可以緩解擁擠區(qū)域的交通壓力。

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

3 實(shí)驗(yàn)仿真及結(jié)果分析

為驗(yàn)證在實(shí)時(shí)環(huán)境下基于多目標(biāo)的路徑選擇模型的合理性及有效性，采用C++編程仿真實(shí)驗(yàn)環(huán)境。以隨機(jī)讀入文本的形式模擬實(shí)時(shí)環(huán)境，即車(chē)流量以文本流的形式更新。

3.1 參數(shù)設(shè)置

在交通信息中，車(chē)流量是實(shí)時(shí)變化的，車(chē)流量Qij與密度kij間存在函數(shù)關(guān)系：

(11)

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

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

(12)

在交通擁擠情形下，車(chē)輛間相互影響產(chǎn)生延遲時(shí)間的計(jì)算方式[5]為

(13)

式中：θij代表單位小時(shí)內(nèi)當(dāng)前路段車(chē)輛的時(shí)間密集度，Lij表示當(dāng)前路段長(zhǎng)度，Lc為有效檢測(cè)器長(zhǎng)度與平均車(chē)長(zhǎng)的距離之和。

形式化交叉口等待時(shí)間為

(14)

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

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

(15)

(16)

式中：cost表示當(dāng)車(chē)輛第一次(γ=1)進(jìn)入擁擠區(qū)域時(shí)繳納擁擠稅，否則，無(wú)需繳納擁擠稅。

3.2 實(shí)驗(yàn)仿真數(shù)據(jù)

利用某城市實(shí)際道路網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行路徑尋優(yōu)仿真實(shí)驗(yàn)，VISSIM仿真將真實(shí)地圖映射為如圖2所示的路網(wǎng)結(jié)構(gòu)。

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

在圖2中有101個(gè)測(cè)試結(jié)點(diǎn)和291條測(cè)試路段，實(shí)驗(yàn)數(shù)據(jù)以VISSIM仿真數(shù)據(jù)并結(jié)合實(shí)際進(jìn)行了合理假設(shè)。車(chē)流量采用VISSIM仿真數(shù)據(jù)并以文本的形式實(shí)時(shí)讀入。速度、燃油費(fèi)、時(shí)間等結(jié)合實(shí)際道路情況進(jìn)行了合理的設(shè)定和計(jì)算。

3.3 評(píng)價(jià)指標(biāo)

到目前為止，針對(duì)路徑選擇模型的評(píng)價(jià)沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)。而目前普通汽車(chē)上安裝的商用導(dǎo)航系數(shù)大多是基于幾何最短路徑或可通達(dá)路徑的靜態(tài)路徑為優(yōu)化路徑。為驗(yàn)證模型的合理性及實(shí)用價(jià)值，與基于幾何距離最短的路徑選擇模型分別以時(shí)間、費(fèi)用、距離等參數(shù)進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果證明了在實(shí)時(shí)環(huán)境下，幾何最短路徑并非最優(yōu)路徑，而基于多目標(biāo)的路徑選擇模型更加合理且具有一定的實(shí)用價(jià)值。

3.4 實(shí)例及結(jié)果分析

本文在仿真實(shí)時(shí)環(huán)境下進(jìn)行了多組實(shí)驗(yàn)，分別從道路暢通及擁擠情形下，以基于幾何最短路徑與本文模型進(jìn)行了對(duì)比實(shí)驗(yàn)。為形象地顯示實(shí)驗(yàn)結(jié)果，本文分別以最優(yōu)路徑對(duì)比圖以及評(píng)價(jià)參數(shù)的對(duì)比結(jié)果加以詮釋。

3.4.1 道路暢通情形下的對(duì)比實(shí)驗(yàn)

在交通暢通的情形下，以結(jié)點(diǎn)1～100為一組實(shí)例進(jìn)行分析。為驗(yàn)證本文組合優(yōu)化函數(shù)模型的有效性，基于該實(shí)例下，以同等實(shí)驗(yàn)環(huán)境，時(shí)間權(quán)重系數(shù)wz分別在0～1以0.1為間隔取值。在不同wz下，最優(yōu)路徑所對(duì)應(yīng)的時(shí)間、費(fèi)用以及兩者比值(費(fèi)用/時(shí)間)如圖3所示，體現(xiàn)了組合權(quán)重與優(yōu)化結(jié)果間的映射關(guān)系。

圖3 道路暢通情形下組合權(quán)重與優(yōu)化結(jié)果映射關(guān)系Fig.3 The mapping relationship between combination weights and the optimization results under the smoother of road traffic

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

為進(jìn)一步驗(yàn)證本模型的優(yōu)勢(shì)，在同等實(shí)驗(yàn)環(huán)境下，本文模型分別以不同時(shí)間權(quán)重系數(shù)下的最優(yōu)路徑與基于幾何最短的最優(yōu)路徑進(jìn)行了對(duì)比實(shí)驗(yàn)，如圖4～6中圖例所示。其中，圖4為幾何最短路徑示意圖，圖5、6是時(shí)間權(quán)重系數(shù)分別為1和0.5的最優(yōu)路徑。

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

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

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

由圖4～6可知，幾何最短路徑的距離明顯優(yōu)于多目標(biāo)模型。為進(jìn)一步說(shuō)明上述結(jié)果，本文分別從距離、時(shí)間、費(fèi)用等參數(shù)進(jìn)行了對(duì)比實(shí)驗(yàn)，其結(jié)果如表1所示。

表1 道路暢通情形下的對(duì)比實(shí)驗(yàn)

對(duì)比表1列出的基于兩種模型下最優(yōu)路徑的距離，可以進(jìn)一步驗(yàn)證上述圖4～6結(jié)果。針對(duì)基于幾何距離最短的路徑選擇模型而言，優(yōu)化是以距離最短為目標(biāo)。所以，基于幾何距離最短的模型下，最優(yōu)路徑的距離最短。

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

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

3.4.2 道路擁擠情形下的對(duì)比實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證基于多目標(biāo)的路徑選擇模型的性能，在道路阻塞的情形下，對(duì)多目標(biāo)模型進(jìn)行了對(duì)比實(shí)驗(yàn)。在反復(fù)多組實(shí)驗(yàn)的基礎(chǔ)上，選取結(jié)點(diǎn)1～39為一組實(shí)例進(jìn)行實(shí)驗(yàn)分析。為驗(yàn)證組合優(yōu)化函數(shù)的有效性，在本實(shí)例下，同樣地，時(shí)間權(quán)重系數(shù)wz以0.1為間隔在0～1取值。在相同的實(shí)驗(yàn)環(huán)境下，組合權(quán)重與優(yōu)化結(jié)果的映射關(guān)系(以費(fèi)用與時(shí)間的比值為優(yōu)化結(jié)果)如圖7所示。

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

圖7 道路擁擠情形下組合權(quán)重與優(yōu)化結(jié)果映射關(guān)系Fig.7 The mapping relationship between combination weights and the optimization results under congestion of road traffic

為進(jìn)一步詮釋本模型的合理性，在相同實(shí)驗(yàn)環(huán)境下，基于多目標(biāo)的路徑選擇模型分別以時(shí)間權(quán)重系數(shù)為0.8和0的最優(yōu)路徑如圖8、9所示與幾何最短路徑如圖10進(jìn)行了對(duì)比實(shí)驗(yàn)。圖示中黑色加重為最優(yōu)路徑，矩形標(biāo)注為擁擠區(qū)域。

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

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

圖9 擁擠情形下wz=0基于多目標(biāo)的路徑選擇模型的最優(yōu)路徑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時(shí)間/s費(fèi)用/元最短路徑10169579476192401本文wz=081064423768647061本文wz=01064423768647061

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

4 結(jié)論

1)采用迭代取最高位的策略，對(duì)組合優(yōu)化函數(shù)中的決策變量進(jìn)行類(lèi)似的量值處理后，組合權(quán)重與最優(yōu)解之間的映射更符合要求且結(jié)果優(yōu)于未預(yù)處理的解。所以，基于多目標(biāo)的路徑選擇模型能滿(mǎn)足出行者多樣化的需求。

2)在道路暢通的情形下，基于多目標(biāo)的路徑選擇模型的路徑在時(shí)間、費(fèi)用上均優(yōu)于基于幾何最短模型的路徑。

3)在道路擁擠的情形下，由于K系數(shù)的約束可以有效避免車(chē)輛進(jìn)入擁擠區(qū)域。所以，基于本文模型的最優(yōu)路徑在時(shí)間、費(fèi)用上均明顯甚優(yōu)于幾何最短距離。

總之，基于多目標(biāo)的路徑選擇模型比基于幾何最短的路徑選擇模型更具有實(shí)用價(jià)值。

[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òng)態(tài)路徑優(yōu)化關(guān)鍵技術(shù)研究[D]. 長(zhǎng)春: 吉林大學(xué), 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]孟夢(mèng), 邵春福, 曾靖靜, 等.考慮出發(fā)時(shí)間的組合出行動(dòng)態(tài)路徑選擇模型[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版, 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]劉艷秋, 劉博. 交通擁堵下基于實(shí)時(shí)交通信息的路徑選擇模型[J]. 沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào), 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]吳磊. 車(chē)輛自組織網(wǎng)絡(luò)環(huán)境下動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)的建模與優(yōu)化策略研究[D].濟(jì)南：山東大學(xué), 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]. 華南理工大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]吳磊, 楊立才. 基于前景理論的實(shí)時(shí)路徑選擇模型[J]. 控制理論與應(yīng)用, 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ī)用戶(hù)均衡交通分配模型[J]. 西南交通大學(xué)學(xué)報(bào), 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]徐鶴鳴. 多目標(biāo)粒子群優(yōu)化算法的研究[D]. 上海: 上海交通大學(xué), 2013: 45-46. XU Heming. Research on Multi-objective particle swarm optimization algorithms[D]. ShangHai: Shanghai Jiao Tong University, 2013: 45-46.

[13]楊雅君, 高宏, 李建中. 多維代價(jià)圖模型上最優(yōu)路徑查詢(xún)問(wèn)題的研究[J]. 計(jì)算機(jī)學(xué)報(bào), 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路阻函數(shù)的改進(jìn)研究[J]. 武漢理工大學(xué)學(xué)報(bào):交通科學(xué)與工程版, 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]馮雨芹. 基于交通流狀態(tài)的城市道路燃油經(jīng)濟(jì)性模型研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 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]隗海林, 王勁松, 王云鵬,等. 基于城市道路工況的汽車(chē)燃油消耗模型[J]. 吉林大學(xué)學(xué)報(bào): 工學(xué)版, 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.

本文引用格式：

陳海鵬，劉陪，申鉉京，等. 實(shí)時(shí)環(huán)境下多目標(biāo)的路徑選擇模型[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 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.

國(guó)家青年科學(xué)基金項(xiàng)目(61305046)；吉林省自然科學(xué)基金項(xiàng)目(20140101193JC， 20150101055JC).

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

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

10.11990/jheu.201604080

TP399

A

1006-7043(2017)08-1285-08

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170427.1510.076.html