張 巖，李 想，孫文橋，劉啟鋼，張 明

（1.中國鐵道科學(xué)研究院集團(tuán)有限公司 運輸及經(jīng)濟(jì)研究所，北京 100081；2.中國鐵路南寧局集團(tuán)有限公司 柳州站，廣西 柳州 545007)

0 引言

鐵路站場取送車是為了實現(xiàn)貨物裝卸、車輛檢修清洗等目的，從站場股道向作業(yè)地點送車和從作業(yè)地點取回車輛的作業(yè)過程，包括單送、單取、送取結(jié)合等多種形式。其中，現(xiàn)場單取作業(yè)場景較多，而且多為可按任意順序掛走的“普通車流”[1-2]。受到車列最大長度限制，取車作業(yè)往往需要多次往返。在此情況下，合理安排調(diào)車機車(以下簡稱“調(diào)機”)的取車順序可以提高機車車輛作業(yè)效率，加快車輛集結(jié)進(jìn)度，保證車流的準(zhǔn)點出發(fā)，有利于縮短車輛周轉(zhuǎn)時間[3]。

鐵路站場取送車順序優(yōu)化問題是一個經(jīng)典的NP難問題，目前國內(nèi)相關(guān)研究較多。李文權(quán)等[4]采用圖論和排序論求解樹枝形鐵路專用線取送車問題。石紅國等[5]將鐵路取送車問題抽象為哈密爾頓圖最短回路問題進(jìn)行求解。這些算法的計算次數(shù)隨著存車股道數(shù)量的增加呈指數(shù)增加，在存車股道數(shù)量較多時，很難在規(guī)定時間內(nèi)求得最優(yōu)解。郭垂江等[6]利用C-W節(jié)約改進(jìn)算法解決動態(tài)規(guī)劃計算量大、耗時長的問題。有部分學(xué)者應(yīng)用蟻群算法、遺傳算法等人工智能算法求解取送車計劃優(yōu)化問題，有效縮短求得可接受解的時間[7-10]。但是，這些研究僅考慮取車、送車、調(diào)車等作業(yè)一次完成的情況，未考慮多次往返目標(biāo)作業(yè)地點的取車場景，算法也難以在有限時間內(nèi)快速求解。另外，還有一些研究表明[11-14]，蟻群算法可以在有限時間內(nèi)求解旅行商問題的最優(yōu)路徑，然而多次往返取車模型涉及“城市”訪問次數(shù)動態(tài)變化的情況，傳統(tǒng)蟻群算法無法直接求解。為此，考慮車組最大長度和最晚取回目標(biāo)站場時間限制，將股道入口信號機與車組之間距離、牽出車組長度納入到調(diào)機總走行距離計算公式，建立數(shù)學(xué)模型以描述鐵路站場取車作業(yè)過程。改進(jìn)傳統(tǒng)蟻群算法步驟，使其適應(yīng)城市訪問次數(shù)動態(tài)變化條件下旅行商問題求解，計算得到多次往返取車作業(yè)順序的最優(yōu)方案。

1 鐵路站場往返取車作業(yè)優(yōu)化模型

1.1 問題描述

鐵路站場包括到達(dá)場、編組場、出發(fā)場、車輛檢修站場、貨物裝卸站場等，大多為樹枝形站場[8]。樹枝形鐵路站場布置示意圖如圖1所示。站場入口處只有1條線路，通過道岔分成多級樹枝形線路，最末端線路為作業(yè)股道。站場入口和股道入口均設(shè)置信號機，調(diào)機經(jīng)入口信號機進(jìn)入站場，按順序進(jìn)入各作業(yè)股道連掛車輛組成車列，再經(jīng)站場入口信號機將車列取回至目標(biāo)車場。如果車列長度超出最大長度限制，則需要進(jìn)行多次往返取車，可能需要多次到同一股道取車。鐵路站場往返取車作業(yè)優(yōu)化問題可以描述為：以調(diào)機總走行距離最短為目標(biāo)，在完成所有的取車任務(wù)的條件下，確定多次往返取車的最優(yōu)取車順序。

圖1 樹枝形鐵路站場布置示意圖Fig.1 Layout of branch-shaped railway yard

為方便建模，提出以下假設(shè)：①只采用1臺調(diào)機進(jìn)行取車作業(yè)，調(diào)機的走行平均速度已知；②調(diào)機起始位置為站場入口信號機外端；③樹枝形站場的線路、道岔、信號機位置已知；④作業(yè)開始前，各作業(yè)股道停留的車輛數(shù)和各車輛長度已知；⑤停留在作業(yè)股道上的車組的位置與股道入口信號機的距離已知；⑥車列最大長度限制已知。

