基于改進遺傳算法的可變信息標志選址優化研究*

張榮輝 馬壯林 黨永樂 徐 婷

(長安大學汽車學院 西安 710064)

0 引 言

可變信息標志(variable message sign，VMS)是先進的出行者信息系統(advanced traveler information systems，ATIS)的重要組成部分，其作為一種有效的群體誘導信息發布系統，向駕駛人提供前方路段的實時路況信息(如擁堵信息、事故信息、行程時間和天氣信息等)，引導駕駛人避開擁堵路段，選擇最合理的出行路徑，達到優化路網車流量時空分布、提高通行效率的目的[1]。目前，VMS已經被廣泛應用于國內外的高速公路和城市快速路，對于緩解交通擁堵、提高路網通行效率起到了不容忽視的作用。但是，這些VMS的布設位置大多依靠當地管理部門的經驗和主觀判斷，無論是VMS的數量，還是VMS的布設位置，都缺乏系統、科學、合理的論證，因此，提出一種系統、科學的VMS選址方法，明晰VMS數量和選址位置對交通流量的誘導效果，對提高整個城市交通誘導系統的效率至關重要。

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

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

上述研究對VMS選址問題的研究進行了深入的探討，但是沒有考慮到可替代路徑對VMS選址的影響，同時也忽略了VMS選址問題是一個綜合的、復雜的、多目標的規劃問題[21]；此外，大多數研究采用傳統的遺傳算法對構建的VMS選址模型進行求解，忽略了其容易出現“早熟”而陷入局部最優解的缺陷。

筆者在上述研究的基礎上，引入可替代路徑的誘導比率和繞行時間2個影響因素，綜合考慮VMS效益和成本的關系，構建VMS效益最大化與成本最小化之比為目標函數的選址模型，采用改進的遺傳算法對模型進行求解，最后結合西安市南二環路的實際交通狀況以及VMS的布設現狀，科學、合理地優化西安市南二環路VMS的布局選址。

1 VMS選址的影響因素分析

VMS的選址原則主要有4點：①應布設在經常發生擁堵或者交通流量較大的路段上游分流口前端的適當位置；②對于城市道路路網而言，在布設VMS時不宜過于密集，避免造成交通信息混亂；③VMS的布設要考慮到其與靜態交通標志的配合和協調，在城市道路中VMS與靜態交通標志至少應相距30 m[22]；④2個連續VMS之間的間距應當合理，保證發布信息內容的準確性和一致性。可見，并不是在每條道路上都布設VMS誘導效果最好，許多道路屬性都會影響布設位置的選擇。根據以上選址原則，筆者歸納總結出VMS選址的影響因素主要體現在以下5個方面。

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

2) 交通擁堵指數。交通擁堵指數(traffic performance index，TPI)是指根據道路通行情況設定的用來定量評價和綜合反映全路網運行狀態(暢通或擁堵)的概念性數值，它把道路交通擁堵狀況采用數量化的形式進行描述，即擁堵指數取值在0至10之間，數值越高，表示交通擁堵狀況越嚴重[23]。常發性交通擁堵信息和因交通事故產生的偶發性交通擁堵信息是VMS向駕駛人提供的重要內容[20]。因此，交通擁堵指數是影響VMS選址的重要因素之一。

3) 信息衰減程度。VMS的信息衰減程度指的是駕駛人在從看到誘導信息的地點行駛到信息發生的地點這一時間段內，VMS發布的誘導信息準確性的衰減程度。布設在某一路段上的VMS顯示的誘導信息為其下游路段的交通狀況，駕駛人看到誘導信息時距離信息發生地越遠，信息的影響程度越弱，甚至在駕駛人到達信息發生地時信息已發生變化[15]，表明VMS發布的誘導信息具有一定的信息衰減程度，這對VMS的選址也具有重要影響。

4)VMS建設成本。VMS的建設成本即為安裝VMS以及后期的運營、維護階段需要花費的成本。VMS的有效性取決于VMS在路網中的安裝位置及安裝VMS的數量。從理論上來講，整個路網都使用VMS時其帶來的效益最大，由于安裝和運營VMS也需要花費一定的成本，因此這是不切合實際的[21]。此外，以往的研究表明，由于駕駛人對實時信息的行為反應，過度使用VMS會使其帶來的效益減小，甚至會產生反作用[24]。

