孫 睿，黃海超，霍欣婷，陳景雅

(河海大學 土木與交通學院，江蘇 南京 210098)

隨著社會經(jīng)濟的不斷發(fā)展，人民生活水平不斷提高，城市路網(wǎng)上私人汽車數(shù)量不斷增加，由此帶來的道路擁堵、停車困難等現(xiàn)象日趨嚴重[1]。路徑誘導(dǎo)及導(dǎo)航服務(wù)是智能交通系統(tǒng)的重要組成部分[2]，是解決用戶出行交通擁堵問題的有效方法[3]，而合理選用和優(yōu)化智能算法進行路徑規(guī)劃是實現(xiàn)路徑誘導(dǎo)及導(dǎo)航服務(wù)的核心[4]。

遺傳算法是一種采用種群搜索策略的全局性尋優(yōu)算法，該搜索機制使求得最優(yōu)解的可能性和效率大大提高，故該算法被廣泛應(yīng)用于包括路徑規(guī)劃在內(nèi)的眾多問題的求解。但傳統(tǒng)遺傳算法存在早熟收斂、種群多樣性降低等問題[5]。同時，由于目前的路徑規(guī)劃研究大多以單一目標(時間最短或者距離最短)進行最優(yōu)路徑搜尋[6-11]，忽略了道路等級、道路擁堵情況等影響因素，使其對現(xiàn)實路網(wǎng)應(yīng)用意義不大。

為解決以上問題，本文在改進經(jīng)典遺傳算法的基礎(chǔ)上，針對路徑規(guī)劃應(yīng)用進行了多目標優(yōu)化：一方面，改進遺傳操作解決傳統(tǒng)遺傳算法在路徑規(guī)劃中的局限性(斷路、回頭路、種群多樣性降低、早熟收斂等)；另一方面,在算法中加入反映個體出行偏好的權(quán)重系數(shù)，綜合考慮平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級4種影響因素，更好地解決出行交通擁堵問題。

1 模型構(gòu)建

1.1 算法編碼

區(qū)別于傳統(tǒng)的二進制編碼，采用實數(shù)編碼方式，更貼近路徑規(guī)劃現(xiàn)實問題。一條路徑就是一個染色體個體，路徑上的每一個道路交叉口或是單獨路段的起終點就是染色體上的基因[12]。如染色體“1-3-5-8-9”代表了路網(wǎng)上由起點1到終點9的一條路徑，1、3、5、8、9都是路網(wǎng)節(jié)點。傳統(tǒng)遺傳算法為了滿足交叉、變異的要求，使用的染色體長度相同[13]。本文采用變長度方式，更能豐富種群的多樣性，也符合現(xiàn)實路徑長度靈活多變的特點。

1.2 初始種群的選取

初始種群的質(zhì)量在遺傳算法中起決定性作用，而遺傳算法采用完全隨機方式產(chǎn)生的初始種群雖然多樣性豐富[14]，但會包含大量的斷路、回頭路，這會導(dǎo)致算法尋優(yōu)效率降低，遲遲無法收斂。

為了保證初始種群的質(zhì)量，避免斷路、回頭路的產(chǎn)生，本文設(shè)計了Dijkstra算法改進的半隨機方式種群初始化策略。具體步驟如下：

Step1將路網(wǎng)中每一節(jié)點與其余節(jié)點的連接作標記，通路標記1，斷路標記0，構(gòu)建鄰接矩陣；

Step2從起點O開始，選擇下一節(jié)點時，按照鄰接矩陣選擇標記1的通路，避免斷路產(chǎn)生；

Step3標記已選擇過的節(jié)點，禁止下次選中，避免回頭路產(chǎn)生；

Step4如果當前節(jié)點已無未標記的連通節(jié)點，則退回上一節(jié)點重新選擇；

Step5重復(fù)Step2—Step4，直至擴展到終點D為止，形成一條不包含斷路、環(huán)路的染色體；

Step6重復(fù)Step2—Step5，直至染色體個數(shù)達到初始種群規(guī)模。

1.3 適應(yīng)度函數(shù)的構(gòu)造

遺傳算法中適應(yīng)度函數(shù)也叫評價函數(shù)，是用來判斷群體中個體的優(yōu)劣程度的指標[15]。本文選用時間單位作為適應(yīng)度函數(shù)的統(tǒng)一量綱，綜合考慮平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級，采用層次分析法 (analytic hierarchy process,AHP)[16]計算個體用戶對以上4種影響因素的偏好權(quán)重系數(shù)。

