潘 輝 馬陳慧 顧正祥

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

1 概述

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

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

2.1 數(shù)學(xué)描述

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

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

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

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

式中：Cijm- 旅客出行的廣義費(fèi)用；Wuv（k）- 在站候車時(shí)間折算費(fèi)用；Tlk- 列車rk在路段elel上開行產(chǎn)生的廣義費(fèi)用。

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

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

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

對(duì)旅客列車停站方案進(jìn)行優(yōu)化設(shè)置時(shí)，同時(shí)考慮剩余旅客周轉(zhuǎn)率的影響，將剩余旅客周轉(zhuǎn)率設(shè)置為最小化目標(biāo)，具體表達(dá)公式如下：

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

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

3 算法設(shè)計(jì)

3.1 開行方案初始化

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

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

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

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

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

Step4：確定跨線列車開行區(qū)段，根據(jù)不同消費(fèi)水平的出行旅客確定列車開行等級(jí)，不同等級(jí)的列車跨線運(yùn)行會(huì)吸引更多消費(fèi)層次旅客同時(shí)出行。

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

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

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

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

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

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

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

Step3：以現(xiàn)有的列車停站方案為基礎(chǔ)，運(yùn)用DMHS 算法對(duì)列車開行對(duì)數(shù)進(jìn)行設(shè)計(jì)，并優(yōu)化調(diào)整列車開行方案，根據(jù)最優(yōu)停站方案計(jì)算的目標(biāo)函數(shù)值，定義為f（Φ'）。

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

Step5：若dn

4 實(shí)例求解

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

圖1 寧安客運(yùn)專線線路圖

表1 列車開行區(qū)段及列車對(duì)數(shù)表

表2 車站服務(wù)頻率統(tǒng)計(jì)表

5 結(jié)論

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