1.2 符號說明

設(shè)站場有n條作業(yè)股道，G= {gi|i= 1，2，…，n}為站場所有作業(yè)股道集合。l為車列最大長度限制；d為本站場入口信號機至取車目標(biāo)站場入口信號機距離；v為調(diào)機走行的平均速度。函數(shù)d(gi)為本站場入口信號機至作業(yè)股道gi入口信號機的距離，函數(shù)dg(gi，gj)為作業(yè)股道gi的入口信號機經(jīng)最近折返道岔至作業(yè)股道gj的入口信號機的距離。

m為停有待取車組的股道總數(shù)，P= {pi|i= 1，2，…，m}為存車股道(在取車開始前有車輛停留的股道)集合。函數(shù)d(pi)為本站場入口信號機至存車股道pi入口信號機的距離；函數(shù)dlt(pi)為存車股道pi上車組最晚到達(dá)目標(biāo)站場的時間；函數(shù)dt(pi)為存車股道pi上車組實際到達(dá)目標(biāo)站場的時間，函數(shù)dp(pi)為存車股道pi上車組與該股道入口信號機之間的距離；函數(shù)dg(pi，pj)為作業(yè)股道pi入口信號機經(jīng)最近折返道岔至存車股道pj入口信號機的距離。當(dāng)pi=gi，pj=gj時，有dp(pi) =dp(gi)， 且dg(pi) =dg(gi)，dg(pi，gj) =dg(gi，gj)。函數(shù)cn(pi)為股道pi停留車組包含的車輛數(shù)；函數(shù)ptl(pi)為股道pi停留車組總長度。

Q= (q1，q2，…，qk)為取車股道順序，其中qi∈P(i= 1，2，…，k)，調(diào)機可能到同一存車股道多次取車，因而在取車股道順序Q中，一個存車股道可能出現(xiàn)多次，有k≥m。函數(shù)tl(qi)為在股道qi取走的車組長度，qtl(qi)為連掛股道qi上車組后車列總長度，有qtl(qi) =qtl(qi-1) +tl(qi)。函數(shù)ptl(qi)為取完股道qi上車組后，股道qi上剩余車組的長度，有ptl(qi) =ptl(qi) -tl(qi)。調(diào)機取車總走行距離為其中dis(qi)為取股道qi上車組的走行距離，表示調(diào)機從站場入口信號機外側(cè)或上一次作業(yè)結(jié)束位置開始，至將目標(biāo)股道車組牽引至目標(biāo)股道入口信號機內(nèi)側(cè)或送至目標(biāo)站場的走行距離。如果送至目標(biāo)站場后仍有待取車組，還應(yīng)包括調(diào)機返回站場入口信號機外側(cè)的距離。

1.3 調(diào)機走行距離計算公式

給出調(diào)機處于不同起始位置時，單次連掛調(diào)機走行距離的計算公式。當(dāng)調(diào)機處于站場入口信號機外側(cè)時，連掛后，如果qtl(qi) ＜l，那么

如果dtl(qi) =l，那么

如果qtl(qi) ＞l，那么

調(diào)機取第1個車組之前或送完1個最大長度車列返回時，調(diào)機處于站場入口信號機外側(cè)。調(diào)機連掛完目標(biāo)股道車組后，將車組牽出至目標(biāo)股道入口信號機內(nèi)側(cè)。公式 ⑴ 表示調(diào)機取車組的走行距離包括站場入口信號機至車組所在股道入口信號機的距離、股道車組停留位置距該股道入口信號機距離的2倍。在股道完成一次作業(yè)后，將剩余車組與該股道入口信號機之間距離dp(pi)更新為0。當(dāng)取最后一個車組時，需將車組牽到站場入口信號機外側(cè)并送至目標(biāo)站場。公式 ⑵ 表示當(dāng)取完目標(biāo)股道車組后車列長度達(dá)到調(diào)機最大牽引推送長度限制時，調(diào)機需要額外將車組牽引出站場入口信號機，并往返至取車目標(biāo)站場，當(dāng)所有車輛取完時不必返回。公式⑶ 表示當(dāng)取完目標(biāo)車組后車列長度大于調(diào)機最大牽引推送長度l限制時，調(diào)機需額外將車組牽引出站場入口信號機，將車組送至取車目標(biāo)站場，返回后停留在站場入口信號機外側(cè)。

