影響最大化算法在城市公交網(wǎng)絡(luò)中的應(yīng)用研究

李 峰

(中北大學(xué)儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室 山西 太原 030051)

0 引 言

近年來(lái)，嚴(yán)重的交通擁堵問(wèn)題成為國(guó)內(nèi)各大城市普遍面臨的困擾，且形勢(shì)日益加劇。而解決這一問(wèn)題的首選措施即發(fā)展以巴士和地鐵為代表的城市公共交通，所以對(duì)城市公交巴士系統(tǒng)的研究成為了一個(gè)熱點(diǎn)課題。

已有的多項(xiàng)成果表明[1-3]，城市公交系統(tǒng)可以通過(guò)將公交站點(diǎn)抽象為節(jié)點(diǎn)，線路/站點(diǎn)間的聯(lián)系抽象為連邊的方式，建模為復(fù)雜網(wǎng)絡(luò)，滿足小世界和無(wú)標(biāo)度等基本特征。對(duì)此，早期的研究多集中于孤立地考慮單條公交路線或單個(gè)?？空军c(diǎn)。然而，城市公交網(wǎng)絡(luò)正常功能的維持往往在于多條重要線路，單獨(dú)研究某一線路對(duì)城市交通網(wǎng)絡(luò)建設(shè)的實(shí)質(zhì)意義不大。所以，研究網(wǎng)絡(luò)內(nèi)所有公交線路間的相互協(xié)作與影響，逐漸成為當(dāng)下探索城市公交系統(tǒng)的主流?；诖?，本文以江蘇省無(wú)錫市公交系統(tǒng)所建模的復(fù)雜網(wǎng)絡(luò)為主體，對(duì)影響最大化算法在該系統(tǒng)的應(yīng)用展開(kāi)研究，以豐富城市公交網(wǎng)智慧化建設(shè)的理論，助力現(xiàn)實(shí)公交系統(tǒng)的規(guī)劃、管理與決策。

1 研究現(xiàn)狀

近年來(lái)，隨著復(fù)雜網(wǎng)絡(luò)理論[4-6]的豐富，城市公交網(wǎng)絡(luò)研究涵蓋了多個(gè)方面，包括城市公交網(wǎng)絡(luò)靜態(tài)特性的分析和統(tǒng)計(jì)、演化生成建模、行為與應(yīng)用研究等。

