基于改進(jìn)遺傳算法的可變信息標(biāo)志選址優(yōu)化研究*

張榮輝 馬壯林 黨永樂 徐 婷

(長(zhǎng)安大學(xué)汽車學(xué)院 西安 710064)

0 引 言

可變信息標(biāo)志(variable message sign，VMS)是先進(jìn)的出行者信息系統(tǒng)(advanced traveler information systems，ATIS)的重要組成部分，其作為一種有效的群體誘導(dǎo)信息發(fā)布系統(tǒng)，向駕駛?cè)颂峁┣胺铰范蔚膶?shí)時(shí)路況信息(如擁堵信息、事故信息、行程時(shí)間和天氣信息等)，引導(dǎo)駕駛?cè)吮荛_擁堵路段，選擇最合理的出行路徑，達(dá)到優(yōu)化路網(wǎng)車流量時(shí)空分布、提高通行效率的目的[1]。目前，VMS已經(jīng)被廣泛應(yīng)用于國內(nèi)外的高速公路和城市快速路，對(duì)于緩解交通擁堵、提高路網(wǎng)通行效率起到了不容忽視的作用。但是，這些VMS的布設(shè)位置大多依靠當(dāng)?shù)毓芾聿块T的經(jīng)驗(yàn)和主觀判斷，無論是VMS的數(shù)量，還是VMS的布設(shè)位置，都缺乏系統(tǒng)、科學(xué)、合理的論證，因此，提出一種系統(tǒng)、科學(xué)的VMS選址方法，明晰VMS數(shù)量和選址位置對(duì)交通流量的誘導(dǎo)效果，對(duì)提高整個(gè)城市交通誘導(dǎo)系統(tǒng)的效率至關(guān)重要。

目前，國內(nèi)外關(guān)于VMS的研究主要集中在顯示內(nèi)容[2-4]、控制邏輯[5-6]、對(duì)駕駛行為的影響[7-10]和布設(shè)選址[11-20]4個(gè)方面。與其他3個(gè)方面的研究相比，VMS布設(shè)選址的研究起步最晚，且成果相對(duì)淺顯。起初，一些學(xué)者研究高速公路上的VMS選址模型，例如，Abbas等[11]構(gòu)建了VMS誘導(dǎo)效益最大化的單目標(biāo)規(guī)劃模型，采用遺傳算法求解模型以確定VMS布設(shè)的最佳位置；Chiu等[12]提出了一種雙層規(guī)劃模型，上層模型為用戶行程時(shí)間最小化，下層為動(dòng)態(tài)流量分配模型，并采用禁忌搜索算法求解。

隨著城市交通擁堵問題的日益嚴(yán)重，越來越多的學(xué)者關(guān)注城市路網(wǎng)的VMS選址研究。徐志等[13]以路網(wǎng)總期望出行時(shí)間最短為目標(biāo)，提出了一種VMS選址計(jì)算流程，并以4×4節(jié)點(diǎn)的棋盤狀路網(wǎng)進(jìn)行驗(yàn)算；四兵鋒等[14]在考慮道路等級(jí)、交通流量、VMS布設(shè)效果以及信息疊加度等因素的基礎(chǔ)上提出一種VMS選址方法，并采用回溯法進(jìn)行求解；上述研究只是提出了城市路網(wǎng)中VMS選址方法的計(jì)算流程，沒有構(gòu)建具體的數(shù)學(xué)規(guī)劃模型。倪富健等[15]對(duì)城市路網(wǎng)中VMS布設(shè)地點(diǎn)的最優(yōu)分布進(jìn)行了研究，建立了一種基于衰減因子的整數(shù)規(guī)劃選址模型，該模型以VMS的效用最大化為目標(biāo)，采用遺傳算法進(jìn)行求解，但沒有考慮到經(jīng)濟(jì)成本和交叉口延誤的影響；Won等[16]以延誤時(shí)間最小化為目標(biāo)，從經(jīng)濟(jì)可行性角度分析了VMS的選址問題，并采用遺傳算法進(jìn)行求解；承向軍等[17]在文獻(xiàn)[15]的基礎(chǔ)上建立考慮交叉口延誤影響的VMS效用最大化的整數(shù)規(guī)劃模型，采用枚舉法對(duì)北京市西直門橋到復(fù)興門橋的VMS布設(shè)進(jìn)行實(shí)證分析；袁舒平等[18]在文獻(xiàn)[15]的基礎(chǔ)上建立考慮誘導(dǎo)信息中道路等級(jí)對(duì)駕駛員影響的VMS效用最大化的整數(shù)規(guī)劃模型，采用遺傳算法對(duì)北京南站周邊路網(wǎng)的VMS布設(shè)進(jìn)行實(shí)證分析；趙敬洋等[19]在文獻(xiàn)[15]的基礎(chǔ)上建立重點(diǎn)考慮典型行車路線上備選路段的VMS效用最大化的整數(shù)規(guī)劃模型，采用改進(jìn)的遺傳算法對(duì)杭州市某區(qū)域路網(wǎng)進(jìn)行實(shí)證分析；Gan等[20]在文獻(xiàn)[15]的基礎(chǔ)上建立常發(fā)性擁堵路段的VMS選址的雙層規(guī)劃模型，上層模型是VMS效用最大化，下層模型是隨機(jī)用戶均衡交通分配模型。

