基于模擬退火算法的鐵路旅客列車車底套用優(yōu)化研究*

肖益帆，朱昌鋒

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅蘭州 730070)

鐵路旅客列車車底是鐵路運(yùn)輸生產(chǎn)組織中的重要資源，合理的車底運(yùn)用模式對(duì)降低鐵路運(yùn)輸成本起著至關(guān)重要的作用。近年來，隨著鐵路運(yùn)輸?shù)陌l(fā)展，開行的旅客列車對(duì)數(shù)逐漸增加，同時(shí)也存在著車底運(yùn)用方式不合理造成的車底在站停留時(shí)間過長(zhǎng)，車底運(yùn)用效率降低和車底運(yùn)行成本增加等問題。文獻(xiàn)［1］建立了車底運(yùn)用的雙層指派模型;文獻(xiàn)［2］建立了以列車運(yùn)輸能力最大化為目標(biāo)的整數(shù)規(guī)劃模型;文獻(xiàn)［3］分析了采用車底套用模型的優(yōu)缺點(diǎn);文獻(xiàn)［5－7］主要研究了高速鐵路動(dòng)車組不固定區(qū)段運(yùn)用的優(yōu)化模型。但上述大部分研究主要針對(duì)動(dòng)車組的不固定區(qū)段使用，針對(duì)普通旅客列車車底的運(yùn)用優(yōu)化又集中在運(yùn)營(yíng)成本方面。本文通過考慮不同等級(jí)列車間的車底運(yùn)用和列車晚點(diǎn)對(duì)車底運(yùn)用數(shù)量等影響，建立了以旅客列車車底數(shù)量為最小的目標(biāo)模型。

1 變量定義及問題描述

m(m=1，2，…，M)為鐵路客運(yùn)站;

r(r=1，2，…，R)為旅客列車車底;

V={vi=tdi，tfi，tfi'，li，ξdi，ξai}為列車集合。

其中:tdi和tfi分別為列車i的圖定始發(fā)時(shí)刻和終到時(shí)刻;tfi'為是列車i實(shí)際運(yùn)行中到達(dá)客運(yùn)站的時(shí)刻;li為列車i的等級(jí)，ξdi為列車i的始發(fā)車站，ξai為列車i的終到車站;ckr為旅客列車車底r的等級(jí)k;cmr為旅客列車備用車底r所屬的車站m;μi為列車i自身晚點(diǎn)的概率;hi為列車i連帶晚點(diǎn)的列車數(shù)量;TR為車底在車站的技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)。

假設(shè)某路網(wǎng)有m個(gè)客運(yùn)站，普通旅客列車、快速旅客列車、特別快速旅客列車可接續(xù)不低于同等級(jí)列車。但是，備用車底在運(yùn)用過程中，可不受到列車等級(jí)的限制。在列車接續(xù)中，需要考慮到列車的晚點(diǎn)問題。以24 h為1個(gè)周期，則該車底套跑問題可轉(zhuǎn)化為列車運(yùn)行網(wǎng)絡(luò)上具有較多約束條件和目標(biāo)函數(shù)的TSP問題。

2 鐵路旅客列車車底套用優(yōu)化模型建立

我國(guó)當(dāng)前的車底運(yùn)用基于固定配屬制，采取固定區(qū)段的使用模式。但是研究發(fā)現(xiàn)，不固定區(qū)段車底的運(yùn)用也可能是一種較好的車底運(yùn)用方式。因此，結(jié)合上述2種車底運(yùn)用模式，可以將運(yùn)用的車底分為不固定區(qū)段使用列車車底和備用車底2種。不固定區(qū)段使用列車無固定歸屬客運(yùn)段，在整個(gè)列車網(wǎng)絡(luò)內(nèi)進(jìn)行運(yùn)用。備用車底有相應(yīng)的歸屬客運(yùn)段，在結(jié)束一次運(yùn)用過程后，需回到相應(yīng)的歸屬客運(yùn)段;由于列車的晚點(diǎn)具有區(qū)間的傳播效應(yīng)，當(dāng)列車在終到站和終到站前車站晚點(diǎn)時(shí)，會(huì)對(duì)列車的車底運(yùn)用造成影響，當(dāng)列車在其他區(qū)間晚點(diǎn)時(shí)，則可以恢復(fù)。

(1)鐵路運(yùn)行圖規(guī)定每一列旅客列車能且只能分配一列旅客列車車底，同時(shí)該列車的等級(jí)應(yīng)不低于被接續(xù)旅客列車的等級(jí);

定義決策變量xij判斷列車i運(yùn)行后是否接續(xù)列車j，則有:

定義li為旅客列車i等級(jí):

定義crk為不固定區(qū)段的旅客列車車底的等級(jí):

由于旅客列車只能由一組列車車底擔(dān)當(dāng)，且該車底的等級(jí)應(yīng)不低于相應(yīng)列車等級(jí)，即?i，j，k，

(2)車底到站后，需進(jìn)行必要的技術(shù)作業(yè)，后續(xù)列車的始發(fā)時(shí)刻和前行列車的實(shí)際終到時(shí)刻差，應(yīng)滿足技術(shù)作業(yè)時(shí)間TR。權(quán)重越大則接續(xù)的可能性越小，同時(shí)使得同等級(jí)列車接續(xù)的可能性更高。

定義0－1變量Pi:

則有

(3)當(dāng)列車i屬于的運(yùn)行線路全周轉(zhuǎn)時(shí)間大于1個(gè)周期結(jié)束時(shí)間時(shí)，該車底只能在下1個(gè)周期返回大型客運(yùn)站，該車底不能再擔(dān)當(dāng)其他列車的接續(xù)。因此，只有滿足列車的全周轉(zhuǎn)時(shí)間在1個(gè)周期內(nèi)的車底能夠進(jìn)行列車的接續(xù)工作;

(4)列車晚點(diǎn)后，由于列車晚點(diǎn)傳播的效應(yīng)，會(huì)造成連帶數(shù)量的旅客列車晚點(diǎn)。

定義0－1決策變量si:

則在車站n備用列車車底的數(shù)量kn為:

(5)由備用車底擔(dān)當(dāng)任務(wù)時(shí)，需要最后返回所屬車站m，則當(dāng)列車j接續(xù)列車i由車底r擔(dān)當(dāng)列車運(yùn)用任務(wù)時(shí)，須滿足如下條件。

定義決策變量qrij:

則旅客列車的最短在站停留時(shí)間為:

因此，列車車底使用總數(shù)為Ntrain－set:

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

3.1 解的表示形式

本算法中，解用矩陣 Y=(Y1，Y2，Y3，…，Yn)來表示，Yi=j表示第i次列車終到車站之后，繼續(xù)擔(dān)當(dāng)?shù)趈次列車的運(yùn)行任務(wù)，稱j為i的接續(xù)車次，每次列車采用自然編碼。根據(jù)解的表示形式，采用兩兩交換的移動(dòng)規(guī)則，對(duì)任一當(dāng)前解，任選2個(gè)不同的終到車次，交換它們擔(dān)當(dāng)?shù)能嚧?，即可產(chǎn)生1個(gè)新解。

