城市軌道交通過軌開行方案編制技術

于 劍 張星臣 徐 彬 陳載朝

（1.中國鐵路經濟規劃研究院，100038，北京；2.北京交通交通運輸學院，100044，北京；3.武漢鐵路局宜昌車務段，443000，宜昌∥第一作者，研究實習員）

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

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

可見，城市軌道交通領域已有的研究成果大多都只定性介紹了不同類型交路的特點和運用條件，同時對給定交路的開行頻率的計算方法、運行圖鋪畫模型及協調方法進行了較為深入的研究，但對交路方案本身的優化方法的相關研究較少，更鮮見過軌條件下的相關研究。

本文要探討的是，如何在一個過軌運營的城市軌道交通網絡上，根據已知的OD（起訖點）客流量，計算合理的交路方案和開行頻率，使其既可降低乘客整體旅行成本，又具備較低運營成本。考慮到優化難度和實際中大多數車站無越行條件、可變編組又增加作業復雜度等的情況，本文采用站站停車、固定編組遠行模式。

1 開行方案優化目標

開行方案的優化目標是算法的優化方向，是合理編制開行方案的基礎，應綜合考慮運營成本和乘客旅行成本兩個方面。

1.1 條件假設

（1）所有網絡化過軌運營條件均已具備。不同于單線運營，過軌運營需要具備一定的線路基礎條件和運營組織條件，本文認為所分析的城市軌道交通系統已具備諸如軌道、通信、信號、調度、旅客服務等一系列條件。

（2）各交路列車均成對開行，每對列車的途經站點集合完全相同。

1.2 符號約定

設城市軌道交通網絡（P，Q）上有n個車站、m條路段、o個不同的運營線路。相關符號說明見表1。

1.3 優化目標

1）總旅客周轉量：是計算各項成本的基礎，是旅客人數與運送距離的乘積。滿足同樣的運輸需求量，產生的周轉量越少，行駛的里程數就越少，運營成本就越低。

總旅客周轉量Z＝所有乘客的乘車距離之和：

表1 相關符號表示

其中，n為路網中站點數量，下同。

2）列車運行能源成本、車輛維修成本、設備維修成本：列車總質量越大、行駛距離越長，所需的能源就越多，車輛、設備維修成本就越大，所以列車運行能源成本、車輛維修成本、設備維修成本可以用質量和周轉量的乘積來計算。其中周轉量包括旅客總周轉量和列車總周轉量，質量包括旅客質量和列車自重。令：

式中：

λ1——列車運行每t·km所需的能源成本；

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

λ3——列車運行每t·km所需的設備維修成本。

3）旅客旅行時間成本：旅客主要旅行時間有乘車時間、換乘時間兩項。

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

（2）換乘時間成本。旅客總換乘時間為所有旅客在各換乘站所經歷的換乘時間之和，故換乘時間成本為：

4）綜合優化目標：根據前述各指標建立的城市軌道交通開行方案綜合優化目標如下：

其中，ω1，ω2（ω1＋ω2＝1）分別為運營成本和旅客旅行成本的權重系數，此指標值越小表示開行方案越優秀。

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

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

在一個已確定的路網上，發車站和折返站是確定的。本文認為，列車可從發車站發出，在另一發車站或折返站折返。算法流程圖如圖1所示。

其中，選擇算子采用輪盤賭選擇法，設式（8）的上限估計值為M，則適應度為M－C。雜交算子采用單點雜交，變異算子采用單點隨機變異，下面對關鍵步驟進行闡述。

2.1 確定備選交路集

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

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

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

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

一個種群有多條染色體，每個染色體代表一套交路方案，染色體的長度等于備選交路集中交路的數量。染色體采用二進制編碼方法，各基因與備選交路集中各交路一一對應：若某基因對應的交路開行，此基因值為1，否則為0。確定初始種群就是確定種群內各染色體的初始編碼。例如某路網經過計算、篩選得出的備選交路集中交路數量為8，種群數量為4，那么初始種群可能為：

設備選交路集中交路的數量為Nz。本文計算初始種群的方法是，事先憑經驗指定擬開行的交路數量Nk，之后以Nk／Nz為開行概率對各基因隨機賦1。

2.3 構建服務網絡和有效路徑搜索

本文以途經站數和換乘次數為考慮因素構建服務網絡［14］。例如，在圖2 中，一個十字形線路上有用虛線表示的l1，l2，l3號3條交路開行，構建的服務網絡示意圖如圖3所示。

圖2 服務網絡構建示例

圖3 服務網絡示意圖

其中，空心圓點代表對應于不同線路停站點的虛擬點，實心圓點代表對應于實際車站的虛擬點，各路段權值標注如圖。其中定義途經1 站的成本為1，旅客認為的換乘一次的平均成本為R。服務網絡與染色體一一對應，不斷進行重構。

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

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

（2）步驟2：恢復路段i－1的原始權值（若算法首次執行至此則無此步），檢查服務網絡的路段i，若其權值非0且不為無窮，則將其權值置為無窮產生新的服務網絡，轉步驟3；否則i＝i＋1，繼續檢查路段i。

（3）步驟3：利用Floyd算法在新產生的服務網絡上求算所有點對間的最短路，記計算所得的m、n兩點間的最短路徑阻抗為Fmn，1，轉步驟4。

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

（5）步驟5：若各點對間已求出次短路，則輸出最短路、次短路，否則證明該點對間無滿足條件的次短路，只輸出最短路，所有點對輸出后算法結束。

3 算例

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

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

優化參數如圖5所示，其中，“換乘一次的當量站數”意為旅客認為的平均每換乘一次的旅行成本相當于乘車途經一個區間旅行成本的倍數，此處定為5，“大致開行的交路數量”Nk定為6。

圖4 算例路網

表2 備選交路集

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

圖5 優化參數設置

表3 優化結果 （最優目標值為262 424元）

4 結語

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

圖6 優化目標值的變化趨勢

［1］毛保華，劉明君，黃榮，等.軌道交通網絡化運營組織理論與關鍵技術［M］.北京：北京科學出版社，2011.

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

［3］黃榮.城市軌道交通網絡化運營的組織方法及實施技術研究［D］.北京：北京交通大學，2010.

［4］房霄虹.城市軌道交通網絡化運輸組織協調理論及方法研究［D］.北京：北京交通大學，2010.

［5］陳強，何世偉，宋瑞，等.動態規劃方法研究城市軌道交通網狀線路跨線列車開行方案［J］.城市軌道交通研究，2010，13（3）：17.

［6］周艷芳.城市軌道交通網絡列車運行計劃一體化編制理論與方法研究［D］.北京：北京交通大學，2012.

［7］王永亮，張星臣，徐彬，等.城市軌道交通網絡化列車開行方案優化方法［J］.中國鐵道科學，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］史峰，鄧連波，霍亮.旅客列車開行方案的雙層規劃模型和算法［J］.中國鐵道科學，2007，28（3）：110.

［12］史峰，鄧連波，黎新華.客運專線相關旅客列車開行方案研究［J］.鐵道學報，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］陳勝波，何世偉，何必勝.客流波動條件下城市軌道交通列車開行方案研究［J］.城市軌道交通研究，2013（10）：53.

［15］于劍，張星臣，徐彬，等.面向客流分配的城市軌道服務網絡構建算法與實現［J］.武漢理工大學學報：交通科學與工程版，2013，37（5）：1036.