基于邊介數(shù)的大城市公交網(wǎng)絡(luò)優(yōu)化模型

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

因此，本文結(jié)合公交網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的實(shí)際，在分析居民出行策略的基礎(chǔ)上，應(yīng)用復(fù)雜網(wǎng)絡(luò)理論，提出基于邊介數(shù)的大城市公交網(wǎng)絡(luò)優(yōu)化模型及其實(shí)現(xiàn)算法.它同時(shí)考慮了不同的路段權(quán)重和節(jié)點(diǎn)處理能力，并對(duì)協(xié)調(diào)參數(shù)β最優(yōu)值進(jìn)行了深入分析和求解.

1 居民出行策略分析

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

對(duì)于選擇小汽車、出租車等方式出行的居民，可根據(jù)經(jīng)驗(yàn)和當(dāng)時(shí)的情況，重新選擇出行路徑，繞過交通擁堵點(diǎn)，這樣雖然相對(duì)最短路繞遠(yuǎn)了，但是縮短了由于交通擁堵?lián)p失的時(shí)間.城市公交車是按照固定站點(diǎn)、固定線路和固定時(shí)刻表為居民提供服務(wù)的交通方式，在發(fā)生交通擁堵時(shí)，無法重新選擇路徑，只能在公交網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)時(shí)，融合繞行策略，繞過交通擁堵點(diǎn)，實(shí)現(xiàn)重新選擇路徑的目的.

繞行策略是在公交網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)時(shí)，使公交車能適時(shí)繞過這樣的擁堵節(jié)點(diǎn)，使居民公交出行時(shí)間變短，線路準(zhǔn)點(diǎn)率提高.它是以犧牲一部分公交網(wǎng)絡(luò)效率為代價(jià)換取居民公交出行成本的降低.

2 拓展邊介數(shù)

為使公交網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)時(shí)實(shí)現(xiàn)繞行策略，應(yīng)用復(fù)雜網(wǎng)絡(luò)理論中的邊介數(shù)識(shí)別交通擁堵.邊介數(shù)為網(wǎng)絡(luò)中所有經(jīng)過該邊的最短路徑數(shù)量與最短路徑總數(shù)之比［8］.為適應(yīng)公交網(wǎng)絡(luò)特征，引入?yún)?shù)β，將邊介數(shù)進(jìn)行拓展.

定義1有效邊介數(shù)定義為對(duì)于給定的參數(shù)β，網(wǎng)絡(luò)中所有經(jīng)過該路段的最短路徑數(shù)量與最短路徑總數(shù)之比.記作Bβ(i)，則

其中:Bβ(i)為路段i的有效邊介數(shù)，njk為節(jié)點(diǎn)(j，k)之間最短路徑的數(shù)量，njk(i)為節(jié)點(diǎn)(j，k)之間最短路徑中經(jīng)過路段i的數(shù)量，β為協(xié)調(diào)參數(shù)，V為網(wǎng)絡(luò)中全部節(jié)點(diǎn)的集合.

定義2規(guī)定L(p(s→t):β)為對(duì)于給定參數(shù)β，節(jié)點(diǎn)(s，t)之間路徑的長(zhǎng)度，則節(jié)點(diǎn)(s，t)之間的有效路徑是使L(p(s→t):β)值最小的路徑.其中L(p(s→t):β)=，N 為路徑p(s→t)包含的路段總數(shù)，r(i)為路段i的阻抗，s.顯然搜索有效路徑時(shí)，路段i的有效權(quán)重為Bβ(i)r(i)，它是在有效邊介數(shù)的基礎(chǔ)上建立的，在有效路徑上布設(shè)的公交線路就是有效線路，有效線路形成的公交網(wǎng)絡(luò)就是有效網(wǎng)絡(luò).

根據(jù)復(fù)雜網(wǎng)絡(luò)理論和有效路徑的定義，協(xié)調(diào)參數(shù)β在這里表征有效路徑偏離擁堵節(jié)點(diǎn)的程度.當(dāng)β=0時(shí)，有效路徑為網(wǎng)絡(luò)最短路，即居民出行為最短路策略;當(dāng)β＞0時(shí)，有效路徑開始偏離擁堵節(jié)點(diǎn)，部分居民出行時(shí)采取繞行策略;當(dāng)β＜0時(shí)，有效路徑更傾向于經(jīng)過樞紐節(jié)點(diǎn)，即居民出行易先到樞紐站點(diǎn)換乘.由此可知，參數(shù)β變化過程模擬了居民出行策略的變化，當(dāng)β＞0時(shí)，有效路徑體現(xiàn)了居民出行應(yīng)用繞行策略的情況，參數(shù)的大小體現(xiàn)了居民出行繞行的程度，最優(yōu)參數(shù)值求解詳見下文.

