李 敏,黃 敏,程智鋒,周 靜

1(招商局重慶交通科研設(shè)計(jì)院有限公司,重慶 400067)

2(中山大學(xué) 智能工程學(xué)院,廣州 510006)

3(廣東工貿(mào)職業(yè)技術(shù)學(xué)院,廣州 510510)

隨著城市化建設(shè)的不斷發(fā)展,路網(wǎng)日趨復(fù)雜,出行者的路徑選擇更趨于多樣化,為此,出行者如何選擇最優(yōu)路徑并高效快捷地到達(dá)目的地成為其關(guān)心的問(wèn)題[1].目前尋找最優(yōu)路徑的算法主要采用啟發(fā)式算法和最佳式算法,啟發(fā)式算法能夠在一定的時(shí)間內(nèi)找出近似最優(yōu)解,常見的啟發(fā)式算法有遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法等.最佳式算法能夠找出最優(yōu)解,但一般時(shí)間復(fù)雜度較高,具有代表性的算法有Dijkstra、BFS 算法等[2].

對(duì)比其他路徑尋優(yōu)算法,遺傳算法是一種全局優(yōu)化算法,能夠有效地進(jìn)行概率意義的全局搜素,具有較強(qiáng)的魯棒性,應(yīng)用較為廣泛,適合于求解復(fù)雜的優(yōu)化問(wèn)題[2].為此,本文旨在運(yùn)用遺傳算法,為出行者找到一條綜合權(quán)值最優(yōu)的路徑.針對(duì)出行者路徑選擇的多樣性,結(jié)合前人研究[2,3],影響出行者路徑選擇因素諸多,主要表現(xiàn)在行程時(shí)間、行程路程、交叉口的個(gè)數(shù)、沿途風(fēng)景等[3,4].本文初步選用以行駛路程和交叉口的個(gè)數(shù)作為綜合指標(biāo),定義綜合指標(biāo)最小的路徑作為最優(yōu)路徑,并以廣州大學(xué)城中山大學(xué)為例,采用遺傳算法的方法,找到從廣州大學(xué)城入口到中山大學(xué)的最優(yōu)路徑,從而驗(yàn)證遺傳算法在路徑規(guī)劃應(yīng)用上的有效性.

1 交通路網(wǎng)模型

城市道路路網(wǎng)是由若干路段(弧段)和交叉口(結(jié)點(diǎn))組成的網(wǎng)狀結(jié)構(gòu),描述了道路和交叉口之間的關(guān)系.在基于拓?fù)渎肪W(wǎng)的情況下,交通路網(wǎng)數(shù)據(jù)可包含道路幾何中心線、路網(wǎng)弧段、路網(wǎng)結(jié)點(diǎn)3 個(gè)部分[5,6].其中三者之間的關(guān)系如圖1所示.本文采用弧段-結(jié)點(diǎn)模型來(lái)描述路網(wǎng),定義以下路網(wǎng)模型,G=(V,E)表示路網(wǎng);其中V={vi|i=1,2,···,n}是G的結(jié)點(diǎn)集,表示路段的端點(diǎn),如道路交叉口或斷頭路口等,E={ei=(vk,vl)|i=1,···,m;vk,vl∈V}是G的弧段集.ei為從vk到vl的有向弧,vk為起點(diǎn)vl為終點(diǎn).為了更好地描述道路交叉路口處的交通限制以及轉(zhuǎn)向信息,在路網(wǎng)模型中引入結(jié)點(diǎn)-弧段夾角及結(jié)點(diǎn)的邏輯連通關(guān)系[2].

圖1 道路路網(wǎng)數(shù)據(jù)地圖

2 遺傳算法基本概念及算法模型

2.1 遺傳算法基本概念

