基于多目標和聲搜索算法的城市單向交通組織優化研究

董潔霜， 王偉智， 劉魏巍

（1.上海理工大學管理學院，上海 200093）

在綠色高效的出行要求下，快速高效的城市路網設計成為當下的研究熱點，但是，在有限的經濟條件下，不可能同時進行大規模的交通基礎設施建設［1］，因此，交通部門往往傾向于對現有的道路網進行優化，期望投入較小的成本，實現交通設施的高效運行.

2006年Giridhar等將啟發式算法應用到道路和信號燈設計方面［2］.2008年Pinninghoff等用進化算法解決洛杉磯城市道路網優化問題［3］.2010年Sanchez－Medina等采用遺傳算法解決西班牙某城市交通信號優化問題［4］.2011年Mesbah等應用進化算法求解交通控制優先模型［5］.2011年Sohn應用標優化技術，在對城市交通的影響度最小的前提下，解決了機動車與非機動車交通空間分配問題［6］.

2009年史峰等將城市道路分為干道（較寬、雙向通行）、支路（較窄、單向通行），在減少污染、緩解擁堵的前提下，解決了城市單向交通組織優化問題［7］.2010年龍東方等為了避免支路超負荷，用模擬退火算法代替遺傳算法［8］.

本文闡述一種新的智能算法，用以處理單向交通重組優化問題（ROWTOP），運用多目標和聲搜索算法解決復雜的單向交通重組優化問題，并在案例中與一般算法進行比較分析.

1 目標函數

對于城市主要道路交通受到嚴重影響的區域，單行道組織優化是一種高效的應對措施.使用有向圖G（v，ε，s）表示路網，v代表節點集，ε表示道路集，s（s∈S）表示方向集，S表示道路的可通行方向.本文中道路分為主干路和單行路，因此，｜S｜＝3，方向集是由單行路方向子集s0、主干路方向子集st組成.

有向圖中A，B表示進入點和離去點，A，B∈v，單向交通重組優化問題得到最優的單行路方向集s0，使得A→B的出行時間最短，本文中最短出行時間將采用A→B路徑中的途經點數量表示.

單向交通重組優化問題的本質是尋找單行道的最優方向子集s0＊，目標函數為

式中，IA，B（ri，s）表示車輛沿路徑ri由進入點A到離去點B所途經的節點數量，ri∈R；pi表示車輛選擇路徑ri的概率.

為了避免死循環，需要設定車輛到達離去點之前途經點的最大值，并定義路徑A→B（或B→A）單輛機動車的最小躍點數（一輛機動車在該路徑通行的途徑路段數），使用Dijkstra算法進行求解.假定s＝st（如所有的街道都是雙向的，s0＝?），可以計算躍點數的下限值（A，B，G），顯然，

1.1 目標函數計算

G＋表示由5個節點和5條邊組成的有向圖，如圖1所示，由進入點A＝1至離去點B＝5，躍點數下限值h＋min（1，5，G＋，s）＝2.

圖1 f（·）計算圖Fig.1 Calculation of objective function f（·）

觀察圖1，可以暫定點4、點5是離去點，一輛車將由A出發，可能在點5離開路網，也可能在點4離開路網.第一種情況下，最短路徑由點1出發途經點3直接到點5，概率為p0＝p12p35（pij為從i→j的概率），在同樣情況下，經過k次循環1→3→2→1后到達點5離開，其概率為

在不計損失的情況下，某點到其相鄰點的概率是相同的，p13＝1，p32＝1／2，p21＝1.

式中，rk表示從圖1中點A＝1經過k次循環到點B＝5.

設途經點數量上限L＝15，因此，I1，5（rk，s）＝3k＋2≤15，k≤13／3，取k＝4，得

第二種情況是車輛經過k次1→3→2循環后到達離去點4，每條路徑的概率為

由上可得，到達離去點B＝4的概率為

1.2 目標函數近似計算

為了降低計算的復雜程度，使用蒙特卡羅模擬方法估算函數值，N輛機動車從點A出發選擇路徑ri到達點B，而pi等于車輛數目Ni與N（N→∞）的比值，即

式中，N代表從點A出發到達點B的所有機動車數量；Ni代表從點A出發選擇路徑ri到達點B的機動車數量.

式（1）可以改寫為

圖2 不同機動車數量下的f＋min（1，5，G＋，s）估計值變化圖Fig.2 Example of objective function estimation f＋min（1，5，G＋，s）using different number of vehicles N

2 多目標和聲搜索算法

