張騰，黃敏，劉芳，鄭健

(中山大學(xué)智能工程學(xué)院∥廣東智能交通系統(tǒng)重點實驗室，廣東 廣州 510006)

指路標(biāo)志是一種交通誘導(dǎo)管理設(shè)施，為交通參與者傳遞道路的相關(guān)信息(方向、地點、距離等信息)，指引駕駛員做出合理的路徑?jīng)Q策。合理的指路標(biāo)志系統(tǒng)可以提高交通系統(tǒng)的運行效率，緩解交通擁擠。而實際情況中，指路標(biāo)志存在信息的缺失、錯誤以及指引路徑不連續(xù)等問題，導(dǎo)致出行者錯行繞行現(xiàn)象頻發(fā)[1]。為出行者提供連續(xù)的指引信息，幫助其順利到達目的地是指路標(biāo)志誘導(dǎo)系統(tǒng)最基本的功能。目前許多學(xué)者針對指引信息可達性進行了研究。韓躍杰等[2]建立了指路標(biāo)志信息連續(xù)性評價模型，對路網(wǎng)中的指引信息可達性進行評價。黃敏等[3]結(jié)合出行者的尋路習(xí)慣，構(gòu)建了指引信息可達性分析模型，并對指路標(biāo)志可達性給予了明確的定義與評價。

基于對指路標(biāo)志系統(tǒng)的可達性評價，優(yōu)化指引信息是完善指路標(biāo)志誘導(dǎo)功能、改善道路出行環(huán)境的重要舉措。有學(xué)者提出了相應(yīng)的指引信息優(yōu)化方案[4]，把不可達路徑擴展為指引可達路徑。但，優(yōu)化方案僅考慮了單條不可達路徑的擴展優(yōu)化，未從整體進行考慮，因此不能滿足實際工程的需要。另一方面，車輛路徑規(guī)劃問題是一個NP問題，只有在路網(wǎng)規(guī)模較小時才有可能尋求其精確解。因此，啟發(fā)式算法的應(yīng)用成為人們研究求解該類問題的重要手段，如：蟻群算法、遺傳算法、粒子群算法等[5-8]。但這些算法本身存在一系列問題，如：蟻群算法收斂速度慢、遺傳算法易早熟收斂、粒子群算法精度不高且易陷入局部最優(yōu)等。

人工蜂群算法(artificial bee colony algorithm，ABC)是由Karaboga.D于2005年提出的一種元啟發(fā)式群智能算法。該算法具有設(shè)置參數(shù)少、搜索速度快，實現(xiàn)方便等優(yōu)點，因此其已經(jīng)被廣泛地應(yīng)用到各個優(yōu)化領(lǐng)域[9-12]，如：求解旅行商問題、機器人路徑規(guī)劃、通訊領(lǐng)域等，并表現(xiàn)出了強大的適應(yīng)性和優(yōu)異性。此前已有學(xué)者[4]將人工蜂群算法應(yīng)用到指引信息的優(yōu)化問題中，并將實驗結(jié)果與遺傳算法進行了對比。實驗表明：人工蜂群算法能比遺傳算法更高效地尋找最優(yōu)路徑。本文針對已有的指路標(biāo)志布設(shè)方案，利用可達性分析模型[3]得出了特定興趣點的多條不可達路徑；為將上述多條不可達路徑擴展為可達路徑，考慮了多條不可達路徑擴展時的相互影響，進一步構(gòu)建出以指引路徑與指路標(biāo)志布設(shè)綜合最優(yōu)為目標(biāo)的優(yōu)化模型；并利用該模型實現(xiàn)已有指路標(biāo)志布設(shè)方案的優(yōu)化。實驗數(shù)據(jù)表明：本模型在指路標(biāo)志優(yōu)化布設(shè)方面具備更好的可行性。

1 指引路徑優(yōu)化問題描述

1.1 路網(wǎng)結(jié)構(gòu)表示

出行者對于路徑的選擇是基于路網(wǎng)進行的，因此交通路網(wǎng)是路徑規(guī)劃的基礎(chǔ)。本文通過“節(jié)點-弧段”的方法對路網(wǎng)進行描述，將路網(wǎng)定義為G={V,A}，其中V={vi}為路網(wǎng)G中的節(jié)點集合，A={aij|aij=(vi,vj),vi、vj∈V}為G中的弧段集合，aij為有向路段vi到vj，cij為弧段aij的弧段信息，如路段長度信息。

1.2 指引路徑與指引可達

指引路徑是駕駛員根據(jù)指路標(biāo)志系統(tǒng)的指引和駕駛員自身駕駛經(jīng)驗的指導(dǎo)，選擇出的一條從起點前往指定終點的期望路徑。在駕駛過程中，駕駛員會根據(jù)指路標(biāo)志給出的指引信息進行路徑選擇。當(dāng)?shù)缆方徊婵谌鄙賹δ康牡刂敢闹嘎窐?biāo)志時，駕駛員會根據(jù)自己的駕駛經(jīng)驗做出選擇。

