基于社區(qū)發(fā)現(xiàn)法的高速鐵路網(wǎng)絡(luò)劃分研究*

姚曉峰 ，張 鵬 ，孫克洋 ，楊 敏

（1 中國鐵路北京局集團有限公司客運部 工程師，北京 100860；2、3、4 西南交通大學交通運輸與物流學院 碩士研究生，四川 成都 610031）

0 引言

隨著我國高速鐵路交織成網(wǎng)，網(wǎng)絡(luò)密度不斷加大、各個線路交叉頻率增加，導致大量本線和跨線列車的復雜開行。 同時，大部分線路不同速度、不同性質(zhì)列車共線運行，列車運行間隔時間、車站作業(yè)間隔時間不統(tǒng)一，導致路網(wǎng)上的列車運行組織極其復雜。 高速鐵路網(wǎng)絡(luò)化列車開行方案優(yōu)化面臨著列車運行徑路選擇、跨線列車組織、換乘節(jié)點選擇等關(guān)鍵問題，尤其在大規(guī)模路網(wǎng)條件下建模求解的復雜度將呈指數(shù)級增加。 因此有必要對目前高速鐵路的網(wǎng)絡(luò)特性進行分析，通過子網(wǎng)劃分的方法將路網(wǎng)條件下列車開行方案優(yōu)化問題轉(zhuǎn)變?yōu)槎鄠€子網(wǎng)的列車開行方案優(yōu)化和合并問題，逐步降低整體求解難度[1]。

針對高速鐵路網(wǎng)絡(luò)的研究以網(wǎng)絡(luò)建設(shè)擴展[2]、網(wǎng)絡(luò)結(jié)構(gòu)演化[3]、網(wǎng)絡(luò)經(jīng)濟發(fā)展[4]、交通小區(qū)劃分[5]等為主， 隨后復雜網(wǎng)絡(luò)理論廣泛應(yīng)用于高鐵網(wǎng)絡(luò)研究。 社區(qū)結(jié)構(gòu)作為復雜網(wǎng)絡(luò)特性之一廣泛運用于人際網(wǎng)絡(luò)、萬維網(wǎng)絡(luò)、客流網(wǎng)絡(luò)[6]、交通出行網(wǎng)絡(luò)[7]中。目前高鐵網(wǎng)絡(luò)劃分的研究以區(qū)域劃分為主， 吳琪[8]引入博弈論的思想分析了區(qū)域鐵路通道線間的協(xié)同競爭， 為編制區(qū)域鐵路通道客運產(chǎn)品奠定基礎(chǔ)。帥斌等[9]采用聚類的方法對全國運輸網(wǎng)絡(luò)進行了區(qū)域劃分。 張強鋒等[10]考慮既有聚類劃分方法存在無法考慮區(qū)域網(wǎng)絡(luò)中心性、連接性等缺點，提出根據(jù)路網(wǎng)的鄰接特性建立區(qū)域網(wǎng)絡(luò)劃分決策優(yōu)化模型。張?zhí)m霞[11]引入群落概念將路網(wǎng)劃分為滿足約束的群落。 王逸飛[12]根據(jù)線路之間的客流交換量將城際鐵路網(wǎng)絡(luò)劃為不同的線團。

需要指出的是既有的區(qū)域劃分存在無法評估、人為割裂長大跨線客流、 受主觀影響較大等弊端。本文引入社區(qū)發(fā)現(xiàn)方法依據(jù)網(wǎng)絡(luò)特性進行客觀劃分， 通過聯(lián)系緊密的社區(qū)結(jié)構(gòu)挖掘鐵路網(wǎng)絡(luò)規(guī)律，劃分結(jié)果可評估，避免了主觀經(jīng)驗主義影響。 同時重疊節(jié)點的發(fā)現(xiàn)可巧妙解決跨線節(jié)點選擇問題，能夠緊密結(jié)合客流需求實現(xiàn)“按流開車”，為網(wǎng)絡(luò)劃分提供了極大的支持。