應用合理的多目標搜索方法能夠生成雙目標函數的平衡解，本文中選取新的多目標計算方法——和聲搜索算法（Harmony Search）［9－11］，簡稱HS算法.

算法可以概括為以下4個步驟：

a.初始化，過程只在第一次迭代中進行.首先生成和聲記憶庫雙向道路的值為2，其它單行路值從｛0，1｝中隨機選取，為避免斷路，要求每一個節點至少有一條出路.

b.創作，對si（k）≠2的音調采取3種不同的概率方式產生新解集，生成新的解集（K集），概率分別為和聲記憶搜尋率（HMCR）、記憶調整率（PAR）、隨機選擇率（RSR）.

c.在尋求合適的f（A，B，G，s）與f（B，A，G，s）目標下，每次迭代都會產生優于之前的結果，最重要的是和聲記憶中儲存的是非支配排序解，同時有助于Pareto最優收斂.首先，音調順序與其非支配水平相關聯（1最好，2次之，等）；然后，群聚距離表示與每個目標值最鄰近的間距之和，依據群聚距離定義每個元素的順序，為了覆蓋目標總體空間，每個解間必須有一定的間距；最終，和聲記憶庫中儲存經過篩選的最優K集［12］.

d.當達到最大迭代次數T時計算停止，第一非支配水平的解集表示Pareto前沿近似結果；如果未達到迭代次數T，則會返回步驟b繼續計算新的K集.

3 案例應用

為了評估多目標和聲搜索算法的性能，在一定數量不同規模的ROWTOP算例和實際案例中進行驗證性對比分析.

3.1 蒙特卡羅算法比較

為了評估HS算法性能，與蒙特卡羅算法進行對比，蒙特卡羅算法是智能交通優化中較為常用的一種算法.蒙特卡羅算法步驟如下：

a.首先清空圖G中的單向邊的方向，假設每條邊可以是任意唯一方向.

b.計算式（3），應用Dijkstra算法獲得A→B途經節點數量的最小值.

c.根據步驟b的輸出結果，構造屬于A→B的最優路徑的單向邊方向集.

d.計算式（4），再次應用Dijkstra算法獲取B→A的途經節點數量最少的路徑，在步驟c中已確定方向的單向邊在本步中不參與計算.

e.根據步驟d的輸出結果，構造屬于B→A的最優路徑的單向邊方向集.

f.從步驟b開始重復，直到不存在其它A→B（或B→A）的路徑.

通過迭代計算得到單向邊方向集，從而確定最優路徑.在迭代過程中，包含單向邊的最優路徑在下一次的搜尋過程中將被剔除，因此，這是一種貪婪式的局部最優構建方法（GCA）.雖然此方法比較簡易，但仍是檢驗多目標和聲算法性能的合理參考算法.GCA算法既不是隨機的，也不是多目標的，然而，f（·）近似值、（A，B）或（B，A）方向集的最小躍點數可以用來作為評價標準.

3.2 算例檢驗

首先用隨機生成的有向圖｛Gi（v，ε，s）｝4i＝1表示不同的ROWTOP算例，改變節點數量、邊、進入點、離去點進行多次計算，構造網絡節點圖（SLG），系數α和β分別設為100和3能夠滿足實驗需求，表1中給出了相關參數參考值.

表1 多目標HS算法相關參數建議值Tab.1 The suggested parameters utilized for multi－objective HS algorithm

表2和表3列出了SLG算例的結果，算法輸出的是單向交通重組優化問題算例的Pareto前沿估計結果，得到的每個要素值f（A，B，G，s），f（B，A，G，s），hmin（A，B，G，s），hmin（B，A，G，s）是經過30次的算法獨立運算的估計值，雙向平衡策略簡稱為ROB，整體Pareto最優前沿估計值表示為ULT.

表2 GCA算法與HS算法關于hmin（·）結果對比表Tab.2 Satistics for hmin（·）obtained by GCA and HS heuristics

表3 GCA算法與HS算法關于f（·）結果對比表Tab.3 Statistics for f（·）obtained by GCA and HS heuristics

表2列出了GCA算法和HS算法的最少途經點hmin（·）統計結果，也包括h＋min（·）（即在不進行單行限制的情況下（A，B）途經點的最小值）.GCA算法尋找正向最短路徑過程中途徑點更接近于h＋min（·）值，但是，對于逆向（B，A）的計算效果卻很差.

表3中f（·）的統計結果能夠體現算法的實際性能，因為，f（·）表示路網中加入交通流的復雜情況下的計算結果.HS方法得到的路線使得平均途經點數量盡可能少，雖然在算例中ROB和ULT統計的f（A，B，G，s）平均值可能會比GCA算法得到的f（A，B，G，s）要大，但f（B，A，G，s）的平均值卻明顯小于GCA算法得到的結果.