基于已有的指引信息可達性分析模型，本文對指引信息構(gòu)成的指引路徑進行分類和定義。已知某路網(wǎng)，路網(wǎng)結(jié)構(gòu)如圖1所示。當(dāng)指引路徑能夠?qū)崿F(xiàn)駕駛員從起點到終點的出行，就稱這條指引路徑是指引可達的，即O1出發(fā)路徑；反之，則稱這條指引路徑是指引不可達的，即O2出發(fā)路徑。

1.3 指引路徑的綜合優(yōu)化問題

決策者在規(guī)劃指引路徑的過程中，需要綜合考慮多方面因素，如：指引路徑的長度、增設(shè)指引信息的數(shù)量、道路的重要程度等。

已有的單條路徑優(yōu)化模型[4]以指引路徑長度和增設(shè)指路標(biāo)志數(shù)量綜合最優(yōu)為目標(biāo)，把單條不可達路徑擴展為指引可達路徑。然而，工程實際中可能出現(xiàn)多條不可達路徑，如果將它們單獨優(yōu)化，并把結(jié)果進行直接疊加，所得的最終路徑可能非最優(yōu)。

圖2 指引路徑單獨優(yōu)化示意圖Fig.2 Single optimization guide path

圖3 指引路徑綜合優(yōu)化示意圖Fig.3 Guide path overall optimization

如圖2路網(wǎng)中，已知O1、O2為D的兩條不可達路徑端點，且路網(wǎng)中已有指向D的指引信息(圖中虛線框內(nèi)為已有指引信息，下同)，對其分別進行優(yōu)化，得到的優(yōu)化路徑如圖2所示。但若對兩條不可達路徑進行綜合優(yōu)化，可得如圖3所示路徑。綜合優(yōu)化考慮到了對重復(fù)指引信息的利用，兩條路徑在v33處合流后，路徑可共用同一指引信息，如：v34、v26處共用已有指引信息，v24處共用新設(shè)指引信息，需增設(shè)指引信息要少于單獨優(yōu)化路徑，因此綜合考慮此路徑可能優(yōu)于單獨優(yōu)化路徑。

為了使系統(tǒng)的整體可達性達到最優(yōu)，需將多個單條擴展路徑看成一個整體進行綜合優(yōu)化。

1.4 指引路徑的綜合優(yōu)化模型

假定路網(wǎng)結(jié)構(gòu)G已知，對給定的被標(biāo)識對象D，其指引信息集合RS={rs}，設(shè)D共有n條不可達路徑x1,x2,,xn。則對于每條不可達路徑xi，從其端點Oi開始擴展，直至到達D，該延伸指引路徑分段記為ei，記e={e1,e2,,en}為D的一條延伸指引路徑。如圖2所示，e={e1,e2}即為D的一條延伸指引路徑。其中，e1為起點O1到終點D的路徑，e2為起點O2到終點D的路徑。E={e}為D的所有可能延伸指引路徑的集合。指路標(biāo)志的綜合優(yōu)化模型需綜合考慮指引路徑長度和增設(shè)指路標(biāo)志數(shù)量兩個要素。但二者的數(shù)量單位不統(tǒng)一，因此需要進行歸一化處理。在已知指引路徑的長度、已設(shè)置指路標(biāo)志數(shù)量的前提下，本文利用最大距離d和最大數(shù)量N，實現(xiàn)了對指引路徑長度和指路標(biāo)志設(shè)置數(shù)量的歸一化處理。

綜上所述，指引路徑的綜合優(yōu)化模型如公式(1)所示。目標(biāo)函數(shù)通過對指引路徑長度和增設(shè)指路標(biāo)志數(shù)量的歸一化處理，使得模型可通過目標(biāo)函數(shù)值實現(xiàn)對整體優(yōu)化方案的優(yōu)劣評價，且目標(biāo)函數(shù)f值越小，指引路徑越優(yōu)。

s.t.RS (ei)∩RS (ej) = ?,?ei,ej∈e

RS (ei)∩RS= ?,?ei∈e

(1)

其中， leni為延伸指引路徑分段ei的長度， numi為ei中需增設(shè)的指引信息個數(shù)，RS (ei)為ei中需增設(shè)的指引信息集合，α1表示路徑長度對決策的重要程度占比，α2表示增設(shè)指引信息對決策的重要程度占比。

2 指引路徑優(yōu)化問題的人工蜂群算法

