基于邊介數的大城市公交網絡優化模型

大城市交通擁堵問題是目前研究的熱點，它對居民出行影響越來越大.從北京、廣州等大城市的交通現狀看，無法在短期內得到有效解決.很多國內外專家就擁堵問題對復雜網絡理論進行了研究［1－2］，它是研究復雜網絡的有力工具.吳建軍等對城市交通系統的復雜性進行了研究，提出緩解交通擁堵的策略和運輸網絡級聯失效的預防策略［3］;Motter等引入介數定義節點的負荷，提出一種級聯失效模型［4］;Yan G等為控制通信網絡中的信息堵塞和改善網絡信息傳遞效率，提出基于節點度的廣義路由算法［5］;Wang W X等提出集成動靜態信息的混合路由算法［6］和基于本地信息的路由策略［7］;這些算法和策略是在通信網絡特征基礎上提出和論證的，是為研究方便，假設所有節點(路由器)數據處理能力相同，邊權都為1，最短路為邊數最少的路徑，顯然這與交通網絡特征不符.

因此，本文結合公交網絡優化設計的實際，在分析居民出行策略的基礎上，應用復雜網絡理論，提出基于邊介數的大城市公交網絡優化模型及其實現算法.它同時考慮了不同的路段權重和節點處理能力，并對協調參數β最優值進行了深入分析和求解.

1 居民出行策略分析

在日常出行中，居民一般以最短路策略選擇路徑到達目的地.中小城市最短路策略是有效的，在大城市出行需求量較大，集中在最短路會造成交通擁堵嚴重，使最短路出行時間變長，成為非最短路或無法通行的路徑.居民的這種出行策略是目前大城市交通擁堵的主要原因之一.

對于選擇小汽車、出租車等方式出行的居民，可根據經驗和當時的情況，重新選擇出行路徑，繞過交通擁堵點，這樣雖然相對最短路繞遠了，但是縮短了由于交通擁堵損失的時間.城市公交車是按照固定站點、固定線路和固定時刻表為居民提供服務的交通方式，在發生交通擁堵時，無法重新選擇路徑，只能在公交網絡優化設計時，融合繞行策略，繞過交通擁堵點，實現重新選擇路徑的目的.

繞行策略是在公交網絡優化設計時，使公交車能適時繞過這樣的擁堵節點，使居民公交出行時間變短，線路準點率提高.它是以犧牲一部分公交網絡效率為代價換取居民公交出行成本的降低.

2 拓展邊介數

為使公交網絡優化設計時實現繞行策略，應用復雜網絡理論中的邊介數識別交通擁堵.邊介數為網絡中所有經過該邊的最短路徑數量與最短路徑總數之比［8］.為適應公交網絡特征，引入參數β，將邊介數進行拓展.

定義1有效邊介數定義為對于給定的參數β，網絡中所有經過該路段的最短路徑數量與最短路徑總數之比.記作Bβ(i)，則

其中:Bβ(i)為路段i的有效邊介數，njk為節點(j，k)之間最短路徑的數量，njk(i)為節點(j，k)之間最短路徑中經過路段i的數量，β為協調參數，V為網絡中全部節點的集合.

定義2規定L(p(s→t):β)為對于給定參數β，節點(s，t)之間路徑的長度，則節點(s，t)之間的有效路徑是使L(p(s→t):β)值最小的路徑.其中L(p(s→t):β)=，N 為路徑p(s→t)包含的路段總數，r(i)為路段i的阻抗，s.顯然搜索有效路徑時，路段i的有效權重為Bβ(i)r(i)，它是在有效邊介數的基礎上建立的，在有效路徑上布設的公交線路就是有效線路，有效線路形成的公交網絡就是有效網絡.

根據復雜網絡理論和有效路徑的定義，協調參數β在這里表征有效路徑偏離擁堵節點的程度.當β=0時，有效路徑為網絡最短路，即居民出行為最短路策略;當β＞0時，有效路徑開始偏離擁堵節點，部分居民出行時采取繞行策略;當β＜0時，有效路徑更傾向于經過樞紐節點，即居民出行易先到樞紐站點換乘.由此可知，參數β變化過程模擬了居民出行策略的變化，當β＞0時，有效路徑體現了居民出行應用繞行策略的情況，參數的大小體現了居民出行繞行的程度，最優參數值求解詳見下文.

3 基于邊介數的公交網絡優化模型

為均衡網絡效率和居民出行時間，在搜索有效路徑的基礎上，應保證公交網絡運輸效率最大化，因此，目標函數為兩個:1)L(p(s→t):β)值最小化;2)公交網絡運輸效率最大化.

L(p(s→t):β)最小時的有效路徑在β＞0時模擬了居民出行時采用繞行策略的情況，應用繞行策略優化的目的就是使所有公交乘客出行時間縮短.目標函數表達式為

