于 劍 張星臣 徐 彬 陳載朝

（1.中國(guó)鐵路經(jīng)濟(jì)規(guī)劃研究院，100038，北京；2.北京交通交通運(yùn)輸學(xué)院，100044，北京；3.武漢鐵路局宜昌車務(wù)段，443000，宜昌∥第一作者，研究實(shí)習(xí)員）

“過軌運(yùn)營(yíng)”，是指在相互銜接的兩條或多條軌道交通線路上，列車從一條線路跨越到另一條歸屬于另一個(gè)運(yùn)營(yíng)實(shí)體的線路，從而與該線路上的原有列車共用某一區(qū)段的運(yùn)營(yíng)組織方式［1］。隨著路網(wǎng)規(guī)模的擴(kuò)大，線路間的影響越來(lái)越多，客流總生成量和換乘客流量均顯著增加，這都使以往僅著眼于匹配一條線路客流的單線獨(dú)立開行模式逐漸不能滿足日益精細(xì)化的運(yùn)營(yíng)需求。針對(duì)此，本文對(duì)過軌運(yùn)營(yíng)城市軌道交通網(wǎng)絡(luò)上的開行方案編制算法進(jìn)行了研究。

相關(guān)研究中，文獻(xiàn)［2］建立了使列車滿載率達(dá)到最大的優(yōu)化模型，考慮了車底銜接問題，求算了合理的列車開行頻率。文獻(xiàn)［3］詳細(xì)闡述了共線運(yùn)營(yíng)、多交路運(yùn)營(yíng)、快慢車結(jié)合組織方式的具體內(nèi)容和相關(guān)條件，并以乘客旅行時(shí)間最小化為目標(biāo)建立了快慢車開行方案優(yōu)化模型。文獻(xiàn)［4］主要從客流、交路、停站、開行密度、運(yùn)行圖協(xié)調(diào)等方面進(jìn)行了研究，其中對(duì)停站方案和開行密度進(jìn)行了定量分析。文獻(xiàn)［5］同時(shí)考慮地鐵運(yùn)營(yíng)方和乘客兩方面效益，應(yīng)用動(dòng)態(tài)規(guī)劃方法研究了跨線列車開行方案編制問題。文獻(xiàn)［6］研究了城市軌道交通運(yùn)行計(jì)劃編制方法，開行方案方面重點(diǎn)研究了開行頻率的確定方法。文獻(xiàn)［7］通過引入備選交路集，利用雙層規(guī)劃模型優(yōu)化了城軌網(wǎng)絡(luò)交路方案和發(fā)車間隔；同時(shí)注意到，鐵路領(lǐng)域?qū)τ陂_行方案的研究更為成熟。文獻(xiàn)［8］利用多目標(biāo)規(guī)劃模型和模糊數(shù)學(xué)規(guī)劃方法研究了城際無(wú)支路高速鐵路的停站方案、開行頻率和編組長(zhǎng)度三個(gè)方面的開行方案優(yōu)化問題。文獻(xiàn)［9－10］研究了具備不同停站特征的鐵路開行方案優(yōu)化問題，以最小化運(yùn)營(yíng)成本為目標(biāo)，利用多個(gè)模型對(duì)交路、頻率、停站方案進(jìn)行了優(yōu)化。文獻(xiàn)［11－12］均衡考慮企業(yè)和旅客的需求，建立了多目標(biāo)規(guī)劃模型、雙層規(guī)劃模型等優(yōu)化模型，并設(shè)計(jì)了開行方案評(píng)價(jià)方法、列車吸流原則、啟發(fā)式優(yōu)化算法。文獻(xiàn)［13］運(yùn)用雙層規(guī)劃模型和模擬退火算法對(duì)大規(guī)模路網(wǎng)上鐵路列車交路及開行頻率問題進(jìn)行了研究。

可見，城市軌道交通領(lǐng)域已有的研究成果大多都只定性介紹了不同類型交路的特點(diǎn)和運(yùn)用條件，同時(shí)對(duì)給定交路的開行頻率的計(jì)算方法、運(yùn)行圖鋪畫模型及協(xié)調(diào)方法進(jìn)行了較為深入的研究，但對(duì)交路方案本身的優(yōu)化方法的相關(guān)研究較少，更鮮見過軌條件下的相關(guān)研究。