其中應(yīng)用研究還處于起步階段，主要包括網(wǎng)絡(luò)中關(guān)鍵站點(diǎn)的探測(cè)和網(wǎng)絡(luò)的設(shè)計(jì)、優(yōu)化與控制兩方面的內(nèi)容。第一類研究的出發(fā)點(diǎn)是城市公交網(wǎng)絡(luò)中部分關(guān)鍵站點(diǎn)對(duì)于網(wǎng)絡(luò)的靜動(dòng)態(tài)性能影響甚大。例如:影響網(wǎng)絡(luò)魯棒性的某些站點(diǎn)一旦失效，將會(huì)導(dǎo)致網(wǎng)絡(luò)連通性的極大降低?；诖耍墨I(xiàn)[7]根據(jù)站點(diǎn)對(duì)網(wǎng)絡(luò)路徑長(zhǎng)度與換乘次數(shù)的綜合作用，提出了探測(cè)網(wǎng)絡(luò)換乘關(guān)鍵站點(diǎn)的方法，并通過(guò)仿真實(shí)驗(yàn)證明了該方法的有效性。第二類研究則是通過(guò)調(diào)整城市公交網(wǎng)絡(luò)的結(jié)構(gòu)來(lái)實(shí)現(xiàn)系統(tǒng)的合理設(shè)計(jì)與優(yōu)化，通過(guò)在網(wǎng)絡(luò)運(yùn)行時(shí)對(duì)網(wǎng)絡(luò)施加干預(yù)來(lái)實(shí)現(xiàn)控制等，從而提升網(wǎng)絡(luò)的整體服務(wù)性能和乘客的滿意度。由于城市公交網(wǎng)絡(luò)的線路優(yōu)化是NP-hard問(wèn)題[8]，所以現(xiàn)有的多數(shù)網(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化研究都是基于啟發(fā)式的優(yōu)化規(guī)則，如基于聚合物理論而提出的根據(jù)乘客出行需求分布數(shù)據(jù)優(yōu)化城市公交線路設(shè)置的算法[9]。網(wǎng)絡(luò)控制研究的難點(diǎn)在于該問(wèn)題的數(shù)學(xué)建模，如文獻(xiàn)[10]中的時(shí)變時(shí)滯公交線路網(wǎng)絡(luò)模型，盡管理論推導(dǎo)成立，卻過(guò)于偏理想化。

到目前為止，基于復(fù)雜網(wǎng)絡(luò)理論的城市公交系統(tǒng)研究尚有很大的探索空間，對(duì)于重要站點(diǎn)集、關(guān)鍵線路組的研究更是屈指可數(shù)。因此，本文以無(wú)錫市公交系統(tǒng)為研究對(duì)象，對(duì)其進(jìn)行網(wǎng)絡(luò)建模，結(jié)合復(fù)雜網(wǎng)絡(luò)理論中的影響最大化算法思想，對(duì)城市公交系統(tǒng)中的核心路線組進(jìn)行識(shí)別和分析。

2 算法應(yīng)用

2.1 無(wú)錫市公交網(wǎng)絡(luò)建模及特征分析

城市公交線路一般由站點(diǎn)和站點(diǎn)間的連接路段組成，有上行線和下行線的區(qū)分。由于任意站點(diǎn)A若存在路線可達(dá)站點(diǎn)B，則同樣由站點(diǎn)B也可通過(guò)此路線到達(dá)站點(diǎn)A，所以，本文以無(wú)向化的方式對(duì)無(wú)錫市公交系統(tǒng)的相關(guān)數(shù)據(jù)進(jìn)行處理。為保證研究的科學(xué)性和真實(shí)性，這里對(duì)本文數(shù)據(jù)做如下說(shuō)明：

(1) 僅采用無(wú)錫市內(nèi)所有的公交路線，不去除環(huán)線、旅游線路和夜班車路線等，周圍區(qū)縣線路不在研究范圍。

(2) 數(shù)據(jù)均來(lái)源于無(wú)錫市公交公司官網(wǎng)。

(3) 采集數(shù)據(jù)截止日期為2019年3月2日，在此之后公交線路的變動(dòng)情況不予考慮。

本文選取無(wú)錫市共302條公交線路，包括2 360個(gè)站點(diǎn)，對(duì)其進(jìn)行公交線路建模和靜態(tài)特征評(píng)估。之后利用影響最大化算法LCIR_AR[11]對(duì)網(wǎng)絡(luò)的抗毀性和平均最短路徑做了科學(xué)的分析，以證明所選線路組的合理性。

2.1.1無(wú)錫市公交線路網(wǎng)絡(luò)模型的構(gòu)建

城市公交系統(tǒng)的網(wǎng)絡(luò)建模主要有兩種方式，一種是將停靠站點(diǎn)作為網(wǎng)絡(luò)節(jié)點(diǎn)，若兩個(gè)站點(diǎn)由同一班車次承載，則建立連邊，為無(wú)權(quán)無(wú)向網(wǎng)絡(luò)；另一種是以公交線路為網(wǎng)絡(luò)節(jié)點(diǎn)，擁有共同?？空军c(diǎn)的兩條線路間存在連邊，邊的權(quán)重取決于共同站點(diǎn)的數(shù)目，即為加權(quán)無(wú)向網(wǎng)絡(luò)。如前所述，本文旨在發(fā)現(xiàn)城市的關(guān)鍵線路組，所以主要采用第二種建模方式構(gòu)建無(wú)錫市公交線路網(wǎng)絡(luò)模型。大致實(shí)現(xiàn)流程如圖1所示。

圖1 無(wú)錫市公交線路網(wǎng)絡(luò)建模實(shí)現(xiàn)流程

其中，數(shù)據(jù)處理部分的格式初始化是指將采集的所有公交線路數(shù)據(jù)中特殊符號(hào)進(jìn)行統(tǒng)一；數(shù)據(jù)清洗主要是對(duì)周圍區(qū)縣線路予以刪除；按需整理則是對(duì)公交線路的重新編號(hào)。部分處理后的公交線路的數(shù)據(jù)格式展示如表1所示。

表1 處理后的公交線路數(shù)據(jù)形式表

最后，利用處理后的公交線路數(shù)據(jù)對(duì)無(wú)錫市公交系統(tǒng)進(jìn)行網(wǎng)絡(luò)建模。具體建模過(guò)程如下：(1) 將公交路線按照編號(hào)抽象為網(wǎng)絡(luò)節(jié)點(diǎn)；(2) 對(duì)各公交線路間的共同?？空军c(diǎn)進(jìn)行統(tǒng)計(jì)，規(guī)定共同?？空军c(diǎn)數(shù)大于0的節(jié)點(diǎn)間形成鏈接。建模后的無(wú)錫市公交系統(tǒng)可視化如圖2所示。

圖2 無(wú)錫市公交線路網(wǎng)絡(luò)圖

2.1.2網(wǎng)絡(luò)基本特征分析

由于在實(shí)際的發(fā)展中，對(duì)城市公交線路進(jìn)行系統(tǒng)設(shè)計(jì)要求數(shù)據(jù)有較高的準(zhǔn)確性，所以，有效分析和計(jì)算其網(wǎng)絡(luò)模型的靜態(tài)特征很有必要，這可以在一定程度上促進(jìn)城市公交網(wǎng)絡(luò)模型構(gòu)建與應(yīng)用的精準(zhǔn)化發(fā)展。目前描述和度量網(wǎng)絡(luò)特征的統(tǒng)計(jì)量眾多，如網(wǎng)絡(luò)平均度與度分布、平均距離、平均最短路徑長(zhǎng)度、平均聚類系數(shù)、緊密度、連通性等。根據(jù)研究需要，本文重點(diǎn)從度分布、平均最短路徑長(zhǎng)度、平均聚類系數(shù)這三個(gè)指標(biāo)對(duì)無(wú)錫市公交線路網(wǎng)絡(luò)進(jìn)行分析。

通過(guò)對(duì)無(wú)錫市公交線路網(wǎng)絡(luò)的建模，利用networkx工具得出該網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布圖如圖3所示。節(jié)點(diǎn)的度可以理解為某條公交線路可以換乘的路線條數(shù)。由圖所反映的情況來(lái)看，degree∈[0,35]的網(wǎng)絡(luò)節(jié)點(diǎn)所占比例相對(duì)較高，即換乘選擇較少的公交線路較多，表明無(wú)錫市公交系統(tǒng)在邊緣線路的建設(shè)方面存在一定合理性；而當(dāng)degree∈[80,120]時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)的度分布近似服從冪律分布，即換乘選擇越多的公交線路數(shù)量越少，體現(xiàn)出無(wú)錫市公交系統(tǒng)相對(duì)科學(xué)，避免了在線路安排上的冗余以及人力、物力上的浪費(fèi)。

