基于人工蜂群算法的交叉口指路標(biāo)志設(shè)置優(yōu)化方法*

張騰，黃敏，劉芳，鄭健

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

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

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

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

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

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

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

1.2 指引路徑與指引可達(dá)

指引路徑是駕駛員根據(jù)指路標(biāo)志系統(tǒng)的指引和駕駛員自身駕駛經(jīng)驗(yàn)的指導(dǎo)，選擇出的一條從起點(diǎn)前往指定終點(diǎn)的期望路徑。在駕駛過(guò)程中，駕駛員會(huì)根據(jù)指路標(biāo)志給出的指引信息進(jìn)行路徑選擇。當(dāng)?shù)缆方徊婵谌鄙賹?duì)目的地指引的指路標(biāo)志時(shí)，駕駛員會(huì)根據(jù)自己的駕駛經(jīng)驗(yàn)做出選擇。

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

2.1 延伸指引路徑表達(dá)方式

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

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

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

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

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

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

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

根據(jù)1.4中對(duì)目標(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

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

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

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

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

(3)

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

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

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

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

2.4 延伸指引路徑更新策略

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

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

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

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

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

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

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

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

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

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

3 實(shí)例應(yīng)用

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

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

在相同條件下，運(yùn)用單條路徑優(yōu)化模型分別對(duì)各個(gè)起點(diǎn)尋找最優(yōu)路徑，其各條路徑尋優(yōu)結(jié)果如圖9所示，路徑信息如表1所示。將其直接疊加，可得到如圖9(d)所示結(jié)果。其中，路徑總長(zhǎng)度為11 499.99 m，各條路徑的指引信息數(shù)之和為8個(gè)，其中有兩個(gè)為相同指引信息，舍棄重復(fù)信息，因此需要設(shè)置的指引信息數(shù)為7個(gè)，計(jì)算得到的其適應(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ù)/個(gè)適應(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)化模型的計(jì)算結(jié)果如表2所示。通過(guò)對(duì)比可發(fā)現(xiàn)，綜合優(yōu)化模型得出的路徑適應(yīng)度更低，結(jié)果更優(yōu)。由此可見(jiàn)，綜合優(yōu)化模型在整體性考慮方面更優(yōu)，更符合實(shí)際需求。圖10為算法的收斂曲線?？梢钥闯觯?40次左右時(shí)適應(yīng)度已收斂至全局最小值。

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