當(dāng)調(diào)機處于股道時，連掛后，如果qtl(qi) ＜l，那么

如果qtl(qi) =l，那么

如果qtl(qi) ＞l，那么

當(dāng)調(diào)機取完某個股道上的車組后，車列長度未達(dá)到l且i＜k，調(diào)機將股道車組釋放在該股道入口信號機內(nèi)側(cè)，繼續(xù)取下一個車組。調(diào)機需要將上一個股道車組牽出到qi-1至qi的折返道岔外側(cè)，因而調(diào)機至下一個股道的走行距離包括股道入口信號機至下一個股道入口信號機之間距離、牽出車組長度和目標(biāo)連掛車組停留位置距股道入口信號機距離的2倍。公式 ⑷ 至 ⑹ 都包含調(diào)機從原股道至取車目標(biāo)股道的走行距離，公式 ⑷ 表示取最后一個車組時，需要將車組牽出站場入口信號機并送至目標(biāo)站場。公式 ⑸、⑹ 表示當(dāng)連掛車組后，車列長度大于等于l時，調(diào)機需要額外將車組牽引至站場入口信號機外側(cè)，送至目標(biāo)站場，返回后停留在站場入口信號機外側(cè)，當(dāng)作業(yè)完畢(即i=k)時不計算返回路程。

對單次連掛調(diào)機走行距離的計算公式求和，得到調(diào)機總走行距離公式。優(yōu)化目標(biāo)是調(diào)機將站場所有停留車組取出并送至目標(biāo)站場的總走行距離R最短，目標(biāo)函數(shù)為

股道上車組到達(dá)目標(biāo)站場的時間dt(pi)為股道上所有車組被送到目標(biāo)站場時，調(diào)機的總走行距離除以調(diào)機的平均速度，計算公式為

2 鐵路站場往返取車作業(yè)優(yōu)化模型求解算法

2.1 求解算法分析

鐵路站場取車模型可以抽象為旅行商問題求解。在鐵路站場往返取車作業(yè)優(yōu)化問題中，將股道看作旅行商問題中的“城市”，將每次車列的移動看作旅行商問題中“城市”之間的一次“遷移”。當(dāng)存車股道較少時，可以使用深度優(yōu)先或廣度優(yōu)先等遍歷算法，搜索取車順序的所有解，從而獲得最優(yōu)解；而當(dāng)存車股道數(shù)量較大時，遍歷算法無法在可以接受的時間內(nèi)完成求解，為此需要借助智能優(yōu)化算法求解。蟻群算法是解決旅行商問題的一種有效的智能優(yōu)化算法，可在較短的時間內(nèi)尋找到NP問題的滿意解[10-11]。傳統(tǒng)旅行商問題可以描述為：尋找一條距離最短的路徑，使旅行商選擇1條路徑從1個城市出發(fā)，經(jīng)過所有城市1次，再回到出發(fā)城市。旅行商問題的實質(zhì)是在1個帶權(quán)無向圖中找1個權(quán)值最小的哈密爾頓回路[12]。但是，傳統(tǒng)旅行商問題只能經(jīng)過同一個城市1次，無法描述多次往返取車的場景。因此，將鐵路取車問題抽象成帶權(quán)有向圖的最小權(quán)重路徑求解問題，節(jié)點間弧的權(quán)重可動態(tài)變化。城市可看作股道，與傳統(tǒng)蟻群算法實現(xiàn)不同，城市i可能等于城市j，即調(diào)機可以重復(fù)經(jīng)過同一個股道。

2.2 螞蟻遷移規(guī)則

在蟻群算法中，每個螞蟻根據(jù)隨機遷移規(guī)則選擇股道，生成一個完整的取車路徑。股道間遷移規(guī)則可用公式 ⑼ 描述。

2.3 信息素更新規(guī)則

當(dāng)一次迭代完成，所有螞蟻都將所有股道上的車組全部取完，并找到一條完整路徑后，需要更新路徑上的信息素，更新公式為

式中：t表示第t次迭代，每次迭代生成全部螞蟻的路徑；ρ為信息素蒸發(fā)系數(shù)，0 ＜ρ＜ 1 ；τij(t)為第t次迭代節(jié)點i到節(jié)點j之間路徑上的信息素濃度；u表示螞蟻的數(shù)量；表示第r個螞蟻在弧ij上留下的信息素，其中θ為信息素增加強度系數(shù)，當(dāng)螞蟻r未經(jīng)過弧ij時，為0；Disr表示第r個螞蟻完成全部取車任務(wù)的總走行距離。

