董小帥 ，毛政元

1.福州大學(xué) 福建省空間信息工程研究中心，福州 350002

2.福州大學(xué) 空間數(shù)據(jù)挖掘與信息共享教育部重點(diǎn)實(shí)驗(yàn)室，福州 350002

3.福州大學(xué) 地理空間信息技術(shù)國(guó)家地方聯(lián)合工程研究中心，福州 350002

1 引言

按照對(duì)時(shí)變性因素的不同處理，路徑規(guī)劃模型分為靜態(tài)和動(dòng)態(tài)兩種類型[1]，前者指在靜態(tài)路網(wǎng)模型上迭加各路段權(quán)重，再采用規(guī)劃與優(yōu)化算法求解最佳路徑，同一問(wèn)題只需求解一次；后者指綜合考慮路網(wǎng)中各路段的通行能力和路網(wǎng)不斷變化的路況信息采用優(yōu)化算法求解最優(yōu)路徑[2-3]。動(dòng)態(tài)路徑規(guī)劃相比靜態(tài)路徑規(guī)劃更具實(shí)用價(jià)值[4]，同時(shí)，由于其采用的動(dòng)態(tài)路網(wǎng)模型加入了實(shí)時(shí)、復(fù)雜、多變的路網(wǎng)信息，經(jīng)典規(guī)劃算法難以高效、魯棒地完成路徑規(guī)劃與優(yōu)化，目前相關(guān)研究中一般采用仿生智能算法實(shí)現(xiàn)動(dòng)態(tài)路徑規(guī)劃[5-9]。

遺傳算法是一種采用種群搜索機(jī)制的全局性尋優(yōu)算法，該搜索策略使求得最優(yōu)解的可能性和效率大大提高[10]，該算法因此被廣泛應(yīng)用于包括路徑規(guī)劃在內(nèi)的眾多問(wèn)題的求解研究。但是傳統(tǒng)的遺傳算法存在“早熟收斂”、種群多樣性逐漸降低和局部搜索能力差等缺陷[11-14]。對(duì)此，相關(guān)研究文獻(xiàn)中提出了一系列的改進(jìn)，比如，采用啟發(fā)式算法生成初始種群[15-17]，提出以相同節(jié)點(diǎn)作為交叉點(diǎn)的交叉策略和變異策略等[18-19]，提高收斂速度，避免“早熟收斂”；采用多種群協(xié)同進(jìn)化策略[20]，優(yōu)良基因以一定概率在不同種群間橫向傳遞，降低“早熟收斂”的可能性；自適應(yīng)交叉概率和變異概率的提出，動(dòng)態(tài)調(diào)整交叉，變異操作[21]，使得隨著迭代次數(shù)增加，種群多樣性不會(huì)大幅降低；引入模擬退火思想[22]以一定的概率接受比當(dāng)前解更差的新解，混合禁忌搜索算法[23]、爬山算法[24]、融入復(fù)合型操作[25]等提高局部搜索能力。這些改進(jìn)能夠在一定程度上克服傳統(tǒng)遺傳算法的缺陷，但在處理大規(guī)模實(shí)時(shí)交通數(shù)據(jù)時(shí)，求解精度與效率仍不能滿足實(shí)時(shí)路徑規(guī)劃的需求。

本文針對(duì)傳統(tǒng)遺傳算法應(yīng)用于動(dòng)態(tài)路徑規(guī)劃求解的局限性提出以下三方面的改進(jìn)：（1）結(jié)合隨機(jī)選擇和趨于終點(diǎn)方向提出一種控制全局搜索方向的種群初始化策略，在保持初始種群多樣性的同時(shí)提高初始種群個(gè)體質(zhì)量，加快收斂。（2）提出一種根據(jù)空間距離的鄰近大小選擇交叉位置點(diǎn)的交叉策略，有效保留父代優(yōu)良基因，同時(shí)避免“早熟收斂”。（3）提出一種基于節(jié)點(diǎn)適應(yīng)度的局部搜索策略，通過(guò)建立節(jié)點(diǎn)選擇概率與節(jié)點(diǎn)適應(yīng)度的正相關(guān)關(guān)系，有效提高局部搜索能力，加快收斂。設(shè)計(jì)與實(shí)現(xiàn)了改進(jìn)的遺傳算法，并以福州市部分路網(wǎng)數(shù)據(jù)為樣本，驗(yàn)證改進(jìn)后的遺傳算法在求解精度、效率與穩(wěn)定性三方面的進(jìn)步。