繞行策略使公交車運行過程中，會繞過介數較大的節點，它們一般都是相對重要的節點或樞紐站點，若過多乘客繞過，必然會使公交網絡運輸效率低下.為使公交網絡運輸效率最大化，設計目標函數表達式為

其中:Z為公交網絡運輸效率，人次/s;xij為線路i上路段j的公交客流量，人次;rij為線路i上路段j的阻抗，s.

單條線路的約束條件包括線路長度，路線非直線系數，路線客運能力，復線條數等.整個線網的約束條件包括線網密度，乘客換乘系數，站點覆蓋率，線網覆蓋率等.它們的計算可參考文獻［9-10］，從而建立公交網絡優化模型.

4 優化模型算法實現

建立的公交網絡優化模型為雙目標規劃模型，大城市公交網絡比較復雜，采用解析法求最優解計算量較大，有些模型可能不存在唯一的最優解．因此，本文提出一種操作性較強的算法，計算過程較為直觀，可控性較強．

4.1 搜索備選線路集

計算路網中各個路段的有效權重，基于繞行策略，應用帶約束條件的k最短路算法搜索備選線路集，其算法如下:1)取一起終點對(s，t)，應用Dijkstra法搜索它們之間的最短路徑sp1，檢驗sp1是否滿足線路長度約束，若滿足則將sp1作為備選線路，并取下一起終點對進行搜索備選線路，否則轉入下一步，其中spk表示k最短路徑．2)當確定spk-1時搜索spk，對Vs中的點進行標號和更新，取一點h，它的標號值為 Ph=，則 Sk=并確定spk．若Ph=Sk且spk過點h，則更新h的標號，更新公式與標號公式相同;若該點已沒有鄰接點，則標號更新為無窮大．其中Vm為m最短路徑經過的點集合為最短路鄰接點集合，Li為節點i到起點s的最短距離，Lij為鄰接點i、j之間的距離，Sm為m最短路徑的長度．3)檢驗spk是否滿足線路長度約束，若滿足則將其作為備選線路;否則返回步驟2．4)檢查是否是最后一對起終點，若是則得到備選線路集合SP，否則返回步驟1．

這樣基于繞行策略得到備選線路集合SP，根據參數β取值，部分路徑可繞過交通擁堵點，因此備選線路集合中的線路都是有效線路．

4.2 有效線路布設

根據目標函數，采用效率最大化原則布設有效線路．分別計算備選線路的運輸效率，將運輸效率最高的備選線路布設在路網中，然后對客流OD矩陣進行更新，其算法思路為:計算線路各個斷面的斷面流量、各個站點流量以及站點容量［11］．1個站點可能同時被多條線路共用，此時，站點流量為經過該站點的各個斷面流量之和．檢驗各個站點流量和站點容量，若各個站點流量均小于站點容量則經過該線路的OD量能全部被運送;若站點流量大于站點容量，則布設的線路只能運送部分客流OD量，具體分為3步．

第1步:確定超載站點集合．選取超載站點遵循就近原則，即線路斷面的超載流量向公交行駛逆方向的站點就近分配，分配流量與各站點的上客量相等(或小于最后一站點上客量)，分配到超載客流的站點就是超載站點．

其中:ΔSl為超載站點l上的超載流量，人次/h;Yl為超載站點l上的背景流量，人次/h;Xl為超載站點l上新增流量，人次/h．

存在實數m滿足

其中:Glk為站點k對超載站點l貢獻的流量;qkij為從站點k上車的OD量;(l-p)表示l減去p，其他類似符號同理．

則站點l后的(m-1)個站點上車經過站點l的OD全部留剩，站點(l-m)上車經過站點l的OD部分留剩．站點l后m個站點進入超載站點集合Vs．

第2步:確定站點(l-m)的OD更新量．在同一站點(l-m)的乘客，具有同等上車的權利，同時具有同等留剩的機會．所以站點(l-m)的OD更新量計算公式為

其中:Qlij-m為從站點(l-m)上車，為超載站點l貢獻的客流量．

第3步:某些站點可能是多個超載站點的貢獻者，取站點OD更新量時，為保證全部站點均不超載，每一OD留剩量取它在線路上各站點留剩量的最大值，即OD矩陣［i，j］更新值為

OD矩陣更新完畢，重新搜索備選線路和布設有效線路，直到所有的起始點對都布設一條有效線路，再進行逐步的調整優化，得到滿足線路約束的有效網絡．

5 確定最優參數β

5.1 參數分析

