小世界網(wǎng)絡(luò)理論在城市公共交通線網(wǎng)優(yōu)化中的應(yīng)用

吳亞萍

摘要：隨著社會經(jīng)濟的不斷發(fā)展，城市交通在城市發(fā)展中所占據(jù)的地位不斷提高，其自身存在的問題也在不斷地出現(xiàn)，對城市內(nèi)部的交通進行優(yōu)先發(fā)展可以優(yōu)化交通資源的利用效率，也可以逐漸解決城市的擁堵問題。優(yōu)先發(fā)展公共交通的關(guān)鍵部分就是對公共交通網(wǎng)絡(luò)進行優(yōu)化，從而促使公共交通競爭力得到提高。因為公交線路的聚集性比較高和平均最短站間路徑小，從而對小世界效應(yīng)進行了反映。以小世界網(wǎng)絡(luò)理論的效率理論為基礎(chǔ)，研究了小世界在公交網(wǎng)絡(luò)中網(wǎng)絡(luò)理論的擬合問題，在公交網(wǎng)絡(luò)優(yōu)化過程中給出小世界網(wǎng)絡(luò)理論應(yīng)用方法。并以杭州市主城區(qū)中心區(qū)公交線網(wǎng)的應(yīng)用為例說明了該方法的應(yīng)用。

關(guān)鍵詞：小世界網(wǎng)絡(luò);公交線網(wǎng);全局效率;局部效率優(yōu)化

中圖分類號：G434? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）19-0263-02

1 引言

在城鎮(zhèn)化和交通汽車化的發(fā)展環(huán)境下，城市交通供給和需求之間的矛盾一天天突出，目前已經(jīng)發(fā)展為在城市長期發(fā)展中急切需要解決的問題。通過對國內(nèi)外相關(guān)理論的研究以及對城市交通建設(shè)現(xiàn)狀進行實地考察，優(yōu)化現(xiàn)有常規(guī)公交系統(tǒng)、建立智能交通網(wǎng)絡(luò)是解決交通擁堵和環(huán)境污染等問題的根本出路。現(xiàn)在，在國內(nèi)普通的公交線路優(yōu)化過程中，基本上是建立數(shù)學(xué)優(yōu)化模型的理論研究。這些措施對于解決公共汽車規(guī)劃過程中遇到的實際問題的效果不是很大，因為數(shù)據(jù)是很難被全部收集到的，這些措施也過于理想化，難以被實際操作。面對這些問題，本文主要在其他學(xué)者研究的基礎(chǔ)之上，根據(jù)公交線網(wǎng)的實際優(yōu)化成果及目前的研究情況，根據(jù)小世界網(wǎng)絡(luò)理論提出了公交網(wǎng)絡(luò)優(yōu)化措施。將小世界網(wǎng)絡(luò)的統(tǒng)計特性應(yīng)用到公共交通網(wǎng)絡(luò)中。以杭州市為例，對公共交通網(wǎng)絡(luò)的優(yōu)化進行了研究。經(jīng)過分析公交網(wǎng)絡(luò)抽象模型，在眾多措施中選擇了最好的網(wǎng)絡(luò)方案，使得公交網(wǎng)絡(luò)的傳輸效率得到提高，以及網(wǎng)絡(luò)的容錯能力也被提高了。結(jié)合定性和定量分析，根據(jù)實際情況提出更具操作性的優(yōu)化方案，為相關(guān)部門和企業(yè)提供決策支持。

2 模型與特性分析

2.1 小世界網(wǎng)絡(luò)模型

1998年，STROGATZ和WATTS提出了小世界網(wǎng)絡(luò)模型（WS模型）[2]。通過和經(jīng)典模型相的對比，小世界網(wǎng)絡(luò)模型可以對很多現(xiàn)實網(wǎng)絡(luò)自己組織形成的體系進行解釋。隨著時代的不斷發(fā)展，關(guān)于該研究的深入程度也在不斷提高，很多的實際考察結(jié)果也現(xiàn)實，很多真實網(wǎng)絡(luò)包括交通網(wǎng)絡(luò)具有的世界特征都是比較小的。小世界網(wǎng)絡(luò)模型能夠被定義為：隨著環(huán)網(wǎng)規(guī)則特別是在具有N個節(jié)點的情況下被給定，每個節(jié)點對稱地連接到其最近的m個鄰居。然后讓每一個節(jié)點都以概率P與其他節(jié)點進行重連便得到了小世界網(wǎng)絡(luò)。如圖1所示演示了這種重連過程。