2 動(dòng)態(tài)交通網(wǎng)絡(luò)規(guī)劃模型

2.1 動(dòng)態(tài)路網(wǎng)模型

在城市交通網(wǎng)絡(luò)中，同一路段的交通狀況一般會(huì)隨時(shí)間而改變，動(dòng)態(tài)路網(wǎng)模型不僅是對(duì)現(xiàn)實(shí)世界中路網(wǎng)的簡(jiǎn)單抽象表達(dá)，同時(shí)還包含路況的實(shí)時(shí)變化信息[26-28]。比如，某些路段在上下班高峰時(shí)段更擁擠，采用傳統(tǒng)的靜態(tài)路阻函數(shù)進(jìn)行時(shí)間最短的路徑規(guī)劃時(shí)，不能有效規(guī)避擁堵路段，時(shí)間成本較高。動(dòng)態(tài)路網(wǎng)模型是靜態(tài)路網(wǎng)模型添加各路段時(shí)態(tài)信息后的擴(kuò)展，其數(shù)學(xué)表達(dá)式如下：

式中，G表示有向帶權(quán)的動(dòng)態(tài)城市交通路網(wǎng)；V表示路網(wǎng)中節(jié)點(diǎn)集合，V={vi|i=1,2,…,n}；E表示路網(wǎng)中各個(gè)節(jié)點(diǎn)連通的有向路段集合，vj∈V}，vi、vj分別是路段e的起點(diǎn)、終點(diǎn)；T表示時(shí)間閉區(qū)間[t0,tm]，t0是起點(diǎn)時(shí)刻，tm是到達(dá)終點(diǎn)時(shí)刻，在實(shí)際交通網(wǎng)絡(luò)中，Δt為間隔時(shí)長(zhǎng)，其值越小越能實(shí)時(shí)反應(yīng)路況信息的變化，一般取5 min，并忽略在該間隔時(shí)長(zhǎng)內(nèi)的路況變化；表示節(jié)點(diǎn)v在時(shí)刻t的時(shí)延集合；W(e,t)表示路段e在時(shí)刻t的路阻系數(shù)集合。

圖1為路網(wǎng)示意圖，其中節(jié)點(diǎn)包括轉(zhuǎn)向延誤節(jié)點(diǎn)和分流節(jié)點(diǎn)兩種類型，后者不產(chǎn)生轉(zhuǎn)向延誤（如V2）；路段具有方向性，在同一時(shí)間間隔內(nèi)，同一路段可能由于方向不同而具有不同的路阻系數(shù)。

圖1 交通路網(wǎng)示意圖

2.2 路徑規(guī)劃模型

如圖1所示，設(shè)vO、vD分別是始節(jié)點(diǎn)、終節(jié)點(diǎn)，ROD是vO到vD所有合格路徑的集合，r=(vO,v2,v4,v5,vD)是其中一條路徑，r∈ROD，時(shí)間最優(yōu)路徑規(guī)劃是指根據(jù)時(shí)刻t所在時(shí)間段的路況信息，分別計(jì)算ROD中每個(gè)路徑的行程時(shí)間Z(r)，從中選擇一條時(shí)間最短的路徑作為該時(shí)間段內(nèi)的最優(yōu)路徑，目標(biāo)函數(shù)如下：

3 改進(jìn)遺傳算法理論

3.1 編碼和初始化

遺傳算法包括三種常用的編碼實(shí)現(xiàn)方式，即二進(jìn)制編碼、符號(hào)編碼與實(shí)數(shù)編碼。在動(dòng)態(tài)路徑規(guī)劃問(wèn)題中，一條路徑相當(dāng)于一個(gè)染色體，路網(wǎng)節(jié)點(diǎn)相當(dāng)于染色體中的基因，由于這些節(jié)點(diǎn)的排列順序正好就是所要求的路徑，所以采用實(shí)數(shù)編碼方式更能直接表達(dá)路徑的實(shí)際意義，同時(shí)也有利于適應(yīng)值函數(shù)的選取和適應(yīng)值的計(jì)算。由于城市交通路網(wǎng)中的節(jié)點(diǎn)數(shù)較大，滿足相同起點(diǎn)和終點(diǎn)之間的不同連通路徑一般具有不同的節(jié)點(diǎn)數(shù)，因此采用變長(zhǎng)度染色體編碼策略比定長(zhǎng)度策略更適合求解動(dòng)態(tài)路徑規(guī)劃這一問(wèn)題。