圖3 無(wú)錫市公交線路網(wǎng)絡(luò)的度分布圖

由于無(wú)錫市公交線路網(wǎng)絡(luò)是完全連通的，所以任意兩點(diǎn)間彼此可達(dá)。通過(guò)計(jì)算得到無(wú)錫市公交線路網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度為2.002 7，具有小世界特性。換句話說(shuō)，兩條線路之間實(shí)現(xiàn)換乘平均需要2次，顯示出無(wú)錫市公交網(wǎng)絡(luò)在換乘上的方便性。

在公交線路網(wǎng)絡(luò)中，平均聚類系數(shù)定義為所有節(jié)點(diǎn)的聚類系數(shù)的平均值。計(jì)算得知無(wú)錫市公交線路網(wǎng)絡(luò)的聚類系數(shù)為0.569 8，聚集特性良好。與北京的0.632 6、上海的0.654 0、杭州的0.620 5[2]相比，還存在一定差距。為便于查看，將該公交線路網(wǎng)絡(luò)的基本拓?fù)涮卣髡砣绫?所示。

表2 無(wú)錫市公交線路網(wǎng)絡(luò)的基本拓?fù)涮卣?/p>

2.2 影響最大化算法

本文選擇影響最大化算法LCIR_AR(Local Collective Influence Rank-Adaptive Recalculation Algorithm)[11]來(lái)開(kāi)展研究。該算法是對(duì)CIM(Collective Influence Maximization Algorithm)算法[12]的改進(jìn)，通過(guò)調(diào)整其影響力節(jié)點(diǎn)的選取策略以及引入影響力節(jié)點(diǎn)候選集和自適應(yīng)重新計(jì)算思維，提高了CIM算法的性能。描述如算法1所示。

