客運專線列車開行方案混合優化算法研究

潘 輝 馬陳慧 顧正祥

（金肯職業技術學院，江蘇 南京211156）

1 概述

文獻[1]研究了在效益最大化的情況下，如何控制直通旅客列車的開行對數；文獻[2]研究了在旅客需求的影響下，如何制定合理的旅客列車開行方案，在目標優化時引入旅客的服務屬性；文獻[3]指出在旅客列車開行方案優化時的主要影響因素，并對每個因素進行比重分析；文獻[4]對旅客列車開行方案進行重新定義，將影響因素細分，對每個影響因子深入研究，并以京滬高鐵為案例進行實例仿真設計；文獻[5]利用BP 網絡對客流量進行預測，將旅客選擇出行方式取決于費用、舒適、便捷和時間這幾個重要因素，其中以費用的因素為主要優化目標進行開行方案目標函數設定，并將優化結果與實際預測作比較；文獻[6]研究了前面學者對旅客列車開行方案優化方法，總結出每個方法的應用范圍及優缺點，對常用的優化方法進行改進并進行實例驗證；文獻[7]對旅客列車開行對數，旅客出行特點做出深入研究，提出了“按流開車”的開行方式；文獻[8]對高速鐵路開行方案進行深入研究，指出高速鐵路旅客列車開行方案優化方法同樣適用于快速旅客列車開行方案優化研究。

2 列車開行方案優化模型

2.1 數學描述

假設旅客列車運行線路集合為Φ=（S，E），其中S={si|i=1，2，…，N}為線路上車站節點的集合；E={el|l=1，2，…，Y}為所有開行路段的集合，每個路段兩端節點為車站。

假設在運輸路段上開行的所有列車集合為R={rk|k=1，2，…，K}；用rk表示開行列車，則不同速度等級范圍為vk，vk=1，2 分別表示列車rk為高速列車或低速列車；用Sk∈S 表示開行列車所有停站模式；Lljk表示車站si運行至車站sj列車rk開行所有徑路集合，為區分中間站之間列車開行徑路集合，定義Lk為始發站運行至終到站開行徑路；列車rk在沿線車站是否停車定義為0-1 變量，使用xik進行標識，當xik=1，列車在站停車，xik=0，列車直接通過；Pk∈S 表示列車rk途中經過的所有車站集合。

2.2 優化目標

根據旅客出行經濟性效用理論，確定旅客出行廣義費用，即旅客從出發至目的地這個過程產生的所有費用，包括購票成本和時間成本，購票成本即乘坐所有交通方式的費用，時間成本是指旅行時間、候車時間和換乘時間的折算費用。旅客乘車時間和到站換乘時間組成，從車站si至sj列車開行方案為Pijm，則旅客通過選擇Pijm某種乘車方案產生的出行廣義費用計算如下：

式中：Cijm- 旅客出行的廣義費用；Wuv（k）- 在站候車時間折算費用；Tlk- 列車rk在路段elel上開行產生的廣義費用。

Wuv（k）與Tlk分別利用如下公式計算：

式中：υ- 旅客出行時間平均價值；Hwuv（k）- 旅客選擇與rk同等級列車從車站su運行至sv站沿途平均換乘等待時間；dl-列車在路段el上的運行距離；ξlk- 列車rk在路段el上平均票價換算率；Jlk- 列車rk在路段el上中途停車費用折算系數；Hlk- 路段el上列車運行總時間（包含始發站整備時間及在中間站停車時間）。

列車停站方案設置應符合列車停站設置原則，同時以出行旅客的角度分析，最大化節約旅客出行費用，提高旅客乘坐體驗，因此要最小化旅客出行廣義費用，旅客出行總廣義費用為：

對旅客列車停站方案進行優化設置時，同時考慮剩余旅客周轉率的影響，將剩余旅客周轉率設置為最小化目標，具體表達公式如下：

式中：Cp- 整條線路上剩余客流量；dij- 車站si至sj站列車開行最短距離；ODij- 車站si至sj站OD 調查客流量。

針對開行方案解的表達方式，設計基于和聲搜索及模擬退火的混合優化算法，算法分為3 個層次，第一層采用模擬退火（SA）算法，該算法是一種概率性的全局優化算法，通用性強，易于實現，用于優化區段列車開行對數; 第二層采用和聲搜索算法，用于優化列車停站方案;第三層利用平衡配流算法優化列車客流分配。通過多層次算法的循環嵌套，實現開行方案的整體優化[9，10]。

3 算法設計

