李光春，聶磊

(北京交通大學，交通運輸學院，北京 100044)

0 引言

交通規(guī)劃是保障城市公共交通發(fā)展的科學先導，而公交線網(wǎng)規(guī)劃一直是其重要任務。合理選取公交站點和科學規(guī)劃公交線網(wǎng)能提升城市公交服務水平，提高乘客綠色出行分擔率，以及緩解交通擁堵等。

王煒[1]提出“逐條布線、優(yōu)化成網(wǎng)”的公交線網(wǎng)規(guī)劃方法，該方法實際可行性較強，是目前較為常用的公交線網(wǎng)布設方法之一。郭志勇等[2]提出“一路一線”的規(guī)劃設想，該方法以直線道路規(guī)劃公交線路，將公交線網(wǎng)與城市路網(wǎng)進行最大限度擬合。王佳等[3]提出建立公交骨架線路和公交接運線路的雙層城市公交網(wǎng)絡結(jié)構(gòu)，建立并求解了雙層優(yōu)化模型。陳巍[4]等將線網(wǎng)規(guī)劃和發(fā)車頻率同步優(yōu)化，提升線網(wǎng)服務效率。綜合現(xiàn)有大量的理論與實踐研究，公交線網(wǎng)設計問題主要分為以實際經(jīng)驗為主的設計，理想條件下的最優(yōu)化設計和基于啟發(fā)式算法的現(xiàn)實設計這3類[5]。

公交線網(wǎng)規(guī)劃模型通?；诔丝统鲂行枨蠛统鞘芯€網(wǎng)指標構(gòu)建，近年來為契合城市規(guī)模擴張和公交服務轉(zhuǎn)型，優(yōu)化模型通常被分層考慮[6]。模型目標函數(shù)主要考慮：乘客出行時間[7]、出行換乘次數(shù)[8]、乘客時間成本與運營企業(yè)成本[9]、最大化乘客舒適度[10]、網(wǎng)絡直達性與覆蓋率等其他需求[11]。約束方面，通常需要結(jié)合實際情況考慮乘客需求、線網(wǎng)長度、服務效率、服務范圍、接駁情況和非直線系數(shù)等規(guī)劃要求。鑒于公交線網(wǎng)規(guī)劃問題復雜度，精確算法求解規(guī)模受限，如遺傳算法[12]、模擬退火算法[13]、禁忌搜索算法[14]、變鄰域搜索算法[15]等啟發(fā)式算法被用于該問題并表現(xiàn)出了較好的結(jié)果。但上述算法通常應用于數(shù)據(jù)集或小型實際案例，大型實際案例還鮮有較為高效的算法。

本文面向于求解公交線網(wǎng)規(guī)劃實際大規(guī)模問題，提出一種乘客出行OD合并算法和基于自適應大鄰域算法的公交線網(wǎng)規(guī)劃方法。該方法考慮乘客路程距離將乘客出行OD進行合并，將公交線網(wǎng)分為主線和支線網(wǎng)絡合理規(guī)劃。在規(guī)劃過程中考慮線網(wǎng)直達效率、線路長度、OD需求覆蓋率和城市公交路網(wǎng)換乘情況等。所設計的改進自適應大鄰域算法包括8種破壞/修復算子，同時設置自適應規(guī)則避免陷入局部最優(yōu)。

1 乘客出行OD合并

線網(wǎng)規(guī)劃問題是一個NP-hard 問題，問題復雜度較高，本文為實現(xiàn)計算實際較大規(guī)模城市案例，設計了一種兩階段算法首先對乘客出行OD 進行合并。該方法思路是將分散的乘客OD 按照空間距離合并至中心的需求節(jié)點，以實現(xiàn)公交備選站點的選取和城市路網(wǎng)骨架的構(gòu)造。第1 階段是交通小區(qū)(計算單元)的劃分工作，交通小區(qū)是具有一定交通關(guān)聯(lián)度和交通相似度的節(jié)點或連線的集合。參考交通小區(qū)劃分規(guī)則，本文為合并乘客OD提出改進“路網(wǎng)切割，補充劃分”的計算單元分割方法，算法流程如下。