5)可替代路徑的誘導比率和繞行時間。曹亞康[1]認為：駕駛人對出行屬性中的出行距離和可替代路徑最為敏感。可替代路徑是信息發布后引導駕駛人選擇合適的路徑以分散主路交通壓力的前提，而道路等級決定了可替代路徑所能服務的交通量的大小。這就要求當VMS顯示前方道路擁堵時，應有合適的可替代路徑供駕駛人選擇，而且可替代路徑的道路等級應盡量高，繞行時間應盡量短，才能有吸引駕駛人選擇繞行。

筆者提出了誘導比率的定義，即在VMS誘導信息作用下車輛的分流率與不同道路等級的誘導比率修正系數的乘積，其反映了不同等級道路對駕駛人的誘導效果。由于可替代路徑的道路等級對駕駛人是否改變路徑有重要影響，因此不同道路等級的可替代路徑對駕駛人的誘導效果不同[18,25]。可替代路徑上路段的道路等級越高，對駕駛人的誘導影響越顯著，即駕駛人更加偏向于從低等級道路轉向高等級道路行駛，因此在選擇VMS的布設位置時應盡量有較高等級的道路作為可替代路徑。

文中定義繞行時間為每條繞行路段的總長度與其限制速度之比。一般情況下，駕駛人會優先選擇繞行時間短的路徑代替原始路徑。如果繞行時間過長，會嚴重影響駕駛人對誘導信息的服從度，從而降低駕駛人對VMS誘導信息的接受率。因此繞行時間也是VMS選址時應重點考慮的因素之一。

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

2.1 模型構建

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

(1)

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

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

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

f=fra×βra

(2)

(3)

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

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

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

(4)

式中：b為不同道路等級的誘導比率修正系數。

不僅可替代路徑的道路等級對VMS的誘導效用有影響，其繞行時間也會影響駕駛人接受VMS提供的誘導信息，因此，本文引入繞行時間影響因子pra，其計算公式見式(5)。

(5)

式中：Tk為駕駛人在繞行路段k上的行程時間。

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

(6)

式中：Za為一個0-1變量，當路段a上布設了VMS時，Za= 1；反之，Za= 0。

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

(7)

式中：V為VMS的數量。

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

(8)

s.t.Za∈{0,1}

(9)

(10)

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

2.2 求解算法

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

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

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

(11)

式中：x為連續未發現更高適應度個體的代數。

當迭代超過20代都沒有發現更高適應度的個體時，應增大變異概率以使算法能夠跳出局部最優解，此時將變異概率設定為0.2。一旦跳出了局部最優解，變異率將重新回到較低水平。

改進后的遺傳算法求解步驟如下

1) 編碼和產生初始群體。采用二進制的編碼方式，由于備選路段有9條，因此用長度為9的二進制編碼串來表示決策方案。每個基因對應一條路段，基因為1時代表在相應路段上布設VMS，為0時代表不布設。隨機產生初始種群，種群中的每個個體是由基因組成的染色體。

2) 計算個體適應度值。算法中以個體適應度的大小來確定該個體被遺傳到下一代的概率，由于模型定義的目標函數連續、非負且取最大值，所以直接根據模型定義的目標函數，定義算法中的適應度函數，并計算每個方案的函數適應度值。

3) 選擇。使用基于適應度大小排序的選擇方法，首先將初始種群中的個體按照適應度大小進行排序，然后將排在前1/3的個體復制2份，中間1/3的個體復制一份，后1/3的個體不復制，由此產生父代種群，體現了遺傳算法優勝劣汰的原則。

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

5) 變異。在所有的個體一樣時，交叉是無法產生新個體的，這時就要依靠變異產生新的個體。傳統的遺傳算法中變異概率設為一個定值，改進的遺傳算法中根據式(11)計算變異概率，對個體的每一個或者幾個基因位做變異操作產生新的個體，即由1變成0或者由0變為1。最后由產生的新個體組成新的種群。

6) 終止。達到規定的迭代次數后終止運算，以進化過程中得到的具有最大適應度值的個體作為最優解輸出。

3 實例分析

3.1 問題描述