圖3表示各算例應用HS算法得到的Pareto前沿近似結果和有向結構圖.d為距離.

圖3 優化結果及有向結構圖Fig.3 Optimization result and graph for the solution

3.3 實例檢驗

為了驗證算法的可行性，現選取某市區為研究范圍，每天在早高峰時間，大量的商家在這里進行交易，道路資源的占用，導致了嚴重的交通矛盾.研究范圍內單行支路比較豐富，但是，缺乏有效的單向交通組織策略，實際路網如圖4所示（見下頁）.

在圖4中用同心圓點表示城區街道的進入和離去端點，點劃線圈內表示受影響嚴重的區域.圖4中共有119個節點，｜v｜＝119.節點1表示來自（到）市南區的進入點（離去點），節點35表示來自（到）市中心的離去點（進入點）.圖5（見下頁）表示經過多目標和聲算法得到的雙向情況下的f（·）最佳平衡值，在該情形下，從點1到點35途經16條線段，從點35點1經過18條線段，將真實的情況用有向圖來解釋，通過式（5）得到的h＋min（·）＝17，揭示了HS算法在尋找最短路徑的優異性能.

圖4 實例路網以及影響范圍Fig.4 Real network and space of influence

圖5 單向交通組織規劃圖Fig.5 Programming diagram of one－way traffic organization

圖6表示進行30次和聲搜索算法后得到的Pareto前沿結果.從圖6可以看出，產生了較寬包絡面，足以說明其平衡性.

圖6 關于ROWTOP實例的Pareto前沿近似結果Fig.6 Pareto front approximations of real instance obtained in ROWTOP

4 結 論

提出了一種多目標和聲搜索的啟發式算法（HS），用以解決城市交通矛盾突發時的單向交通組織問題，并對該問題進行了求解說明，包括2個目標函數以及如何用蒙特卡羅模擬方法求解.描述多目標和聲搜索算法的計算步驟，并與一般算法相比，在不同的算例和實例中驗證了HS算法的平衡性和高效性.通過計算模擬，證實該方法能夠得到近于最優的單行道重組方案，以提高當城市交通沖突發生時路網2節點間的機動車通行性能，減輕部分區域道路阻斷對整個地區的通勤影響.

［1］ 董潔霜.港口集疏運系統優化模型［J］.上海理工大學學報，2007，29（5）：453－456.

［2］ Giridhar A，Kumar P R.Scheduling automated traffic on a network of roads［J］.IEEE Transactions on Vehicular Technology，2006，55（5）：1467－1474.

［3］ Pinninghoff M，Contreras R，Atkinson J.Using genetic algorithms to model road networks［J］.IEEE Computer，2008，41（12）：60－67.

［4］ Sanchez－Medina J J，Galan－Moreno M J，Rubio－Royo E.Traffic signal optimization in“La Almozara”district in saragossa under congestionconditions，using genetic algorithms，traffic microsimulation，and cluster computing［J］.IEEE Transactions on Intelligent Transportation Systems，2010，11（1）：132－141.

［5］ Mesbah M，Sarvi M，Currie G.Optimization of transit priority in the transportation network using agenetic algorithm［J］.IEEE Transactions on Intelligent Transportation Systems，2011，12（3）：908－919.

［6］ Sohn K.Multi－objective optimization of a road diet network design［J］.Transportation Research Part A，2011，45（6）：499－511.

［7］ 史峰，黃恩厚，陳群，等.城市微循環交通網絡中單行交通組織優化［J］.交通運輸系統工程與信息，2009，9（4）：30－35.

［8］ 龍東方，史峰，王英姿.基于道路負荷與公平性的單向交通組織優化［J］.交通運輸系統工程與信息，2010，10（6）：109－114.

［9］ Landa－Torres I，Gil－Lopez S，Salcedo－Sanz S，et al.A novel grouping harmony search algorithm for the multiple－type access node location problem［J］.Expert Systems with Applications，2011，39（5）：5262－5270.

［10］ Geem Z W，Kim J H，Loganathan G V.A new heuristic optimization algorithm：harmony search［J］.Simulation，2001，76（2）：60－68.

［11］ 劉思遠，柳景青.一種新的多目標改進和聲搜索優化算法［J］.計算機工程與應用，2010，46（34）：27－30.

［12］ Deb K，Pratap A，Agrawal S，et al.A fast and elitist multiobjective genetic：NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197.