遺傳算法是一種借鑒達(dá)爾文提出的生物進(jìn)化論的思想,利用計(jì)算機(jī)科學(xué)與自然遺傳學(xué)相互結(jié)合去解決一些復(fù)雜的優(yōu)化問(wèn)題[7,8].在遺傳算法中存在一些遺傳學(xué)與進(jìn)化的概念,如染色體、種群、適應(yīng)度等概念,為此闡述其各自的定義.染色體:英文全稱為chromosome,染色體又可以稱作為個(gè)體,一條染色體代表著一個(gè)可行解.種群:英文全稱為population,表示每代染色體的總數(shù),一個(gè)種群表示解決該問(wèn)題的部分解的集合.基因:英文全稱為gene,基因是染色體的組成元素,用來(lái)表達(dá)個(gè)體的基本特性.適應(yīng)度:英文全稱為fitness,適應(yīng)度表示衡量對(duì)環(huán)境的適應(yīng)程度,每條染色體都有對(duì)應(yīng)一個(gè)適應(yīng)度值.

遺傳算法的過(guò)程主要分成以下幾個(gè)過(guò)程即種群的初始化、適應(yīng)度值計(jì)算、選擇、交叉、變異、產(chǎn)生新種群.接下來(lái)分別介紹種群中染色體在指路標(biāo)志誘導(dǎo)系統(tǒng)中的編碼、適應(yīng)度函數(shù)的設(shè)計(jì)、選擇、交叉、變異等操作.

2.2 種群的初始化

在種群初始化之前,需要進(jìn)行染色體編碼,本文遺傳算法采用的編碼方式不同于傳統(tǒng)的遺傳算法中的0-1 編碼,本文中遺傳算法的染色體是由一系列路網(wǎng)的結(jié)點(diǎn)組成,形成一條完整的路徑,為此將這種編碼方式稱為路徑編碼方法.這種方法規(guī)定每條染色體中的基因不允許有重復(fù)編碼的基因,但對(duì)于染色體的長(zhǎng)度并沒(méi)有強(qiáng)行規(guī)定即染色體的長(zhǎng)度是變化的,但其長(zhǎng)度需要滿足小于路網(wǎng)的結(jié)點(diǎn)總數(shù).染色體編碼即為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的隊(duì)列組成,以圖2的路網(wǎng)為例.

圖2 路由路徑與其編碼表示

圖2中一條從節(jié)點(diǎn)S 到節(jié)點(diǎn)D的一個(gè)染色體,其編碼可為:S-4-9-10-11-16-D,其中染色體編碼的第一位置基因(節(jié)點(diǎn))是源節(jié)點(diǎn),第二位置基因是從與源節(jié)點(diǎn)連接的其他節(jié)點(diǎn)中隨機(jī)選擇或啟發(fā)式選擇.選擇的節(jié)點(diǎn)從結(jié)構(gòu)信息庫(kù)中刪除,避免重復(fù),再重復(fù)過(guò)程直到目的地節(jié)點(diǎn)D.種群可以根據(jù)路網(wǎng)的大小來(lái)設(shè)定初始的染色體數(shù)量.

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

本文主要考慮行駛路程和交叉口的個(gè)數(shù)作為綜合指標(biāo),以綜合指標(biāo)最小的路徑作為最優(yōu)路徑.由于兩大指標(biāo)存在量綱差異,為此需要對(duì)其進(jìn)行歸一化處理,本文借鑒前人研究成果,將兩大指標(biāo)轉(zhuǎn)換成時(shí)間消耗成本[7,8].出行者從始發(fā)地到目的地的時(shí)間總消耗由路段時(shí)間消耗與節(jié)點(diǎn)時(shí)間消耗組成,其中路段時(shí)間消耗取決于路程的長(zhǎng)度、行駛的速度等因素,本文假定車輛在道路上勻速行駛,為此單位長(zhǎng)度下的時(shí)間消耗是固定的,從而路段總消耗時(shí)間可用路徑總長(zhǎng)度乘以單位長(zhǎng)度下的時(shí)間消耗得到[8].節(jié)點(diǎn)時(shí)間消耗取決于交叉口的類型、轉(zhuǎn)向方向等因素[8],為此節(jié)點(diǎn)總消耗時(shí)間即通過(guò)每個(gè)交叉口時(shí)間消耗的累加.根據(jù)交叉口信號(hào)配時(shí)經(jīng)驗(yàn),綠燈配置時(shí)間從長(zhǎng)到短依次為直行方向、右轉(zhuǎn)方向、左轉(zhuǎn)及掉頭方向,然而在時(shí)間消耗上則成反向,假定左轉(zhuǎn)及掉頭方向的時(shí)間消耗是直行方向的2 倍,右轉(zhuǎn)方向的時(shí)間消耗是直行方向的1.5 倍[8,9].基于上述分析,適應(yīng)度函數(shù)可以表達(dá)如式(1)所示.

