劉明敏，何鴻杰，金安

（廣州市交通規(guī)劃研究院有限公司，廣州 510030）

0 引言

近年各城市陸續(xù)開(kāi)通軌道交通線路，軌網(wǎng)規(guī)模逐年擴(kuò)大[1]。一方面，單位里程軌道建設(shè)成本不斷增加，資金需求巨大；另一方面，客流效益不足，運(yùn)營(yíng)補(bǔ)虧負(fù)擔(dān)較重。由于軌道交通網(wǎng)絡(luò)建成后難以改變，網(wǎng)絡(luò)設(shè)計(jì)和線路選擇的在軌道交通線網(wǎng)規(guī)劃階段則顯得尤為重要。

線網(wǎng)規(guī)劃理論研究層面：Ralf 等[2]、Bruno 等[3]、Laporte等[4]以系統(tǒng)行程時(shí)間為目標(biāo)進(jìn)行網(wǎng)絡(luò)設(shè)計(jì)，黃超等[5]以社會(huì)經(jīng)濟(jì)收益為目標(biāo)進(jìn)行城市群鐵路網(wǎng)絡(luò)設(shè)計(jì)，衛(wèi)振林等[6]以運(yùn)營(yíng)效果、線網(wǎng)結(jié)構(gòu)等綜合因素為目標(biāo)對(duì)方案進(jìn)行優(yōu)選。Dicesare[7]、Current等[8]以總成本最小為目標(biāo)進(jìn)行線路選擇，Bussieck等[9]、Canca 等[10]以客流覆蓋最大為目標(biāo)確定線路走向。大部分相關(guān)研究均在建立數(shù)學(xué)模型后，使用非精確算法求解最優(yōu)方案?，F(xiàn)有研究成果中，模型復(fù)雜導(dǎo)致難以應(yīng)用于城市大規(guī)模站點(diǎn)、多線路計(jì)算；網(wǎng)絡(luò)設(shè)計(jì)和線路布設(shè)時(shí)缺乏建設(shè)時(shí)的工程可行性和開(kāi)通后的運(yùn)營(yíng)約束考慮。

規(guī)劃實(shí)踐層面，我國(guó)線網(wǎng)規(guī)劃的技術(shù)人員普遍采用“點(diǎn)-線-網(wǎng)”的規(guī)劃方法，先確定客流集散點(diǎn)，再根據(jù)客流走廊和土地利用確定線路走向，最后基于線路確定大致網(wǎng)絡(luò)形態(tài)。在基于給定站點(diǎn)設(shè)計(jì)網(wǎng)絡(luò)和布設(shè)線路這一問(wèn)題上，實(shí)踐主要依據(jù)個(gè)人技術(shù)經(jīng)驗(yàn)，缺少量化計(jì)算，未充分定量考慮建設(shè)成本、可行性和服務(wù)水平。一方面，規(guī)劃工作難度巨大；另一方面，初始方案質(zhì)量難以保證。

綜上，本文對(duì)城市軌道交通線網(wǎng)規(guī)劃階段的軌道交通線網(wǎng)網(wǎng)絡(luò)設(shè)計(jì)和線路選擇問(wèn)題進(jìn)行研究，提出一種定量的線網(wǎng)規(guī)劃初步輔助構(gòu)建模型。在模型中考慮線網(wǎng)總里程、直達(dá)客流、換乘客流量等目標(biāo)，并根據(jù)實(shí)踐需求改進(jìn)求解算法。在給定大規(guī)模站點(diǎn)條件下，可以實(shí)現(xiàn)網(wǎng)絡(luò)設(shè)計(jì)和線路選擇等計(jì)算，可形成初步方案，便于輔助規(guī)劃人員進(jìn)行后續(xù)線網(wǎng)規(guī)劃工作。

1 問(wèn)題描述