遺傳算法與其他搜索算法最大的區(qū)別之一就是其面向種群進(jìn)行搜索的并行性，初始種群的設(shè)定對(duì)整個(gè)遺傳算法的運(yùn)行性能具有決定作用。傳統(tǒng)的遺傳算法采用隨機(jī)的方式生成初始種群，這樣雖能提高種群的多樣性，但整個(gè)搜索過(guò)程缺乏方向性的引導(dǎo)，同時(shí)會(huì)出現(xiàn)斷路或環(huán)路現(xiàn)象，使得遺傳的進(jìn)化操作復(fù)雜化甚至無(wú)意義。為了保證種群的多樣性、避免出現(xiàn)斷路與環(huán)路現(xiàn)象，同時(shí)又提高初始種群個(gè)體的質(zhì)量，本文采用半隨機(jī)方式生成初始種群，即引入控制全局搜索方向的啟發(fā)式搜索策略。具體操作步驟如下：（1）以起節(jié)點(diǎn)O作為染色體的第一個(gè)基因，以終節(jié)點(diǎn)D作為染色體的最后一個(gè)基因。（2）為了規(guī)避斷路或環(huán)路現(xiàn)象，當(dāng)一個(gè)節(jié)點(diǎn)被選中后，就標(biāo)記該節(jié)點(diǎn)，若當(dāng)前節(jié)點(diǎn)無(wú)未標(biāo)記的鄰接節(jié)點(diǎn)可用于選擇時(shí)，退回當(dāng)前節(jié)點(diǎn)的上一節(jié)點(diǎn)重新進(jìn)行選擇并標(biāo)記當(dāng)前節(jié)點(diǎn)禁止下一次被搜索到。（3）以當(dāng)前節(jié)點(diǎn)C的所有未被標(biāo)記的鄰接節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)N的候選節(jié)點(diǎn)，從中按照一定的選擇概率使用隨機(jī)方式或最優(yōu)夾角方式確定下一個(gè)節(jié)點(diǎn)，若選擇最優(yōu)夾角方式，計(jì)算有向路段的夾角，選擇夾角最小的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)。（4）重復(fù)步驟（2）和（3）直到當(dāng)前節(jié)點(diǎn)C 為終節(jié)點(diǎn)D，即為一個(gè)初始染色體。（5）按照此方式求解下一個(gè)染色體，直至達(dá)到初始種群規(guī)模的要求。（6）為了進(jìn)一步提高初始種群個(gè)體的平均質(zhì)量，本文確定初始種群規(guī)模為設(shè)定種群規(guī)模數(shù)的1.2倍，最后按表現(xiàn)排名依次舍去最差的多余個(gè)體。

3.2 選擇操作

定義適應(yīng)度函數(shù)的值為每個(gè)個(gè)體所包含路段和中間節(jié)點(diǎn)的交通時(shí)間阻抗之和，根據(jù)第二章得出的動(dòng)態(tài)路網(wǎng)模型和動(dòng)態(tài)最優(yōu)路徑模型可知，個(gè)體適應(yīng)度函數(shù)為：

式中，Z(r)越小，染色體的適應(yīng)值越小，所對(duì)應(yīng)的路徑所花費(fèi)的行程時(shí)間越少，越接近于路徑最優(yōu)解。

選擇操作是指從當(dāng)代種群中選擇優(yōu)秀個(gè)體以生成交配池遺傳給下一代的過(guò)程，聯(lián)賽選擇、最佳個(gè)體保留、適應(yīng)值比例選擇是目前最常用的三種選擇策略。本文選擇聯(lián)賽選擇與最佳個(gè)體保留相結(jié)合的策略，前者的基本思想為：從當(dāng)代群體中隨機(jī)選擇一定規(guī)模的個(gè)體，比較后選擇適應(yīng)值小的個(gè)體放入交配池；可通過(guò)調(diào)整聯(lián)賽規(guī)模動(dòng)態(tài)控制群體選擇壓力，一般聯(lián)賽規(guī)模取2。同時(shí)采用最佳個(gè)體保留策略將當(dāng)代種群中最優(yōu)的個(gè)體直接復(fù)制進(jìn)入子代，使得子代種群中的最優(yōu)個(gè)體不會(huì)出現(xiàn)比父代種群中的最優(yōu)個(gè)體差的可能，從而保證進(jìn)化方向，加快收斂速度。