1 問題分析

高速鐵路網(wǎng)絡(luò)是一個無向有權(quán)網(wǎng)絡(luò)，且社區(qū)結(jié)構(gòu)呈現(xiàn)重疊社區(qū)結(jié)構(gòu)特性，本文根據(jù)既有重疊網(wǎng)絡(luò)研究方法，結(jié)合空間網(wǎng)絡(luò)特性，提出客流、距離加權(quán)的重疊社區(qū)發(fā)現(xiàn)方法進行網(wǎng)絡(luò)劃分。 網(wǎng)絡(luò)劃分的核心原則是根據(jù)客流需求、路網(wǎng)結(jié)構(gòu)、動車組檢修分布等將路網(wǎng)劃分為多個運輸區(qū)域，區(qū)域內(nèi)部可根據(jù)各自特點設(shè)立不同的列車開車方案[13]。 在高速鐵路網(wǎng)絡(luò)上，由旅客出行需求形成OD 客流網(wǎng)絡(luò)，體現(xiàn)了節(jié)點之間的聯(lián)系； 當旅客選擇對應(yīng)的出行方案時，客流也就相應(yīng)加載到高鐵線路上，形成客流分配網(wǎng)絡(luò)，體現(xiàn)出線路之間的聯(lián)系。 研究高速鐵路網(wǎng)絡(luò)，既要從網(wǎng)絡(luò)節(jié)點出發(fā)研究不同車站之間的客流交互、距離等因素，也要從網(wǎng)絡(luò)邊出發(fā)研究不同出行徑路的選擇和線路能力等。 本文提出的路網(wǎng)劃分方法不再僅僅基于高速鐵路網(wǎng)絡(luò)的物理分布， 而是引入OD 客流和路徑客流，研究客流對路網(wǎng)劃分的影響。假定在OD 客流已知的基礎(chǔ)上，參考文獻[14]和[15]構(gòu)建基于出行徑路選擇的高速鐵路網(wǎng)絡(luò)客流分配模型， 分別在OD 客流網(wǎng)絡(luò)和客流分配網(wǎng)絡(luò)上基于社區(qū)發(fā)現(xiàn)方法進行網(wǎng)絡(luò)劃分形成對應(yīng)的三級網(wǎng)絡(luò)，如圖1 所示。

圖1 高速鐵路“路網(wǎng)-區(qū)域-線團”三級網(wǎng)絡(luò)形成流程

2 路網(wǎng)-區(qū)域-線團三級網(wǎng)絡(luò)劃分方法

2.1 高速鐵路區(qū)域網(wǎng)絡(luò)劃分

2.1.1 網(wǎng)絡(luò)劃分相關(guān)概念

由于旅客出行的多樣化，高速鐵路網(wǎng)絡(luò)會產(chǎn)生不同起訖點之間的客流，通過客流分配模型進而可以確定出各條線路上的客流量。 各個節(jié)點之間以客流的交互量表示聯(lián)系強度，與客流量的大小成正相關(guān)；以相互之間的距離表示影響強度，與距離遠近成負相關(guān)，因此以節(jié)點客流量作為相似權(quán)，以節(jié)點距離作為相異權(quán)，將二者形成組合模重[16]來為高速鐵路網(wǎng)絡(luò)賦權(quán)，重構(gòu)高速鐵路網(wǎng)絡(luò)。

重疊網(wǎng)絡(luò)社區(qū)劃分主要有局部擴展、邊劃分和模糊發(fā)現(xiàn)等幾類方法[17]，高速鐵路網(wǎng)絡(luò)布局呈現(xiàn)向四周發(fā)散的路網(wǎng)結(jié)構(gòu)，局部擴展方法較為適用。 核心思想是通過聯(lián)合引力度確定重疊社區(qū)的中心節(jié)點，然后從中心向鄰接節(jié)點擴散，根據(jù)鄰接節(jié)點對重疊社區(qū)的隸屬度逐步合并社區(qū)，直到模塊度最高為止。 設(shè)節(jié)點va，聯(lián)合引力度定義如下：