上述研究對(duì)VMS選址問題的研究進(jìn)行了深入的探討，但是沒有考慮到可替代路徑對(duì)VMS選址的影響，同時(shí)也忽略了VMS選址問題是一個(gè)綜合的、復(fù)雜的、多目標(biāo)的規(guī)劃問題[21]；此外，大多數(shù)研究采用傳統(tǒng)的遺傳算法對(duì)構(gòu)建的VMS選址模型進(jìn)行求解，忽略了其容易出現(xiàn)“早熟”而陷入局部最優(yōu)解的缺陷。

筆者在上述研究的基礎(chǔ)上，引入可替代路徑的誘導(dǎo)比率和繞行時(shí)間2個(gè)影響因素，綜合考慮VMS效益和成本的關(guān)系，構(gòu)建VMS效益最大化與成本最小化之比為目標(biāo)函數(shù)的選址模型，采用改進(jìn)的遺傳算法對(duì)模型進(jìn)行求解，最后結(jié)合西安市南二環(huán)路的實(shí)際交通狀況以及VMS的布設(shè)現(xiàn)狀，科學(xué)、合理地優(yōu)化西安市南二環(huán)路VMS的布局選址。

1 VMS選址的影響因素分析

VMS的選址原則主要有4點(diǎn)：①應(yīng)布設(shè)在經(jīng)常發(fā)生擁堵或者交通流量較大的路段上游分流口前端的適當(dāng)位置；②對(duì)于城市道路路網(wǎng)而言，在布設(shè)VMS時(shí)不宜過于密集，避免造成交通信息混亂；③VMS的布設(shè)要考慮到其與靜態(tài)交通標(biāo)志的配合和協(xié)調(diào)，在城市道路中VMS與靜態(tài)交通標(biāo)志至少應(yīng)相距30 m[22]；④2個(gè)連續(xù)VMS之間的間距應(yīng)當(dāng)合理，保證發(fā)布信息內(nèi)容的準(zhǔn)確性和一致性?？梢?，并不是在每條道路上都布設(shè)VMS誘導(dǎo)效果最好，許多道路屬性都會(huì)影響布設(shè)位置的選擇。根據(jù)以上選址原則，筆者歸納總結(jié)出VMS選址的影響因素主要體現(xiàn)在以下5個(gè)方面。

1) 道路交通流量。道路交通流量是指在單位時(shí)間內(nèi)通過道路某一地點(diǎn)、某一斷面或某一車道的交通實(shí)體數(shù)。可見，衡量某個(gè)路段是否需要設(shè)置VMS的首要因素是該路段的交通量[19]。從交通量的大小可以判定道路的交通擁擠狀況，并且可以直接反映VMS發(fā)布的誘導(dǎo)信息的受眾的多少，直接決定VMS的誘導(dǎo)效果[14]。因此，道路交通流量是影響VMS選址的重要因素之一。

