基于車流接續(xù)代價最小的編組站配流計劃優(yōu)化研究

許 可，馬海東 ，趙 鵬，馬亞鋒，任逸飛

（1.北京交通大學(xué) 交通運輸學(xué)院，北京 100044；2.華東交通大學(xué) 交通運輸與物流學(xué)院，江西 南昌330006；3.中國鐵路太原局集團有限公司 大同車務(wù)段，山西 太原 030013)

0 引言

編組站是鐵路網(wǎng)上車流集散和列車解編的基地，主要負責(zé)貨物列車的解體和編組，是鐵路運輸系統(tǒng)的重要一環(huán)，其作業(yè)效率直接影響鐵路運輸效率和經(jīng)濟效益。據(jù)統(tǒng)計，鐵路運輸過程中，由于調(diào)車作業(yè)和集結(jié)等待時間較長，在站停留時間約占總運輸時間的70%，而合理的編組站配流計劃能夠高效地組織貨物列車的解編，大大減少在站作業(yè)和等待時間，有助于提高編組站解編效率、縮短車輛周轉(zhuǎn)時間。編組站配流問題是在滿足時間、設(shè)備、人員和車流接續(xù)約束情況下，確定列車解體順序和編入出發(fā)列車的內(nèi)容，即確定編組站的自編始發(fā)列車由哪些到達車流組成(到達列車、車輛數(shù))。配流是編組站的核心環(huán)節(jié)，貫穿于整個編組站的作業(yè)計劃。

編組站配流問題是一個復(fù)雜的問題，需要合理組織車站的人員、設(shè)備及車流按要求完成編組。許多學(xué)者對此進行研究，王慈光[1]將編組站配流看作資源分配問題，引入“代價”概念，把配流問題轉(zhuǎn)化為求解代價最小的運輸問題，并運用表上作業(yè)法求解。郭瑞等[2]針對采用“單推單溜”作業(yè)方式的編組站，以車輛在站停留時間最短和階段出發(fā)列車數(shù)最多為目標，設(shè)計多目標、分階段的配流問題推理算法。張正坤等[3]根據(jù)Petri 網(wǎng)理論，在謂詞/變遷(Pr/T)系統(tǒng)的基礎(chǔ)上，引入時間參數(shù)，建立了編組站TPr/T_系統(tǒng)模型，以保證列車按計劃滿軸出發(fā)為約束，利用反向推理思想設(shè)計算法求解。張英群等[4]研究調(diào)車場分類線運用優(yōu)化調(diào)車作業(yè)，以出發(fā)列車連掛次數(shù)最少為目標，建立基于分類線運用的0-1 整數(shù)規(guī)劃配流模型。李晟東等[5]根據(jù)貨物的運輸時間要求差異，賦予貨物列車不同的權(quán)重，以列車在站停留加權(quán)值最小為目標，建立基于運到期限的編組站配流優(yōu)化模型，并設(shè)計模擬退火算法進行求解。薛鋒等[6]考慮配流所需要的車流、調(diào)機、到發(fā)線等資源的可用性，以車輛在站停留時間最小為目標，建立基于資源可用性的編組站配流模型，并通過分層優(yōu)化方法降低求解難度。趙永亮[7]研究利用編組站、貨運站和海港組成的綜合運輸體系，使用三角模糊數(shù)量化運輸系統(tǒng)中技術(shù)作業(yè)執(zhí)行時間的不確定性，構(gòu)建技術(shù)作業(yè)執(zhí)行時間目標函數(shù)，求解具有最小在站作業(yè)時間的最大可能載貨量。

然而，既有研究存在以下問題：一是對編組站作業(yè)過程車流接續(xù)研究不夠深入；二是建立符合實際作業(yè)的配流模型比較困難，有的模型為了提高求解效率，將模型進行了過度的簡化，不能滿足實際需要，而有的模型考慮的因素過多，導(dǎo)致求解困難。為此，將配流問題轉(zhuǎn)化為運籌學(xué)的運輸問題，以車流接續(xù)總代價最小作為目標函數(shù)，建立基于車流接續(xù)代價最小的編組站配流優(yōu)化模型，并設(shè)計相應(yīng)的求解算法，得到優(yōu)化的配流計劃方案，為編組站配流問題提供解決方案。