本文要探討的是，如何在一個(gè)過軌運(yùn)營(yíng)的城市軌道交通網(wǎng)絡(luò)上，根據(jù)已知的OD（起訖點(diǎn)）客流量，計(jì)算合理的交路方案和開行頻率，使其既可降低乘客整體旅行成本，又具備較低運(yùn)營(yíng)成本?？紤]到優(yōu)化難度和實(shí)際中大多數(shù)車站無(wú)越行條件、可變編組又增加作業(yè)復(fù)雜度等的情況，本文采用站站停車、固定編組遠(yuǎn)行模式。

1 開行方案優(yōu)化目標(biāo)

開行方案的優(yōu)化目標(biāo)是算法的優(yōu)化方向，是合理編制開行方案的基礎(chǔ)，應(yīng)綜合考慮運(yùn)營(yíng)成本和乘客旅行成本兩個(gè)方面。

1.1 條件假設(shè)

（1）所有網(wǎng)絡(luò)化過軌運(yùn)營(yíng)條件均已具備。不同于單線運(yùn)營(yíng)，過軌運(yùn)營(yíng)需要具備一定的線路基礎(chǔ)條件和運(yùn)營(yíng)組織條件，本文認(rèn)為所分析的城市軌道交通系統(tǒng)已具備諸如軌道、通信、信號(hào)、調(diào)度、旅客服務(wù)等一系列條件。

（2）各交路列車均成對(duì)開行，每對(duì)列車的途經(jīng)站點(diǎn)集合完全相同。

1.2 符號(hào)約定

設(shè)城市軌道交通網(wǎng)絡(luò)（P，Q）上有n個(gè)車站、m條路段、o個(gè)不同的運(yùn)營(yíng)線路。相關(guān)符號(hào)說明見表1。

1.3 優(yōu)化目標(biāo)

1）總旅客周轉(zhuǎn)量：是計(jì)算各項(xiàng)成本的基礎(chǔ)，是旅客人數(shù)與運(yùn)送距離的乘積。滿足同樣的運(yùn)輸需求量，產(chǎn)生的周轉(zhuǎn)量越少，行駛的里程數(shù)就越少，運(yùn)營(yíng)成本就越低。

總旅客周轉(zhuǎn)量Z＝所有乘客的乘車距離之和：

表1 相關(guān)符號(hào)表示

其中，n為路網(wǎng)中站點(diǎn)數(shù)量，下同。

2）列車運(yùn)行能源成本、車輛維修成本、設(shè)備維修成本：列車總質(zhì)量越大、行駛距離越長(zhǎng)，所需的能源就越多，車輛、設(shè)備維修成本就越大，所以列車運(yùn)行能源成本、車輛維修成本、設(shè)備維修成本可以用質(zhì)量和周轉(zhuǎn)量的乘積來(lái)計(jì)算。其中周轉(zhuǎn)量包括旅客總周轉(zhuǎn)量和列車總周轉(zhuǎn)量，質(zhì)量包括旅客質(zhì)量和列車自重。令：

式中：

λ1——列車運(yùn)行每t·km所需的能源成本；

λ2——列車運(yùn)行每t·km所需的車輛維修成本；

λ3——列車運(yùn)行每t·km所需的設(shè)備維修成本。

3）旅客旅行時(shí)間成本：旅客主要旅行時(shí)間有乘車時(shí)間、換乘時(shí)間兩項(xiàng)。

（1）乘車時(shí)間成本。旅客總乘車時(shí)間為所有旅客乘車時(shí)間之和，所以總乘車時(shí)間成本為：

（2）換乘時(shí)間成本。旅客總換乘時(shí)間為所有旅客在各換乘站所經(jīng)歷的換乘時(shí)間之和，故換乘時(shí)間成本為：

4）綜合優(yōu)化目標(biāo)：根據(jù)前述各指標(biāo)建立的城市軌道交通開行方案綜合優(yōu)化目標(biāo)如下：

其中，ω1，ω2（ω1＋ω2＝1）分別為運(yùn)營(yíng)成本和旅客旅行成本的權(quán)重系數(shù)，此指標(biāo)值越小表示開行方案越優(yōu)秀。

2 基于遺傳算法的開行方案編制方法

算法的主要思路是，首先生成一個(gè)包含多條染色體的初始種群，每條染色體均代表一套可行的交路方案（包含多條交路）；之后針對(duì)每套交路方案進(jìn)行客流分配和各交路開行對(duì)數(shù)的求算（以輸送能力剛好超過最大客流區(qū)段客流量為準(zhǔn)），并計(jì)算、記錄此開行方案的優(yōu)化目標(biāo)值、適應(yīng)度；完成一代計(jì)算后，經(jīng)過選擇、雜交和變異產(chǎn)生新一代種群，重復(fù)上述步驟，直至一定代數(shù)后終止，選擇最優(yōu)染色體（和相應(yīng)開行頻率）作為最終開行方案。