式中：Fa為節(jié)點va的聯(lián)合引力度為節(jié)點 va和 vj之間的最短距離；ma、mj為節(jié)點的加權(quán)質(zhì)量，可用節(jié)點的聯(lián)合度表示，表示節(jié)點在全網(wǎng)的影響力，與連接的節(jié)點數(shù)量和連接邊權(quán)重有關(guān)； 其中Ka、Sa分別為節(jié)點va的連接度、連接強度，連接度為節(jié)點的連接節(jié)點數(shù)量，連接強度為連接邊權(quán)重，β 為調(diào)節(jié)參數(shù)。

聯(lián)合隸屬度是判斷節(jié)點對重疊社區(qū)的隸屬關(guān)系的重要指標，設(shè)有重疊社區(qū)C，任意節(jié)點a 對重疊社區(qū)的聯(lián)合隸屬度，如式（2）所示。

式中：K(a,C)為節(jié)點a 對重疊社區(qū)C 的連接度，即連接的節(jié)點數(shù)量；S(a,C)為節(jié)點a 對重疊社區(qū)C 的連接強度，即連接邊權(quán)重。

2.1.2 二級區(qū)域網(wǎng)絡(luò)劃分流程

Step 1：初始化網(wǎng)絡(luò)。 根據(jù)高速鐵路網(wǎng)絡(luò)權(quán)重設(shè)計方法， 并輸入相關(guān)信息構(gòu)建加權(quán)網(wǎng)絡(luò)G=（V，E，W），并將所有節(jié)點標記為“N”，即為尚未劃入重疊社區(qū)。

Step 2：判斷節(jié)點是否有標記“N”，若有，進入Step 3；若沒有，結(jié)束。

Step 3：計算所有節(jié)點 a（標記為“N”）的聯(lián)合引力度，取 max（Fa）,?a∈V 的節(jié)點為重疊社區(qū)的中心節(jié)點z。

Step 4：構(gòu)建初始中心社區(qū)。 搜索中心節(jié)點z 的所有鄰接節(jié)點放入集合Vs中。 判斷節(jié)點標記為“N”，則歸入中心節(jié)點z，形成初始中心社區(qū)C，同時將中心社區(qū)的節(jié)點放入集合Vz。

Step 5：確定中心社區(qū)。 遍歷集合 Vz，?a∈Vz，計算B(a,C)，如果聯(lián)合隸屬度大于閾值，即B(a,C)≥BT，則從集合V 中刪除節(jié)點a，進入下一步。否則，在集合Vz中刪除節(jié)點a，最終形成中心社區(qū)Cz。

Step 6：搜索中心社區(qū)的鄰接節(jié)點。 搜索中心社區(qū)的鄰接節(jié)點放入集合VJ中，并計算節(jié)點對中心社區(qū)的聯(lián)合隸屬度 B(b,Cz)，?b∈VJ。

Step 7：構(gòu)建擴展集合。置擴展VK=Φ，遍歷集合VJ，判斷?b∈VJ，若 B(b,Cz)≥BT，則將節(jié)點 b 放入集合VK中。

Step 8：擴展中心社區(qū)。判斷擴展結(jié)合VK是否為空集， 若不是空集， 則將擴展集合節(jié)點加入中心社區(qū)，形成新的中心社區(qū)Cz，中心社區(qū)中所有節(jié)點標記為“J”，并返回 Step 5；若是空集，則返回 Step 2。

2.1.3 區(qū)域網(wǎng)絡(luò)劃分評價

模塊度是評估社區(qū)發(fā)現(xiàn)算法質(zhì)量的常用指標，根據(jù)Newman[18]提出的Q 函數(shù)可知，當模塊度最大時，網(wǎng)絡(luò)社區(qū)的劃分效果最好。 考慮到空間網(wǎng)絡(luò)對實際距離的敏感度較大， 需改進普通的模塊度公式，從而提出了距離模塊度[19]概念，如式（3）和式（4）所示。