城市軌道交通線網(wǎng)規(guī)劃實(shí)踐中，基于給定站點(diǎn)，希望通過(guò)最短的軌道網(wǎng)絡(luò)里程規(guī)模，串接選定站點(diǎn)，實(shí)現(xiàn)最大客流覆蓋范圍；同時(shí)在換乘次數(shù)盡可能少的情況下，構(gòu)建線路，實(shí)現(xiàn)較高的客流服務(wù)水平。由于缺乏量化為主的成網(wǎng)技術(shù)流程，選定站點(diǎn)較多時(shí)，規(guī)劃人員難以主觀確定較優(yōu)的線網(wǎng)規(guī)劃方案，故本文根據(jù)上述目標(biāo)建立數(shù)學(xué)模型并通過(guò)算法求解，提出量化初步成網(wǎng)技術(shù)流程，為后續(xù)線網(wǎng)規(guī)劃工作提供輔助參考。

上述目標(biāo)具體為在給定站點(diǎn)和對(duì)應(yīng)站點(diǎn)間的預(yù)測(cè)客流OD前提下，以網(wǎng)絡(luò)總里程最小化和直達(dá)客流比、一次換乘客流比最大化為目標(biāo)，建立數(shù)學(xué)模型，采取逐個(gè)節(jié)點(diǎn)進(jìn)行連接，不斷變換線路布設(shè)方式的策略，求解獲得最優(yōu)網(wǎng)絡(luò)和線路方案。

（1）決策變量

xij——0-1 變量，站點(diǎn)i和j的鄰接關(guān)系，若站點(diǎn)i和j之間相互連接且i≠j，xij=1 ，否則，xij=0，xij作為元素組成的對(duì)稱鄰接矩陣為X；

yijk——0-1變量，若在線路k上站點(diǎn)i和j是相鄰的兩個(gè)站點(diǎn)，yijk=1，否則，yijk=0，yijk作為元素組成的對(duì)稱鄰接矩陣為Yk。

（2）其他變量

G——軌道交通網(wǎng)絡(luò)的無(wú)向圖；

V——G的站點(diǎn)編號(hào)集合；

ε——G的邊集合；

K——線路編號(hào)集合；

aij——0-1變量，若站點(diǎn)i和j之間相互可達(dá)且i≠j，aij=1，否則，aij=0，aij可由鄰接矩陣X通過(guò)Warshall算法計(jì)算得到；

θi,bc——站點(diǎn)i作為頂點(diǎn)，與另外兩個(gè)不同站點(diǎn)b，c形成的夾角角度；

dij——站點(diǎn)i和j的距離，以時(shí)間、長(zhǎng)度等形式表示；

tij——站點(diǎn)i至站點(diǎn)j的起訖點(diǎn)客流量；

rd——直達(dá)客流比，使用Logit 模型根據(jù)tij和Yk計(jì)算得到；

rx——一次換乘客流比，使用Logit模型根據(jù)tij和Yk計(jì)算得到；

ra——rd和rx通過(guò)理想點(diǎn)法轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題的目標(biāo)值；

ukl——線路k和線路l間復(fù)線段的數(shù)量；

qik——用于子回路消除約束的輔助變量。

（3）基本假設(shè)

為簡(jiǎn)化問(wèn)題，提出以下假設(shè)：

①忽略換乘的時(shí)間成本；

②任意兩個(gè)相連站點(diǎn)間的距離用直線距離替代實(shí)際距離。

2 數(shù)學(xué)模型

2.1 模型結(jié)構(gòu)

雙層模型將從“點(diǎn)-網(wǎng)-線”的角度進(jìn)行線網(wǎng)規(guī)劃，首先根據(jù)給定站點(diǎn)生成最優(yōu)網(wǎng)絡(luò)，然后在生成的最優(yōu)網(wǎng)絡(luò)上進(jìn)行線路布設(shè)。模型上層為網(wǎng)絡(luò)設(shè)計(jì)模型，以實(shí)現(xiàn)站點(diǎn)全部覆蓋的網(wǎng)絡(luò)總長(zhǎng)度最小化為目標(biāo)，基于給定站點(diǎn)生成軌道網(wǎng)絡(luò)；模型下層為線路選擇模型，以直達(dá)客流比和一次換乘客流比為目標(biāo)，基于上層模型生成的軌道網(wǎng)絡(luò)，進(jìn)行線路布設(shè)。

2.2 網(wǎng)絡(luò)設(shè)計(jì)模型

網(wǎng)絡(luò)設(shè)計(jì)模型作為雙層模型的上層，將基于給定站點(diǎn)初步生成軌道交通網(wǎng)絡(luò)，其目標(biāo)和約束為

