基于時(shí)空-狀態(tài)網(wǎng)絡(luò)的機(jī)車調(diào)配運(yùn)用模型與算法研究

姜安培，陳軍華，王志美

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044）

機(jī)車調(diào)配是安排機(jī)車牽引列車的過程,是一種復(fù)雜的指派問題,即在規(guī)定時(shí)間內(nèi),以機(jī)車運(yùn)用成本最小為目標(biāo),完成機(jī)車與列車的匹配關(guān)系,是鐵路運(yùn)輸組織研究的重點(diǎn)之一[1-2]。在機(jī)車調(diào)配時(shí)需要考慮機(jī)車的牽引區(qū)段是否固定,其中非固定牽引方式允許跨區(qū)域牽引列車運(yùn)行,具有更高的運(yùn)輸效率[3-4]。有些研究從運(yùn)行圖不成對(duì)[5]、多機(jī)牽引[6]、實(shí)時(shí)調(diào)整[7]等角度對(duì)非固定牽引區(qū)段的機(jī)車調(diào)配運(yùn)用進(jìn)行探討,并引入時(shí)空網(wǎng)絡(luò)對(duì)機(jī)車的運(yùn)用配置進(jìn)行優(yōu)化[8-9]。目前關(guān)于機(jī)車調(diào)配的研究多將機(jī)車任務(wù)的接續(xù)或折返限制在區(qū)段站及其以上等級(jí)車站,而實(shí)際生產(chǎn)組織中中間站也會(huì)辦理上述作業(yè)。為解決該類機(jī)車調(diào)配問題,提出一種兩階段調(diào)配方法,以機(jī)車是否需要回段檢修為依據(jù)劃分為2個(gè)階段：第一階段安排機(jī)車牽引接續(xù)較為緊密的列車以形成牽引任務(wù)組,第二階段安排機(jī)車執(zhí)行相接續(xù)的牽引任務(wù)組。通過構(gòu)建時(shí)空-狀態(tài)網(wǎng)絡(luò)描述兩階段調(diào)配方法流程,將時(shí)間、空間和機(jī)車的牽引狀態(tài)等信息整合在網(wǎng)絡(luò)中,建立非固定區(qū)段機(jī)車調(diào)配的0-1整數(shù)規(guī)劃模型。

1 問題描述

機(jī)車調(diào)配問題需要解決的是根據(jù)線路上的列車運(yùn)輸任務(wù),合理確定牽引機(jī)車的來源以及任務(wù)完成后的去向。機(jī)車在運(yùn)行時(shí)會(huì)占用線路上的空間資源,因而調(diào)配過程需要通過整合機(jī)車對(duì)時(shí)間與空間的利用情況,以最小成本完成規(guī)定的列車牽引任務(wù)。先將鐵路線路看作一維空間,加入時(shí)間軸后即可表示機(jī)車在時(shí)空網(wǎng)絡(luò)上的運(yùn)行情況。而機(jī)車自身的時(shí)空信息不足以支持調(diào)配決策,機(jī)車當(dāng)前是否牽引列車對(duì)機(jī)車運(yùn)用會(huì)產(chǎn)生直接影響,因而將機(jī)車的牽引狀態(tài)加入到網(wǎng)絡(luò)中,建立時(shí)空-狀態(tài)網(wǎng)絡(luò)模型。

1.1 基于時(shí)空-狀態(tài)網(wǎng)絡(luò)的機(jī)車調(diào)配過程

基于時(shí)空-狀態(tài)網(wǎng)絡(luò)的機(jī)車調(diào)配過程,主要采用兩階段的機(jī)車調(diào)配方法。

（1）第一階段在考慮機(jī)車牽引狀態(tài)的基礎(chǔ)上,調(diào)配機(jī)車執(zhí)行車站間形成的列車接續(xù)任務(wù),形成機(jī)車不回段的一次牽引任務(wù)組。機(jī)車的初始狀態(tài)為0,此時(shí)可以前往其他車站或在該站等待后續(xù)牽引任務(wù)；機(jī)車連掛列車后,狀態(tài)變?yōu)?,此時(shí)只能執(zhí)行列車的牽引任務(wù),直至與列車分離,狀態(tài)變回0。