3.2 初始解的產(chǎn)生

任選某一客運(yùn)中心站的列車時(shí)刻表，并對(duì)該站的始發(fā)終到列車進(jìn)行順序編號(hào)，初始解為每個(gè)終到車次對(duì)應(yīng)的始發(fā)車次的編號(hào)。例如:1303次列車(編號(hào)為i)終到車站后，經(jīng)過一段時(shí)間的整備后，擔(dān)當(dāng)1304次(編號(hào)為Yi)列車的運(yùn)行任務(wù)。

3.3 溫度的控制

根據(jù)Δf/t0≈0，Δf為每次鄰域移動(dòng)后目標(biāo)函數(shù)值的增量，由于本文中的目標(biāo)函數(shù)只與相互接續(xù)的兩個(gè)車次的始發(fā)終到時(shí)刻相關(guān)，通過分析不難發(fā)現(xiàn)，每次鄰域移動(dòng)后，Δf有以下幾種情況，即:0，±1 440。所以，根據(jù)Δf/t0≈0，t0越高越好。

采用 T=T × r的降溫方式，r=0.95 ～ 0.99，這種降溫方法在溫度高時(shí)降溫快，溫度低時(shí)降溫緩慢。理論上終止溫度越低越好，最佳狀態(tài)為0℃，終止溫度小于1×10－4℃時(shí)，即可停止降溫過程。另外，本文采用兩數(shù)據(jù)交換構(gòu)造鄰域，鄰域移動(dòng)次數(shù)應(yīng)不少于C2n次。

針對(duì)本模型的實(shí)際問題，約束條件處理時(shí)應(yīng)以不影響算法性能和計(jì)算的復(fù)雜度為前提，在本論文中采取拒絕策略即不滿足約束條件時(shí)就排除該方案，將0～24 h表示為0～1 440 min，把每一個(gè)由時(shí)分表示的始發(fā)、終到時(shí)刻換算成分鐘形式。