求解指引路徑優(yōu)化問題的關(guān)鍵在于綜合考慮延伸指引路徑的路徑長度及增設(shè)指引信息數(shù)量，使得延伸指引路徑的總評價指數(shù)最優(yōu)。結(jié)合人工蜂群算法的基本特點，本文設(shè)計了一種人工蜂群算法用于求解該優(yōu)化問題。

2.1 延伸指引路徑表達方式

本文將單條延伸指引路徑e定義為單個蜜源，并記錄為e={ei|i=1,2,···,n}，其中n為延伸指引路徑中分段數(shù)。假設(shè)延伸指引路徑分段ei從Oi點出發(fā)，依次經(jīng)過vp(i)、、vq(i)等點，到達D點，則記錄e為

其中，tj表示該路徑經(jīng)過節(jié)點vj處是否需要增設(shè)指引信息。若需要，則tj=1；反之，則tj=0。

根據(jù)前人的研究[15]，在缺少指引信息的路口，絕大多數(shù)駕駛員會選擇直行。為簡化算法表達，本文僅在延伸指引路徑轉(zhuǎn)彎處增設(shè)指引信息。

如圖4所示路網(wǎng)，存在兩條不可達路徑，端點分別為O1、O2，目的地為D，且在v26處已有指向D的左轉(zhuǎn)指引信息。則圖4中黑線為一條延伸指引路徑e={e1,e2}，并在轉(zhuǎn)彎處增設(shè)指引信息，該路徑e的編碼為

其中，e2經(jīng)過點v25時，此處已有e1增設(shè)指引信息，不需重復(fù)增設(shè)，因此e2中t25=0。

圖4 延伸指引路徑示意圖Fig.4 The extended guidance path

2.2 適應(yīng)度函數(shù)

根據(jù)1.4中對目標(biāo)函數(shù)的分析，延伸指引路徑e的優(yōu)劣程度由適應(yīng)度F判斷。路徑適應(yīng)度F由式(2)求得，適應(yīng)度函數(shù)值越小，指引路徑越優(yōu)。

(2)

2.3 算法整體流程

人工蜂群算法的整體流程如圖5所示。

圖5 算法流程圖Fig.5 Procedure of algorithm

其對延伸指引路徑的更新分為引領(lǐng)蜂、觀察蜂及偵察蜂三個階段進行，計算步驟如下：

(1)初始迭代次數(shù)cycle= 1，并初始化蜜源種群R={ek|ek∈E,k= 1,2,···,SN }，其中SN為蜜源種群規(guī)模。

(2)引領(lǐng)蜂k對延伸指引路徑ek采用鄰域搜索策略進行更新，k=1,2,,SN。

(3)觀察蜂k依據(jù)概率隨機選擇一條路徑，并采用鄰域搜索策略對所選路徑ei進行更新，選中路徑ei的概率Pi由式(3)求得：

(3)

其中，F(xiàn)i為路徑ei的適應(yīng)度，k=1,2,,SN,i∈{1,2,,SN}。

(4)令單條路徑最大連續(xù)搜索數(shù)為limit，對ek連續(xù)搜索次數(shù)進行判斷，若連續(xù)搜索次數(shù)超過limit路徑ek仍未發(fā)生變化，則視為陷入局部最優(yōu)，舍棄該條路徑，由偵察蜂重新生成新的ek，k=1,2,,SN。

(5)將當(dāng)代所有指引路徑ek與歷史最優(yōu)指引路徑eopt的適應(yīng)度進行比較，更新最優(yōu)指引路徑eopt。

(6)令算法的最大優(yōu)化代數(shù)為MEN，若cycle=MEN，算法終止，最優(yōu)路徑為eopt；反之，cycle=cycle+1，返回步驟(2)，繼續(xù)優(yōu)化。

2.4 延伸指引路徑更新策略

由2.3中的整體流程可知，算法更新路徑主要采用鄰域搜索策略，但實際路網(wǎng)結(jié)構(gòu)復(fù)雜，路徑之間的鄰近關(guān)系不規(guī)則，無法直接采用函數(shù)優(yōu)化中構(gòu)造鄰域的方法，因此本文設(shè)計了一種適應(yīng)于路網(wǎng)結(jié)構(gòu)的鄰域搜索策略，以實現(xiàn)指引路徑的更新，其更新操作如下所示：

(1)計算路徑e={ei}的適應(yīng)度F，并將其分解為n條分路徑ei，移除所有增設(shè)指引信息。

(2)為分路徑ei搜索鄰域分路徑，令i=1。

(3)隨機選取路徑ei上兩點作為鄰域段的起點和終點。

(4)刪除鄰域段內(nèi)節(jié)點，重新選取該段路徑，用新生成路段補全鄰域段。

(5)按規(guī)則添加指引信息，并對路徑重新編碼，生成ei的鄰域分路徑ei′。

(6)若i=n，轉(zhuǎn)步驟(7)；反之，i=i+1，轉(zhuǎn)步驟 (3)。