2) 交通擁堵指數(shù)。交通擁堵指數(shù)(traffic performance index，TPI)是指根據(jù)道路通行情況設(shè)定的用來定量評(píng)價(jià)和綜合反映全路網(wǎng)運(yùn)行狀態(tài)(暢通或擁堵)的概念性數(shù)值，它把道路交通擁堵狀況采用數(shù)量化的形式進(jìn)行描述，即擁堵指數(shù)取值在0至10之間，數(shù)值越高，表示交通擁堵狀況越嚴(yán)重[23]。常發(fā)性交通擁堵信息和因交通事故產(chǎn)生的偶發(fā)性交通擁堵信息是VMS向駕駛?cè)颂峁┑闹匾獌?nèi)容[20]。因此，交通擁堵指數(shù)是影響VMS選址的重要因素之一。

3) 信息衰減程度。VMS的信息衰減程度指的是駕駛?cè)嗽趶目吹秸T導(dǎo)信息的地點(diǎn)行駛到信息發(fā)生的地點(diǎn)這一時(shí)間段內(nèi)，VMS發(fā)布的誘導(dǎo)信息準(zhǔn)確性的衰減程度。布設(shè)在某一路段上的VMS顯示的誘導(dǎo)信息為其下游路段的交通狀況，駕駛?cè)丝吹秸T導(dǎo)信息時(shí)距離信息發(fā)生地越遠(yuǎn)，信息的影響程度越弱，甚至在駕駛?cè)说竭_(dá)信息發(fā)生地時(shí)信息已發(fā)生變化[15]，表明VMS發(fā)布的誘導(dǎo)信息具有一定的信息衰減程度，這對(duì)VMS的選址也具有重要影響。

4)VMS建設(shè)成本。VMS的建設(shè)成本即為安裝VMS以及后期的運(yùn)營、維護(hù)階段需要花費(fèi)的成本。VMS的有效性取決于VMS在路網(wǎng)中的安裝位置及安裝VMS的數(shù)量。從理論上來講，整個(gè)路網(wǎng)都使用VMS時(shí)其帶來的效益最大，由于安裝和運(yùn)營VMS也需要花費(fèi)一定的成本，因此這是不切合實(shí)際的[21]。此外，以往的研究表明，由于駕駛?cè)藢?duì)實(shí)時(shí)信息的行為反應(yīng)，過度使用VMS會(huì)使其帶來的效益減小，甚至?xí)a(chǎn)生反作用[24]。

5)可替代路徑的誘導(dǎo)比率和繞行時(shí)間。曹亞康[1]認(rèn)為：駕駛?cè)藢?duì)出行屬性中的出行距離和可替代路徑最為敏感?？商娲窂绞切畔l(fā)布后引導(dǎo)駕駛?cè)诉x擇合適的路徑以分散主路交通壓力的前提，而道路等級(jí)決定了可替代路徑所能服務(wù)的交通量的大小。這就要求當(dāng)VMS顯示前方道路擁堵時(shí)，應(yīng)有合適的可替代路徑供駕駛?cè)诉x擇，而且可替代路徑的道路等級(jí)應(yīng)盡量高，繞行時(shí)間應(yīng)盡量短，才能有吸引駕駛?cè)诉x擇繞行。

筆者提出了誘導(dǎo)比率的定義，即在VMS誘導(dǎo)信息作用下車輛的分流率與不同道路等級(jí)的誘導(dǎo)比率修正系數(shù)的乘積，其反映了不同等級(jí)道路對(duì)駕駛?cè)说恼T導(dǎo)效果。由于可替代路徑的道路等級(jí)對(duì)駕駛?cè)耸欠窀淖兟窂接兄匾绊懀虼瞬煌缆返燃?jí)的可替代路徑對(duì)駕駛?cè)说恼T導(dǎo)效果不同[18,25]?？商娲窂缴下范蔚牡缆返燃?jí)越高，對(duì)駕駛?cè)说恼T導(dǎo)影響越顯著，即駕駛?cè)烁悠蛴趶牡偷燃?jí)道路轉(zhuǎn)向高等級(jí)道路行駛，因此在選擇VMS的布設(shè)位置時(shí)應(yīng)盡量有較高等級(jí)的道路作為可替代路徑。