公式 ⑽ 中，當(dāng)出現(xiàn)車組實際到達(dá)時間超出車組最晚到達(dá)時間時，有

式中：DP為晚點懲罰系數(shù)。

選取我院不良事件上報系統(tǒng)中2013年1月—2016年12月發(fā)生的跌倒墜床事件35例，其中，有陪護(hù)23例，無陪護(hù)12例；其中，男11例，女24例，年齡56～97歲，其中60歲以下6例，61～69歲有7例，70～79歲有10例，80～89歲有9例，90歲以上3例；08：00 AM—07：59 PM跌倒墜床16人，08：00PM—07：59AM跌倒墜床19人；生活自理能力評分（ADL）均在50～60分之間，其中≤54分12例，≥55分23例；發(fā)生在衛(wèi)生間6例，走廊4例，病室25例?；颊咦晕艺疹櫮芰Γ耗茏岳?0人，部分自理16例，不能自理9例。

車組實際到達(dá)目標(biāo)站場的時間算法如圖2所示。

圖2 車組實際到達(dá)目標(biāo)站場的時間算法Fig.2 Algorithm of arrival time to destination yard of wagon group

2.4 蟻群算法步驟

取車最優(yōu)路徑求解算法函數(shù)結(jié)構(gòu)如圖3所示。首先，初始化信息素，然后進(jìn)入循環(huán)。每次迭代都先將所有螞蟻隨機放置在股道上，然后循環(huán)處理每一個螞蟻，為其找到完整的取車路徑。路徑搜索過程與傳統(tǒng)蟻群算法不同，傳統(tǒng)算法城市數(shù)量固定，弧數(shù)量固定，可以確定循環(huán)次數(shù)，通常用For循環(huán)實現(xiàn)[11-13]，而取車最優(yōu)路徑問題求解中，每個螞蟻經(jīng)過股道的數(shù)量可變，因而用圖2中第6行所示的While循環(huán)實現(xiàn)，循環(huán)結(jié)束條件是所有股道上車組全部取完。循環(huán)處理完所有螞蟻后，計算并將上一次迭代中的最優(yōu)路徑賦值給第一個螞蟻。然后，按信息素更新規(guī)則更新信息素，進(jìn)入下一次迭代。當(dāng)找到滿意解或者達(dá)到最大迭代次數(shù)后，循環(huán)結(jié)束。

3 算例分析

3.1 基礎(chǔ)數(shù)據(jù)

某編組站樹枝形鐵路站場線路如圖1所示。圖1中，g1至g8代表8個股道，d0代表站場入口信號機，d1至d8代表各股道入口信號機，w1至w7為道岔的岔心編號，c為目標(biāo)站場。調(diào)機初始停于d0外側(cè)，車列最大長度限制l= 600 m。假設(shè)車輛長度全為均值15 m時，車列最大車輛數(shù)量為40。股道入口信號機間距離如表1所示；股道入口信號機與站場入口信號機間距離如表2所示。本站場入口信號機至取車目標(biāo)站場入口信號機距離d= 2 000 m，調(diào)機速度v= 3 m/s。

圖3 改進(jìn)蟻群算法結(jié)構(gòu)Fig.3 Structure of improved ACA

表1 股道入口信號機間距離 mTab.1 Distance between track entrance signals

表2 股道入口信號機與站場入口信號機間距離 mTab.2 Distance between track entrance signal and shunting yard entrance signal

3.2 算例結(jié)果

當(dāng)股道g1，g5，g8停有車組時，P= {g1，g5，g8}。車組停放位置描述如表3所示。在一臺中央處理器為i7-3630Q 2.4 GHz，內(nèi)存12 GB的計算機上求解。蟻群算法信息素的重要度α= 0.7，啟發(fā)因子的重要度β= 0.7，信息素蒸發(fā)系數(shù)ρ= 0.9，信息素增加強度系數(shù)θ= 0.1，最大迭代次數(shù)設(shè)為1 000，晚點到達(dá)懲罰系數(shù)DP為20 000 m。蟻群算法迭代10次后可收斂到最優(yōu)解，求得次優(yōu)路徑為“g8—g5—g1—c—g1—c”，次優(yōu)走行距離為9 170 m，最優(yōu)路徑為“g1—g8—c—g5—c”，最短走行距離為9 130 m，無晚點，與利用深度優(yōu)先算法求解得到的結(jié)果一致。