3 基于邊介數(shù)的公交網(wǎng)絡(luò)優(yōu)化模型

為均衡網(wǎng)絡(luò)效率和居民出行時(shí)間，在搜索有效路徑的基礎(chǔ)上，應(yīng)保證公交網(wǎng)絡(luò)運(yùn)輸效率最大化，因此，目標(biāo)函數(shù)為兩個(gè):1)L(p(s→t):β)值最小化;2)公交網(wǎng)絡(luò)運(yùn)輸效率最大化.

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

繞行策略使公交車運(yùn)行過程中，會(huì)繞過介數(shù)較大的節(jié)點(diǎn)，它們一般都是相對(duì)重要的節(jié)點(diǎn)或樞紐站點(diǎn)，若過多乘客繞過，必然會(huì)使公交網(wǎng)絡(luò)運(yùn)輸效率低下.為使公交網(wǎng)絡(luò)運(yùn)輸效率最大化，設(shè)計(jì)目標(biāo)函數(shù)表達(dá)式為

其中:Z為公交網(wǎng)絡(luò)運(yùn)輸效率，人次/s;xij為線路i上路段j的公交客流量，人次;rij為線路i上路段j的阻抗，s.

單條線路的約束條件包括線路長(zhǎng)度，路線非直線系數(shù)，路線客運(yùn)能力，復(fù)線條數(shù)等.整個(gè)線網(wǎng)的約束條件包括線網(wǎng)密度，乘客換乘系數(shù)，站點(diǎn)覆蓋率，線網(wǎng)覆蓋率等.它們的計(jì)算可參考文獻(xiàn)［9-10］，從而建立公交網(wǎng)絡(luò)優(yōu)化模型.

4 優(yōu)化模型算法實(shí)現(xiàn)

建立的公交網(wǎng)絡(luò)優(yōu)化模型為雙目標(biāo)規(guī)劃模型，大城市公交網(wǎng)絡(luò)比較復(fù)雜，采用解析法求最優(yōu)解計(jì)算量較大，有些模型可能不存在唯一的最優(yōu)解．因此，本文提出一種操作性較強(qiáng)的算法，計(jì)算過程較為直觀，可控性較強(qiáng)．

4.1 搜索備選線路集

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

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

4.2 有效線路布設(shè)

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

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

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

存在實(shí)數(shù)m滿足

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

則站點(diǎn)l后的(m-1)個(gè)站點(diǎn)上車經(jīng)過站點(diǎn)l的OD全部留剩，站點(diǎn)(l-m)上車經(jīng)過站點(diǎn)l的OD部分留剩．站點(diǎn)l后m個(gè)站點(diǎn)進(jìn)入超載站點(diǎn)集合Vs．

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

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

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

OD矩陣更新完畢，重新搜索備選線路和布設(shè)有效線路，直到所有的起始點(diǎn)對(duì)都布設(shè)一條有效線路，再進(jìn)行逐步的調(diào)整優(yōu)化，得到滿足線路約束的有效網(wǎng)絡(luò)．

5 確定最優(yōu)參數(shù)β

5.1 參數(shù)分析

根據(jù)前面的分析可知，參數(shù)β與居民出行時(shí)間之間的函數(shù)關(guān)系曲線應(yīng)為先下降再上升．當(dāng)發(fā)生交通擁堵時(shí)，部分居民采取繞行策略，偏離樞紐節(jié)點(diǎn)可繞過交通擁堵點(diǎn)，這時(shí)可縮短居民出行時(shí)間;隨著參數(shù)β的逐漸增大，居民出行路徑逐漸偏離擁堵點(diǎn)，離交通擁堵點(diǎn)越來越遠(yuǎn)，居民出行時(shí)間就越來越短;當(dāng)參數(shù)β達(dá)到一個(gè)臨界值βc時(shí)，居民出行路徑偏離交通擁堵點(diǎn)縮短的時(shí)間與居民繞遠(yuǎn)增加的時(shí)間相等．當(dāng)參數(shù)β繼續(xù)變大時(shí)，居民總的出行時(shí)間開始逐漸增加．