文中定義繞行時(shí)間為每條繞行路段的總長(zhǎng)度與其限制速度之比。一般情況下，駕駛?cè)藭?huì)優(yōu)先選擇繞行時(shí)間短的路徑代替原始路徑。如果繞行時(shí)間過長(zhǎng)，會(huì)嚴(yán)重影響駕駛?cè)藢?duì)誘導(dǎo)信息的服從度，從而降低駕駛?cè)藢?duì)VMS誘導(dǎo)信息的接受率。因此繞行時(shí)間也是VMS選址時(shí)應(yīng)重點(diǎn)考慮的因素之一。

2 VMS選址規(guī)劃模型的建立及求解算法

2.1 模型構(gòu)建

假設(shè)路段a屬于路徑r，在路段a上布設(shè)VMS，且假設(shè)路段a上最多只能布設(shè)1個(gè)VMS，則路段a上的VMS對(duì)路徑r上出行者的影響程度βra可用式(1)表示，即

(1)

式中：qi為路段i上的交通擁堵指數(shù)，表示路段i的道路擁擠程度；Sra為路段a上VMS獨(dú)立有效影響路段的集合。

需要說明的是，本文中路段a上VMS的獨(dú)立有效影響路段的集合是指路段a上的VMS的有效影響路段去掉該路徑上下一個(gè)VMS的有效影響路段的剩余路段的集合[12]。

路段a上的VMS在路徑r上的效益f可表示為路段a上的交通流量fra與影響指數(shù)βra的乘積，即

f=fra×βra

(2)

(3)

式中：θ為一個(gè)區(qū)間常數(shù)，其值介于0和1之間；n為路段i與路段a之間相隔的路段數(shù)量。

為了進(jìn)一步說明式(3)的含義，以1條由7個(gè)路段組成的路徑進(jìn)行詳細(xì)闡述，具體如圖1所示。

圖1 VMS衰減程度說明示意圖
Fig.1 Schematic diagram of VMS attenuation degree

(4)

式中：b為不同道路等級(jí)的誘導(dǎo)比率修正系數(shù)。

不僅可替代路徑的道路等級(jí)對(duì)VMS的誘導(dǎo)效用有影響，其繞行時(shí)間也會(huì)影響駕駛?cè)私邮躒MS提供的誘導(dǎo)信息，因此，本文引入繞行時(shí)間影響因子pra，其計(jì)算公式見式(5)。

(5)

式中：Tk為駕駛?cè)嗽诶@行路段k上的行程時(shí)間。

因此，路徑r上所有VMS的總效用F可表示為

(6)

式中：Za為一個(gè)0-1變量，當(dāng)路段a上布設(shè)了VMS時(shí)，Za= 1；反之，Za= 0。