式中：pmax——站點(diǎn)度的最大值；

ω——轉(zhuǎn)向最大角度；

dmin、dmax——任意兩個(gè)站點(diǎn)間距的最小值、最大值。

優(yōu)化目標(biāo)式（1）表示期望實(shí)現(xiàn)網(wǎng)絡(luò)總長(zhǎng)度最小化。約束：式（2）表示站點(diǎn)間可達(dá)性約束，即生成的網(wǎng)絡(luò)需要覆蓋到全部站點(diǎn)；式（3）表示站點(diǎn)的度約束，即確定與每個(gè)站點(diǎn)相連的其他站點(diǎn)的數(shù)量范圍；式（4）和式（5）均為工程可行性約束，式（4）表示角度約束，網(wǎng)絡(luò)中站點(diǎn)的度為2的站點(diǎn)所在的歐拉路徑，轉(zhuǎn)向角度不能大于ω；式（5）表示站間距約束，限制兩個(gè)相連站點(diǎn)的間距。

2.3 線路選擇模型

線路選擇模型的目的是基于上層模型求解得到的網(wǎng)絡(luò)，進(jìn)行線路布設(shè)，確定線路數(shù)量、線路走向和線路經(jīng)過(guò)的站點(diǎn)數(shù)量，線路選擇模型如下：

式中：r——從rd，rx和ra中選用的目標(biāo)函數(shù)；

τmin、τmax——線路的最小、最大長(zhǎng)度；

N1,min、N1,max——線路最小、最大站點(diǎn)數(shù)；

N2,max——任意復(fù)線段上的最大站點(diǎn)數(shù)；

N3,max——任意復(fù)線段上的最大線路數(shù)；

N4,max——G中出現(xiàn)復(fù)線段的最大次數(shù)；

M——一個(gè)很大的常數(shù)。

優(yōu)化目標(biāo)式（6）表示最大化目標(biāo)函數(shù)。約束：式（7）表示線路必須在已有網(wǎng)絡(luò)上布設(shè)；式（8）表示連續(xù)性約束，確保各個(gè)線路連續(xù)不能中斷；式（9）表示站點(diǎn)訪問(wèn)約束，各個(gè)站點(diǎn)至少被線路經(jīng)過(guò)1 次；式（10）和式（11）表示線路長(zhǎng)度約束，分別表示線路的長(zhǎng)度范圍和經(jīng)過(guò)站點(diǎn)數(shù)量范圍；式（12）～式（14）表示復(fù)線約束，分別表示兩條線路間復(fù)線段包含站點(diǎn)的數(shù)量范圍、復(fù)線段上的線路數(shù)量范圍和G中出現(xiàn)復(fù)線場(chǎng)景的最大次數(shù)；式（15）表示角度約束，任意線路的轉(zhuǎn)向角度不能大于ω；式（16）表示Miller 等針對(duì)車輛路徑規(guī)劃問(wèn)題提出的子回路限制約束[11]，防止產(chǎn)生環(huán)線外的異常環(huán)路。

3 網(wǎng)絡(luò)設(shè)計(jì)模型求解算法

3.1 基于聚類的最小生成樹(shù)網(wǎng)絡(luò)求解

上層模型式（1）～式（5）可轉(zhuǎn)化為帶約束的最小生成樹(shù)求解問(wèn)題，故使用Kruskal 算法求解上層模型。由于Kruskal 算法的時(shí)間復(fù)雜度較大，且最小生成樹(shù)的網(wǎng)絡(luò)結(jié)構(gòu)與實(shí)際城市軌道交通系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)存在較大區(qū)別，為解決以上兩個(gè)問(wèn)題，提出基于聚類求解最小生成樹(shù)方法，操作示例如圖1所示，具體步驟如下：

圖1 基于聚類的最小生成樹(shù)求解算法Fig.1 Minimum spanning tree algorithm based on clustering

Step 1 分解。將G中所有站點(diǎn)按照它們的相對(duì)位置，使用聚類算法（如Kmeans 算法），將站點(diǎn)分為不同聚類。