在一個(gè)已確定的路網(wǎng)上，發(fā)車站和折返站是確定的。本文認(rèn)為，列車可從發(fā)車站發(fā)出，在另一發(fā)車站或折返站折返。算法流程圖如圖1所示。

其中，選擇算子采用輪盤賭選擇法，設(shè)式（8）的上限估計(jì)值為M，則適應(yīng)度為M－C。雜交算子采用單點(diǎn)雜交，變異算子采用單點(diǎn)隨機(jī)變異，下面對(duì)關(guān)鍵步驟進(jìn)行闡述。

2.1 確定備選交路集

圖1 列車開行方案算法流程圖

首先定義全交路集，它是指路網(wǎng)上所有可能開行交路的集合，本文將各發(fā)車站和發(fā)車站、發(fā)車站和折返站之間的最短路徑的集合作為全交路集的主要組成部分，再通過人工增加部分環(huán)線、繞行線等最短路徑算法無(wú)法算得的線路共同構(gòu)成全交路集。備選交路集通過對(duì)全交路集進(jìn)行篩選得出，是指路網(wǎng)上可開行的、較為合理的所有交路的集合，最終的交路方案是備選交路集的一個(gè)子集。由于城市軌道交通系統(tǒng)主要吸引中遠(yuǎn)途客流，為減少換乘次數(shù)，篩選應(yīng)遵循：①排除過短交路；②排除本線客流（能通過該線路直達(dá)的客流）較小的交路。

其中，第一個(gè)原則可作為計(jì)算機(jī)自動(dòng)篩選交路的依據(jù)。對(duì)于第二個(gè)原則，由于難以在計(jì)算前對(duì)本線客流量設(shè)定科學(xué)的下限，且還需考慮線路走向等因素，故通過人工篩選更合理。

2.2 染色體描述方法和初始種群

一個(gè)種群有多條染色體，每個(gè)染色體代表一套交路方案，染色體的長(zhǎng)度等于備選交路集中交路的數(shù)量。染色體采用二進(jìn)制編碼方法，各基因與備選交路集中各交路一一對(duì)應(yīng)：若某基因?qū)?yīng)的交路開行，此基因值為1，否則為0。確定初始種群就是確定種群內(nèi)各染色體的初始編碼。例如某路網(wǎng)經(jīng)過計(jì)算、篩選得出的備選交路集中交路數(shù)量為8，種群數(shù)量為4，那么初始種群可能為：

設(shè)備選交路集中交路的數(shù)量為Nz。本文計(jì)算初始種群的方法是，事先憑經(jīng)驗(yàn)指定擬開行的交路數(shù)量Nk，之后以Nk／Nz為開行概率對(duì)各基因隨機(jī)賦1。

2.3 構(gòu)建服務(wù)網(wǎng)絡(luò)和有效路徑搜索

本文以途經(jīng)站數(shù)和換乘次數(shù)為考慮因素構(gòu)建服務(wù)網(wǎng)絡(luò)［14］。例如，在圖2 中，一個(gè)十字形線路上有用虛線表示的l1，l2，l3號(hào)3條交路開行，構(gòu)建的服務(wù)網(wǎng)絡(luò)示意圖如圖3所示。

圖2 服務(wù)網(wǎng)絡(luò)構(gòu)建示例

圖3 服務(wù)網(wǎng)絡(luò)示意圖

其中，空心圓點(diǎn)代表對(duì)應(yīng)于不同線路停站點(diǎn)的虛擬點(diǎn)，實(shí)心圓點(diǎn)代表對(duì)應(yīng)于實(shí)際車站的虛擬點(diǎn)，各路段權(quán)值標(biāo)注如圖。其中定義途經(jīng)1 站的成本為1，旅客認(rèn)為的換乘一次的平均成本為R。服務(wù)網(wǎng)絡(luò)與染色體一一對(duì)應(yīng)，不斷進(jìn)行重構(gòu)。

令換乘路徑阻抗為其所包含的所有路段的阻抗權(quán)值之和。本文利用刪邊法求算了服務(wù)網(wǎng)絡(luò)中任意兩點(diǎn)間的前兩條最短路徑作為旅客的有效路徑，具體算法如下：