由于VMS的效用由其在路網(wǎng)上的位置和布設(shè)數(shù)量共同決定，因此，還要考慮VMS的建設(shè)成本。根據(jù)工程實(shí)際，隨著VMS布設(shè)數(shù)目的增多，會(huì)節(jié)省施工、運(yùn)營，以及后期維護(hù)階段中的人力物力和財(cái)力投入，因此，假設(shè)每多布設(shè)1個(gè)VMS，該VMS的建設(shè)成本為上1個(gè)VMS總建設(shè)成本的g倍，(0

(7)

式中：V為VMS的數(shù)量。

VMS的效用達(dá)到最大、建設(shè)成本達(dá)到最小是理想的目標(biāo)，而效用函數(shù)和成本函數(shù)的變化趨勢(shì)是相互抵觸的，因此本文采用VMS效用函數(shù)與成本函數(shù)之比的形式作為模型的目標(biāo)函數(shù)[26]，即

(8)

s.t.Za∈{0,1}

(9)

(10)

式中：H為最終目標(biāo)函數(shù)的值；M，m分別為VMS布設(shè)數(shù)量的上限和下限；A為路徑r上路段a的集合。

2.2 求解算法

遺傳算法是一種通過模擬生物進(jìn)化過程尋求函數(shù)最優(yōu)解的方法，應(yīng)用選擇、交叉、變異等操作逐漸繁衍選擇適應(yīng)度高的個(gè)體，淘汰適應(yīng)度低的個(gè)體，最終得到最優(yōu)解種群[27]。遺傳算法已經(jīng)廣泛應(yīng)用于許多科技領(lǐng)域，但其容易收斂到局部最優(yōu)解的缺陷(即“早熟”現(xiàn)象)仍是一個(gè)待解決的關(guān)鍵問題。針對(duì)此問題，在選擇方式以及變異概率的選取上對(duì)遺傳算法進(jìn)行了改進(jìn)。

1) 傳統(tǒng)的遺傳算法最常用的選擇方式為輪盤賭選擇法，該方法按照個(gè)體適應(yīng)度的大小在總適應(yīng)度中所占的比例選擇父代，這樣容易造成適應(yīng)度值大的個(gè)體占據(jù)種群，導(dǎo)致后期個(gè)體適應(yīng)度相差不大而停止進(jìn)化[28]，因此，改進(jìn)了原有的選擇方式，采用一種基于適應(yīng)度大小排序的選擇方法代替輪盤賭選擇法。

2)在設(shè)計(jì)算法時(shí)，變異概率的選取十分重要，傳統(tǒng)的遺傳算法變異概率為定值，且數(shù)值的選擇大多依靠經(jīng)驗(yàn)。當(dāng)變異概率的值很小時(shí)，群體穩(wěn)定性好，但產(chǎn)生新個(gè)體的能力差，容易出現(xiàn)“早熟”現(xiàn)象；當(dāng)變異概率的值較大時(shí)，又會(huì)破壞種群中的優(yōu)良模式，改變遺傳算法固有的搜索機(jī)制，使遺傳算法淪為隨機(jī)搜索算法[29]，因此采用動(dòng)態(tài)變異概率。動(dòng)態(tài)變異概率指的是在算法運(yùn)行過程中變異概率不再是一個(gè)定值，而是會(huì)根據(jù)適應(yīng)度大小的變化而變化，即當(dāng)適應(yīng)度的值在迭代過程中不會(huì)再增大時(shí)提高變異概率的取值，使算法能夠跳出局部最優(yōu)解。變異概率的選取受種群大小、染色體長(zhǎng)度等因素的影響，一般取值在0.01～0.2之間，因此采用分段函數(shù)形式描述變異概率公式[30]，具體見式(11)。

(11)

式中：x為連續(xù)未發(fā)現(xiàn)更高適應(yīng)度個(gè)體的代數(shù)。

當(dāng)?shù)^20代都沒有發(fā)現(xiàn)更高適應(yīng)度的個(gè)體時(shí)，應(yīng)增大變異概率以使算法能夠跳出局部最優(yōu)解，此時(shí)將變異概率設(shè)定為0.2。一旦跳出了局部最優(yōu)解，變異率將重新回到較低水平。

改進(jìn)后的遺傳算法求解步驟如下

1) 編碼和產(chǎn)生初始群體。采用二進(jìn)制的編碼方式，由于備選路段有9條，因此用長(zhǎng)度為9的二進(jìn)制編碼串來表示決策方案。每個(gè)基因?qū)?yīng)一條路段，基因?yàn)?時(shí)代表在相應(yīng)路段上布設(shè)VMS，為0時(shí)代表不布設(shè)。隨機(jī)產(chǎn)生初始種群，種群中的每個(gè)個(gè)體是由基因組成的染色體。

2) 計(jì)算個(gè)體適應(yīng)度值。算法中以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代的概率，由于模型定義的目標(biāo)函數(shù)連續(xù)、非負(fù)且取最大值，所以直接根據(jù)模型定義的目標(biāo)函數(shù)，定義算法中的適應(yīng)度函數(shù)，并計(jì)算每個(gè)方案的函數(shù)適應(yīng)度值。