以西安市南二環路及其周邊道路組成的路網作為研究對象。西安市南二環路為城市快速路，東起沙坡立交橋，西止豐登南路，全長10.79 km，研究區域如圖2所示。通過調研，南二環路共有9處放置了VMS，其具體布設位置見表1。

表1 西安市南二環VMS布設現狀

考慮到路網的復雜性，將南二環路附近主要道路組成的路網進行簡化，并對路網中的交叉口和路段分別按順序編號，簡化后的路網如圖3所示。為研究方便，本文只研究南二環路上由西向東方向VMS布設位置的優化問題。

圖2 研究區域Fig.2 Research area

圖3 南二環路區域路網Fig.3 Road network in the Southern Second Circular Road

由圖3可見，研究路網由30個交叉口和71條路段組成，交叉口編號為(1)～(30)，路段編號為1～71。A代表南二環路路徑起點，B代表南二環路路徑終點。結合當前南二環路VMS的布設現狀，本文假設路段10～18為VMS布設的備選路段，每條路段的流量和擁堵指數見表2。

表2 路段流量、交通擁堵指數

假設每1條路段有2條可替代路徑，即駕駛人在看到VMS信息后會做出2種選擇：保持當前路徑不變(保持直行)；選擇替代路徑(左轉或者右轉)。其中，假設誘導比率中駕駛人受VMS誘導作用影響而左轉、右轉的分流率α分別為10%[7]，可替代路徑相對于原始路徑的誘導比率修正系數b的具體數據如表3所示。

表3 基于不同道路等級的誘導比率修正系數

從表3可以看出，對角線上的系數為1，表明駕駛人選擇不改變路徑出行其誘導比率修正系數為1；對角線上方系數小于1，表明駕駛人由當前行駛路徑轉向較低等級道路對誘導產生的是負影響；對角線下方系數大于1，表明駕駛人由當前行駛路徑轉向較高等級道路對誘導產生的是正影響[18]。

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

3.2 模型求解

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

表4 誘導比率和繞行時間

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

表5 不同數目VMS的函數適應度值及其最優布設路段

從表5可見：2種算法得出的結論都是隨著VMS數量的增加，函數適應度值呈現出先增加后減少的趨勢，可見VMS的布設數量達到一定程度后其效用達到最大，隨著VMS數量的增加其建設成本也增加，導致VMS產生的總體效益隨之下降；無論是傳統的遺傳算法，還是改進的遺傳算法，當設置4塊VMS時，函數的適應度值達到最大，為44.8872，此時最優解為100101010，即在路段10，13，15，17上布設VMS可以得到最大的效益。

為了直觀地了解2種遺傳算法的求解能力，將2種遺傳算法以總迭代次數為100次重復運行50次后，從函數適應度值、搜索到最優解的迭代次數以及重復運行50次其中局部收斂的次數和局部收斂概率這幾個因素對2種算法進行對比，對比結果見表6。其中函數適應度值和迭代次數為算法重復運行50次的平均值。

表6 2種遺傳算法的求解能力對比

從表6可以得到以下結論。

1) 算法重復運行50次后改進的遺傳算法所得到的最優解的平均值較傳統的遺傳算法所得到的最優解的平均值大，更接近表5中得出的最優函數適應度值，因此文中改進的遺傳算法求解的精確度更高。

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

3) 在傳統的遺傳算法重復運行的50次之中有21次函數陷入局部最優解，改進算法后只有6次陷入局部最優解，局部收斂概率遠小于傳統遺傳算法，說明改進的遺傳算法既保證了群體穩定性又能很好地避免函數出現“早熟”現象。

3.3 與現狀比較

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

4 結束語

1) 依據VMS的選址原則以及VMS選址的影響因素，在前人研究的基礎上，對原始的單目標選址規劃模型進行了改進，增加可替代路徑的誘導比率和繞行時間兩個因素對VMS選址的影響，構建了以VMS效用最大和總成本最小為目標的雙目標規劃模型。

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

3) 得出的VMS最優布設情況與南二環路VMS的布設現狀相比，布設路段的繞行時間更短、誘導比率更大，因此函數適應度值更大、布設效果更好，可以為優化南二環路VMS的布局選址、改善當前的交通擁堵狀況提供科學、合理的依據。

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