算法1LCIR_AR算法

輸入：網(wǎng)絡(luò)G={V,E}，距離長(zhǎng)度l，影響力節(jié)點(diǎn)集的規(guī)模k，控制參數(shù)λ

輸出：選取的影響力節(jié)點(diǎn)集合S，執(zhí)行輪數(shù)c

開(kāi)始：

Step1以網(wǎng)絡(luò)中任意節(jié)點(diǎn)i為根節(jié)點(diǎn)，利用廣度(或深度)遍歷其l層所有鄰居節(jié)點(diǎn)。

Step2根據(jù)式(1)-式(3)計(jì)算節(jié)點(diǎn)i的CI值及LCII值，并將LCII值為0的節(jié)點(diǎn)添加到影響力節(jié)點(diǎn)候選集Sc。

Step3依次對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)執(zhí)行上述步驟Step 1-Step 2。

Step4初始化c=0。

Step5在網(wǎng)絡(luò)G中移除Sc內(nèi)的節(jié)點(diǎn)，執(zhí)行c=c+1。

Step6并對(duì)更新網(wǎng)絡(luò)重復(fù)Step 1-Step 5，直至節(jié)點(diǎn)候選集的規(guī)模達(dá)到|Sc|=k/λ。

Step7對(duì)候選集Sc中節(jié)點(diǎn)按照CI值降序排列，截取Top-k節(jié)點(diǎn)加入影響力節(jié)點(diǎn)集S。

Step8返回S、c。

結(jié)束

(1)

(2)

(3)

式中：di為節(jié)點(diǎn)i的度，N(i)表示節(jié)點(diǎn)i鄰居節(jié)點(diǎn)的集合，l為距離節(jié)點(diǎn)i的最短路徑長(zhǎng)度。Ball(i,l)定義為屬于以節(jié)點(diǎn)i為中心，半徑為l的球內(nèi)的節(jié)點(diǎn)集合， ?Ball(i,l)則表示該球的邊界。便于理解，將變量含義示意如圖4。

圖4 CIM算法的概念標(biāo)注圖

該算法主要有以下優(yōu)勢(shì)：(1) 避免了原CIM算法在網(wǎng)絡(luò)適用中可能出現(xiàn)的富人俱樂(lè)部現(xiàn)象，進(jìn)一步提高了算法在影響力節(jié)點(diǎn)識(shí)別上的準(zhǔn)確度，同時(shí)保留了其發(fā)掘扮演經(jīng)紀(jì)人角色的低度節(jié)點(diǎn)的能力。(2) 受益于局部領(lǐng)袖節(jié)點(diǎn)的選取策略、影響力節(jié)點(diǎn)候選集和自適應(yīng)重新計(jì)算的思想，算法的執(zhí)行效率較CIM大幅提升。映射到本文城市公交系統(tǒng)網(wǎng)絡(luò)的影響力節(jié)點(diǎn)識(shí)別問(wèn)題中，則表現(xiàn)為：不僅僅是轉(zhuǎn)乘選擇多的公交線路，轉(zhuǎn)乘路線較少的公交線路同樣具有被發(fā)掘重要性的可能，即該算法能夠更準(zhǔn)確地挖掘出無(wú)錫市公交系統(tǒng)中的重要線路。此外，該算法保證了所選公交線路的分散性，從而使得識(shí)別出的核心線路組在現(xiàn)實(shí)系統(tǒng)中的實(shí)際影響范圍更大。最后，高效的執(zhí)行效率對(duì)于處理規(guī)模隨時(shí)會(huì)擴(kuò)張的城市公交網(wǎng)絡(luò)具有很強(qiáng)的適用性。