3) 選擇。使用基于適應(yīng)度大小排序的選擇方法，首先將初始種群中的個(gè)體按照適應(yīng)度大小進(jìn)行排序，然后將排在前1/3的個(gè)體復(fù)制2份，中間1/3的個(gè)體復(fù)制一份，后1/3的個(gè)體不復(fù)制，由此產(chǎn)生父代種群，體現(xiàn)了遺傳算法優(yōu)勝劣汰的原則。

4) 交叉。計(jì)算出群體中各個(gè)個(gè)體的選擇概率后，為了進(jìn)行后續(xù)的交叉操作，需進(jìn)行多輪選擇，且每一輪產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)作為選擇指針來確定被選個(gè)體。個(gè)體被選后隨機(jī)地組成交配對(duì)，設(shè)定交叉概率Pc，采用單點(diǎn)交叉的方式隨機(jī)地交換選中個(gè)體中相同位置的某些基因，產(chǎn)生新的基因組合即新的個(gè)體。

5) 變異。在所有的個(gè)體一樣時(shí)，交叉是無法產(chǎn)生新個(gè)體的，這時(shí)就要依靠變異產(chǎn)生新的個(gè)體。傳統(tǒng)的遺傳算法中變異概率設(shè)為一個(gè)定值，改進(jìn)的遺傳算法中根據(jù)式(11)計(jì)算變異概率，對(duì)個(gè)體的每一個(gè)或者幾個(gè)基因位做變異操作產(chǎn)生新的個(gè)體，即由1變成0或者由0變?yōu)?。最后由產(chǎn)生的新個(gè)體組成新的種群。

6) 終止。達(dá)到規(guī)定的迭代次數(shù)后終止運(yùn)算，以進(jìn)化過程中得到的具有最大適應(yīng)度值的個(gè)體作為最優(yōu)解輸出。

3 實(shí)例分析

3.1 問題描述

以西安市南二環(huán)路及其周邊道路組成的路網(wǎng)作為研究對(duì)象。西安市南二環(huán)路為城市快速路，東起沙坡立交橋，西止豐登南路，全長(zhǎng)10.79 km，研究區(qū)域如圖2所示。通過調(diào)研，南二環(huán)路共有9處放置了VMS，其具體布設(shè)位置見表1。

表1 西安市南二環(huán)VMS布設(shè)現(xiàn)狀

考慮到路網(wǎng)的復(fù)雜性，將南二環(huán)路附近主要道路組成的路網(wǎng)進(jìn)行簡(jiǎn)化，并對(duì)路網(wǎng)中的交叉口和路段分別按順序編號(hào)，簡(jiǎn)化后的路網(wǎng)如圖3所示。為研究方便，本文只研究南二環(huán)路上由西向東方向VMS布設(shè)位置的優(yōu)化問題。

圖2 研究區(qū)域Fig.2 Research area

圖3 南二環(huán)路區(qū)域路網(wǎng)Fig.3 Road network in the Southern Second Circular Road

由圖3可見，研究路網(wǎng)由30個(gè)交叉口和71條路段組成，交叉口編號(hào)為(1)～(30)，路段編號(hào)為1～71。A代表南二環(huán)路路徑起點(diǎn)，B代表南二環(huán)路路徑終點(diǎn)。結(jié)合當(dāng)前南二環(huán)路VMS的布設(shè)現(xiàn)狀，本文假設(shè)路段10～18為VMS布設(shè)的備選路段，每條路段的流量和擁堵指數(shù)見表2。

表2 路段流量、交通擁堵指數(shù)

假設(shè)每1條路段有2條可替代路徑，即駕駛?cè)嗽诳吹絍MS信息后會(huì)做出2種選擇：保持當(dāng)前路徑不變(保持直行)；選擇替代路徑(左轉(zhuǎn)或者右轉(zhuǎn))。其中，假設(shè)誘導(dǎo)比率中駕駛?cè)耸躒MS誘導(dǎo)作用影響而左轉(zhuǎn)、右轉(zhuǎn)的分流率α分別為10%[7]，可替代路徑相對(duì)于原始路徑的誘導(dǎo)比率修正系數(shù)b的具體數(shù)據(jù)如表3所示。

表3 基于不同道路等級(jí)的誘導(dǎo)比率修正系數(shù)