表3 車組停放位置描述Tab.3 Description of wagon group parking position

3.3 算法性能分析

為了驗證取車最優(yōu)路徑求解蟻群算法執(zhí)行性能和結(jié)果正確性，利用相同站場對不同股道停車情況進(jìn)行計算，將計算時間和結(jié)果與深度優(yōu)先算法進(jìn)行對比。車組停放數(shù)量描述如表4所示。

表4 車組停放數(shù)量描述Tab.4 Description of wagon group parking number

P1至P6代表6種停車情況，如P1代表股道g1，g2，g3上停有車組，6種停車情況具體如下。

P1= {g1，g2，g3}

P2= {g1，g2，g3，g4}

P3= {g1，g2，g3，g4，g5}

P4= {g1，g2，g3，g4，g5，g6}

P5= {g1，g2，g3，g4，g5，g6，g7}

P6= {g1，g2，g3，g4，g5，g6，g7，g8}

針對以上6種停車情況，不考慮最晚到達(dá)約束，分別利用深度優(yōu)先算法和蟻群算法進(jìn)行求解。蟻群算法相關(guān)參數(shù)取值為α= 0.7，β= 0.7，ρ= 0.9，θ= 0.1，最大迭代次數(shù)設(shè)為1 000，不設(shè)迭代提前停止條件，晚點到達(dá)懲罰系數(shù)DP為20 000 m。深度優(yōu)先算法通過遍歷所有路徑，求出的最短距離即為最優(yōu)解。

算例計算結(jié)果比較如表5所示。由表5可知，在全部6種停車情況下，蟻群算法求得的最短路徑與深度優(yōu)先算法求得的最短路徑相等，即為最優(yōu)解。隨著存車股道數(shù)量增加，深度優(yōu)先算法需要遍歷的路徑總量和計算時間快速增加，P5和P6的計算時間已經(jīng)達(dá)到92.545 s和3 350.608 s。

表5 算例計算結(jié)果比較Tab.5 Comparison of algorithm case calculation result

算法實際計算時間變化趨勢如圖4所示。圖4的橫坐標(biāo)代表不同存車股道集合，縱坐標(biāo)代表計算時間，虛線為深度優(yōu)先算法，實線為蟻群算法。由圖4可知，深度優(yōu)先算法的計算時間隨著存車股道數(shù)量的增長呈指數(shù)增長，蟻群算法計算時間隨著存車股道數(shù)量的增長呈線性增長，增幅基本不變。在6個股道停車的情況下，蟻群算法計算時間仍小于1 s。

分別對6種停車情況進(jìn)行100次求解，統(tǒng)計收斂到最優(yōu)解迭代次數(shù)的最小、最大和平均值。不同停車情況下最優(yōu)解迭代次數(shù)統(tǒng)計如表6所示。

由表6可知，每種情況最優(yōu)解迭代次數(shù)的最小值均為1次，最大值隨著存車股道數(shù)量的增加而不斷增加，但均可在100次迭代以后收斂到最優(yōu)解。實際應(yīng)用過程中，如將蟻群算法最大迭代次數(shù)設(shè)為1 000，則可保證大部分情況下在1 s以內(nèi)求出最優(yōu)解，計算結(jié)果可信，求解算法具備一定的實用性。

圖4 算法實際計算時間變化趨勢Fig.4 Variation trend of algorithm actual calculation time

表6 不同停車情況下最優(yōu)解迭代次數(shù)統(tǒng)計 次Tab.6 Statistics of iteration number of different wagon parking situation

4 研究結(jié)論

（1）建立鐵路站場多次取車作業(yè)模型，對實際調(diào)車線路參數(shù)、牽出車組連掛車數(shù)動態(tài)變化、調(diào)機走行模式等特征進(jìn)行描述，使模型更接近鐵路實際調(diào)車作業(yè)場景。

（2）當(dāng)存車股道規(guī)模加大，改進(jìn)蟻群算法較深度優(yōu)先算法在計算時間上存在明顯優(yōu)勢，且實際上都可以在規(guī)定迭代次數(shù)內(nèi)獲得最優(yōu)解，能夠為鐵路站場取車計劃編制提供智能輔助決策，有效壓縮取車時間，加速車輛周轉(zhuǎn)。