第2階段是在模塊分割完成后，依次計算所有計算單元內(nèi)部的合并中心點。該問題現(xiàn)實意義可理解為基于散布于區(qū)域中的乘客出行OD 如何有效設置公交站點?？紤]到每個單元內(nèi)節(jié)點數(shù)量較少，本文建立選址問題模型并使用Gurobi求解以獲得中心點。對于所有單元內(nèi)被合并點流量均歸并至中心點，歸并完成后刪除所有被合并點。

2 主線及支線公交線網(wǎng)規(guī)劃模型

2.1 模型假設及符號說明

本文問題是在給定乘客出行OD 需求、節(jié)點和節(jié)點間距離條件下，計算等同于預設線路集合N數(shù)量的由車輛站點k∈K構(gòu)成的城市公交線網(wǎng)。其中，所設置任意線路n需要包含符合要求數(shù)量的站點k，站點間依次連接構(gòu)成公交線路，所有公交線路共同構(gòu)成公交線網(wǎng)。構(gòu)建模型所需符號的說明如表1所示。

表1 符號說明Table 1 Notations

2.2 目標函數(shù)

目標函數(shù)為

總目標函數(shù)為

式(1)表示線網(wǎng)直達客流占路網(wǎng)總客流的比例；式(2)表示線網(wǎng)總長度與城市路網(wǎng)總長度的比值；式(3)表示線網(wǎng)覆蓋的站點數(shù)量與站點總數(shù)之比；式(4)為總的目標函數(shù)。

2.3 約束條件

2.3.1 城市線網(wǎng)規(guī)劃模型約束

其中，式(5)表示正反向連通性一致；式(6)表示同一線路中連通性一致；式(7)表示線路選中站點即為被服務站點；式(8)表示線路中節(jié)點的數(shù)量應與路段數(shù)量保持對應關(guān)系；式(9)和式(10)表示線路中任意節(jié)點只能有兩個或一個相鄰節(jié)點；式(11)和式(12)表示每條線路包含的節(jié)點數(shù)量應滿足預設上下限；式(13)用以避免子環(huán)路的形成；式(14)表示每條線路的非直線系數(shù)應滿足要求；式(15)用以判斷節(jié)點i,j是否可互相直達；式(16)和式(17)表示線網(wǎng)的總長度滿足預設上下限；式(18)～式(20)對決策變量進行定義。

2.3.2 支線模型更新

考慮到主線和支線網(wǎng)絡在城市公交系統(tǒng)中功能定位和服務需求不同，其規(guī)劃工作應存在一定差異性。本文所設計支線網(wǎng)絡規(guī)劃在完成主線規(guī)劃的基礎上進行，清除主線網(wǎng)絡已服務的OD，該階段更側(cè)重于延展輻射的城市區(qū)域和滿足主線線路間的換乘。支線模型做出如下修改。

(1)新增約束

每條支線至少與一條主線相連(有換乘節(jié)點)，即

(2)預設參數(shù)調(diào)整

對支線線路規(guī)劃標準更新，如線路長度、節(jié)點數(shù)量、非直線系數(shù)、線網(wǎng)總長等約束按需求進行調(diào)整。

(3)目標函數(shù)權(quán)重調(diào)整

增加目標函數(shù)中節(jié)點覆蓋率部分的權(quán)重。

3 改進自適應大鄰域搜索算法

本文問題是一個NP-hard 問題，且考慮到城市實際乘客出行規(guī)模，選擇自適應大鄰域搜索算法求解。

3.1 編碼結(jié)構(gòu)與初始可行解