未進(jìn)行優(yōu)化的機(jī)車調(diào)配時(shí)空-狀態(tài)網(wǎng)絡(luò)如圖1所示,圖1中示意了機(jī)車a,b和c的牽引任務(wù),T軸表示時(shí)間,D軸表示距離,S軸表示狀態(tài)。設(shè)StationA和StationC距離Depot1較近,StationB距離Depot2較近。機(jī)車a由Depot1出發(fā)前往StationC,在連掛上列車1后,狀態(tài)由0變?yōu)?；將列車運(yùn)至目的地StationB后,狀態(tài)變回0,而后返回機(jī)務(wù)段Depot1。

圖1 未進(jìn)行優(yōu)化的機(jī)車調(diào)配時(shí)空-狀態(tài)網(wǎng)絡(luò)Fig.1 Space-time-state network of unoptimized locomotive assignment

該方案為每列車配屬1臺(tái)機(jī)車,完成牽引任務(wù)后機(jī)車返回機(jī)務(wù)段,機(jī)車調(diào)配第一階段的時(shí)空網(wǎng)絡(luò)圖如圖2所示,為減少空走成本,圖2中給出改進(jìn)。機(jī)車a在完成列車1的牽引任務(wù)后,由StationB單機(jī)前往StationA,而后等待至列車2的發(fā)車時(shí)刻,牽引其到達(dá)StationC,而后由StationC開回與其距離最近的機(jī)務(wù)段Depot1,至此機(jī)車a完成一個(gè)牽引任務(wù)組,即第一階段完成。

圖2 機(jī)車調(diào)配第一階段的時(shí)空網(wǎng)絡(luò)圖Fig.2 Space-time network of locomotive assignment in phase 1

（2）第二階段將以同一區(qū)段站為起訖點(diǎn)的牽引任務(wù)組進(jìn)行串聯(lián)。機(jī)車調(diào)配第二階段的時(shí)空網(wǎng)絡(luò)圖如圖3所示,圖3中機(jī)車k1由Depot3出發(fā),完成牽引任務(wù)組a后進(jìn)行整備,之后繼續(xù)執(zhí)行牽引任務(wù)組c,而后返回Depot1整備。之后完成任務(wù)組g的牽引工作后,機(jī)車k1回Depot3,至此得到機(jī)車k1的全部牽引任務(wù)。

圖3 機(jī)車調(diào)配第二階段的時(shí)空網(wǎng)絡(luò)圖Fig.3 Space-time network of locomotive assignment in phase 2

1.2 重載列車多機(jī)牽引求解