從表3可以看出，對(duì)角線上的系數(shù)為1，表明駕駛?cè)诉x擇不改變路徑出行其誘導(dǎo)比率修正系數(shù)為1；對(duì)角線上方系數(shù)小于1，表明駕駛?cè)擞僧?dāng)前行駛路徑轉(zhuǎn)向較低等級(jí)道路對(duì)誘導(dǎo)產(chǎn)生的是負(fù)影響；對(duì)角線下方系數(shù)大于1，表明駕駛?cè)擞僧?dāng)前行駛路徑轉(zhuǎn)向較高等級(jí)道路對(duì)誘導(dǎo)產(chǎn)生的是正影響[18]。

根據(jù)以上參數(shù)和前文定義，可計(jì)算出路段10～18的可替代路徑的誘導(dǎo)比率以及繞行時(shí)間，具體數(shù)據(jù)見表4。

3.2 模型求解

根據(jù)西安市南二環(huán)路的區(qū)域路網(wǎng)及相關(guān)數(shù)據(jù)，分別采用傳統(tǒng)的遺傳算法和改進(jìn)的遺傳算法求解上述模型。算法的編碼方式采用二進(jìn)制編碼，有9條備選路段，染色體長(zhǎng)度為9。當(dāng)路段上布設(shè)VMS時(shí)，相應(yīng)的基因值為1，否則為0，由于備選路段為10～18，則染色體“100100100”表示在路段10，13，16上布設(shè)VMS，適應(yīng)度函數(shù)即為選址模型中的目標(biāo)函數(shù)。傳統(tǒng)的遺傳算法的參數(shù)設(shè)置如下：種群規(guī)模為100，交叉概率為0.8，變異概率為0.01。在改進(jìn)的遺傳算法中，選擇方式如前文所述，變異概率計(jì)算公式見式(11)，在保證群體穩(wěn)定性的基礎(chǔ)上避免陷入局部最優(yōu)解，提高解的質(zhì)量。

表4 誘導(dǎo)比率和繞行時(shí)間

假設(shè)布設(shè)1個(gè)VMS的成本C為1萬元，θ取0.6，g取0.8，放置VMS的個(gè)數(shù)為2～6個(gè)。根據(jù)以上設(shè)置的參數(shù)和相關(guān)數(shù)據(jù)運(yùn)行算法，可以得到種群中每個(gè)布設(shè)方案的初始適應(yīng)度值，然后進(jìn)行選擇、交叉、變異等步驟，迭代100次之后，結(jié)果發(fā)現(xiàn)2種算法在布設(shè)相同數(shù)目的VMS時(shí)得到的結(jié)果相同，具體結(jié)果如表5所示。

表5 不同數(shù)目VMS的函數(shù)適應(yīng)度值及其最優(yōu)布設(shè)路段

從表5可見：2種算法得出的結(jié)論都是隨著VMS數(shù)量的增加，函數(shù)適應(yīng)度值呈現(xiàn)出先增加后減少的趨勢(shì)，可見VMS的布設(shè)數(shù)量達(dá)到一定程度后其效用達(dá)到最大，隨著VMS數(shù)量的增加其建設(shè)成本也增加，導(dǎo)致VMS產(chǎn)生的總體效益隨之下降；無論是傳統(tǒng)的遺傳算法，還是改進(jìn)的遺傳算法，當(dāng)設(shè)置4塊VMS時(shí)，函數(shù)的適應(yīng)度值達(dá)到最大，為44.8872，此時(shí)最優(yōu)解為100101010，即在路段10，13，15，17上布設(shè)VMS可以得到最大的效益。

為了直觀地了解2種遺傳算法的求解能力，將2種遺傳算法以總迭代次數(shù)為100次重復(fù)運(yùn)行50次后，從函數(shù)適應(yīng)度值、搜索到最優(yōu)解的迭代次數(shù)以及重復(fù)運(yùn)行50次其中局部收斂的次數(shù)和局部收斂概率這幾個(gè)因素對(duì)2種算法進(jìn)行對(duì)比，對(duì)比結(jié)果見表6。其中函數(shù)適應(yīng)度值和迭代次數(shù)為算法重復(fù)運(yùn)行50次的平均值。