算法編碼結(jié)構(gòu)是設計元啟發(fā)算法的先決條件，本文針對公交線網(wǎng)規(guī)劃問題性質(zhì)，選取自然數(shù)編碼結(jié)構(gòu)。為避免線路重復度過高、線路多樣性不足和線路關(guān)聯(lián)性較差等問題，本文在初始解生成階段首先構(gòu)建待選線路池。初始可行解生成方法如圖1所示，其流程為：從全網(wǎng)隨機選取一條邊作為起始邊，通過向兩邊合理延伸擴充線路站點，當生成達到一定長度或站點數(shù)后結(jié)束延展生成單條線路。若生成的線路滿足單條線路要求，則將其加入線路池中。不斷生成單條線路，當線路池所含線路數(shù)量達到預設規(guī)模后，從中選取一組預設數(shù)量的線路構(gòu)成滿足約束的解方案。

圖1 初始解生成算法Fig.1 Initial solution generation algorithm

3.2 鄰域構(gòu)造

算法尋優(yōu)效率通常和算子設置密切相關(guān)，一些現(xiàn)有元啟發(fā)式算法算子缺乏與現(xiàn)實問題的契合性，本文結(jié)合公交線路特性，共設計8 種鄰域算子，如圖2所示。

圖2 破壞算子和修復算子Fig.2 Destroy operators and repair operators

3.3 自適應規(guī)則

普通鄰域搜索算法通常包含多種算子，但往往缺少不斷更新的自適應機制，加入自適應規(guī)則能確保算子和當前解的適配度較高。本文設計自適應大鄰域算法自適應規(guī)則如下。

(1)接受規(guī)則

當所得解優(yōu)于當前最優(yōu)解時，記錄當前解為最優(yōu)解。為避免陷入局部最優(yōu)，本文設置80%概率接受一個較差解，其中較差解的定義為目標函數(shù)值大于等于0.8乘當前解的目標函數(shù)值的解。

(2)概率計算規(guī)則

(3)權(quán)重更新規(guī)則

定義權(quán)重為ψ，a和b表示上次迭代中的不同算子方法。若當前解為全局最優(yōu)解，則ψ=2；若當前解優(yōu)于記錄解，則ψ=1；若當前解被記錄，則ψ=0.5；若當前解不被記錄，則ψ=0。權(quán)重更新公式為

3.4 算法流程

綜上所述，本文設計算法整體流程如圖3 所示。算法首先對原始路網(wǎng)數(shù)據(jù)使用節(jié)點合并算法縮減問題規(guī)模；其次將合并后節(jié)點作為備選站點輸入，運用改進自適應大鄰域算法計算縮減規(guī)模后的公交線網(wǎng)規(guī)劃問題。在該問題計算過程中，第1階段計算主線網(wǎng)絡，第2階段更新主線結(jié)果后計算支線網(wǎng)絡，最終將結(jié)果進行匯總得到整體線網(wǎng)。

4 案例分析

為全面分析本文方法在線網(wǎng)規(guī)劃中的應用效果，本文分別選取數(shù)據(jù)集案例和實際案例進行驗證。案例均在一臺搭載16 G內(nèi)存和2.30 GHz i7-11800H CPU的筆記本電腦上完成。通過Windows 11環(huán)境下的Python3.9實現(xiàn)算法編寫和案例計算。

4.1 公測數(shù)據(jù)集算例

本文選取Transportation Networks 數(shù)據(jù)集中的Sioux-falls 路網(wǎng)進行計算，該路網(wǎng)共24 個節(jié)點，76 條有向邊，528 個OD 對(Sioux-falls 路網(wǎng)的具體細節(jié)可參考胡繼華[16]的研究)。為更直觀地進行算法層面對比，本文不對該路網(wǎng)進行節(jié)點合并且僅進行一次改進自適應大鄰域算法，將所得結(jié)果與現(xiàn)有算法進行對比。圖4 展示了算法迭代過程，表2 詳細展示了計算結(jié)果。表3指標結(jié)果表明，本文改進自適應大鄰域算法具有更高的直達率和更少的換乘次數(shù)，且不會出現(xiàn)二次換乘情況。

圖4 Sioux-falls路網(wǎng)算法迭代圖Fig.4 Sioux-falls network algorithm iteration

表2 Sioux-falls詳細對比結(jié)果Table 2 Sioux-falls network detailed comparison