由于重載列車需要多機(jī)牽引,因而會(huì)由于列車種類的不同而產(chǎn)生不同的機(jī)車指派方案,采用“影子列車”代替法,將不可由單機(jī)牽引的重載列車“分解”為一組多列的普通列車。分解后每組“影子列車”具有完全相同的參數(shù)設(shè)置(如到發(fā)時(shí)刻、?？寇囌镜?,但服務(wù)同組“影子列車”的機(jī)車不必同時(shí)到達(dá)。

機(jī)車調(diào)配問題的圖形輸入如圖4所示,每列普通列車在網(wǎng)絡(luò)中有2個(gè)坐標(biāo)點(diǎn)(departi,arrivei),分別代表起點(diǎn)和目的地；而每列重載列車由多列完全相同的“影子列車”組合而成(如列車5'和5"組成重載列車5)。機(jī)車一般由以點(diǎn)表示的機(jī)務(wù)段(如機(jī)務(wù)段Depot1)出發(fā),分配到與該機(jī)務(wù)段鄰近的各車站,執(zhí)行出發(fā)列車的牽引任務(wù)。

在對(duì)列車信息進(jìn)行初步處理后,通過建立混合整數(shù)規(guī)劃模型,在第一階段搜索可行方案,得到一系列的牽引任務(wù)組,第二階段給出啟發(fā)式規(guī)則進(jìn)行機(jī)車周轉(zhuǎn)圖的鋪畫,獲得機(jī)車所執(zhí)行的牽引任務(wù)組,進(jìn)而確定每臺(tái)機(jī)車的列車牽引任務(wù)。

圖4 機(jī)車調(diào)配問題的圖形輸入Fig.4 Graphical input in locomotive assignment problem

2 基于時(shí)空-狀態(tài)網(wǎng)絡(luò)的機(jī)車調(diào)配運(yùn)用模型

2.1 符號(hào)定義

引入3個(gè)0-1變量,xijk= 1表示機(jī)車k從列車i或機(jī)務(wù)段i前往列車j或機(jī)務(wù)段j,xijk= 0表示其他；ypk= 1表示機(jī)車k從機(jī)務(wù)段p出發(fā),0表示其他；ukt= 1表示機(jī)車k在t時(shí)刻已連掛列車,0表示其他。模型涉及的集合和參數(shù)如表1所示。

2.2 模型構(gòu)建

考慮機(jī)車運(yùn)轉(zhuǎn)時(shí)間、保有數(shù)量、接續(xù)匹配、位置狀態(tài)和列車時(shí)間窗等約束條件,以資源消耗少、機(jī)車作業(yè)強(qiáng)度均衡、調(diào)配連續(xù)性強(qiáng)為 目標(biāo)建立模型如下。

模型的目標(biāo)函數(shù)包括3部分：一是在保證完成列車牽引任務(wù)的前提下,機(jī)車調(diào)配過程中所消耗的資源最少(空走費(fèi)用,等待費(fèi)用等)。二是由于每臺(tái)機(jī)車均由機(jī)務(wù)人員執(zhí)行任務(wù),并且機(jī)務(wù)人員排班計(jì)劃一般以機(jī)車運(yùn)用計(jì)劃為基礎(chǔ),因而為保證機(jī)務(wù)人員工作強(qiáng)度的均衡,必須保證調(diào)配方案中每臺(tái)機(jī)車在運(yùn)轉(zhuǎn)時(shí)間、運(yùn)轉(zhuǎn)距離以及等待時(shí)間等方面的均衡性。這里引入機(jī)車工作時(shí)間方差作為目標(biāo)函數(shù),實(shí)現(xiàn)機(jī)車工作強(qiáng)度的均衡。三是為保障各機(jī)務(wù)段服務(wù)強(qiáng)度的均衡性和后續(xù)調(diào)配工作的接續(xù)性,加入機(jī)務(wù)段的開出/駛?cè)霗C(jī)車數(shù)量方差作為目標(biāo)函數(shù),使得各機(jī)務(wù)段在一定周期內(nèi)機(jī)車進(jìn)出數(shù)量大抵相當(dāng)。其中ξ1,ξ2,ξ3為目標(biāo)函數(shù)權(quán)重系數(shù)。

表1 模型涉及的集合和參數(shù)Tab.1 Sets and parameters involved in the model

約束 ⑵ 表示機(jī)車連續(xù)運(yùn)轉(zhuǎn)的最長(zhǎng)時(shí)間限制,機(jī)車k的運(yùn)轉(zhuǎn)時(shí)間由空駛時(shí)間、牽引列車時(shí)間和駐留等待時(shí)間構(gòu)成；約束 ⑶ 為機(jī)車數(shù)量限制；約束⑷—⑼ 表示機(jī)車在機(jī)務(wù)段、牽引任務(wù)之間的接續(xù)約束：約束 ⑷ 為變量x和變量y的匹配關(guān)系；約束⑸ 表示機(jī)車滿足出入段條件,不要求與其出發(fā)機(jī)務(wù)段相同；約束 ⑹ 和 ⑺ 表示列車與機(jī)車的一一對(duì)應(yīng)關(guān)系；約束 ⑻ 為機(jī)車接續(xù)約束,表示機(jī)車在牽引完列車i的任務(wù)后必須是從i出發(fā)；約束 ⑼ 為各個(gè)機(jī)車交路的“小回路”破壞條件,表示機(jī)車k只有從機(jī)務(wù)段開出后,才能去執(zhí)行列車的牽引任務(wù)；約束 ⑽ 為機(jī)車的牽引狀態(tài)對(duì)其能否前往牽引列車的限制；約束 ⑾—⒀ 為時(shí)間窗約束：約束 ⑾ 為同一機(jī)車牽引的接續(xù)列車間的時(shí)間匹配約束；約束⑿限制了機(jī)車到達(dá)牽引列車所在站的時(shí)間范圍；約束⒀ 為補(bǔ)充條件,規(guī)定機(jī)務(wù)段的到達(dá)時(shí)間、等待時(shí)間和運(yùn)輸任務(wù)時(shí)間為0。

2.3 求解算法

機(jī)車調(diào)配問題在本質(zhì)上是一個(gè)混合整數(shù)規(guī)劃問題,一般的數(shù)學(xué)軟件在求解小規(guī)模問題時(shí)往往能較快找到全局最優(yōu)解,但規(guī)模一旦過大,求解的速度就很難滿足需要。此時(shí)可以使用啟發(fā)式算法進(jìn)行求解,通過設(shè)計(jì)一種模擬退火算法,可以在較短時(shí)間內(nèi)找到較好的解,下面給出第一階段(機(jī)車不回段的一次連續(xù)運(yùn)轉(zhuǎn)過程)的算法實(shí)現(xiàn)步驟。

步驟1：生成初始機(jī)車運(yùn)用方案P0。

步驟2：設(shè)置約束條件Const,初始溫度T,臨界溫度e,小循環(huán)次數(shù)k和降溫系數(shù)a。

步驟3：開始模擬退火內(nèi)循環(huán),令I(lǐng)= 0。

步驟4：通過隨機(jī)條件進(jìn)行判定,改變機(jī)車發(fā)出到達(dá)的機(jī)務(wù)段、交換運(yùn)輸任務(wù)的牽引機(jī)車或合并機(jī)車的牽引任務(wù),產(chǎn)生新解P1。

步驟5：若新解P1不滿足約束條件Const,則轉(zhuǎn)步驟4。否則令Δ =obj(P1) -obj(P0),若Δ ≤ 0,則令P0=P1；否則生成0到1之間的隨機(jī)數(shù)r=random(0,1),若r＜exp (-Δ /T),令P0=P1。

步驟6：令I(lǐng)=I+ 1,若I＜K,則轉(zhuǎn)到步驟4。

步驟 7 ：令T=αT,若T＜ε,則轉(zhuǎn)到步驟 3。

步驟8：輸出第一階段求解結(jié)果P0。

其中,為提高計(jì)算效率,初始解的產(chǎn)生方式由下面規(guī)則給出。

步驟1：設(shè)置剩余列車集N_remain為全部列車任務(wù)。

步驟2：令每列列車由距離出發(fā)站最近的機(jī)務(wù)段開出機(jī)車進(jìn)行牽引,對(duì)各機(jī)車可最早出發(fā)時(shí)間leavetime進(jìn)行排序,選擇該值最小的一組機(jī)車k和列車j,令k前往牽引j；更新N_remain,leavetime。

步驟3：設(shè)置機(jī)車k可牽引列車集N_left為空,在剩余列車集中尋找滿足機(jī)車k接續(xù)牽引的列車,并加入N_left中。

步驟4：若可牽引列車集N_left為空,則轉(zhuǎn)到步驟7。

步驟5：對(duì)機(jī)車k到達(dá)列車i出發(fā)站的時(shí)間進(jìn)行排序,選擇該值最小的列車作為機(jī)車k的下一牽引列車,更新N_remain,leavetime。

步驟6：若可牽引列車集N_left非空,則返回步驟3。

步驟7：記錄列車機(jī)車k的牽引列車組,若剩余列車集合N_remain非空,則返回步驟2。

步驟8：輸出初始可行解。

第二階段(牽引任務(wù)組的接續(xù)過程）同樣可以使用這種算法求解,只需將其中的列車改為牽引任務(wù)組即可。為了提高問題的求解速度,針對(duì)第二階段本文給出一種啟發(fā)式規(guī)則,實(shí)現(xiàn)步驟如下。

步驟1：輸入牽引任務(wù)組總數(shù)N,設(shè)置各站整備完成的機(jī)車數(shù)初始值L均為0。

步驟2：設(shè)置選擇牽引任務(wù)組的初始編號(hào)J= 1,設(shè)置所需機(jī)車總數(shù)的初始值n= 0。

步驟3：若牽引任務(wù)組J的出發(fā)站機(jī)車數(shù)L(j) ＞ 0,則令最早整備完成的機(jī)車執(zhí)行J,L(j) =L(j) - 1；否則,L(j)開出一臺(tái)機(jī)車執(zhí)行J,所需機(jī)車總數(shù)n=n+ 1。

步驟4：若J整備完成,則令J的到達(dá)站機(jī)車數(shù)L(j) =L(j) + 1。

步驟5：令J=J+ 1；若J≤N,則返回步驟3。

步驟6：輸出結(jié)果。

3 算例研究

通過2個(gè)案例對(duì)提出的方法進(jìn)行驗(yàn)證,案例1由隨機(jī)生成,使用Lingo和啟發(fā)式算法分別求解,以驗(yàn)證算法的適用性；案例2基于包神鐵路的實(shí)際運(yùn)營(yíng)數(shù)據(jù),運(yùn)用啟發(fā)式算法求解。所設(shè)計(jì)的模擬退火算法在MATLAB R2014b平臺(tái)編程實(shí)現(xiàn),在Intel Core i73.2GHz處理器和16GB主存儲(chǔ)器的戴爾NMK500個(gè)人電腦上運(yùn)行。

3.1 模擬案例

某鐵路貨運(yùn)區(qū)間有7個(gè)站,首尾站分別為機(jī)務(wù)段和折返段所在地,某段鐵路各區(qū)間走行時(shí)間如表2所示。某段時(shí)間內(nèi)開行6列普通列車和1列重載列車,列車運(yùn)行情況如表3所示。

表2 某段鐵路各區(qū)間走行時(shí)間表 minTab.2 Running schedule in each section of a railway

表3 列車運(yùn)行情況表Tab.3 Train operation table

為簡(jiǎn)化模型輸入,利用“影子”列車來代替重載列車,機(jī)車在站整備時(shí)長(zhǎng)20 min,參數(shù)計(jì)算表如表4所示。

設(shè)置參數(shù)(ξ1,ξ2,ξ3) = (1,0,0),分別使用Lingo內(nèi)置求解器和模擬退火算法求解,模擬退火算法求解機(jī)車調(diào)配結(jié)果方案表如表5所示,算法求解調(diào)配結(jié)果機(jī)車周轉(zhuǎn)圖如圖5所示。第一階段解得列車60004和60023組成牽引任務(wù)組,列車10003_2和60029組成牽引任務(wù)組；第二階段將列車60008的牽引任務(wù)合并到機(jī)車k1執(zhí)行,列車60006和60027的牽引任務(wù)合并為機(jī)車k2執(zhí)行。2種方法求解結(jié)果比較如表6所示。

以此可看出,啟發(fā)式算法雖然比Lingo求解結(jié)果略差,但運(yùn)行時(shí)間大大縮短,因而所給算法在解決較大規(guī)模實(shí)際問題時(shí)具有可行性。

3.2 包神鐵路南線機(jī)車調(diào)配實(shí)例

包神鐵路(包頭—神木)是國(guó)家能源集團(tuán)煤運(yùn)通道的重要組成部分,南線為雙線鐵路,共設(shè)置9個(gè)車站,包神鐵路南線線路如圖6所示。該段鐵路機(jī)車交路較短,導(dǎo)致牽引作業(yè)有效時(shí)間減小,機(jī)車的運(yùn)用受到影響,調(diào)配問題顯著。包神鐵路南線的機(jī)務(wù)段位于東勝站,折返段位于烏蘭木倫,列車平均速度49.14 km/h,單機(jī)走行速度50.35 km/h,該段鐵路重載列車都由雙機(jī)進(jìn)行牽引。

應(yīng)用機(jī)車調(diào)配模型,在考慮資源消耗、強(qiáng)度均衡和工作連續(xù)性的情景下進(jìn)行優(yōu)化計(jì)算。實(shí)例選取包神鐵路南線2017年7月8日開行的59列重載列車和179列普通列車,包神鐵路南線某日列車運(yùn)行圖如圖7所示。

表4 參數(shù)計(jì)算表Tab.4 Parameter calculation table

表5 模擬退火算法求解機(jī)車調(diào)配結(jié)果方案表Tab.5 Locomotive assignment plan solving by Simulated Annealing Algorithm

圖5 算法求解調(diào)配結(jié)果機(jī)車周轉(zhuǎn)圖Fig.5 Locomotive rotation diagram solving by algorithm

表6 求解結(jié)果比較Tab.6 Comparison of the results

使用模擬退火算法求解該機(jī)車調(diào)配問題,不同參數(shù)設(shè)置下目標(biāo)函數(shù)值如圖8所示。

當(dāng)參數(shù)時(shí),目標(biāo)函數(shù)取得最小值4612.65。不同情景下機(jī)車調(diào)配結(jié)果對(duì)比如圖9所示,只考慮資源消耗優(yōu)化,參數(shù)設(shè)置為的機(jī)車周轉(zhuǎn)圖如圖10所示,結(jié)果相比于優(yōu)化前,機(jī)車的使用數(shù)量大大減少,平均接續(xù)時(shí)間得到縮短,空駛成本降低。加入機(jī)車工作強(qiáng)度均衡和工作接續(xù)性2個(gè)目標(biāo)函數(shù),參數(shù)設(shè)置為,由于機(jī)車的工作時(shí)間平均化,以及等待成本所占比重降低,使得機(jī)車的平均等待時(shí)間增長(zhǎng)；而為了滿足工作連續(xù)性而采用的機(jī)務(wù)段開出/開回機(jī)車均衡,使得機(jī)車可能由距離列車出發(fā)站較遠(yuǎn)的機(jī)務(wù)段開出,因而機(jī)車平均接續(xù)時(shí)間略有增長(zhǎng)。

圖6 包神鐵路南線線路圖Fig.6 Circuit diagram of Baotou-Shenmu south railway line

圖7 包神鐵路南線某日列車運(yùn)行圖Fig.7 Train operation diagram in Baotou-Shenmu south railway line in one day

4 結(jié)束語(yǔ)

針對(duì)鐵路企業(yè)開行始發(fā)終到站位于中間站列車的機(jī)車調(diào)配問題,提出了一種兩階段機(jī)車調(diào)配方法,并對(duì)包神鐵路南線重載運(yùn)輸通道的機(jī)車調(diào)配運(yùn)用進(jìn)行優(yōu)化,為鐵路機(jī)車的靈活調(diào)配提供了一種新的思路和途徑。由于機(jī)車調(diào)配在鐵路運(yùn)輸組織中并不是一個(gè)單獨(dú)的過程,如果能與機(jī)務(wù)排班和列車開行方案協(xié)同編制,則會(huì)使機(jī)車的運(yùn)用效率得到更好地發(fā)揮。另外,對(duì)于重載列車與普通列車混行的運(yùn)輸組織模式,提出的“影子列車”是一種處理列車輸入的方法,雖然能解決該機(jī)車調(diào)配問題但未能將問題普適化,因而考慮將拖車問題引入并用以解決該類問題是進(jìn)一步研究的重要方向。

圖8 不同參數(shù)設(shè)置下目標(biāo)函數(shù)值Fig.8 Results under different parameter settings

圖9 不同情景下機(jī)車調(diào)配結(jié)果對(duì)比圖Fig.9 Comparison of the locomotive assignment results in various scenarios

圖10 參數(shù)設(shè)置為(1，0，0)的機(jī)車周轉(zhuǎn)圖Fig.10 Locomotive turnaround chart when the parameter is set to (1, 0, 0)