若要網(wǎng)絡(luò)顯示為正則網(wǎng)絡(luò)，則重聯(lián)概率為0;若要網(wǎng)絡(luò)顯示為隨機網(wǎng)絡(luò)，則要求p為1;若要求網(wǎng)絡(luò)形成是小世界網(wǎng)絡(luò)，則要求p處于特殊區(qū)間，也就是0與1之間。網(wǎng)絡(luò)可以表示為G=（V，E），其中V代表給定的節(jié)點，是一組網(wǎng)絡(luò)節(jié)點;E表示邊，是網(wǎng)絡(luò)節(jié)點關(guān)系的集合。N為網(wǎng)絡(luò)節(jié)點數(shù)，A=（aij）是相應(yīng)的鄰接矩陣。對于0，1矩陣A來說，若節(jié)點i與節(jié)點j相連，而且i不等于j，aij=1就會出現(xiàn)，否則aij=0。

2.2 模型特性分析

①小世界網(wǎng)絡(luò)平均路徑長度L和聚集系數(shù)C

在常規(guī)的網(wǎng)絡(luò)中，節(jié)點和節(jié)點間最小的路徑的平均值是路徑平均長度，同時路徑的平均長度也是對節(jié)點分離程度的參數(shù)的描述;網(wǎng)絡(luò)中全部節(jié)點的聚類系數(shù)的平均值是聚合系數(shù)，是對網(wǎng)絡(luò)的容錯性能進行描述和對聚合程度盡心表述的參數(shù)[2]。在規(guī)則性的網(wǎng)絡(luò)中，因為節(jié)點是根據(jù)特定的條件進行分布的，這種情況下它們的聚集系數(shù)C都是比較大的，只是節(jié)點和節(jié)點間的平均路徑長度L的值也會比較大。隨機網(wǎng)絡(luò)因為它們節(jié)點的分布都是比較隨意的，所包含的聚集系數(shù)一般比較小，以及平均路徑長度L也比較小。作為分布于兩種網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò)，使得小世界網(wǎng)絡(luò)同時具備這兩種網(wǎng)絡(luò)的長處，也就是含有較大的聚集系數(shù)C，較小的平均路徑長度L，從而使得小世界網(wǎng)絡(luò)具備比較好的網(wǎng)絡(luò)特性。

②小世界網(wǎng)絡(luò)的效率

為了使得小世界網(wǎng)絡(luò)可以被更直接又生動地表現(xiàn)出來，對于引入其他重要的參數(shù)效率也是必要的。經(jīng)過對這個參數(shù)的引入，使得小世界網(wǎng)絡(luò)的效用能夠被用一個定值表現(xiàn)出來?；诰W(wǎng)絡(luò)知識和圖論，在描述一個公共網(wǎng)絡(luò)的過程中能夠使用兩個矩陣：相互關(guān)聯(lián)的矩陣（aij）和一階鄰接矩陣（lij）[3]。當(dāng)點i和點j的邊連通無阻時，aij=1，lij是兩點之間的現(xiàn)實距離;當(dāng)i點和j點沒有被直接連通時，aij=0，lij=∞。如圖2所示。

在得到aij和lij后，用貝爾曼算法能夠取得最短路徑矩陣dij[3]，并將i點和j點兩點間的效率解釋為eij=1/dij，vi，j，如果dij≤lij，那么i點和j點之間的效率也可以被闡釋為eij=1/dij，vi，j。若dij=∞，那么aij=0，能夠總結(jié)出e（g）=[1/（n-1）]1/dij是網(wǎng)絡(luò)的平均傳輸效率。理想情況下，它可以被認為是dij=lij，emax=e（g（n，n（n-1）/2）=[1/n（n-1）]1/lij。上面所描述的就是全局效率Eglobe參數(shù)[4]，對于完整網(wǎng)絡(luò)和現(xiàn)實的網(wǎng)絡(luò)在他們之間的平均路徑的對比過程中進行描述，也就是對平均路徑在現(xiàn)實網(wǎng)絡(luò)和完整網(wǎng)絡(luò)之間到底有多大的相似度，能夠得出0≤e（g）≤1，如果e越接近1，那么效率就會變高。

但是，在實際網(wǎng)絡(luò)中，維持每一個節(jié)點都可以正常并同時間進行工作的狀態(tài)是很難的。如果一個節(jié)點在網(wǎng)絡(luò)中不能和平常情況一樣進行工，那么對于提高網(wǎng)絡(luò)的效率就是必須要做的事情。在對網(wǎng)絡(luò)中容錯性尤其是自治分散板塊進行描述時，對另外一個參數(shù)進行了定義：局部效率ELOC[4]。如果全局效率gi是除去網(wǎng)絡(luò)中i點后的，那么局部效率公式就可以被闡釋為Eloc=1/NΣE（gi）。