1.3.14種因素的權(quán)重系數(shù)計算

1)構(gòu)建判斷矩陣

在用戶現(xiàn)實選擇時，經(jīng)典9種標度可能會因為重要性區(qū)分不明顯而產(chǎn)生困擾，故模型采用簡化后的3種標度，規(guī)定如表1所示。

根據(jù)表1構(gòu)建4種因素的判斷矩陣并計算權(quán)重，其隨著用戶對4種影響因素重要性排序不同而改變，此處只是舉例說明。D1、D2、D3、D4分別對應(yīng)平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級4種因素，判斷矩陣如表2所示。

用和法計算D1影響因素權(quán)重：

=0.576 9

同理可得其余3種影響因素權(quán)重分別為：0.115 4、0.192 3、0.115 4。

2)一致性檢驗：

=4.000 2

=0.000 067

=0.000 074<0.10

式中：λmax為n階判斷矩陣的最大特征值；n為影響因素個數(shù)；dij為判斷矩陣中因素i對因素j的比重；wj、wi分別為影響因素j、i的權(quán)重；CI為一致性指標；CR為檢驗系數(shù)；RI為隨機一致性指標，判斷矩陣階數(shù)為4時取值為0.90。

判斷矩陣通過一致性檢驗。

1.3.24種因素量綱統(tǒng)一

1)交叉口延誤與道路擁擠狀況

對于交叉口而言，在現(xiàn)階段研究中它的主要評價指標是延誤時間。美國道路通行能力手冊給出了交叉口的評價標準，將服務(wù)水平分為六級[17]；對于道路擁擠狀況，已有研究采用模糊數(shù)學中的綜合評價方法計算道路擁擠度系數(shù)對城市路網(wǎng)的交通擁堵狀態(tài)進行評價，并將其分為6個服務(wù)水平等級[18]。鑒于交叉口和道路擁擠狀況的服務(wù)水平等級都是六級，匯總得到表3。

本文通過地點速度[19]計算擁擠度系數(shù)S來判斷服務(wù)水平等級，通過線性插值法計算路網(wǎng)交叉口的平均延誤時間t2；量化道路擁擠狀況影響因素至時間量綱，以表3中擁擠度系數(shù)S為折減系數(shù)，則擁擠延誤時間t3可在平均行駛時間t1的基礎(chǔ)上通過折減計算得到。

2)道路等級

曼徹斯特是英國重要交通樞紐，本文選取其局部公路網(wǎng)作為模型實驗對象，路網(wǎng)包含50個節(jié)點，交通流數(shù)據(jù)來自英國公路交通數(shù)據(jù)集[20]。在《Guidance on Road Classification and the Primary Route Network》(《道路分類和主要路網(wǎng)指南》)中，全英道路劃分為4個分類等級：A類道路，B類道路，分類未編號道路，未分類道路[21]。本文選取的曼徹斯特局部路網(wǎng)只包含A類道路和B類道路2種。圖1為簡化路網(wǎng)示意圖。

將道路等級轉(zhuǎn)換為時間量綱t4是通過將其轉(zhuǎn)換為折減系數(shù)以在平均行駛時間上進行折算。若每一條染色體個體中包含的A類道路數(shù)量≥B類道路數(shù)量，則t4=0，否則按0.2的折減系數(shù)對t1進行折減。

1.3.3適應(yīng)度函數(shù)計算

綜上，考慮平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級后的適應(yīng)度函數(shù)計算如下：

(1)

(2)

t2(i,i+1)=t2b+(t2u-t2b)(S(i,i+1)-Sb)×

(Su-Sb)

(3)

(4)

(5)

式中：m為染色體個體中包含的路網(wǎng)節(jié)點數(shù)量；w1、w2、w3、w4分別為4種因素的權(quán)值；L(i,i+1)為節(jié)點i到節(jié)點i+1的距離；Vi、Vi+1分別為節(jié)點i,i+1的速度；S(i,i+1)為節(jié)點i到節(jié)點i+1路段的擁擠度系數(shù)；t2b、t2u分別為表3中不同服務(wù)等級對應(yīng)t2的下限值和上限值；Sb、Su分別為表3中對應(yīng)擁擠度系數(shù)S的下限值和上限值；NA、NB分別為一條染色體中A類、B類道路數(shù)量。

1.4 遺傳操作的改進

1.4.1選擇操作