2.3 關(guān)鍵公交線路組的識(shí)別

2.3.1實(shí)驗(yàn)平臺(tái)及設(shè)置

本文實(shí)驗(yàn)的硬件環(huán)境為：2.50 GHz Intel(R) Core(TM) i5-3210 CPU，4 GB的內(nèi)存；操作系統(tǒng)為：Windows；開(kāi)發(fā)環(huán)境及語(yǔ)言為Python 2.7。影響最大化算法LCIR_AR的參數(shù)設(shè)置為距離長(zhǎng)度l=2，核心線路數(shù)k=50，控制參數(shù)λ=1。實(shí)驗(yàn)主要從兩部分展開(kāi)：首先是所選節(jié)點(diǎn)集對(duì)網(wǎng)絡(luò)平均最短路徑的影響，其次是對(duì)網(wǎng)絡(luò)連通性的影響。所有實(shí)驗(yàn)的比較對(duì)象均為隨機(jī)選擇的同等規(guī)模的節(jié)點(diǎn)集合。鑒于該公交線路網(wǎng)絡(luò)的密度過(guò)高，刪除較少節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的連通性基本無(wú)影響。所以在第二部分實(shí)驗(yàn)中，對(duì)網(wǎng)絡(luò)進(jìn)行一定的簡(jiǎn)化處理，僅保留共同?？空军c(diǎn)大于2的連邊，以增強(qiáng)效果的可視性。

2.3.2實(shí)驗(yàn)結(jié)果和分析

在城市公交系統(tǒng)中，遇到人為或者自然的意外而導(dǎo)致某些線路無(wú)法正常使用的情況在所難免。這種場(chǎng)景映射到公交線路網(wǎng)絡(luò)，即為節(jié)點(diǎn)失效。站在研究的角度上來(lái)說(shuō)，最常見(jiàn)的處理方式則為刪除該失效節(jié)點(diǎn)及與之關(guān)聯(lián)的鏈接。不失一般性，本節(jié)實(shí)驗(yàn)中，將LCIR_AR算法所選影響力節(jié)點(diǎn)集中的所有節(jié)點(diǎn)視為失效，對(duì)其及其連邊進(jìn)行移除操作，從而分析其對(duì)網(wǎng)絡(luò)平均最短路徑和網(wǎng)絡(luò)連通性的影響。關(guān)于LCIR_AR算法的節(jié)點(diǎn)選擇策略可見(jiàn)算法1，這里不再贅述。為證明該算法在影響力節(jié)點(diǎn)選取上的精準(zhǔn)性，從公交線路網(wǎng)絡(luò)中的302個(gè)節(jié)點(diǎn)中隨機(jī)選取相同數(shù)目的節(jié)點(diǎn)作為對(duì)比。

(1) 網(wǎng)絡(luò)平均最短路徑實(shí)驗(yàn)。此實(shí)驗(yàn)中，所用網(wǎng)絡(luò)為未簡(jiǎn)化的無(wú)錫市公交線路原型網(wǎng)絡(luò)，兩種方式下所選的待移除節(jié)點(diǎn)記錄如表3所示，表中節(jié)點(diǎn)區(qū)分先后。圖5為依次移除所選節(jié)點(diǎn)，網(wǎng)絡(luò)的平均最短路徑變化曲線。

表3 LCIR_AR算法和隨機(jī)選擇的Top-50節(jié)點(diǎn)

圖5 節(jié)點(diǎn)移除與網(wǎng)絡(luò)平均最短路徑長(zhǎng)度關(guān)系圖

由圖5可以看出，隨著LCIR_AR算法所選網(wǎng)絡(luò)節(jié)點(diǎn)的逐個(gè)移除，平均最短路徑大致呈增長(zhǎng)趨勢(shì)，而隨機(jī)選擇情況下，網(wǎng)絡(luò)平均最短路徑?jīng)]有明顯的變化。這是因?yàn)楫?dāng)某些重要公交線路無(wú)法運(yùn)行時(shí)，民眾出行的便利性受到影響，換乘/繞道的概率上升，網(wǎng)絡(luò)的平均最短路徑自然加大。對(duì)比之下不難發(fā)現(xiàn)，同樣是網(wǎng)絡(luò)中50個(gè)節(jié)點(diǎn)，后者所選出的節(jié)點(diǎn)，對(duì)于網(wǎng)絡(luò)平均最短路徑的影響更大。也就是說(shuō)，公交線路存在重要與否的差異，針對(duì)性地攻擊會(huì)比隨機(jī)破壞，在網(wǎng)絡(luò)平均最短路徑上更有殺傷力。因此，需對(duì)公交系統(tǒng)中的多條重要線路加強(qiáng)保護(hù)，以維護(hù)該城市公交出行的方便度。