式中：f(d(vi,vj))為節(jié)點 vi、vj的距離衰減函數(shù)，衰減函數(shù)為為實際距離，o 為數(shù)據(jù)的自適應(yīng)值；d(vi,vj)為節(jié)點 vi、vj的實際距離。

2.2 高速鐵路線團網(wǎng)絡(luò)劃分

二級區(qū)域網(wǎng)絡(luò)實現(xiàn)了區(qū)域內(nèi)部聯(lián)系緊密，然而區(qū)域網(wǎng)絡(luò)內(nèi)含的節(jié)點仍舊較多，直達、換乘的處理仍舊比較復雜。 根據(jù)客流分配結(jié)果和路網(wǎng)基礎(chǔ)結(jié)構(gòu)分析，從經(jīng)濟效益和旅客出行需求出發(fā)，考慮在跨線節(jié)點處的客流達到一定的閾值才開行跨線列車，否則組織旅客中轉(zhuǎn)換乘。 因此，借用換乘虛擬弧和換乘概率對二級區(qū)域網(wǎng)絡(luò)內(nèi)部線路進行再劃分。 劃分的方法如下：

假設(shè)一個高速鐵路小線網(wǎng)有三條線路，分別為B-C、A-E、D-F， 其中車站 C、D 為網(wǎng)絡(luò)中的跨線節(jié)點，如圖2 所示。

圖2 小線網(wǎng)示意

設(shè)根據(jù)客流分布計算出在跨線節(jié)點C、D 的換乘概率如表1 所示，取換乘概率閾值為0.5。

表1 小線網(wǎng)換乘節(jié)點換乘概率（單向）

圖3 線團網(wǎng)絡(luò)劃分示意

3 案例分析

以成都局管內(nèi)高速鐵路線路為網(wǎng)絡(luò)基礎(chǔ)數(shù)據(jù)，進行實例分析。 根據(jù)鐵路運行圖編制系統(tǒng)V4.0 的2021 年高速鐵路列車開行情況為基礎(chǔ)，假定分界站為終到站，分界站以遠不作考慮，選擇10 個線路上的62 個車站構(gòu)建物理網(wǎng)絡(luò)。 以2021 年第四季度的客票數(shù)據(jù)作為依據(jù)，統(tǒng)計某日內(nèi)高速鐵路網(wǎng)絡(luò)上的OD 客流數(shù)據(jù)， 并根據(jù)車站和線路區(qū)間的基礎(chǔ)數(shù)據(jù)構(gòu)建物理網(wǎng)路。

借用文獻[13]提出的改進Dijkstra 算法先求解最短徑路，再用雙掃描算法求解合理徑路集，根據(jù)OD 客流數(shù)據(jù)， 共計客流1 202 對， 在操作系統(tǒng)為WINdows11，CPU：Intel(R) Core(TM)i7-10710U，主頻1.19 GHz，16.0 GB 的系統(tǒng)環(huán)境下使用 Python 軟件進行求解，取繞行率，搜索出合理徑路集8 262 條。隨后借鑒文獻[20]和文獻[21]的研究數(shù)據(jù)進行試驗配流，可得到各線路區(qū)間的客流分配量，如圖4 所示。

圖4 客流分配結(jié)果

隨后進行二級區(qū)域網(wǎng)絡(luò)劃分。 以路網(wǎng)中節(jié)點之間1 202 對OD 客流以及節(jié)點之間的距離為基礎(chǔ)數(shù)據(jù)，設(shè)加權(quán)網(wǎng)絡(luò)調(diào)試權(quán)重為βw，以社區(qū)評價指標距離模塊度Q 作為評價指標。 當βw=0.3 時，有最高距離模塊度Q=0.76，最終得到最佳的區(qū)域劃分結(jié)果，從中發(fā)現(xiàn)重疊節(jié)點和中心節(jié)點，如圖5 和表2 所示。