3.3 交叉操作

交叉算子是模仿自然界染色體基因交叉重組將父代的優(yōu)良基因遺傳給下一代個(gè)體的操作。采用隨機(jī)確定交叉點(diǎn)對(duì)或選擇相同節(jié)點(diǎn)作為交叉點(diǎn)對(duì)的傳統(tǒng)方式進(jìn)行交叉操作存在明顯的局限性，前者需對(duì)子代個(gè)體進(jìn)行連通化處理，從而使父代的優(yōu)良基因發(fā)生劇變；后者會(huì)因?yàn)閮筛复鷤€(gè)體在此節(jié)點(diǎn)的前后基因片段相同而產(chǎn)生等同于父代的個(gè)體，使得交叉操作無(wú)效。因此本文采用啟發(fā)式鄰近交叉算子操作，主要步驟如下：（1）從其中一個(gè)雙親中隨機(jī)選擇待交叉點(diǎn)（除去O、D點(diǎn)）。（2）計(jì)算另一雙親中的節(jié)點(diǎn)與該節(jié)點(diǎn)的空間距離，選取距離最小的節(jié)點(diǎn)作為交叉點(diǎn)。（3）在交叉點(diǎn)連通生成子代個(gè)體，使子代表示的路徑合格化。此策略把需要連通處理的路段降到最小，同時(shí)保留了父代雙親的優(yōu)良基因。

3.4 變異操作

傳統(tǒng)的單點(diǎn)、多點(diǎn)變異等策略在路徑規(guī)劃問(wèn)題中不能有效地維持種群的多樣性，容易導(dǎo)致個(gè)體向更壞的方向變異，本文采用多向變異策略，主要步驟如下：（1）按照變異概率選擇變異個(gè)體，隨機(jī)選擇變異個(gè)體的變異點(diǎn)（除去O、D點(diǎn)）。（2）以該點(diǎn)為起點(diǎn)，O點(diǎn)為終點(diǎn)，逆向搜索獲得變異個(gè)體。（3）以D節(jié)點(diǎn)為起點(diǎn)，該變異點(diǎn)為終點(diǎn)，逆向搜索求得變異個(gè)體。（4）對(duì)兩個(gè)變異個(gè)體進(jìn)行去環(huán)路處理。（5）比較兩種方式下變異個(gè)體的適應(yīng)度，選擇適應(yīng)度大的個(gè)體作為子代個(gè)體。（6）為保證種群多樣性，每隔五代重新生成一個(gè)新的個(gè)體取代其中一個(gè)待變異個(gè)體。

3.5 局部搜索策略

前人引入模擬退火、爬山與禁忌搜索等思想設(shè)計(jì)的混合遺傳算法雖在一定程度上能提高遺傳算法的局部搜索能力，但由于局部搜索過(guò)程中多次隨機(jī)生成若干路段，然后比較擇優(yōu)替代舊局部路段，而沒(méi)有考慮或者利用局部路段中鄰接節(jié)點(diǎn)的路況、轉(zhuǎn)向等已知信息的綜合影響，從而導(dǎo)致經(jīng)過(guò)大量時(shí)間解算得到的最優(yōu)路徑中的部分路段為次優(yōu)而非最優(yōu)，因此本文引入節(jié)點(diǎn)適應(yīng)度這一新的局部搜索策略對(duì)各代種群個(gè)體的隨機(jī)部分基因片段進(jìn)行自學(xué)習(xí)，以替代適應(yīng)度差的舊基因片段，且每次自學(xué)習(xí)只需搜索一次。根據(jù)路段的實(shí)時(shí)路況Traffic、路段的道路等級(jí)類型Type、轉(zhuǎn)彎類型Turn，以及與基因片段終點(diǎn)的夾角Angle四個(gè)影響因子對(duì)當(dāng)前節(jié)點(diǎn)的鄰接節(jié)點(diǎn)進(jìn)行適應(yīng)度評(píng)價(jià)，定義為節(jié)點(diǎn)適應(yīng)度，按照適應(yīng)度所占比例選取下一節(jié)點(diǎn)。節(jié)點(diǎn)適應(yīng)度與節(jié)點(diǎn)選擇概率定義為：