根據前面的分析可知，參數β與居民出行時間之間的函數關系曲線應為先下降再上升．當發生交通擁堵時，部分居民采取繞行策略，偏離樞紐節點可繞過交通擁堵點，這時可縮短居民出行時間;隨著參數β的逐漸增大，居民出行路徑逐漸偏離擁堵點，離交通擁堵點越來越遠，居民出行時間就越來越短;當參數β達到一個臨界值βc時，居民出行路徑偏離交通擁堵點縮短的時間與居民繞遠增加的時間相等．當參數β繼續變大時，居民總的出行時間開始逐漸增加．

顯然，參數β的最優值與實際網絡和城市交通擁堵程度有關，交通擁堵越嚴重，臨界值βc越大．通過分析不同β可觀察繞行策略下居民的出行軌跡，從而驗證該策略在大城市公交網絡優化設計中的合理性．

5.2 參數求解

長春市交通擁堵嚴重，其中主干道人民大街、南湖大路、自由大路、亞泰大街、解放大路、吉林大路等“堵點”較多，其他市區支路交叉口擁堵也較為嚴重．以長春市道路網作為基礎網絡求解參數β的最優值．將長春市劃分為163個交通小區，應用TransCAD搜索并記錄它們之間的有效路徑，經過分析計算可得到各個網絡指標值．

根據反復計算的結果，參數β與擁擠網絡效率E1、平均出行時間的變化趨勢見圖1．從圖中可以看出，當居民平均出行時間最短，網絡效率最高時，β的最優值為0.1．β ＞0時，的變化趨勢與參數分析中的結論一致;β＜0時，有效路徑傾向于經過樞紐站點，由于樞紐站點處理能力較高，增長較慢．越短，E1越高，這與圖中趨勢一致．

參數β與零流網絡效率E0、擁擠網絡效率E1以及由于擁擠造成的效率損失ΔE的變化趨勢見圖3．從圖中可以看出，由于交通擁擠，存在網絡效率損失．相對于E0，E1的峰值右移，β值由0變化增長至0.1．在β=0.1時，損失值急劇減少，這種相變現象是由于繞過交通擁堵產生的積極影響．當β繼續增大時，出行路徑逐漸繞到負荷較低的路段，交通擁堵影響較小，效率損失也逐漸降低．β＜0時，由于樞紐節點發生擁堵，網絡效率損失保持較大的數值．

圖2 不同β與、的變化趨勢圖

圖3 不同β與E0、E1、ΔE的變化趨勢圖

6 結論

1)根據繞行策略優化城市公交網絡，既可充分利用樞紐站的高效處理能力，又可使公交出行適時避開交通擁堵，縮短出行時間，因此可適合在大城市或存在交通擁堵的城市應用．

2)基于邊介數優化的大城市公交網絡可使部分乘客出行時避開交通擁堵點，這將增強網絡對蓄意攻擊的抵抗能力，改善網絡的魯棒性．

3)雙重策略提高公交網絡的可靠性．繞行策略是將公交車作為機動車一種，考慮整個交通系統的擁堵對公交系統的影響;站點容量模型考慮了由于線路運輸能力限制產生的擁堵對公交系統的影響．

4)以長春市路網為基礎求解β最優值，結果表明，最小化網絡平均出行時間、最大化網絡效率可確定β的最優值．

［1］汪小帆，李翔，陳關榮．復雜網絡理論及其應用［M］．北京:清華大學出版社，2006．

［2］PORTA S，CRUCITTI P，LATORA V．The network analysis of urban streets:a dual approach［J］．Environment and Planning B:Planning and Design，2006，33(5):705－725.

［3］吳建軍，高自友，孫會君，等.城市交通系統復雜性:復雜網絡方法及其應用［M］.北京:科學出版社，2010.

［4］MOTTER A E，LAI Y C.Cascade-based attacks on complex networks［J］.Physical Review E，2002，66:65102.

［5］YAN G，ZHOU B，HU B，et al.Efficient routing on complex networks［J］.Physical Review E，2006，73:46108.

［6］WANG W X，YIN C Y，YAN G，et al.Integrating local static and dynamic information for routing traffic［J］.Physical Review E，2006，74:16101.

［7］WANG W X，WANG B H，YIN C Y，et al.Traffic dynamics based on local routing protocol on a scale-free network［J］.Physical Review E，2006，73:26111.

［8］ BOCCALETTI S，LATORA V，MORENO Y，et al.Complex networks:structure and dynamics［J］.Physics Reports，2006，424:175 －308.

［9］王煒，楊新苗，陳學武.城市公共交通系統規劃方法與管理技術［M］.北京:科學出版社，2002.

［10］胡啟洲，鄧衛.城市常規公共交通系統的優化模型與評價方法［M］.北京:科學出版社，2009.

［11］趙淑芝，田慶飛，曹陽.基于站點容量限制的公交效率網絡設計模型［J］.吉林大學學報:工學版，2011，41(增刊1):81－84.