圖5 二級區(qū)域網(wǎng)絡(luò)節(jié)點劃分結(jié)果

表2 二級區(qū)域網(wǎng)絡(luò)劃分結(jié)果

隨后在二級區(qū)域劃分的基礎(chǔ)上進行線團網(wǎng)絡(luò)劃分。 本文以區(qū)域1 為例，基于客流分配結(jié)果和路網(wǎng)基礎(chǔ)條件分析客流分布和線路走向， 如表3 所示，在換乘節(jié)點12 處，共銜接成貴、成渝、滬蓉、西成四個線路方向，根據(jù)客流分配結(jié)果可得到四個方向的銜接的跨線客流量， 根據(jù)公式可計算換乘節(jié)點的各個方向客流的換乘概率， 如表3所示。

表3 換乘節(jié)點12 各銜接方向的換乘率

根據(jù)表3 可知， 虛擬換乘弧21-12-52 和13-12-52 的換乘率較低，有開行直達列車的潛力，而虛擬換乘弧45-12-52 和21-12-45 的換乘率較高，考慮換乘運輸。 同時，根據(jù)線路走向分析可知，成貴和西成高鐵較為平順地銜接于成都東站，而成渝和西成高鐵的銜接相對比較彎曲， 故將該換乘節(jié)點12設(shè)置50%為換乘率閾值，其他弧段的換乘率為中間值，將成貴和西成高鐵化為同一線團網(wǎng)絡(luò)，成渝和滬蓉則單獨成團。 同理，區(qū)域網(wǎng)絡(luò)1 在節(jié)點23 處有綿瀘高鐵銜接，并在節(jié)點23 處形成一個Y 行線路，弧段22-23-54 則相對平滑， 故可將兩條線路劃分為同一線團網(wǎng)絡(luò)。 因此，可將區(qū)域1 內(nèi)的區(qū)域網(wǎng)絡(luò)劃分為三個線團網(wǎng)絡(luò)，如圖6 所示，圖中黑色節(jié)點23、47 為二級社區(qū)網(wǎng)絡(luò)劃分時發(fā)現(xiàn)的重疊節(jié)點，節(jié)點12 則是在三級網(wǎng)絡(luò)劃分時發(fā)現(xiàn)的換乘節(jié)點。

圖6 區(qū)域網(wǎng)絡(luò)1 的三級網(wǎng)絡(luò)劃分結(jié)果

4 結(jié)論

本文分析了既有區(qū)域劃分的劣勢，根據(jù)我國鐵路網(wǎng)絡(luò)長短途客流并存、 區(qū)域性結(jié)構(gòu)布局等特點，探索性地提出高速鐵路“路網(wǎng)-區(qū)域-線團”三級網(wǎng)絡(luò)劃分：將高速鐵路物流網(wǎng)絡(luò)轉(zhuǎn)換為客流網(wǎng)絡(luò)并將其作為一級網(wǎng)絡(luò)；二級區(qū)域網(wǎng)絡(luò)劃分以節(jié)點客流量和距離作為相似權(quán)和相異權(quán)， 采用局部擴散思想，并基于聯(lián)合引力度的重疊社區(qū)發(fā)現(xiàn)方法尋找中心社區(qū)， 完成社區(qū)結(jié)構(gòu)劃分從而形成二級區(qū)域網(wǎng)絡(luò)；三級線團網(wǎng)絡(luò)劃分根據(jù)換乘節(jié)點的換乘概率和列車運行條件，形成內(nèi)部以直達客流交互為主的線路團體，從而形成高速鐵路“路網(wǎng)-區(qū)域-線團”的三級網(wǎng)絡(luò)。 最后選取成都局管內(nèi)的高速鐵路網(wǎng)絡(luò)作為案例，將路網(wǎng)劃分為3 個二級區(qū)域網(wǎng)絡(luò)并以區(qū)域1 為例將其劃分為3 個線團網(wǎng)絡(luò)，為高速鐵路列車開行方案優(yōu)化設(shè)計提供了良好的前提條件。