（1）步驟1：初始化，i＝1，利用Floyd算法求算路網(wǎng)所有點(diǎn)對(duì)間的最短路。記m、n兩點(diǎn)間的最短路徑阻抗為Fmn，0，記目前求得的m、n兩點(diǎn)間的次短路徑阻抗為Smn，令Smn＝∞，?m，n∈［1，N］，其中N為服務(wù)網(wǎng)絡(luò)中點(diǎn)的數(shù)量。

（2）步驟2：恢復(fù)路段i－1的原始權(quán)值（若算法首次執(zhí)行至此則無(wú)此步），檢查服務(wù)網(wǎng)絡(luò)的路段i，若其權(quán)值非0且不為無(wú)窮，則將其權(quán)值置為無(wú)窮產(chǎn)生新的服務(wù)網(wǎng)絡(luò)，轉(zhuǎn)步驟3；否則i＝i＋1，繼續(xù)檢查路段i。

（3）步驟3：利用Floyd算法在新產(chǎn)生的服務(wù)網(wǎng)絡(luò)上求算所有點(diǎn)對(duì)間的最短路，記計(jì)算所得的m、n兩點(diǎn)間的最短路徑阻抗為Fmn，1，轉(zhuǎn)步驟4。

（4）步驟4：若Fmn，1≤Fmn，0＋μ（無(wú)過遠(yuǎn)繞行約束，μ為閾值）、Fmn，1＜Smn且Fmn，1對(duì)應(yīng)的路徑與Fmn，0對(duì)應(yīng)的最短路徑不同，則Smn＝Fmn，1，記錄相應(yīng)的換乘路徑；否則變更m、n點(diǎn)對(duì)，重新執(zhí)行步驟4，直到所有點(diǎn)對(duì)均已判斷。之后i＝i＋1，若i已超過服務(wù)網(wǎng)絡(luò)的路段數(shù)，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟2。

（5）步驟5：若各點(diǎn)對(duì)間已求出次短路，則輸出最短路、次短路，否則證明該點(diǎn)對(duì)間無(wú)滿足條件的次短路，只輸出最短路，所有點(diǎn)對(duì)輸出后算法結(jié)束。

3 算例

利用C#語(yǔ)言開發(fā)“網(wǎng)絡(luò)化條件下城市軌道交通開行方案編制”軟件。算例為一個(gè)類似“田”字形的中型路網(wǎng)（見圖4），站點(diǎn)以字母命名，共計(jì)21個(gè)，外圍一周車站 A1、B1、C1、A5、B5、C5、D1、D2、E1、E2、F1、F2為發(fā)車站點(diǎn)，A3、B2、B3、B4、C3 為折返站點(diǎn)。編制該路網(wǎng)1 h內(nèi)的OD 客流，共運(yùn)送旅客120 906人次。

以6 km 作為交路長(zhǎng)度下限，利用最短路算法求出一個(gè)備選交路集，數(shù)量恰為100條；為繼續(xù)縮小規(guī)模，將本線OD 客流量在8 140人次以下的交路全部刪除，得到有15條交路的備選交路集，如表2所示。

優(yōu)化參數(shù)如圖5所示，其中，“換乘一次的當(dāng)量站數(shù)”意為旅客認(rèn)為的平均每換乘一次的旅行成本相當(dāng)于乘車途經(jīng)一個(gè)區(qū)間旅行成本的倍數(shù)，此處定為5，“大致開行的交路數(shù)量”Nk定為6。

圖4 算例路網(wǎng)

表2 備選交路集

優(yōu)化耗時(shí)43 min 37 s，結(jié)果如表3所示。每代種群中最好的優(yōu)化目標(biāo)值隨著進(jìn)化代數(shù)增加的變化趨勢(shì)圖如圖6：部分進(jìn)化階段目標(biāo)值顯現(xiàn)出提前成熟、局部收斂的現(xiàn)象，但隨著變異率的提高，目標(biāo)值總體呈現(xiàn)下降的趨勢(shì)。此外，為與單線運(yùn)營(yíng)作對(duì)比，將備選交路集中交路確定為直線交路A1－A5、B1－B5、C1－C5、D1－D2、E1－E2、F1－F2并全部開行，在相同參數(shù)下算得的優(yōu)化目標(biāo)值為300 755元。而利用本文算法得出的優(yōu)化開行方案目標(biāo)值為262 424元，相比降低12.7%，證明網(wǎng)絡(luò)化過軌運(yùn)營(yíng)能夠比單線運(yùn)營(yíng)大幅降低綜合成本，提高組織效率。

