客運專線列車開行方案混合優(yōu)化算法研究

潘 輝 馬陳慧 顧正祥

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

1 概述

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

2 列車開行方案優(yōu)化模型

2.1 數學描述

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

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

2.2 優(yōu)化目標

根據旅客出行經濟性效用理論，確定旅客出行廣義費用，即旅客從出發(fā)至目的地這個過程產生的所有費用，包括購票成本和時間成本，購票成本即乘坐所有交通方式的費用，時間成本是指旅行時間、候車時間和換乘時間的折算費用。旅客乘車時間和到站換乘時間組成，從車站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上列車運行總時間（包含始發(fā)站整備時間及在中間站停車時間）。

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

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

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

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

3 算法設計

3.1 開行方案初始化

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

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

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

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

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

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

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

3.2 混合優(yōu)化算法流程

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

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

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

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

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

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

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

Step5：若dn

4 實例求解

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

圖1 寧安客運專線線路圖

表1 列車開行區(qū)段及列車對數表

表2 車站服務頻率統計表

5 結論

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