3 模型算例

在城市公共交通網(wǎng)絡(luò)的建設(shè)過程中，其社會性的特點在逐漸的突出，人工規(guī)劃城市公共交通網(wǎng)絡(luò)的過程中，所受到的影響因素是多方面的。所以，由此看，總線網(wǎng)絡(luò)不僅不是完整網(wǎng)絡(luò)也不是隨機網(wǎng)絡(luò)。從城市交通網(wǎng)絡(luò)自身的特性來進行了解，發(fā)現(xiàn)較小的世界效應(yīng)都是經(jīng)過較小的平均站間和較大的聚集度進行反映的。一些研究表明，公交網(wǎng)絡(luò)是一個小型世界網(wǎng)絡(luò)，具有通過指數(shù)進行分布、明顯的社區(qū)結(jié)構(gòu)以及較強的通信能力等特點。

為了對公交線網(wǎng)優(yōu)化中的小世界網(wǎng)絡(luò)的應(yīng)用進行研究，對杭州市主城區(qū)中心區(qū)域公交站點和線路組成的網(wǎng)絡(luò)進行實例分析。圖3見研究區(qū)域的公交站點。

在實例分析中，對現(xiàn)有網(wǎng)絡(luò)進行了抽象描述：（1）將每個車站視為網(wǎng)絡(luò)中不同的節(jié)點;（2）同一條線路作為節(jié)點在不同的車站以相同公交站名處理;（3）將公交線路網(wǎng)絡(luò)中站點間的連接線視為連接網(wǎng)絡(luò)節(jié)點之間的弧線;（4）圓弧兩端兩個節(jié)點和節(jié)點間的距離是對圓弧的權(quán)重的表示;（5）孤立的車站不存在于公交網(wǎng)絡(luò)中，因為所有的兩個車站都能夠被一條或多條線路進行連接，因此網(wǎng)絡(luò)連接是比較完全的。在上述抽象定義的基礎(chǔ)上，通過在杭州主城區(qū)中心區(qū)布置公交線路和站點，共得到78個節(jié)點，即N為78，從而建立了78階距離矩陣。得到了公交網(wǎng)絡(luò)的最短路徑矩陣。網(wǎng)絡(luò)系統(tǒng)的全局效率和局部效率分別為0.2864和0.4674。所以，當(dāng)全局和局部之間的效率越來越接近1時，也是網(wǎng)絡(luò)整體性能最好的時刻。由于計算結(jié)果仍遠未達到預(yù)期水平，對目前存在的網(wǎng)絡(luò)進行了重新架構(gòu)，并通過增加和刪除一些總線線路和調(diào)整網(wǎng)絡(luò)節(jié)點進行了改進。優(yōu)化后，總效率為0.4227，局部效率為0.5324，都有一定的提升。公交線網(wǎng)優(yōu)化的流程圖見圖4。

4 結(jié)論與展望

公交線網(wǎng)優(yōu)化是系統(tǒng)工程，需要循環(huán)往復(fù)的進行優(yōu)化，從而使得在公交線網(wǎng)優(yōu)化中使用小世界理論給出最直接的參考依據(jù)。但是根據(jù)本研究所提方法對現(xiàn)有公交線網(wǎng)進行調(diào)整涉及方方面面的復(fù)雜因素，不一定能起到立竿見影的效果，最多可以給城市交通的管理者提供具有限制的參考價值，因此本研究方法比較適用于新建公交網(wǎng)絡(luò)的設(shè)計。另外在規(guī)模較大線網(wǎng)系統(tǒng)中，建立矩陣和計算需要大量的工作量，也可通過對線網(wǎng)系統(tǒng)進行適當(dāng)分塊來解決，怎么樣將規(guī)模比較大的線網(wǎng)系統(tǒng)進行合理的優(yōu)化和劃分還需要進行深入的探討。

參考文獻：

[1] Christos Valouxis，EfthymiosHousos.Combined bus and driver scheduling.Computer& Operations Research 29，2002：243-259.

[2] WATTS D J， STROGATEZ S H.Collective dynamics of small-world netword[J].Nature，1998，3（5）：393-440.

[3] 樊夢.基于WS小世界網(wǎng)絡(luò)拓撲特性的自組織PSO算法[J].大眾科技，2010（10）：35-37.

[4] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[5] 史路.城市公共交通線路模擬優(yōu)化[J].公路交通技術(shù)，2014（04）：111-118.

【通聯(lián)編輯：王力】