(7)將鄰域路徑ei′整合為e的鄰域路徑e′={ei′}，計算其適應(yīng)度F′，并與F比較，保留更優(yōu)路徑。

以圖4所示延伸指引路徑e={e1,e2}為例，e1選取v63為鄰域起點、v35為鄰域終點，重新選取新路段組成鄰域分路徑e1′，并增設(shè)指引信息，如圖6(a)所示；e2選取v32為鄰域起點、v35為鄰域終點，重新選取新路段組成鄰域分路徑e2′，并增設(shè)指引信息，如圖6(b)所示；將兩條鄰域分路段進行整合，組成鄰域路徑e′，如圖6(c)所示。由于F′

圖6 指引路徑鄰域搜索過程圖Fig.6 Guide path neighborhood search process graph

3 實例應(yīng)用

選擇廣州大學(xué)城路網(wǎng)作為試驗路網(wǎng)，路網(wǎng)總共包括333個節(jié)點，812條路段。利用已有可達性分析模型[3]分析，A、B、C三處都是中山大學(xué)的指引不可達路徑端點，其中A為華南快速路出口，C為交叉口，B為道路入口，已有指引信息如圖7所示。因此，選擇點A、B、C作為延伸指引路徑的起點，點D中山大學(xué)作為終點，對指引路徑進行綜合優(yōu)化。本實驗認(rèn)為路徑長度、增設(shè)標(biāo)志數(shù)對選擇的貢獻值相同，因此取α1=50%，α2=50%。同時根據(jù)多次試驗確定了模型的參數(shù)為SN=100，MEN=200，limit=200，并借助 ArcGis 10.0 平臺進行了實驗仿真，程序采用C#編程語言實現(xiàn)。

對圖7運用指引路徑優(yōu)化模型，可得到如圖8所示結(jié)果。其中路徑總長度為11 510.99 m，總共需要增設(shè)的指引信息數(shù)為6個，計算得到的適應(yīng)度值為1.196 409。

在相同條件下，運用單條路徑優(yōu)化模型分別對各個起點尋找最優(yōu)路徑，其各條路徑尋優(yōu)結(jié)果如圖9所示，路徑信息如表1所示。將其直接疊加，可得到如圖9(d)所示結(jié)果。其中，路徑總長度為11 499.99 m，各條路徑的指引信息數(shù)之和為8個，其中有兩個為相同指引信息，舍棄重復(fù)信息，因此需要設(shè)置的指引信息數(shù)為7個，計算得到的其適應(yīng)度值為1.273 985。

圖7 廣州大學(xué)城路網(wǎng)Fig.7 Guangzhou University city road network

圖8 算法優(yōu)化結(jié)果Fig.8 Algorithm optimization results

最優(yōu)路徑指引路徑的距離/m需設(shè)指引信息數(shù)/個適應(yīng)度FA→D優(yōu)化4 675.87830.435 070 4B→D優(yōu)化2 712.35330.582 804 6C→D優(yōu)化4 111.75520.390 283 4

指引路徑綜合優(yōu)化模型、單條路徑優(yōu)化模型的計算結(jié)果如表2所示。通過對比可發(fā)現(xiàn)，綜合優(yōu)化模型得出的路徑適應(yīng)度更低，結(jié)果更優(yōu)。由此可見，綜合優(yōu)化模型在整體性考慮方面更優(yōu)，更符合實際需求。圖10為算法的收斂曲線。可以看出，迭代至140次左右時適應(yīng)度已收斂至全局最小值。

表2 結(jié)果數(shù)據(jù)對比Table 2 Results by different methods

圖9 單條路徑優(yōu)化結(jié)果示意圖Fig.9 Single path optimization results

圖10 算法收斂曲線Fig.10 Algorithm convergence curve

4 總 結(jié)

本文探討了人工蜂群算法在指引路徑綜合優(yōu)化中的應(yīng)用，提出了一種適應(yīng)路網(wǎng)結(jié)構(gòu)的鄰域搜索策略，并綜合考慮路徑的長度、設(shè)置指引信息數(shù)兩項指標(biāo)，初步構(gòu)建了相應(yīng)的優(yōu)化模型，并將其運用于實際路網(wǎng)。實驗證明：指引路徑綜合優(yōu)化模型具有可行性和良好的適用性，且相較于單條路徑優(yōu)化模型，更符合實際需求。但，目前模型只考慮了單個指引對象，當(dāng)存在多個指引對象時，指引路徑間會相互影響，還會出現(xiàn)過載現(xiàn)象，且模型在優(yōu)化過程中考慮的影響因素等方面仍有深入研究的價值，后續(xù)研究中將會進一步擴大優(yōu)化考慮范圍，提高模型的實際應(yīng)用性。