Step 2 子最小生成樹(shù)求解。使用Kruskal算法求解各個(gè)聚類中關(guān)于站點(diǎn)的最小生成樹(shù)。

Step 3 合并。將各個(gè)聚類的子最小生成樹(shù)進(jìn)行合并，組成完整網(wǎng)絡(luò)，合并的原則是使所有站點(diǎn)間相互可達(dá)和網(wǎng)絡(luò)總長(zhǎng)度增加最小。

3.2 生成網(wǎng)絡(luò)修正

盡管在最小生成樹(shù)求解過(guò)程中加入了式（3）～式（5），但生成的網(wǎng)絡(luò)與實(shí)際軌道交通網(wǎng)絡(luò)相比，仍會(huì)有許多不合理的異常連接方式，這些異?？赡軙?huì)導(dǎo)致線路長(zhǎng)度過(guò)短、換乘站數(shù)量過(guò)多、網(wǎng)絡(luò)非直線系數(shù)增加等問(wèn)題，進(jìn)而影響線路布設(shè)。為消除異常連接方式，提出以下幾種生成網(wǎng)絡(luò)的修正操作，修正操作示例如圖2 所示，修正方法如表1 所示。具體修正流程如下：

圖2 網(wǎng)絡(luò)修正方法示意Fig.2 Illustrations of network repair strategies

Step 1 對(duì)于通過(guò)基于聚類的最小生成樹(shù)求解算法獲得網(wǎng)絡(luò)，首先檢查表1 中所有異常連接方式，并使用表1中對(duì)應(yīng)的修正操作按順序逐步進(jìn)行修正。

表1 網(wǎng)絡(luò)修正方法Table 1 Methods to modify network generated

Step 2 修正操作可能產(chǎn)生新的異常連接，重新檢查網(wǎng)絡(luò)中存在的異常并進(jìn)行相應(yīng)的修正操作，若修正操作對(duì)應(yīng)的異常不存在，則跳過(guò)該修正操作。

Step 3 重復(fù)Step 2 直到網(wǎng)絡(luò)中不存在異常連接方式為止。

3.3 迭代優(yōu)選

最小生成樹(shù)求解算法和聚類算法的計(jì)算結(jié)果具有不確定性，導(dǎo)致每次生成網(wǎng)絡(luò)及其總長(zhǎng)度大小可能不一致，需要多次進(jìn)行基于聚類的最小生成樹(shù)網(wǎng)絡(luò)求解和生成網(wǎng)絡(luò)修正，直到最小生成網(wǎng)絡(luò)里程在多次迭代中不再下降保持穩(wěn)定，以獲得總長(zhǎng)度最小的最優(yōu)網(wǎng)絡(luò)。

4 線路選擇模型求解算法

4.1 網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)化

生成網(wǎng)絡(luò)G中的非換乘站、非起終點(diǎn)站對(duì)線路的布設(shè)影響較小，通過(guò)移除這些站點(diǎn)，獲得只包含換乘站和起終點(diǎn)站的簡(jiǎn)化網(wǎng)絡(luò)GS=（VS,εS），以簡(jiǎn)化計(jì)算，網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)化的示意圖如圖3所示。

圖3 網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)化示意Fig.3 Illustrations of simplification of generated network

4.2 求解算法選擇和可行解表達(dá)

下層線路選擇模型式（6）～式（16）屬于NP-hard問(wèn)題，在站點(diǎn)較多時(shí)使用精確算法無(wú)法求解，因此基于禁忌算法設(shè)計(jì)求解算法。

每個(gè)線網(wǎng)線路方案由可行解表達(dá)，單個(gè)可行解中包括 |K|條完整線路，每條線路以站點(diǎn)編號(hào)序列形式表示，例如{10,2,5,18,…} ，編號(hào)的順序表示線路逐個(gè)經(jīng)過(guò)的站點(diǎn)，該可行解形式保證可行解的編碼長(zhǎng)度可變，使禁忌算法能直接對(duì)可行解進(jìn)行操作，同時(shí)降低解空間的規(guī)模[12]。

4.3 初始可行解構(gòu)造

在構(gòu)造初始可行解時(shí)，對(duì)式（10）和式（11）進(jìn)行松弛，忽略線路長(zhǎng)度限制。為了使禁忌算法快速找到質(zhì)量較優(yōu)的可行解，采用貪心策略構(gòu)造初始可行解，具體步驟如下：