圖5 優(yōu)化參數(shù)設(shè)置

表3 優(yōu)化結(jié)果 （最優(yōu)目標(biāo)值為262 424元）

4 結(jié)語(yǔ)

隨著各國(guó)大型城市地面軌道交通路網(wǎng)規(guī)模的不斷擴(kuò)大，采取過軌運(yùn)營(yíng)等運(yùn)輸組織方式，提高客流直達(dá)率，減少運(yùn)營(yíng)和旅行成本必將是規(guī)劃建設(shè)和運(yùn)營(yíng)組織的重點(diǎn)研究方向之一。本文研究了城市軌道交通列車過軌開行方案的計(jì)算機(jī)編制方法與技術(shù)，提出的算法可優(yōu)化中小型路網(wǎng)的列車過軌開行方案。但是，仍存在很多不足，例如較少考慮編制開行方案的約束條件，如車站、區(qū)間能力限制、線路間相互干擾以及車底調(diào)度等問題，未考慮停站和編組方案的優(yōu)化；同時(shí)算法效率有待提高，今后應(yīng)在有關(guān)方面進(jìn)行更加深入的探索。

圖6 優(yōu)化目標(biāo)值的變化趨勢(shì)

［1］毛保華，劉明君，黃榮，等.軌道交通網(wǎng)絡(luò)化運(yùn)營(yíng)組織理論與關(guān)鍵技術(shù)［M］.北京：北京科學(xué)出版社，2011.

［2］孫焰，施其洲，趙源.城市軌道交通列車開行方案的確定［J］.同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，32（8）：1005.

［3］黃榮.城市軌道交通網(wǎng)絡(luò)化運(yùn)營(yíng)的組織方法及實(shí)施技術(shù)研究［D］.北京：北京交通大學(xué)，2010.

［4］房霄虹.城市軌道交通網(wǎng)絡(luò)化運(yùn)輸組織協(xié)調(diào)理論及方法研究［D］.北京：北京交通大學(xué)，2010.

［5］陳強(qiáng)，何世偉，宋瑞，等.動(dòng)態(tài)規(guī)劃方法研究城市軌道交通網(wǎng)狀線路跨線列車開行方案［J］.城市軌道交通研究，2010，13（3）：17.

［6］周艷芳.城市軌道交通網(wǎng)絡(luò)列車運(yùn)行計(jì)劃一體化編制理論與方法研究［D］.北京：北京交通大學(xué)，2012.

［7］王永亮，張星臣，徐彬，等.城市軌道交通網(wǎng)絡(luò)化列車開行方案優(yōu)化方法［J］.中國(guó)鐵道科學(xué)，2012，33（5）：120.

［8］Chang Yuhern，Yeh Chunghsing，Shen Chingcheng.A multiobjective model for passenger train services planning：application to Taiwan＇s high－speed rail line ［J］.Transportation Research Part B：Methodological，2000，34（2），91.

［9］Jan－Willem Goossens，Stan van Hoesel，Leo Kroon.A Branch－and－Cut Approach for Solving Railway Line－Planning Problems［J］.Transportation Science.2004，38（3）：379.

［10］Jan－Willem Goossens，Stan van Hoesel，Leo Kroon.On solving multi－type railway line planning problems［J］.European Journal of Operational Research.2006，168（2）：403.

［11］史峰，鄧連波，霍亮.旅客列車開行方案的雙層規(guī)劃模型和算法［J］.中國(guó)鐵道科學(xué)，2007，28（3）：110.

［12］史峰，鄧連波，黎新華.客運(yùn)專線相關(guān)旅客列車開行方案研究［J］.鐵道學(xué)報(bào)，2004，26（2）：16.

［13］Lin Boliang，Wang Zhimei，Ji Lijun，et al.Optimizing the freight train connection service network of a large－scale rail system ［J ］.Transportation Research Part B：Methodological.2012，46（5）：649.

［14］陳勝波，何世偉，何必勝.客流波動(dòng)條件下城市軌道交通列車開行方案研究［J］.城市軌道交通研究，2013（10）：53.

［15］于劍，張星臣，徐彬，等.面向客流分配的城市軌道服務(wù)網(wǎng)絡(luò)構(gòu)建算法與實(shí)現(xiàn)［J］.武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2013，37（5）：1036.