Step 1指定數(shù)據(jù)文件名、初始溫度、降溫系數(shù)、終止溫度及熱平衡次數(shù)等參數(shù)。

Step 2給定1個(gè)初始解S0作為當(dāng)前解，T=T0，ci=1。

Step 3判斷列車i，j是否晚點(diǎn)，若晚點(diǎn)則Pi=Pj=1，否則，Pi=Pj=0。

Step 4判斷接續(xù)i，j列車的車底是否為備用車底，若為備用車底則pr=pr=1，否則，pr=pripijpjipijpj=0。

Step 5任意交換Yi，Yj，產(chǎn)生鄰域解S，檢驗(yàn)新解S是否滿足約束條件，本文的約束條件為:

(1)每一旅客列車能且只能被分配一車底，同時(shí)該列車的等級(jí)應(yīng)不低于被接續(xù)旅客列車的等級(jí);

(2)終到車次的終到時(shí)刻與其接續(xù)的始發(fā)車次的始發(fā)時(shí)刻之間滿足整備等時(shí)間約束;

若滿足上述2個(gè)條件轉(zhuǎn)入Step 6，否則轉(zhuǎn)Step 7。

Step 6計(jì)算f(S)與f(S0)的差值f，若f＜0，令S0=S，若 f＞ 0，產(chǎn)生1個(gè)(0，1)間的隨機(jī)數(shù) x。若exp(－ f/T)＞ x，則 S0=S。

若f(S0)是歷史最優(yōu)解，則更新最優(yōu)解;否則，轉(zhuǎn)Step 7。

Step 7 ci=ci+1。如果ci＜ Q，轉(zhuǎn)Step 4;否則，轉(zhuǎn)Step 8。

Step 8如果T ＞ 1 ×10－4，轉(zhuǎn)到 Step 2，否則結(jié)束。

4 實(shí)例分析

以某鐵路網(wǎng)的A，B，C和D 4個(gè)站為例。各車站的位置如圖1所示。各車站間的徑路如表1所示。各車站客車車流信息見表2～5。

圖1 鐵路網(wǎng)絡(luò)車站示意圖Fig.1 Location of railway passenger stations

表1 鐵路網(wǎng)絡(luò)內(nèi)列車徑路表Table 1 Train routing of railway network

表2 A車站客車車流信息表Table 2 Information of passenger train flow of A passenger station

表3 B車站客車車流信息表Table 3 Information of passenger train flow of B passenger station

K117 A B 20:48 —0.2 2 K179 A B 08:07 — 0.3 1 T817 A B 18:28 — 0.4 1 T167 A B 21:54 — 0.2 2 T201 A B 01:09 — 0.2 3 1918 C B 22:03 — 0.1 2 T198 D B 06:06 — 0.4 1 T138 C B 16:18 — 0.2 3 K126 C B 18:40 — 0.1 1 K132 D B 03:30 —0.1 2

表4 C車站客車車流信息表Table 4 Information of passenger train flow of C passenger station

表5 D車站客車車流信息表Table 5 Information of passenger train flow of D passenger station

根據(jù)各站旅客列車車流信息，可計(jì)算出車底在站停留時(shí)間，可得滿足4個(gè)車站列車開行方案所需的車底有36組，其中普通旅客列車車底6組，快速旅客列車車底16組，特快旅客列車車底12組。旅客列車在站停留時(shí)間如表6所示。

表6 旅客列車在站停留時(shí)間Table 6 Stop time at stations of railway passenger trains

用MATLAB計(jì)算。其收斂性檢驗(yàn)以及初始溫度Tf與最優(yōu)解出現(xiàn)個(gè)數(shù)的關(guān)系如圖2和圖3所示。

圖2 算法收斂性圖Fig.2 Convergence of algorithm

圖3 初始溫度Tf與最優(yōu)解出現(xiàn)個(gè)數(shù)的關(guān)系Fig.3 Relationship between initial temperature Tf and optimization solutions number

得到列車車底的接續(xù)方案如表7－8所示。

通過計(jì)算可得調(diào)整后的旅客列車車底在站停留時(shí)間的總和為16 732 min，比原有的接續(xù)方案少7 602 min，可以節(jié)約5組車底。根據(jù)計(jì)算由于每個(gè)車站需要1組備用車底，因此，總共可以節(jié)約1組車底。

表7 優(yōu)化后的旅客列車車底接續(xù)表Table 7 Optimized train set assignment

表8 優(yōu)化后的旅客列車車底接續(xù)表Table 8 Optimized train set assignment

