董潔霜， 王偉智， 劉魏巍

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

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

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

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

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

1 目標函數(shù)

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

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

單向交通重組優(yōu)化問題的本質(zhì)是尋找單行道的最優(yōu)方向子集s0＊，目標函數(shù)為

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

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

1.1 目標函數(shù)計算

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

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

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

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

式中，rk表示從圖1中點A＝1經(jīng)過k次循環(huán)到點B＝5.

設(shè)途經(jīng)點數(shù)量上限L＝15，因此，I1，5（rk，s）＝3k＋2≤15，k≤13／3，取k＝4，得

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

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

1.2 目標函數(shù)近似計算

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

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

式（1）可以改寫為

圖2 不同機動車數(shù)量下的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 多目標和聲搜索算法

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

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

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

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

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

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

3 案例應(yīng)用

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

3.1 蒙特卡羅算法比較

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

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

b.計算式（3），應(yīng)用Dijkstra算法獲得A→B途經(jīng)節(jié)點數(shù)量的最小值.

c.根據(jù)步驟b的輸出結(jié)果，構(gòu)造屬于A→B的最優(yōu)路徑的單向邊方向集.

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

e.根據(jù)步驟d的輸出結(jié)果，構(gòu)造屬于B→A的最優(yōu)路徑的單向邊方向集.

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

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

3.2 算例檢驗

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

表1 多目標HS算法相關(guān)參數(shù)建議值Tab.1 The suggested parameters utilized for multi－objective HS algorithm

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

表2 GCA算法與HS算法關(guān)于hmin（·）結(jié)果對比表Tab.2 Satistics for hmin（·）obtained by GCA and HS heuristics

表3 GCA算法與HS算法關(guān)于f（·）結(jié)果對比表Tab.3 Statistics for f（·）obtained by GCA and HS heuristics

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

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

圖3表示各算例應(yīng)用HS算法得到的Pareto前沿近似結(jié)果和有向結(jié)構(gòu)圖.d為距離.

圖3 優(yōu)化結(jié)果及有向結(jié)構(gòu)圖Fig.3 Optimization result and graph for the solution

3.3 實例檢驗

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

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

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

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

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

圖6 關(guān)于ROWTOP實例的Pareto前沿近似結(jié)果Fig.6 Pareto front approximations of real instance obtained in ROWTOP

4 結(jié) 論

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

［1］ 董潔霜.港口集疏運系統(tǒng)優(yōu)化模型［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］ 史峰，黃恩厚，陳群，等.城市微循環(huán)交通網(wǎng)絡(luò)中單行交通組織優(yōu)化［J］.交通運輸系統(tǒng)工程與信息，2009，9（4）：30－35.

［8］ 龍東方，史峰，王英姿.基于道路負荷與公平性的單向交通組織優(yōu)化［J］.交通運輸系統(tǒng)工程與信息，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］ 劉思遠，柳景青.一種新的多目標改進和聲搜索優(yōu)化算法［J］.計算機工程與應(yīng)用，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.