Step 1 選擇GS中任意未被任何線路經(jīng)過(guò)的起終點(diǎn)站或換乘站作為起始點(diǎn)，開(kāi)始新線路的構(gòu)造。

Step 2 在GS中，嘗試將線路延長(zhǎng)至與當(dāng)前點(diǎn)連接的其他站點(diǎn)，在滿足式（7）～式（16）的情況下，將線路延長(zhǎng)至客流效益目標(biāo)值增量最大的站點(diǎn)。

Step 3 若線路延長(zhǎng)至起始點(diǎn)外的起終點(diǎn)站或不能繼續(xù)延長(zhǎng)，轉(zhuǎn)到Step 4；否則，重復(fù)Step 2。

Step 4 若線路經(jīng)過(guò)至少兩個(gè)或以上的站點(diǎn)，將該線路加入初始可行解。

Step 5 若沒(méi)有新線路能夠生成，轉(zhuǎn)到Step 6；否則，回到Step 1。

Step 6 為減少不滿足式（15）和式（16）最小值限制的過(guò)短線路數(shù)量，在滿足式（7）～式（16）的情況下，合并初始可行解中任意兩條線路，直到?jīng)]有線路能被合并為止。

4.4 當(dāng)前可行解鄰域構(gòu)造

為禁忌算法構(gòu)造如下5種鄰域操作。

（1）線路交換。

選擇當(dāng)前可行解中的兩條相交線路，將它們中的一個(gè)換乘站作為中斷點(diǎn)，拆解兩條線路，然后隨機(jī)重新組合。

（2）線路拆解

選擇當(dāng)前可行解中的較長(zhǎng)線路，線路上的一個(gè)換乘站作為中斷點(diǎn)，將其拆解為兩條較短線路。

（3）直達(dá)線路構(gòu)造

兩個(gè)起終點(diǎn)站間的最短路站點(diǎn)序列直接作為新線路，新線路可能會(huì)與已有線路發(fā)生重疊，在發(fā)生重疊的位置上，剔除已有線路發(fā)生重疊的部分，產(chǎn)生新的較短線路。若剔除部分會(huì)將已有線路打斷，則進(jìn)行打斷并產(chǎn)生兩條新線路代替已有線路；若剔除部分與已有線路完全相同，則移除已有線路。

（4）復(fù)線交換

減少GS中一個(gè)復(fù)線段上的線路數(shù)量，即減少?gòu)?fù)線段上發(fā)生重疊的其中一條線路，減少線路數(shù)量的過(guò)程中，會(huì)剔除經(jīng)過(guò)復(fù)線段一條線路的重疊部分，剔除方法與（3）相同。同時(shí)在GS中的任意其他部分，通過(guò)延伸另外一條已有線路的形式，使延伸部分與其他線路發(fā)生重疊，增加新的復(fù)線段，或在已有復(fù)線段上增加重疊的線路數(shù)量。

（5）線路合并

合并當(dāng)前可行解中任意兩條線路，直到?jīng)]有線路能被合并為止。

以上5 種鄰域操作生成的新線路必須滿足式（7）～式（16），通過(guò)5種鄰域操作的不同組合可以獲得圖4所示的6種鄰域。

圖4 當(dāng)前可行解的6種鄰域Fig.4 Six neighborhoods of current feasible solution

4.5 禁忌表設(shè)置和藐視準(zhǔn)則

分別為線路交換和拆解操作設(shè)置禁忌表，站點(diǎn)i作為中斷點(diǎn)，使用某種操作得到的鄰域被選為最優(yōu)解時(shí)，對(duì)應(yīng)禁忌表中站點(diǎn)i會(huì)被加上禁忌代數(shù)θ。在隨后θ次迭代中，不能滿足藐視規(guī)則且再次以站點(diǎn)i作為中斷點(diǎn)的對(duì)應(yīng)操作獲得的鄰域?qū)?huì)被拋棄。禁忌長(zhǎng)度與站點(diǎn)數(shù)量正相關(guān)。