(2) 網(wǎng)絡(luò)連通性實(shí)驗(yàn)。如前所述，此實(shí)驗(yàn)以簡(jiǎn)化處理后的無(wú)錫市公交線路網(wǎng)絡(luò)為主體。此時(shí)由LCIR_AR算法和隨機(jī)選擇所確定的待移除節(jié)點(diǎn)記錄如表4所示，節(jié)點(diǎn)同樣區(qū)分先后。隨著所選節(jié)點(diǎn)的移除，網(wǎng)絡(luò)的最大連通分量和連通分量個(gè)數(shù)均會(huì)受到影響，變化曲線分別如圖6和圖7所示。

表4 LCIR_AR算法和隨機(jī)選擇的Top-50節(jié)點(diǎn)

圖6 節(jié)點(diǎn)移除與網(wǎng)絡(luò)最大連通分量關(guān)系圖

圖7 節(jié)點(diǎn)移除與網(wǎng)絡(luò)連通分量個(gè)數(shù)關(guān)系圖

觀察圖6和圖7，可以得出結(jié)論：較之于隨機(jī)選擇，從網(wǎng)絡(luò)中移除LCIR_AR算法所選的影響力節(jié)點(diǎn)，網(wǎng)絡(luò)連通性快速下降，形成多個(gè)網(wǎng)絡(luò)碎片。原因是LCIR_AR算法可以識(shí)別公交系統(tǒng)中的若干樞紐線路，對(duì)其進(jìn)行移除后，網(wǎng)絡(luò)急劇瓦解，系統(tǒng)的運(yùn)輸功能極大受阻或減弱。

綜上，影響力最大化算法LCIR_AR能有效挖掘無(wú)錫市公交系統(tǒng)中的核心線路組，對(duì)于該市公交系統(tǒng)的線路保護(hù)、合并或撤銷等建設(shè)工作具有一定的指導(dǎo)意義。

3 結(jié) 語(yǔ)

本文以無(wú)錫市公交系統(tǒng)為例，建立了無(wú)錫市公交線路復(fù)雜網(wǎng)絡(luò)模型，通過(guò)運(yùn)用復(fù)雜網(wǎng)絡(luò)中的影響最大化算法對(duì)網(wǎng)絡(luò)中的若干關(guān)鍵線路進(jìn)行識(shí)別，并結(jié)合網(wǎng)絡(luò)抗毀性等實(shí)驗(yàn)，分析驗(yàn)證了所選線路的有效性。該研究的主要貢獻(xiàn)可以歸結(jié)為：

(1) 首次將影響最大化理論引入于城市公交系統(tǒng)的研究，可為該領(lǐng)域后續(xù)更深入的探索工作提供參考。

(2) 識(shí)別公交系統(tǒng)的核心線路組，對(duì)于理解、完善城市公交的骨架結(jié)構(gòu)有重要意義，如擴(kuò)大覆蓋率、平衡均衡性、調(diào)整公交線安排等。

(3) 基于挖掘到的核心線路組，一定程度上能夠指導(dǎo)城市公交的重建/恢復(fù)工程。當(dāng)城市公交系統(tǒng)由于不可抗力的災(zāi)難基本崩潰，優(yōu)先修復(fù)這些重要線路，以最大限度地保障公交網(wǎng)絡(luò)的正常功能。

(4) 核心線路組的利用，有助于提升外來(lái)游客的出行體驗(yàn)。從核心線路組內(nèi)選擇出行方案，能夠在減少換乘次數(shù)的同時(shí)節(jié)省一定的時(shí)間。