3.1 開行方案初始化

列車初始開行方案初始化會根據旅客出行周轉量進行開行區段的選取，初始化操作時會優先選取客流量較大的車站作為運行區段，具體初始化流程如下進行：

Stepl：令列車編號k=1，不同方向上列車的服務頻率γij=0，剩余客流量f'ij=fij。

Step2：區間剩余客流量決定了列車開行對數是否滿足客運周轉量需求，通過確定直達客運周轉量確定直達列車開行條件。直達列車開行條件初始階段可以設置站站停模式，隨著直達客運周轉量增加，開行徑路調整，列車k 停站方案也會發生改變，根據最小廣義阻抗費用優化列車停站方案，同時作為直達列車開行條件和停站要求。

Step3：根據初始客流量的大小，在滿足列車最大載客能力的情況下，同時考慮旅客在運行途中換乘的因素，區分列車k吸引的客流，由于客流的初始分配對運行區段剩余客流量選取影響較大，所以在旅客不進行換乘時計算區段剩余客流量：

式中：fij（k）-si～sj區間客流初分配時選乘列車k 的客流量。

Step4：確定跨線列車開行區段，根據不同消費水平的出行旅客確定列車開行等級，不同等級的列車跨線運行會吸引更多消費層次旅客同時出行。

Step5：更新當前路段廣義阻抗，令k=k+1，搜索其他路段是否存在相同廣義阻抗路段，若存在，轉Step2，否則，終止列車開行方案初始化流程。

3.2 混合優化算法流程

旅客列車開行方案混合優化算法以將模擬退火算法和和聲算法有效結合，通過對列車開行對數和停站方案分別優化求解，最終得到寧安客運專線最優開行方案，混合算法具體流程如下：

輸入：旅客列車運行線路集合為Φ=（S，E），各車站接發車能力、到達列車數量、不同等級列車區間通過能力，列車的最大停站比率、旅客出行平均時間價值以及吸引出行旅客OD 客流量fij等已知條件。

輸出：旅客列車開行方案，包括各區間不同等級列車開行對數、車站停站比率、列車運行徑路以及停站方案。

Step1：設置模擬退火算法初始溫度T，內、外循環迭代次數Dn和Dw，在算法初始迭代計算時，令內、外循環迭代次數dn=0，dw=0。初始化列車開行方案Φ。

Step2：在列車運行徑路上隨機選取某個區段，假設固定開行列車對數增加一列，根據增加后的開行對數計算廣義阻抗路徑，最小化參數處理后生成列車停站方案以及開行方案的鄰域解Φ'。

Step3：以現有的列車停站方案為基礎，運用DMHS 算法對列車開行對數進行設計，并優化調整列車開行方案，根據最優停站方案計算的目標函數值，定義為f（Φ'）。

Step4：計算增量Δf=f（Φ）-f（Φ'），若Δf>0，則Φ' 為當前最優列車停站方案，即Φ=Φ'，并更新當前最優解Φ*，否則，以概率exp（Δf/T）認可Φ'為當前列車停站方案。

Step5：若dn

4 實例求解

對上述設計的混合算法進行實施驗證，以寧安客運專線為例進行仿真求解，定義線路運行網絡為G={S1，S2，…，S10}，S1，S2，…，S10分別表示沿線上的客運站，如下圖所示。始發站為南京南站，終到站為安慶站，在區間開行的動車組列車最高運行速度為250km/h，根據各個車站的級別，確定列車是否停站以及停站等待時間，在始發站列車整備時間為9min，在沿線中間站停時2min。根據OD 客流預測及設定的停站方案，利用VC++6.0 編程工具對寧安客運專線列車開行對數以及服務頻率進行優化設計，求解的優化對數及服務頻率如表1、表2 所示。

圖1 寧安客運專線線路圖

表1 列車開行區段及列車對數表

表2 車站服務頻率統計表

5 結論

本文首先分析了旅客列車開行方案優化設計是一個難度較大的復雜問題，需要應用高效率的智能優化算法進行求解，進而介紹了三種比較常用的智能優化算法：模擬退火算法、遺傳算法和和聲算法。HS 算法在復雜問題求解上得到很好地應用，根據HS 算法的強大優勢，與模擬退火算法相結合，形成基于種群多樣性的混合優化算法（DMHS），用模擬退火算法設計流程開行對數，用HS 算法優化列車停站模式，以此對列車開行方案進行整體優化。最后，以寧安客運專線列車開行方案優化問題為例，對混合優化算法的有效性進行了驗證。