藐視準(zhǔn)則是禁忌算法中常用的準(zhǔn)則，即對(duì)于某個(gè)處于禁忌中的鄰域，如果該鄰域的目標(biāo)值優(yōu)于當(dāng)前最優(yōu)解的目標(biāo)值，則該鄰域可以直接無(wú)視禁忌代數(shù)，直接作為當(dāng)前最優(yōu)解和當(dāng)前可行解。

4.6 求解流程

為了降低解決問(wèn)題的難度，使用禁忌算法分別預(yù)先求出rd和rx的最優(yōu)目標(biāo)值，再解決兩個(gè)目標(biāo)rd和rx同時(shí)優(yōu)化的問(wèn)題。禁忌算法流程如圖5所示。

圖5 單目標(biāo)禁忌算法Fig.5 Tabu Search for single objective problem

在使用單目標(biāo)禁忌算法求解最優(yōu)rd和rx后，使用理想點(diǎn)法式（17）將rd和rx同時(shí)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題，然后以ra作為目標(biāo)，再次使用相同算法得到最優(yōu)方案。傳統(tǒng)多目標(biāo)算法求解的結(jié)果為Pareto 解集，需要對(duì)Pareto 解集中的方案進(jìn)行二次評(píng)選，過(guò)于復(fù)雜，而理想點(diǎn)法可直接得到最優(yōu)方案。相較于傳統(tǒng)的線性加權(quán)法，理想點(diǎn)法能夠保證算法的搜索路徑朝向兩個(gè)目標(biāo)共同優(yōu)化的方向。

式中：rd*、r*x——使用單目標(biāo)禁忌算法得到的最優(yōu)直達(dá)換乘比、一次換乘客流比；

wd、wx——對(duì)應(yīng)目標(biāo)值的權(quán)重。

5 計(jì)算實(shí)例

5.1 案例介紹

以某市現(xiàn)狀城市軌道交通站點(diǎn)為例，使用雙層模型自動(dòng)生成最優(yōu)線網(wǎng)規(guī)劃方案。網(wǎng)絡(luò)結(jié)構(gòu)方面，站點(diǎn)間距離假設(shè)為直線距離時(shí)，現(xiàn)狀網(wǎng)絡(luò)總里程為475.77 km，共有228 個(gè)站點(diǎn)，其中34 個(gè)換乘站，現(xiàn)狀線路共15 條，網(wǎng)絡(luò)平均最短路徑長(zhǎng)度為33.00 km；運(yùn)營(yíng)效率方面，日均出行量為518.44 萬(wàn)人次，rd=0.4284 和rx=0.3268。

5.2 網(wǎng)絡(luò)設(shè)計(jì)

算法參數(shù)設(shè)定：pmax=4，ω=90°，dmax=5 km，聚類算法選擇Kmeans算法，聚類數(shù)量選定為14，迭代求解次數(shù)為50次。

根據(jù)現(xiàn)狀站點(diǎn)，使用上層網(wǎng)絡(luò)設(shè)計(jì)模型求解得到的最優(yōu)網(wǎng)絡(luò)如圖6所示。與現(xiàn)狀網(wǎng)絡(luò)比較，生成網(wǎng)絡(luò)的總里程減少至467.89 km，換乘站數(shù)量仍為34個(gè)，平均最短路徑長(zhǎng)度為33.07 km。自動(dòng)生成網(wǎng)絡(luò)與現(xiàn)狀網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)區(qū)別不大，主要區(qū)別集中在圖6 灰色方框處，與現(xiàn)狀網(wǎng)絡(luò)相比，灰色方框處的交叉和冗余減少，平順性增加。外圍區(qū)域站點(diǎn)密度較低，成網(wǎng)方式簡(jiǎn)單明顯，這些部分自動(dòng)生成網(wǎng)絡(luò)與現(xiàn)狀網(wǎng)絡(luò)相同。

圖6 現(xiàn)狀網(wǎng)絡(luò)和上層網(wǎng)絡(luò)設(shè)計(jì)模型求解得到的最優(yōu)網(wǎng)絡(luò)Fig.6 Existed network and optimal network generated by upper-layer network design model

另外，從圖7 可以看到，求解算法在迭代至10次之前已經(jīng)搜索到最優(yōu)解，說(shuō)明算法的收斂速度較快，剩余30次迭代計(jì)算最優(yōu)目標(biāo)函數(shù)值并無(wú)變化。