其中,F—適應(yīng)度函數(shù)值;

a、b—權(quán)重系數(shù),本文認(rèn)為兩個(gè)指標(biāo)影響程度一致,為此將二者權(quán)重比設(shè)為1:1;

L—行駛路徑總長(zhǎng)度(km);

C1—單位路段長(zhǎng)度所需消耗的時(shí)間;

T1—交叉口所有直行方向的次數(shù);

T2—交叉口所有右轉(zhuǎn)方向的次數(shù);

T3—交叉口所有左轉(zhuǎn)及掉頭方向的次數(shù);

C2—單個(gè)節(jié)點(diǎn)上直行方向上所需消耗的時(shí)間.

根據(jù)式(1)可知,適應(yīng)度F值越小,則時(shí)間消耗越少,即路徑選擇越優(yōu).

2.4 選擇-復(fù)制

選擇操作是用來(lái)確定交叉?zhèn)€體,以及產(chǎn)生多少個(gè)子代個(gè)體.在選擇過(guò)程時(shí)應(yīng)保持種群的整體數(shù)量不變.計(jì)算種群中各個(gè)染色體的適應(yīng)值,并按照適應(yīng)度由小到大排序?qū)⑷旧w中適應(yīng)度最小的個(gè)體直接保留到下一代,然而個(gè)體適應(yīng)度值越小,則被選擇的概率就越高,相同染色體只保留一條染色體.

2.5 交叉

通過(guò)選擇得到的兩個(gè)個(gè)體,將其部分結(jié)構(gòu)相互交換,生成新個(gè)體.不同于傳統(tǒng)的單點(diǎn)交叉,兩個(gè)染色體選擇一個(gè)公共的基因(節(jié)點(diǎn))作為交叉點(diǎn);一般選擇第一個(gè)公共節(jié)點(diǎn),若交叉后代與父代染色體一樣則改選其他公共節(jié)點(diǎn).以圖3為例.父代染色體:Chromosome1:S-4-9-10-11-16-D與Chromosome2:S-4-5-10-15-16-D;其兩條染色體的公共基因結(jié)點(diǎn)為4、10、16;因此按照公共基因的選擇規(guī)則,首先選擇結(jié)點(diǎn)4,發(fā)現(xiàn)并無(wú)新的染色產(chǎn)生,則選擇另一個(gè)公共結(jié)點(diǎn)10,通過(guò)交叉后得到新的兩條子代染色體Chromosome1*:S-4-9-10-15-16-D與Chromosome2*:S-4-5-10-11-16-D;其中交叉后染色體如圖4所示.

圖3 交叉前的染色體路徑

圖4 交叉后新的染色體路徑

2.6 校正

交叉后產(chǎn)生的新個(gè)體中不能產(chǎn)生環(huán)路,即滿足同一節(jié)點(diǎn)只能選擇一次原則,為此需要對(duì)染色體進(jìn)行校正操作.以圖5為例,父代染色體為Chromosome1:S-4-5-10-11-16-D與Chromosome2:S-4-9-14-15-10-5-6-11-16-D;其中假設(shè)選擇公共結(jié)點(diǎn)10 作為交叉點(diǎn),則交叉后的子代染色體為:Chromosome1*:S-4-5-10-5-6-11- 16-D與Chromosome2*:S-4-9-14-15-10-11-16-D;很明顯子代染色體1 需要校正,經(jīng)過(guò)校正處理后,得到校正后的染色體為Chromosome1**:S-4-5-6-11-16-D.

圖5 校正前后的染色體路徑

2.7 變異

變異以很小的隨即概率改變?nèi)旧w上的某些基因,找回較好的基因,與種群大小無(wú)關(guān).同時(shí)變異操作是一種局部隨機(jī)搜索,選取適應(yīng)度最差的或者滿足突變概率的染色體.假設(shè)需突變?nèi)旧wChromosome1:S-4-5-10-9-14-15-16-D,如圖6所示.從染色體中隨機(jī)選擇一個(gè)基因作為突變基因(假設(shè)10),則從源節(jié)點(diǎn)到變異點(diǎn)的基因保持不變,變異點(diǎn)之后的基因則從連接的基因隨機(jī)選擇,直到目的節(jié)點(diǎn).突變后染色體Chromosome1*:S-4-5-10-11-16-D,如圖7所示.