表6 2種遺傳算法的求解能力對(duì)比

從表6可以得到以下結(jié)論。

1) 算法重復(fù)運(yùn)行50次后改進(jìn)的遺傳算法所得到的最優(yōu)解的平均值較傳統(tǒng)的遺傳算法所得到的最優(yōu)解的平均值大，更接近表5中得出的最優(yōu)函數(shù)適應(yīng)度值，因此文中改進(jìn)的遺傳算法求解的精確度更高。

2) 改進(jìn)選擇方式和變異概率后迭代次數(shù)由67次減小到35次，可以看出改進(jìn)后的遺傳算法收斂速度更快。

3) 在傳統(tǒng)的遺傳算法重復(fù)運(yùn)行的50次之中有21次函數(shù)陷入局部最優(yōu)解，改進(jìn)算法后只有6次陷入局部最優(yōu)解，局部收斂概率遠(yuǎn)小于傳統(tǒng)遺傳算法，說明改進(jìn)的遺傳算法既保證了群體穩(wěn)定性又能很好地避免函數(shù)出現(xiàn)“早熟”現(xiàn)象。

3.3 與現(xiàn)狀比較

根據(jù)圖2可知，南二環(huán)路由西向東方向共有4處放置了VMS，分別布設(shè)在路段10，12，16，18。當(dāng)布設(shè)4塊VMS且放置在路段10，12，16，18上時(shí)，函數(shù)適應(yīng)度值為42.937 6，小于本文得出的最大函數(shù)適應(yīng)度值44.887 2，即VMS設(shè)置在路段10，13，15，17。這主要是因?yàn)槁范?2，16的可替代路徑繞行時(shí)間較長(zhǎng)，且路段18的可替代路徑為等級(jí)較低的次干路，與其他路段相比，其誘導(dǎo)比率較小。由此可見，可替代路徑的繞行時(shí)間和誘導(dǎo)比率對(duì)VMS的選址有重要影響，進(jìn)一步驗(yàn)證了本文構(gòu)建模型的有效性，并且為優(yōu)化南二環(huán)路VMS的布局選址提供了理論支撐。

4 結(jié)束語

1) 依據(jù)VMS的選址原則以及VMS選址的影響因素，在前人研究的基礎(chǔ)上，對(duì)原始的單目標(biāo)選址規(guī)劃模型進(jìn)行了改進(jìn)，增加可替代路徑的誘導(dǎo)比率和繞行時(shí)間兩個(gè)因素對(duì)VMS選址的影響，構(gòu)建了以VMS效用最大和總成本最小為目標(biāo)的雙目標(biāo)規(guī)劃模型。

2) 采用改進(jìn)的遺傳算法求解模型，并結(jié)合西安市南二環(huán)路的VMS布設(shè)情況，對(duì)南二環(huán)路的VMS選址進(jìn)行優(yōu)化分析，結(jié)果表明：布設(shè)4塊VMS時(shí)可以獲得最佳的布設(shè)效果，最佳布設(shè)路段為10，13，15，17；同時(shí)，改進(jìn)的遺傳算法與傳統(tǒng)的遺傳算法相比，算法的精確度更高、收斂速度更快，在一定程度上避免了陷入局部最優(yōu)搜索。

3) 得出的VMS最優(yōu)布設(shè)情況與南二環(huán)路VMS的布設(shè)現(xiàn)狀相比，布設(shè)路段的繞行時(shí)間更短、誘導(dǎo)比率更大，因此函數(shù)適應(yīng)度值更大、布設(shè)效果更好，可以為優(yōu)化南二環(huán)路VMS的布局選址、改善當(dāng)前的交通擁堵狀況提供科學(xué)、合理的依據(jù)。

4) 只研究了南二環(huán)路由西向東方向VMS的布設(shè)情況，VMS選址的備選路段不夠充足，且沒有考慮在誘導(dǎo)信息影響下不同分流率對(duì)VMS選址的影響，這將是以后研究的重點(diǎn)方向。