表3 Sioux-falls網(wǎng)絡指標Table 3 Evaluating indicator of Sioux-falls network

4.2 邢臺實際算例

為有效驗證本文方法在現(xiàn)實中計算效果，本文選取邢臺市進行驗證，結(jié)合當?shù)匾?guī)章制度、實際路網(wǎng)情況和算法測試結(jié)果，參數(shù)標定如表4所示。

表4 參數(shù)設定Table 4 Parameters setting

本文所獲原始數(shù)據(jù)為基于1372 個節(jié)點的乘客出行OD，設置合并距離上限φ=500 m，合并后站點所含發(fā)生交通量的上限β=10000 人，采用節(jié)點合并算法合并備選站點285 個。如圖5(a)所示，大量散步節(jié)點被歸納至合并點，該情況在中心城區(qū)尤為明顯。圖5(b)將合并點以直徑1 km畫圓，合并點可有效輻射整個邢臺城區(qū)，少有的未輻射區(qū)域為景區(qū)或大型設施等無法覆蓋區(qū)域。同時，合并點覆蓋重復率也較低，驗證了本文OD合并算法的準確性。

圖5 OD合并和覆蓋情況示意圖Fig.5 OD merging and coverage

表5 為邢臺市實際計算結(jié)果指標，圖6(a)為規(guī)劃線網(wǎng)布局，圖6(b)為線網(wǎng)客流覆蓋熱力圖。如圖表所示，本文所設計的公交線網(wǎng)規(guī)劃方法對大規(guī)模實際問題具有良好的適用性，主要表現(xiàn)為以下兩點。

圖6 規(guī)劃線網(wǎng)與道路和OD匹配示意圖Fig.6 Network planning and matching condition of road and OD

表5 邢臺線網(wǎng)評價指標Table 5 Evaluating indicator of Xingtai network

(1)整體網(wǎng)絡覆蓋率、服務率和服務效率均表現(xiàn)較高水平

整體網(wǎng)絡站點覆蓋率為78.94%，覆蓋節(jié)點間的流量占所有節(jié)點間流量的84.67%，覆蓋率較高。整體網(wǎng)絡直達率為26.58%，一次換乘率為59.69%，超過80%的需求僅通過至多一次換乘即可滿足，99.76%的出行需求可以在兩次換乘以內(nèi)實現(xiàn)，較好地滿足了大部分居民的乘車需求。

(2)主線與支線規(guī)劃合理

規(guī)劃公交線路與城市路網(wǎng)匹配情況良好，主線百公里服務人次為3662.370，明顯高于支線的747.299，大批客流通過主線線路運輸，符合主線網(wǎng)絡服務核心路段和OD 的設計目的。支線線路數(shù)為主線的2倍，但支線網(wǎng)絡總長度為296774.31 km，與主線網(wǎng)絡總長275817.00 km相差不大，符合設計短程支線接駁換乘的需求。此外，在主線網(wǎng)絡站點覆蓋率為45.6%的情況下，加入支線網(wǎng)絡使整體覆蓋率達到了78.94%，說明支線網(wǎng)絡覆蓋了較多主線網(wǎng)絡未覆蓋的節(jié)點，大幅提升了公交服務覆蓋率。

5 結(jié)論

本文為解決實際公交線網(wǎng)規(guī)劃問題提出了一套兩階段規(guī)劃方法，其中，所設計的OD 合并算法能有效篩選公交站點和縮減問題計算規(guī)模；數(shù)學模型將城市公交線路分為主線和支線，分別以不同約束條件和參數(shù)設置體現(xiàn)其差異性；設計了一種對公交線網(wǎng)規(guī)劃問題適配度較高的改進自適應大鄰域搜索算法進行計算。通過公共數(shù)據(jù)集網(wǎng)絡和邢臺市數(shù)據(jù)進行案例分析，結(jié)果表明：本文自適應大鄰域算法效果明顯優(yōu)于其他現(xiàn)有研究算法，主線和支線規(guī)劃合理；該方法整體規(guī)劃效果良好，線路服務水平較高。