式中，f(xj)為當(dāng)前節(jié)點(diǎn)的鄰接節(jié)點(diǎn)xj的適應(yīng)度；根據(jù)路段的路阻系數(shù)，分為通暢、較通暢、擁擠和擁堵四種類型，分別對(duì)應(yīng)的 Traffic值為1、0.75、0.5、0；根據(jù)城市交通道路的等級(jí)類型，分為主干路和支路兩種類型，分別對(duì)應(yīng)的Type值為1和0.5；通過(guò)判斷通往下一節(jié)點(diǎn)的行駛轉(zhuǎn)向，分為直行、右轉(zhuǎn)、左轉(zhuǎn)和掉頭四種類型，對(duì)應(yīng)的Turn值分別為1、0.75、0.5和0.25；Angle為有向路段----CN與------

ND的夾角所對(duì)應(yīng)弧度值（C為當(dāng)前節(jié)點(diǎn)，N為待選鄰接節(jié)點(diǎn)，D為所選基因片段的終點(diǎn)），由于其與適應(yīng)度呈為負(fù)相關(guān)，需要進(jìn)行倒數(shù)處理。P(xj)為鄰接節(jié)點(diǎn)xj的選擇概率，節(jié)點(diǎn)適應(yīng)度越大，選擇概率就越大。

3.6 算法步驟

改進(jìn)的動(dòng)態(tài)路徑規(guī)劃算法的主要步驟如下：（1）設(shè)定遺傳參數(shù)以及動(dòng)態(tài)路阻系數(shù)。（2）采用啟發(fā)式策略獲得初始種群。（3）計(jì)算個(gè)體適應(yīng)度，判斷是否滿足算法終止條件，滿足則算法終止輸出實(shí)時(shí)路徑轉(zhuǎn)步驟（6），不滿足轉(zhuǎn)步驟（4）。（4）進(jìn)行選擇算子、交叉算子、變異算子操作，對(duì)遺傳算子操作生成的子代個(gè)體進(jìn)行局部搜索，并通過(guò)篩選生成子代種群。（5）轉(zhuǎn)步驟（3）。（6）按照最優(yōu)路徑行駛，每隔5 min更新動(dòng)態(tài)路阻系數(shù)，并判斷當(dāng)前最優(yōu)行車路線上是否出現(xiàn)某一個(gè)或幾個(gè)路段發(fā)生擁堵等嚴(yán)重影響正常通行的現(xiàn)象，若不發(fā)生繼續(xù)原定路線行駛，若發(fā)生轉(zhuǎn)步驟（7）。（7）定位當(dāng)前位置的下一節(jié)點(diǎn)，若其為終點(diǎn)，結(jié)束行程，若不為終點(diǎn)則以該節(jié)點(diǎn)為起點(diǎn)重新進(jìn)行路徑規(guī)劃。如圖2為算法流程。

4 實(shí)驗(yàn)與分析

4.1 數(shù)據(jù)處理

圖2 改進(jìn)后的算法流程

有向交通路網(wǎng)向量數(shù)據(jù)主要包括節(jié)點(diǎn)圖層和路段圖層，依據(jù)時(shí)間最短的路徑規(guī)劃需求，先設(shè)計(jì)節(jié)點(diǎn)與路段的字段屬性表：前者包括RoadID、FromNodeID、ToNodeID、Road_Type、Speed、Length與Real_Traffic字段，分別表示路段編號(hào)、路段起節(jié)點(diǎn)編號(hào)、路段終節(jié)點(diǎn)編號(hào)、路段等級(jí)、通暢時(shí)速度、長(zhǎng)度、擁堵系數(shù)；后者包括NodeID、X、Y與Node_Type字段，分別表示節(jié)點(diǎn)編號(hào)、X坐標(biāo)值、Y坐標(biāo)值、節(jié)點(diǎn)是否為轉(zhuǎn)向節(jié)點(diǎn)；二者通過(guò)路段屬性表中的FromNodeID、ToNodeID字段與節(jié)點(diǎn)屬性表中的NodeID字段關(guān)聯(lián)。為了模擬路網(wǎng)的動(dòng)態(tài)性，采用時(shí)間離散化方法對(duì)路段擁堵系數(shù)進(jìn)行每隔5 min的變化處理，結(jié)合路段長(zhǎng)度以及通暢時(shí)路段速度求解路段行駛時(shí)間。本文采用的福州市部分路網(wǎng)數(shù)據(jù)共包含3 757個(gè)節(jié)點(diǎn)（包括轉(zhuǎn)向時(shí)延節(jié)點(diǎn)和轉(zhuǎn)向非時(shí)延節(jié)點(diǎn)），5 981個(gè)路段（包括單向路段和雙向路段），228個(gè)時(shí)段的擁堵系數(shù)。