5 結(jié)論

本文針對(duì)旅客列車的晚點(diǎn)傳播效應(yīng)，建立了旅客列車車底套用模型，計(jì)算方法簡(jiǎn)便，可操作性強(qiáng)，在實(shí)際生產(chǎn)中，還存在著車站的到發(fā)線、調(diào)集、整備線等均衡運(yùn)用多方面的因素，這有待進(jìn)一步研究。

［1］陳 剛，史 峰.鐵路旅客列車運(yùn)行圖編制要點(diǎn)分析［J］.鐵道運(yùn)輸與經(jīng)濟(jì)，2004，26(5):37 －38.CHEN Gang，SHI feng.Analysis on the key points for drawing up passenger train graph［J］.Railway Transport and Economy，2004，26(5):37 －38.

［2］謝金貴，曾 亮，徐昕愷.鐵路旅客列車車底套用優(yōu)化模型的研究［J］.鐵道運(yùn)輸與經(jīng)濟(jì)，2006，28(12):75－77.XIE Jin-gui，ZENG Liang XUE Xing-kai.Optimization on model of railway passenger train set assignment［J］.Railway Transport and Economy，2006，28(12):75－77.

［3］李 棟.關(guān)于利用外局(段)折返客車車底套跑短途旅客列車合理性的探討［J］.科協(xié)論壇，2008(5):43.LI Dong.Study on passenger train set assignment of which is from external railway bureau science＆technology association forum［J］.2008，(5):43.

［4］趙 鵬，富井規(guī)雄.動(dòng)車組運(yùn)用計(jì)劃及其編制算法［J］.鐵道學(xué)報(bào)，2006，25(3):1 －7.ZHAO Peng，NORIO Tomii.Train － set scheduling and an algorithm journal of the china railway society［J］.Journal of the China Railway Society，2006，25(3):1 －7.

［5］趙 鵬，楊 浩，胡安洲.高速鐵路動(dòng)車組的不固定區(qū)段使用問題［J］.鐵道學(xué)報(bào)，1997，19(2):15 －19.ZHAO Peng，YANG Hao，HU An-zhou.Research on usage of high speed passenger trains on uncertain railroad region［J］.Journal of the China Railway Society，1997，19(2):15－19.

［6］趙 鵬，胡安洲，楊 浩.高速鐵路動(dòng)車組不固定區(qū)段使用條件下周轉(zhuǎn)優(yōu)化問題的研究［J］.北方交通大學(xué)學(xué)報(bào)，1997，21(6):621 －624.ZHAO Peng，YANG Hao，HU An-zhou.Research on the circulating optimization in the condition of using high speed passenger trains in uncertain railroad region［J］.Journal of the China Railway Society，1997，21(6):621－624.

［7］耿敬春，肖榮國(guó)，倪少權(quán)，等.客運(yùn)專線動(dòng)車組周期性運(yùn)用計(jì)劃編制的研究［J］.鐵道學(xué)報(bào)，2006，28(4):17－21.GENG Jing-chun，XIAO Rong-guo，NI Shao-quan，et al.Research on periodicity of motor train set scheduling for special lines for passenger traffic［J］.Journal of the China Railway Society，2006，28(4):17 －21.

［8］馬建軍，許 紅，胡思繼，等.京滬高速鐵路列車運(yùn)行圖指標(biāo)評(píng)價(jià)體系的研究［J］.北方交通大學(xué)學(xué)報(bào)，2003，27(5):46－50.MA Jian-jun，XU Hong，HU Si-ji，et al.Study on index evaluation system of train working diagram on jinghu high－ speed railway line［J］.Journal of Northern Jiaotong U-niversity，2003，27(5):46 －50.

［9］孫 焰，劉胤宏，李致中，等.列車運(yùn)行圖的晚點(diǎn)概率分析［J］.長(zhǎng)沙鐵道學(xué)院學(xué)報(bào)，1994，16(4):83 －89.YANG Yan，LIU Yin-hong，LI Zhi-zhong，et al.The analysis of delaying time probability for the travelling graph of trains［J］.Journal of Changsha Railway University，1994，16(4):83 －89.

［10］楊肇夏，胡安洲，李 菊，等.列車運(yùn)行圖動(dòng)態(tài)性能及其指標(biāo)體系的研究［J］.鐵道學(xué)報(bào)，1993，15(14):46－56.YANG Zhao-xia，HU An-zhou，LI Ju，et al.A study of the dynamic performance＆index system of the trains operation diagram［J］.Journal of the China Railway Society，1993，15(14):46 －56.