顯然，參數(shù)β的最優(yōu)值與實(shí)際網(wǎng)絡(luò)和城市交通擁堵程度有關(guān)，交通擁堵越嚴(yán)重，臨界值βc越大．通過分析不同β可觀察繞行策略下居民的出行軌跡，從而驗(yàn)證該策略在大城市公交網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中的合理性．

5.2 參數(shù)求解

長(zhǎng)春市交通擁堵嚴(yán)重，其中主干道人民大街、南湖大路、自由大路、亞泰大街、解放大路、吉林大路等“堵點(diǎn)”較多，其他市區(qū)支路交叉口擁堵也較為嚴(yán)重．以長(zhǎng)春市道路網(wǎng)作為基礎(chǔ)網(wǎng)絡(luò)求解參數(shù)β的最優(yōu)值．將長(zhǎng)春市劃分為163個(gè)交通小區(qū)，應(yīng)用TransCAD搜索并記錄它們之間的有效路徑，經(jīng)過分析計(jì)算可得到各個(gè)網(wǎng)絡(luò)指標(biāo)值．

根據(jù)反復(fù)計(jì)算的結(jié)果，參數(shù)β與擁擠網(wǎng)絡(luò)效率E1、平均出行時(shí)間的變化趨勢(shì)見圖1．從圖中可以看出，當(dāng)居民平均出行時(shí)間最短，網(wǎng)絡(luò)效率最高時(shí)，β的最優(yōu)值為0.1．β ＞0時(shí)，的變化趨勢(shì)與參數(shù)分析中的結(jié)論一致;β＜0時(shí)，有效路徑傾向于經(jīng)過樞紐站點(diǎn)，由于樞紐站點(diǎn)處理能力較高，增長(zhǎng)較慢．越短，E1越高，這與圖中趨勢(shì)一致．

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

圖2 不同β與、的變化趨勢(shì)圖

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

6 結(jié)論

1)根據(jù)繞行策略優(yōu)化城市公交網(wǎng)絡(luò)，既可充分利用樞紐站的高效處理能力，又可使公交出行適時(shí)避開交通擁堵，縮短出行時(shí)間，因此可適合在大城市或存在交通擁堵的城市應(yīng)用．

2)基于邊介數(shù)優(yōu)化的大城市公交網(wǎng)絡(luò)可使部分乘客出行時(shí)避開交通擁堵點(diǎn)，這將增強(qiáng)網(wǎng)絡(luò)對(duì)蓄意攻擊的抵抗能力，改善網(wǎng)絡(luò)的魯棒性．

3)雙重策略提高公交網(wǎng)絡(luò)的可靠性．繞行策略是將公交車作為機(jī)動(dòng)車一種，考慮整個(gè)交通系統(tǒng)的擁堵對(duì)公交系統(tǒng)的影響;站點(diǎn)容量模型考慮了由于線路運(yùn)輸能力限制產(chǎn)生的擁堵對(duì)公交系統(tǒng)的影響．

4)以長(zhǎng)春市路網(wǎng)為基礎(chǔ)求解β最優(yōu)值，結(jié)果表明，最小化網(wǎng)絡(luò)平均出行時(shí)間、最大化網(wǎng)絡(luò)效率可確定β的最優(yōu)值．

［1］汪小帆，李翔，陳關(guān)榮．復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］．北京:清華大學(xué)出版社，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］吳建軍，高自友，孫會(huì)君，等.城市交通系統(tǒng)復(fù)雜性:復(fù)雜網(wǎng)絡(luò)方法及其應(yīng)用［M］.北京:科學(xué)出版社，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］王煒，楊新苗，陳學(xué)武.城市公共交通系統(tǒng)規(guī)劃方法與管理技術(shù)［M］.北京:科學(xué)出版社，2002.

［10］胡啟洲，鄧衛(wèi).城市常規(guī)公共交通系統(tǒng)的優(yōu)化模型與評(píng)價(jià)方法［M］.北京:科學(xué)出版社，2009.

［11］趙淑芝，田慶飛，曹陽(yáng).基于站點(diǎn)容量限制的公交效率網(wǎng)絡(luò)設(shè)計(jì)模型［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2011，41(增刊1):81－84.