鄰接矩陣和鄰接鏈表是路網(wǎng)資料常用的兩種存儲(chǔ)結(jié)構(gòu)，由于城市有向路網(wǎng)的大規(guī)模性和稀疏性，采用鄰接矩陣表達(dá)路網(wǎng)數(shù)據(jù)需要消耗大量存儲(chǔ)空間與搜索時(shí)間，而鄰接鏈表充分利用了路網(wǎng)中路段的鄰接特性進(jìn)行存儲(chǔ)，存儲(chǔ)空間和搜索時(shí)間的消耗均遠(yuǎn)遠(yuǎn)小于鄰接矩陣。因此，本文選用鄰接鏈表數(shù)據(jù)結(jié)構(gòu)，在.NET平臺(tái)下，利用ArcEngine組件庫(kù)進(jìn)行仿真實(shí)驗(yàn)。

4.2 結(jié)果分析

種群規(guī)模是遺傳算法的一個(gè)重要參數(shù)，對(duì)求解精度和求解效率都存在較大影響，如圖3顯示了種群規(guī)模與收斂適應(yīng)值、收斂代數(shù)的關(guān)系：當(dāng)種群規(guī)模較小時(shí)，需要較多收斂代數(shù)，同時(shí)求解的收斂適應(yīng)值較大不能滿足路徑規(guī)劃的精度要求；隨著種群規(guī)模增大，收斂次數(shù)減少，同時(shí)求解的收斂適應(yīng)值逐漸減低，最終收斂次數(shù)和收斂適應(yīng)值趨于平穩(wěn)；當(dāng)種群規(guī)模為20～60時(shí)，收斂適應(yīng)值和收斂代數(shù)皆滿足最優(yōu)路徑規(guī)劃的精度要求，但隨著種群規(guī)模的增加，同樣的收斂代數(shù)，種群規(guī)模越小，收斂計(jì)算時(shí)間越少。通過(guò)多次模擬分析，綜合考慮求解精度和效率，本文設(shè)定種群規(guī)模為30，交叉率為0.9，變異率為0.05，迭代終止條件為最優(yōu)適應(yīng)值連續(xù)5代保持不變或達(dá)到最大迭代次數(shù)100。

圖3 種群規(guī)模對(duì)收斂適應(yīng)值和收斂代數(shù)影響

為便于比較分析算法的性能，選取傳統(tǒng)遺傳算法（GA）、文獻(xiàn)[22]中基于模擬退火的混合遺傳算法（SAGA），以及本文改進(jìn)的遺傳算法（IGA）進(jìn)行實(shí)驗(yàn)對(duì)比，隨機(jī)選取一對(duì)OD點(diǎn)對(duì)，同時(shí)進(jìn)行100代進(jìn)化操作實(shí)驗(yàn)，分析對(duì)比進(jìn)化過(guò)程中每代種群中最優(yōu)適應(yīng)值的變化情況。如圖4所示，IGA在進(jìn)化至13代時(shí)已達(dá)到收斂適應(yīng)值，求解收斂速度快于GA和SAGA，同時(shí)IGA所求得的收斂適應(yīng)值明顯優(yōu)于GA和SAGA。分析可知，本文所采用的局部搜索策略通過(guò)利用鄰接節(jié)點(diǎn)自身的先驗(yàn)知識(shí)，構(gòu)建節(jié)點(diǎn)適應(yīng)度，然后根據(jù)各節(jié)點(diǎn)選擇概率進(jìn)行搜索，強(qiáng)化了局部搜索的目的性，進(jìn)化過(guò)程中每一代種群最優(yōu)值都有所提高，直至達(dá)到收斂適應(yīng)值，從而提高了算法的局部搜索能力，使其具有更好的收斂性。

圖4 進(jìn)化過(guò)程中最優(yōu)適應(yīng)值變化