1 基于車流接續(xù)代價最小的編組站配流優(yōu)化模型

1.1 編組站系統(tǒng)分析

根據(jù)編組站各項技術(shù)作業(yè)的層次性和相關(guān)性，將編組站系統(tǒng)劃分為到達解體子系統(tǒng)和編組出發(fā)子系統(tǒng)2 個子系統(tǒng)。在2 個子系統(tǒng)的配合下，根據(jù)階段列車到達計劃和列車出發(fā)計劃，合理地組織列車的解體編組工作，即配流計劃。配流計劃是編組站運輸組織工作的核心，貫穿于編組站的日常工作[8]。編組站系統(tǒng)示意圖如圖1 所示。

1.2 編組站配流優(yōu)化模型

假設(shè)：①編組站站型為單向編組站，只有1 套調(diào)車系統(tǒng)；②駝峰采用“單推單溜”方式作業(yè)，即只有當前列車解體作業(yè)完成后，下一列車的解體作業(yè)才能進行；③到達和出發(fā)列車的技術(shù)作業(yè)都按規(guī)定時間標準完成，并且沒有待解、待編等非生產(chǎn)作業(yè)時間；④編組場、到發(fā)場等固定設(shè)備能力足夠大。

在滿足車流接續(xù)時間、到發(fā)車流總量、滿軸等約束條件下，引入懲罰系數(shù)衡量配流的代價，設(shè)計車流總配流代價最小的配流方案[9]，其目標函數(shù)為

式中：Z為車流總配流代價；n為到達列車總數(shù)(當i= 0 時，表示現(xiàn)存車情況)；m為出發(fā)列車總數(shù)；pij為懲罰系數(shù)，表示第i列到達列車中的車流配入第j列出發(fā)列車的代價，pij越大表示配流方案越不合理；xij為第i列到達列車的車流配入第j列出發(fā)列車的車輛數(shù)。

編組站配流優(yōu)化模型包含車流接續(xù)時間約束、到發(fā)車流總量約束、滿軸約束及配流過程中的懲罰系數(shù)等約束條件，具體如下。

（1）車流接續(xù)時間約束。到達列車在站最早解體時刻早于到達列車實際解體時刻，可表示為

圖1 編組站系統(tǒng)示意圖Fig.1 Schematic diagram of marshalling station system

出發(fā)列車實際編組時刻早于出發(fā)列車最晚編組時刻，可表示為

第i列到達列車在站最早解體時刻等于列車到達時刻加上到達作業(yè)時間，可表示為

式中：Tdi為到達時刻；Tdz為到達技術(shù)作業(yè)時間。

第j列出發(fā)列車最晚編組時刻等于出發(fā)時刻減去出發(fā)技術(shù)作業(yè)時間和編組技術(shù)作業(yè)時間，可表示為

式中：Tcj為出發(fā)時刻；Tcz為出發(fā)技術(shù)作業(yè)時間；為第j列出發(fā)列車編組技術(shù)作業(yè)時間。

配流中的可用車流除了本站作業(yè)車和轉(zhuǎn)場車流等不需要進行到解技術(shù)作業(yè)直接是可用車流外，其他的車流在站需要經(jīng)過到達、解體等作業(yè)進入調(diào)車場后，才能成為實際可用于編組的車流，因而在到發(fā)車流接續(xù)時還要考慮技術(shù)作業(yè)的時間[10]，具體約束如下。

式中：為第i列到達列車解體時間。

（2）到發(fā)車流總量約束可表示為

式中：m為出發(fā)列車總數(shù)；n為到達列車總數(shù)；ai為供應(yīng)車流量，即到達車輛數(shù)；bj為需求車流量，即出發(fā)車輛數(shù)。

（3）滿軸約束可表示為

（4）配流過程中的懲罰系數(shù)的確定。

記Uij表示編組去向是否相符，可以表示為