本文的選擇方法采用輪盤賭選擇法，但一般輪盤賭選擇法應(yīng)用中，染色體個體的適應(yīng)度值越大越容易被選擇保留，與本模型的適應(yīng)度值越小越優(yōu)化原則相悖，所以將個體被選擇概率作如下改進：

(6)

式中：sp為初始種群規(guī)模；fj為個體j的適應(yīng)度值。

輪盤賭選擇結(jié)束后，為了進一步提高選擇后群體的質(zhì)量，采用最佳個體保留策略，即用此時群體池中適應(yīng)度值最小個體替換適應(yīng)度值最大的個體，保證種群向最優(yōu)方向進化。

1.4.2交叉操作

遺傳算法通過交叉操作將種群中2個個體隨機交換某些基因，期望有益基因組合在一起；但在路徑規(guī)劃問題中這樣的方式極大概率會使后代產(chǎn)生斷路、回頭路，使得交叉操作無意義，大大降低路徑尋優(yōu)的成功率和效率。因此，本文設(shè)計基于鄰接矩陣的深度優(yōu)先遍歷交叉策略，不僅完全避免了斷路、回頭路的產(chǎn)生，同時保證交叉操作使子代優(yōu)于父代。具體步驟如下：

Step1在群體池中按事先設(shè)定的交叉率pc選取兩個父代個體I1，I2。

Step2在個體I1中隨機選取一個節(jié)點m1(除起、終點外)作為待交叉點。

Step3按照鄰接矩陣在個體I2中查找所有與m1鄰接的點，計算m1與各鄰接點的平均行駛時間，選擇最小值對應(yīng)的鄰接點作為個體I2中的待交叉點。若個體I2中沒有與m1連通的鄰接點，則返回Step2重新選取待交叉點。

Step4父代個體I1,I2分別在各自待交叉點斷開，交換前后基因，產(chǎn)生2個子代個體N1,N2。

Step5計算I1,I2,N1,N2的適應(yīng)度值，比較四者。若最優(yōu)個體在子代中產(chǎn)生，說明交叉操作成功，將四者中適應(yīng)度值最小的2個個體作為交叉后產(chǎn)生的個體；否則交叉操作失敗，返回Step2重新選取待交叉點。

Step6重復(fù)Step1—Step5，直至交叉操作結(jié)束。

1.4.3變異操作

遺傳算法對變異個體采取隨機變異的方式，會破壞交叉操作的全局尋優(yōu)結(jié)果，而且在路徑規(guī)劃問題中并不能達到豐富群體多樣性的功能，反而會降低種群質(zhì)量。因此，本文設(shè)計鄰接限制半隨機變異策略，在保護交叉操作全局搜索能力的基礎(chǔ)上，兼顧變異操作的局部搜索能力，同時維持群體的多樣性，防止出現(xiàn)未成熟收斂現(xiàn)象。具體步驟如下：

Step1對群體池中個體按事先設(shè)定的變異概率pm判斷是否要進行變異。

Step2在變異個體中隨機選擇除起、終點外的基因位置作為待變異點，d為待變異點在該個體中的基因位置序號。

Step3按鄰接矩陣尋找基因位置d-1，d+1上節(jié)點的鄰接點，去除d基因位置上的節(jié)點，確定二者的交集B。

Step4若B不是空集，則將待變異位置d上的節(jié)點隨機變異為B中包含的節(jié)點；若B是空集，返回Step2，重新選擇待變異點。

Step5變異后檢查此時個體中是否有節(jié)點重復(fù)出現(xiàn)，若有，返回Step2。

Step6若該個體中始終沒有符合要求的待變異點，則返回Step1，進行下一個體是否需要變異的判斷。

2 實例應(yīng)用

2.1 模型參數(shù)選取

在本模型中，種群規(guī)模過小會導(dǎo)致算法難以收斂，同時得到的最優(yōu)路徑的綜合代價過高，不滿足用戶現(xiàn)實需求；種群規(guī)模過大會浪費計算資源，增加用戶等待時間。為選取最優(yōu)參數(shù)，進行多次實驗?zāi)M，模擬結(jié)果如圖2所示。由圖2可以看出：隨著種群規(guī)模增大，收斂迭代次數(shù)呈下降趨勢，最優(yōu)路徑綜合代價先降低后不變。因此最終確定：種群規(guī)模為40，交叉概率為0.9，變異概率為0.1，最大迭代次數(shù)為120。

2.2 實例實驗