進(jìn)一步對(duì)該OD點(diǎn)對(duì)進(jìn)行20次實(shí)驗(yàn)，并利用第100代最優(yōu)適應(yīng)值的均值對(duì)之前每一代種群中最優(yōu)適應(yīng)值的均值做標(biāo)準(zhǔn)化處理，其值越趨近于1對(duì)應(yīng)路徑越優(yōu)，結(jié)果如圖5。IGA在前20代中具有很快的收斂速度，在進(jìn)化至20代左右時(shí)的標(biāo)準(zhǔn)化適應(yīng)值已達(dá)到0.9，即20次實(shí)驗(yàn)中有若干次已十分逼近收斂結(jié)果，而GA和SAGA進(jìn)化緩慢，直到40代之后才達(dá)到0.9，說(shuō)明本文提出的改進(jìn)算法IGA的收斂性和穩(wěn)定性均優(yōu)于GA和SAGA。

圖5 進(jìn)化過(guò)程中標(biāo)準(zhǔn)化適應(yīng)值變化

為避免偶然性，選取10對(duì)OD點(diǎn)對(duì)分別進(jìn)行20次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1。精度上：IGA搜索到的最優(yōu)個(gè)體所對(duì)應(yīng)路徑的行程時(shí)間更少，相較于GA縮短約38%，相較于SAGA縮短約6%；效率上：IGA收斂時(shí)所需計(jì)算時(shí)間平均值為1.232 s，相較于GA降低約30%，比SAGA降低約20%。本文提出的算法IGA具有更好的局部搜索能力，求解精度和求解效率均有明顯提升，能更好地滿足動(dòng)態(tài)路徑規(guī)劃需求。

表1 不同OD點(diǎn)對(duì)實(shí)驗(yàn)結(jié)果

為檢驗(yàn)本文提出的算法的動(dòng)態(tài)性與優(yōu)越性，選擇錦繡大廈為起點(diǎn)，光明港公園為終點(diǎn)，采用三種算法分別進(jìn)行動(dòng)態(tài)路徑規(guī)劃誘導(dǎo)，結(jié)果如圖6、7、8所示，其中紅色代表?yè)矶侣范危S色代表?yè)頂D路段，淡綠色代表較通暢路段，綠色代表通暢路段。初始時(shí)刻IGA所規(guī)劃的最優(yōu)路徑避免不必要的轉(zhuǎn)向等次優(yōu)行駛決策，具有更好的局部搜索效果，行程時(shí)間為19.69 min，優(yōu)于GA的34.68 min，和SAGA的22.56 min；5 min后規(guī)劃路徑中剩余部分未出現(xiàn)擁堵路段，不需要重新進(jìn)行路徑規(guī)劃；10 min后規(guī)劃路徑中剩余部分出現(xiàn)擁堵路段，重新規(guī)劃后得到規(guī)避了擁堵路段的新路徑。對(duì)比可知，本文提出的算法IGA能更好地處理動(dòng)態(tài)路徑規(guī)劃問(wèn)題。

圖6 GA動(dòng)態(tài)路徑規(guī)劃

圖7 SAGA動(dòng)態(tài)路徑規(guī)劃

圖8 IGA動(dòng)態(tài)路徑規(guī)劃

5 結(jié)論

本文針對(duì)城市路網(wǎng)中動(dòng)態(tài)路徑規(guī)劃問(wèn)題，提出一種改進(jìn)的遺傳算法，該算法采用啟發(fā)式策略控制全局搜索方向確定初始種群；采用空間鄰近交叉策略完成交叉操作；使用前向、逆向的多向變異和重新生成新個(gè)體變異相結(jié)合的變異策略實(shí)施變異操作；引入節(jié)點(diǎn)選擇概率的局部搜索策略進(jìn)行局部搜索，能有效克服傳統(tǒng)遺傳算法存在的“早熟收斂”，局部搜索能力差等問(wèn)題，同時(shí)有著更高的收斂效率與更穩(wěn)定的收斂性。實(shí)驗(yàn)結(jié)果表明，提出的算法在搜索最優(yōu)路徑的過(guò)程中具有更優(yōu)的局部搜索能力，能有效地規(guī)避交通擁堵路段，滿足行進(jìn)中的動(dòng)態(tài)最優(yōu)路徑規(guī)劃對(duì)求解精度和效率的要求。