2.8 算法流程

章節(jié)2.2～2.7 分別闡述了在交通拓?fù)渎肪W(wǎng)下,利用遺傳算法尋找最優(yōu)路徑的具體運(yùn)算步驟.算法的主要思路為:根據(jù)給定的起點(diǎn)生成相應(yīng)的初始種群,接著計(jì)算各種群中染色體的適應(yīng)度值,并將最優(yōu)染色體直接保存于下一代,再在種群中進(jìn)行選擇、交叉-校正、變異操作產(chǎn)生新的種群,重復(fù)上述過(guò)程直至到達(dá)指定的進(jìn)化代數(shù)后停止進(jìn)化.其中算法流程如圖8所示.算法中用到的符號(hào)如下:

OptV:起點(diǎn)集合,針對(duì)多入口路網(wǎng);

Gen:迭代的次數(shù);

K:起點(diǎn)的個(gè)數(shù);

F:各種群中染色體的適應(yīng)度值;

L:行駛路徑的長(zhǎng)度;

T:交叉口的個(gè)數(shù);

Fcpti:第i次進(jìn)化時(shí)的最優(yōu)的適應(yīng)度值.

圖6 變異前的染色體路徑

圖7 變異后的染色體路徑

圖8 算法流程圖

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

本研究基于C#與ArcGIS的開發(fā)下,采取廣州大學(xué)城作為實(shí)例,將上述算法應(yīng)用于該路網(wǎng)中,路網(wǎng)的入口O1、O2、O3、O4、O5如圖9所示,目的地(D)為中山大學(xué),路網(wǎng)中各個(gè)路段的權(quán)值如圖10所示.

圖9 廣州大學(xué)城出入口示意圖

對(duì)于適應(yīng)度函數(shù)參數(shù)的設(shè)定,參照《城市道路路線設(shè)計(jì)規(guī)范》CJJ193-2012和《城市道路交叉口設(shè)計(jì)規(guī)程》CJJ152-2010,并結(jié)合廣州大學(xué)城車輛運(yùn)行的實(shí)際情況,本文采用50 km/h的速度作為車輛的平均行駛速度,從而單位長(zhǎng)度上的時(shí)間消耗為1.2 min.根據(jù)前人研究成果[7,9–11],直行方向消耗的時(shí)間為0.5 min,從而適應(yīng)度函數(shù)可以表示為F=1.2L+0.5(T1+1.5T2+2T3).對(duì)于算法中的參數(shù):根據(jù)相關(guān)資料[7–9]及多次試驗(yàn),設(shè)定種 群中染色體數(shù)為40、最大進(jìn)化代數(shù)為40、交叉概率為0.9、變異概率為0.1.最終總的最優(yōu)路線如圖11所示,其中各入口到中山大學(xué)的最優(yōu)適應(yīng)度值及相關(guān)指標(biāo)如表1所示.

圖10 廣州大學(xué)城道路距離權(quán)值圖

圖11 總的最優(yōu)路徑規(guī)劃圖

表1 各入口到中山大學(xué)最優(yōu)路徑下的相關(guān)指標(biāo)及適應(yīng)度值

4 結(jié)語(yǔ)

本文采用遺傳算法對(duì)路徑尋優(yōu)問(wèn)題進(jìn)行了探討,在明確起終點(diǎn)條件下,以行駛路程和交叉口個(gè)數(shù)作為綜合指標(biāo),找到了一定路網(wǎng)范圍內(nèi)的最優(yōu)路徑,驗(yàn)證了遺傳算法在路徑規(guī)劃上的有效性.但本文只考慮了行駛路程和交叉口個(gè)數(shù)作為出行者的考慮因素,在后續(xù)的研究中將對(duì)出行者的路徑選擇進(jìn)行綜合分析,從綜合影響因素出發(fā),系統(tǒng)地對(duì)路徑規(guī)劃進(jìn)行研究,進(jìn)一步提高算法的科學(xué)性與合理性.