圖7 上層模型目標(biāo)函數(shù)值隨迭代計(jì)算的變化Fig.7 Change in objective function value of upper model with iterative computation

5.3 線路選擇

算法參數(shù)設(shè)定：τmin=0.3 h ，τmax=1.2 h ，N1,min=9，N1,max=32，N2,max=2，N3,max=2，N4,max=1，ω=90°，禁忌算法迭代求解次數(shù)為200 次，每次迭代每種鄰域構(gòu)造5個(gè)，θ=4，wd=1.5，wx=1.0。

根據(jù)生成網(wǎng)絡(luò)，使用下層模型求解得到的最優(yōu)線路方案如圖8 和圖9 所示，不同明暗粗細(xì)的線代表不同線路，橫縱坐標(biāo)X和Y表示平面坐標(biāo)系中的相對(duì)位置。運(yùn)營(yíng)效率方面，最優(yōu)方案中包含14條線路，rd=0.4315 和rx=0.3406，均比現(xiàn)狀線網(wǎng)高，最優(yōu)方案具有更好地運(yùn)營(yíng)效率。線路走向方面，與現(xiàn)狀線路對(duì)比，線路數(shù)量減少1條，部分線路有一定程度的延長(zhǎng)；對(duì)于現(xiàn)狀換乘量較大的兩條線路，算法對(duì)其進(jìn)行了交換以減少換乘次數(shù)。

圖8 現(xiàn)狀線路和下層線路選擇模型求解得到的最優(yōu)線路方案（線路1～7）Fig.8 Current scheme and optimal scheme generated by second-layer line planning model（Line 1～7）

圖9 現(xiàn)狀線路和下層線路選擇模型求解得到的最優(yōu)線路方案（線路8～14）Fig.9 Current scheme and optimal scheme generated by second-layer line planning model（Line 8～14）

圖10 指出，ra、rd和rx分別迭代40，20，60 次左右時(shí)目標(biāo)函數(shù)值收斂，說(shuō)明禁忌算法效率收斂速度較快，能快速獲得最優(yōu)線路方案，剩余100 次迭代并無(wú)目標(biāo)值變化，從圖中省略。

圖10 下層模型目標(biāo)函數(shù)值隨迭代計(jì)算的變化Fig.10 Change in objective function value of second-layer model with iterative computation

6 結(jié)論

針對(duì)城市軌道交通線網(wǎng)規(guī)劃中網(wǎng)絡(luò)設(shè)計(jì)和線路布設(shè)問(wèn)題，本文建立由網(wǎng)絡(luò)設(shè)計(jì)模型和線路選擇模型組成的雙層模型，并設(shè)計(jì)以基于聚類的最小生成樹(shù)算法和禁忌算法為核心的求解算法。以實(shí)際軌網(wǎng)為例，比較分析實(shí)例和模型計(jì)算結(jié)果。得到結(jié)論如下：

（1）網(wǎng)絡(luò)設(shè)計(jì)模型可處理大規(guī)模站點(diǎn)，快速得到滿足站點(diǎn)可達(dá)性、工程可行性約束的初步網(wǎng)絡(luò)。引入的多種網(wǎng)絡(luò)修復(fù)策略，可以自主調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)。模型生成的初步網(wǎng)絡(luò)相較于實(shí)例，形態(tài)結(jié)構(gòu)近似，不存在不合理分支，線網(wǎng)總里程更短。

（2）線路選擇模型引入貪心策略生成質(zhì)量較優(yōu)的初始線路方案，再使用禁忌算法搜尋最優(yōu)方案，模型生成的初始線路方案的客流走廊與實(shí)例近似，且線路交叉和線路總數(shù)有所減少，具備更高的直達(dá)客流比和一次換乘比。

本文的模型可推廣到大城市軌道交通線網(wǎng)規(guī)劃中，基于選定的客流集散點(diǎn)或候選站點(diǎn)，輔助生成質(zhì)量較優(yōu)的初步規(guī)劃線網(wǎng)備選方案，作為初始方案為后續(xù)線網(wǎng)規(guī)劃工作提供輔助參考。