懲罰系數(shù)pij取值規(guī)則為：在解體順序一定的條件下，當?shù)桨l(fā)列車編組去向不同和車流接續(xù)時間不足時，表明無法配入，則pij=M1(M1表示一個充分大的數(shù))；當總車流量不相同情況下，虛設(shè)到達或出發(fā)列車，則將配入虛擬到達或出發(fā)列車的懲罰系數(shù)pij=M2(M2表示一個比λj大的數(shù))；不是以上情況，就令pij等于編入出發(fā)列車j的排序號λj。

1.3 模型求解

編組站配流優(yōu)化模型是針對列車解體順序已定的靜態(tài)配流模型，充分考慮了車流編組方向、接續(xù)時間、技術(shù)作業(yè)及滿軸等約束，引入“懲罰系數(shù)”衡量到發(fā)列車接續(xù)的代價，其求解步驟如下。

（1）判斷總車流量是否守恒，設(shè)總供應(yīng)量為A，總需求量為B，則

當A＜B時，虛設(shè)一個發(fā)點(即出發(fā)列車)，供應(yīng)量為an+1=B-A；當A＞B時，虛設(shè)一個收點(即到達列車)，需求量為bn+1=A-B。

（2）將階段內(nèi)有不同編組去向車流化為單組列車，確定問題研究的總的到達車數(shù)n及供應(yīng)車流量ai，出發(fā)車數(shù)m及需求車流量bj。

（3）分析階段內(nèi)的全部出發(fā)列車，包括虛設(shè)的出發(fā)列車和去向不同的出發(fā)列車，將其按列車等級排序規(guī)則排序標號。

（4）根據(jù)約束條件，確定懲罰系數(shù)pij，若Uij= 0 或Hij= 0，則pij=M1；若Uij= 1 且Hij= 1，且j=m+1，則pij=M2；否則pij=λj。

（5）根據(jù)已知資料編制求解配流資料平衡表，將發(fā)點、收點、各供應(yīng)、需求量及懲罰系數(shù)等填入表中，對于復(fù)雜的配流問題用網(wǎng)絡(luò)模型進行輔助說明。

（6）根據(jù)配流資料平衡表設(shè)計Matlab 程序利用計算機求解最優(yōu)的配流方案。

2 算例分析

以編組站K 為研究對象，考慮實際編組中的編組去向約束、到發(fā)車流量不同、各項技術(shù)作業(yè)時間、滿軸要求及車流接續(xù)時間等約束，基于車流接續(xù)代價最小構(gòu)建編組站配流優(yōu)化模型，運用建模求解思路進行算例分析，并優(yōu)化配流方案。

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

現(xiàn)存車主要指已經(jīng)完成了到解技術(shù)作業(yè)，已經(jīng)在調(diào)車場等待編組的車輛，其到達時刻就是階段開始時刻且不需要進行技術(shù)作業(yè)。假設(shè)a，b，c，d 為原到達列車或出發(fā)列車車輛的去向，編組站K 一個階段內(nèi)車站現(xiàn)存車情況為：調(diào)車場集結(jié)有去向a 方向的15 輛及去向c方向的25 輛。到達列車基本信息如表1 所示，出發(fā)列車基本信息如表2 所示。

表1 到達列車基本信息表Tab.1 Information sheet of arrival train

表2 出發(fā)列車基本信息表Tab.2 Information sheet of departure train

2.2 編組站配流優(yōu)化模型構(gòu)建及求解

根據(jù)以上車站現(xiàn)存車基本情況、到達列車基本信息表和出發(fā)列車基本信息表，進行配流問題的轉(zhuǎn)化。首先進行到發(fā)車流總量的判斷，到達車輛總數(shù)量335 輛小于出發(fā)車輛總數(shù)量345 輛，因而應(yīng)虛設(shè)一列到達列車供應(yīng)車流使階段內(nèi)到發(fā)車總量相等。接著判斷列車中是否有不同向的車組，如果有不同向的車組，則將到、發(fā)列車的多編組方向化為單編組方向，表1 和表2 中有多種不同向的列車，將其按方向化為單一方向的車組，將每單一車組視為一列到達列車ddi(i= 0，1，2，…，n)或一列出發(fā)列車cfj(j= 1，2，…，m)。經(jīng)過計算可得，共有13 列單組到達列車和9 列單組出發(fā)列車。