本模型采用多目標優(yōu)化-改進遺傳算法(multi-objective-improved genetic algorithm,M-IGA)。為了驗證改進算法和多目標優(yōu)化的性能以及二者組合后模型的整體性能，進行以下4組對比實驗：單目標-改進遺傳算法(single-objective-improved genetic algorithm,S-IGA)與單目標-經(jīng)典遺傳算法(single-objective-genetic algorithm,S-GA)；多目標-經(jīng)典遺傳算法(multi-objective-genetic algorithm,M-GA)與單目標-經(jīng)典遺傳算法(S-GA)；M-IGA與S-GA；M-IGA與多目標-蟻群算法(multi-objective-ant colony algorithm,M-ACA)。每組實驗選取曼徹斯特局部路網(wǎng)上5個起終點(origin destination，OD)對，每個OD對分別做20次實驗，對比實驗結(jié)果見表4。由表4可知：

1)S-IGA與S-GA

相比于S-GA，S-IGA的算法運行時間平均增加了14.809 8%，最優(yōu)路徑綜合代價平均降低了12.575 0%。

2)M-GA與S-GA

相比于S-GA，M-GA的算法運行時間平均增加了3.807 4%，最優(yōu)路徑綜合代價平均降低了21.390 2%。

3)M-IGA與S-GA

相比于S-GA，M-IGA的算法運行時間平均增加了21.182 2%，最優(yōu)路徑綜合代價平均降低了23.609 1%。

4)M-IGA與M-ACA

相比于M-ACA，M-IGA的算法運行時間平均減少了54.322 0%，最優(yōu)路徑綜合代價平均降低了26.589 4%。

2.3 結(jié)果分析

S-IGA與S-GA對比實驗結(jié)果顯示，改進的遺傳算法可以有效降低收斂后的路徑綜合代價。經(jīng)分析可知：本文設(shè)計的Dijkstra算法改進的半隨機方式種群初始化策略、基于鄰接矩陣的深度優(yōu)先遍歷交叉策略和鄰接限制半隨機變異策略，可以保證進化向最優(yōu)推進而并非隨機發(fā)散式無效迭代，同時避免算法陷入局部最優(yōu)解，使改進后的算法全局優(yōu)化出綜合代價更低的路徑。

M-GA與S-GA對比實驗結(jié)果顯示，引進偏好權(quán)重系數(shù)的多目標優(yōu)化可以有效改善經(jīng)典遺傳算法的收斂結(jié)果。經(jīng)分析可知：本文在選擇操作的適應(yīng)度函數(shù)設(shè)計中引入平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級的偏好權(quán)重系數(shù)，可以有效為用戶避開擁堵、交叉口多的路徑，使得路徑規(guī)劃結(jié)果更符合用戶預(yù)期。

M-IGA與S-GA以及M-ACA的對比實驗結(jié)果表明，本文設(shè)計的多目標優(yōu)化-改進遺傳算法組合模型，雖然犧牲了少部分算法運行效率，但是模型規(guī)劃出的最優(yōu)路徑的綜合代價大大降低，減少了3～6 min。與經(jīng)典遺傳算法縱向比較，最優(yōu)路徑綜合代價降低了23.609 1%；與多目標蟻群算法橫向比較，最優(yōu)路徑綜合代價降低了26.589 4%。

3 結(jié)論

本文針對經(jīng)典遺傳算法路徑規(guī)劃的弊端，分別進行了改進算法、模型多目標優(yōu)化兩方面的研究：

1)Dijkstra算法改進的半隨機方式種群初始化策略，100%規(guī)避了斷路、回頭路的產(chǎn)生，提高了初始種群質(zhì)量；基于鄰接矩陣的深度優(yōu)先遍歷交叉策略，在完全避免斷路、回頭路產(chǎn)生的同時，保證交叉后子代適應(yīng)度值優(yōu)于父代，提高交叉操作全局尋優(yōu)能力；鄰接限制半隨機變異策略，在不破壞群體池內(nèi)優(yōu)秀個體基因的基礎(chǔ)上，維持種群多樣性，防止早熟收斂。

2)在適應(yīng)度函數(shù)設(shè)計時引入偏好權(quán)重系數(shù)，對模型進行多目標優(yōu)化。用戶可根據(jù)習慣偏好，在模型的輸入中設(shè)置平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級的重要程度排序。實驗結(jié)果表明，最優(yōu)路徑的綜合代價相比于單目標減少了23.609 1%，模型可以按需避開交叉口多、擁堵的路段，得到更符合用戶期望的路徑規(guī)劃結(jié)果。