配流網(wǎng)絡(luò)模型圖如圖2 所示。輸入層共有13列單組到達列車，輸出層共有9 列單組出發(fā)列車，其中dd0和dd1是階段開始時車站現(xiàn)存車，dd12是虛擬的到達列車，可以編入任意一列出發(fā)列車中。

圖2 配流網(wǎng)絡(luò)模型圖Fig.2 Distribution network model

圖2 直觀地表示了車流的接續(xù)關(guān)系，然后編組站配流優(yōu)化模型求解步驟3 對出發(fā)列車的排序規(guī)則進行計算，對單組出發(fā)列車cfj按照列車種類、去向多少及出發(fā)時刻進行等級排序，令各列車等級序號對應(yīng)為λj，作出出發(fā)列車排序表如表3 所示。

表3 出發(fā)列車排序表Tab.3 Sorting list of departure train

編組站配流優(yōu)化模型求解步驟4 進行車流接續(xù)懲罰系數(shù)的計算，根據(jù)公式 ⑵ 至公式 ⑾ 及表3中數(shù)據(jù)，計算懲罰系數(shù)pij，如果Uij= 0 或Hij= 0，則pij=M1；如果Uij= 1，Hij= 1，且j=m+1，則pij=M2；否則pij=λj。如果dd1和cf1編組去向不同，則U11= 0，此時p11=M1；U101= 1 表示dd10和cf1編組去向相同，但是接續(xù)時間不滿足Uij= 0，此時p101=M1，依次按規(guī)則進行計算。

為了計算的方便，可以把M1和M2進行合適的賦值(不會對結(jié)果造成影響)。在計算單組出發(fā)列車排序中λj最大為9，因而可令M1= 100，其懲罰系數(shù)值已經(jīng)遠大于其他λj，表示不可接續(xù)；相應(yīng)令M2= 50，表示懲罰系數(shù)較大，盡量避免接續(xù)。

根據(jù)各約束條件確定各系數(shù)，然后將懲罰系數(shù)、各到發(fā)列車和對應(yīng)車輛數(shù)代入，得到配流資料平衡表如表4 所示。

根據(jù)編組站配流優(yōu)化模型求解步驟，設(shè)計Matlab 算法程序進行最優(yōu)配流方案的求解，可以極大地提高配流準確性和效率。在Matlab 2016b 環(huán)境下運行程序，得到配流矩陣A。配流矩陣中標有NaN的是非基變量，標有數(shù)字的是基變量，也就是求解出的具體配流方案。

根據(jù)Matlab 程序運行求解出的配流方案矩陣，將相對應(yīng)的數(shù)值填入配流資料平衡表中，可以得到在滿足約束條件下最優(yōu)的編組站配流方案如表5 所示。根據(jù)表5 進一步優(yōu)化，得到優(yōu)化后的配流方案表如表6 所示。

3 結(jié)束語

編組站是鐵路部門運輸生產(chǎn)的基本單位，配流問題是編組站的核心，提高編組站配流水平，能夠支撐鐵路運輸組織、服務(wù)水平和經(jīng)營效率效益進一步提升，對于保障節(jié)支降耗、提質(zhì)增效具有顯著成果。基于車流接續(xù)代價最小的編組站配流優(yōu)化研究，充分考慮編組站實際作業(yè)的不確定性和復(fù)雜性，對編組站配流問題進行研究，最終得到更為優(yōu)化的可行配流計劃方案，為優(yōu)化編組站配流問題做了有力支撐，在對優(yōu)化車站作業(yè)提高工作效率，促進車站高效地完成運輸任務(wù)，更大程度地發(fā)揮編組站列車中轉(zhuǎn)基地的作用，更好地提高鐵路貨物運輸?shù)男屎透偁幜Α?/p>

表4 配流資料平衡表Tab.4 Balance sheet of distribution data

表5 配流方案表Tab.5 Flow distribution scheme

表6 優(yōu)化后的配流方案表Tab.6 Optimized distribution scheme