基于貨物運(yùn)到期限的編組站動(dòng)態(tài)配流優(yōu)化研究

李晟東，徐長(zhǎng)安，呂紅霞*,c，李文新

(西南交通大學(xué)a.交通運(yùn)輸與物流學(xué)院；b.全國(guó)鐵路列車運(yùn)行圖編制研發(fā)培訓(xùn)中心；c.綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，成都610031)

0 引 言

貨物運(yùn)到期限是指鐵路運(yùn)輸部門(mén)規(guī)定的貨物運(yùn)輸一定里程所需要的時(shí)間標(biāo)準(zhǔn).保障運(yùn)到期限，是履行對(duì)托運(yùn)人關(guān)于貨物運(yùn)輸時(shí)間的承諾，對(duì)加快貨物送達(dá)，保證運(yùn)輸質(zhì)量，提高鐵路貨物運(yùn)輸市場(chǎng)競(jìng)爭(zhēng)力有重要意義.

貨物運(yùn)輸時(shí)間由技術(shù)站中轉(zhuǎn)時(shí)間、區(qū)間運(yùn)行時(shí)間和裝卸作業(yè)時(shí)間組成.貨物的區(qū)間運(yùn)行和裝卸站作業(yè)環(huán)節(jié)簡(jiǎn)單，作業(yè)時(shí)間容易控制，而技術(shù)站的作業(yè)環(huán)節(jié)多且復(fù)雜，導(dǎo)致技術(shù)站中轉(zhuǎn)時(shí)間難以控制.因此應(yīng)主要從技術(shù)站，尤其是編組站作業(yè)入手以保障運(yùn)到期限.

編組站階段計(jì)劃作為車站作業(yè)計(jì)劃的具體安排，主要包括：配流計(jì)劃、調(diào)機(jī)運(yùn)用計(jì)劃和到發(fā)線運(yùn)用計(jì)劃，其中配流計(jì)劃與調(diào)機(jī)運(yùn)用計(jì)劃聯(lián)系緊密，而到發(fā)線運(yùn)用計(jì)劃相對(duì)獨(dú)立.配流計(jì)劃確定出發(fā)列車的車流來(lái)源，是階段計(jì)劃的主要內(nèi)容，直接影響貨物在編組站的中轉(zhuǎn)時(shí)間.因此在配流環(huán)節(jié)對(duì)運(yùn)到期限加以考慮，將極大地保障鐵路貨物運(yùn)到期限.

王慈光[1]將配流問(wèn)題分為靜態(tài)配流和動(dòng)態(tài)配流，靜態(tài)配流是在解編方案確定的前提下研究合理配流，動(dòng)態(tài)配流的前提條件則是解編方案不確定.關(guān)于靜態(tài)配流的研究中，薛鋒等[2]建立了雙向編組站靜態(tài)配流的雙層多目標(biāo)決策模型，利用禁忌搜索策略和配流網(wǎng)絡(luò)相結(jié)合的算法求解；景云等[3]通過(guò)構(gòu)建網(wǎng)絡(luò)模型，將靜態(tài)配流問(wèn)題轉(zhuǎn)化為固定費(fèi)用的產(chǎn)銷平衡運(yùn)輸問(wèn)題.關(guān)于動(dòng)態(tài)配流的研究中，何世偉等[4]建立了階段計(jì)劃解編作業(yè)與車流推算優(yōu)化混合0-1規(guī)劃模型，并給出了啟發(fā)式分解算法；王明慧等[5]綜合優(yōu)化編組站列車解體、配流、編組及到發(fā)線運(yùn)用計(jì)劃，并設(shè)計(jì)了啟發(fā)式算法求解；王正彬等[6]結(jié)合求解運(yùn)輸問(wèn)題的表上作業(yè)法，設(shè)計(jì)了混合遺傳算法.國(guó)外研究中，S.Yagar等[7]提出了一種HSS算法，并采用動(dòng)態(tài)規(guī)劃的方法，尋求最優(yōu)的解編順序；Mark A.Turnquist等[8]運(yùn)用排隊(duì)論模型求解編組站列車解編順序.

既有研究中較少考慮運(yùn)到期限，文獻(xiàn)[9-10]考慮了運(yùn)到期限因素，但都是先構(gòu)造列車解編順序，將問(wèn)題轉(zhuǎn)化為靜態(tài)配流問(wèn)題進(jìn)行研究.本文在編組站配流中考慮運(yùn)到期限，綜合考慮調(diào)機(jī)運(yùn)用計(jì)劃與配流計(jì)劃，建立0-1規(guī)劃模型，并設(shè)計(jì)模擬退火算法求解.

1 數(shù)學(xué)優(yōu)化模型

1.1 建模分析

編組站配流優(yōu)化模型中，對(duì)于運(yùn)到期限的考慮主要體現(xiàn)在如下目標(biāo)函數(shù)與約束條件方面.

(1)目標(biāo)函數(shù).

不同貨物對(duì)運(yùn)輸時(shí)效性的要求不同，以車流在站停留時(shí)間加權(quán)值的總和最小為優(yōu)化目標(biāo)構(gòu)建目標(biāo)函數(shù)，此權(quán)重體現(xiàn)對(duì)于時(shí)效性要求高的貨物在配流中的優(yōu)先考慮.

而運(yùn)輸時(shí)效性要求高與低是一個(gè)模糊概念，因此本文以運(yùn)到期限等級(jí)的概念表示貨物對(duì)運(yùn)輸時(shí)效性的要求，即目標(biāo)函數(shù)中的權(quán)重，同時(shí)以模糊數(shù)學(xué)相關(guān)理論定量化確定運(yùn)到期限等級(jí)評(píng)判方法.劃分運(yùn)到期限等級(jí)評(píng)語(yǔ)集V={V1,V2,V3,V4,V5}={低，較低，一般，較高，高}，對(duì)應(yīng)模糊等級(jí)為D={1,2,3,4,5}，進(jìn)而構(gòu)建梯形隸屬函數(shù)為

(2)約束條件.

在約束條件方面，將運(yùn)到期限分配至編組站配流環(huán)節(jié)，通過(guò)保證配流環(huán)節(jié)的時(shí)限要求，以保障運(yùn)到期限.貨物運(yùn)輸作業(yè)環(huán)節(jié)主要包括貨物作業(yè)停留、技術(shù)站中轉(zhuǎn)作業(yè)及區(qū)間運(yùn)行等.由文獻(xiàn)[9]可知，貨物作業(yè)停留時(shí)間、技術(shù)站中轉(zhuǎn)作業(yè)時(shí)間(分有調(diào)和無(wú)調(diào)中轉(zhuǎn)作業(yè)時(shí)間)及區(qū)間運(yùn)行時(shí)間等都可由正態(tài)分布描述，因此有，ui為Xi的均值，為X的方差，i=1,2,…,n，X為作業(yè)環(huán)節(jié)i消耗的ii時(shí)間.則由正態(tài)分布相關(guān)性質(zhì)可知，貨物運(yùn)輸全程時(shí)間Y也服從正態(tài)分布，其分布形式為

因此在分配運(yùn)到期限到貨物運(yùn)輸各個(gè)環(huán)節(jié)時(shí)，可采用均值比例分配法，指按貨物運(yùn)輸各個(gè)環(huán)節(jié)的平均作業(yè)時(shí)間占總時(shí)間的比例分配運(yùn)到期限，即

式中：Ti為作業(yè)環(huán)節(jié)i的時(shí)限要求；T為貨物運(yùn)到期限；ti為作業(yè)環(huán)節(jié)i的平均作業(yè)時(shí)間，可由《全國(guó)鐵路統(tǒng)計(jì)資料匯編》等資料獲取.

因而對(duì)于一批貨物，通過(guò)車流徑路和編組計(jì)劃等文件，可得知其從始發(fā)站至終到站的運(yùn)行路徑，途經(jīng)的技術(shù)站，技術(shù)站中轉(zhuǎn)作業(yè)類型等信息，即得知貨物運(yùn)輸全程包含的作業(yè)環(huán)節(jié)，進(jìn)而利用均值比例分配法分配運(yùn)到期限，得到貨物在各環(huán)節(jié)的最大時(shí)限.當(dāng)運(yùn)到期限分配至作業(yè)環(huán)節(jié)i后，可進(jìn)一步計(jì)算得到該環(huán)節(jié)的保障率pi為

1.2 模型假設(shè)

本文所建模型條件假設(shè)如下：

(1)1臺(tái)調(diào)機(jī)解體、1臺(tái)調(diào)機(jī)編組的作業(yè)系統(tǒng)；

(2)本站作業(yè)車、轉(zhuǎn)場(chǎng)車從駝峰進(jìn)入系統(tǒng)；

(3)不考慮部分改編中轉(zhuǎn)列車；

(4)有足夠的到達(dá)線、調(diào)車線、出發(fā)線等線路.

1.3 符號(hào)說(shuō)明

參數(shù)：[Tjhs,Tjhe]為計(jì)劃的編制時(shí)段；D為到達(dá)列車集合，D={d1,d2,…,dn}，i為到達(dá)列車索引，d1為虛擬到達(dá)列車，表示計(jì)劃編制起始時(shí)調(diào)車場(chǎng)的現(xiàn)車，Ki為到達(dá)列車i包含的貨車數(shù)，k為到達(dá)列車i的貨車索引；F為出發(fā)列車集合，F(xiàn)={f1,f2,…,fm}，j為出發(fā)列車索引，fm為虛擬出發(fā)列車，表示計(jì)劃編制結(jié)束時(shí)調(diào)車場(chǎng)的殘存車；Td為到達(dá)列車到達(dá)時(shí)刻集合，Tdi表示到達(dá)列車i的到達(dá)時(shí)刻；Tf為出發(fā)列車出發(fā)時(shí)刻集合，Tfj表示出發(fā)列車j的出發(fā)時(shí)刻；Tjd、Tjj、Tjb和Tjf分別為到達(dá)、解體、編組和出發(fā)技術(shù)作業(yè)時(shí)間；gikj表示到達(dá)列車i中的貨車k按編組去向是否能編入出發(fā)列車j，是為1，否為0；wik、lik分別表示到達(dá)列車i中貨車k的重量和換算長(zhǎng)度；和分別表示出發(fā)列車j的最小重量、最大重量、最小換算長(zhǎng)度和最大換算長(zhǎng)度的編組要求；αik為到達(dá)列車i中貨車k的貨物運(yùn)到期限等級(jí)；Tik為到達(dá)列車i中貨車k的在站最大停留時(shí)間.

變量：tikj為到達(dá)列車i中貨車k編入出發(fā)列車j的在站停留時(shí)間；為到達(dá)列車i的解體開(kāi)始時(shí)刻；為出發(fā)列車j的編組結(jié)束時(shí)刻；φikj表示若到達(dá)列車i的解體結(jié)束時(shí)刻早于出發(fā)列車j的編組開(kāi)始時(shí)刻，則到達(dá)列車i中貨車k可編入出發(fā)列車j，此時(shí)φikj取值為1，否則為0為0-1變量；表示到達(dá)列車i是否按最早解體開(kāi)始時(shí)刻Tzjs(Tzjs=Tdi+Tjd)解體，是為0，否為1；表示出發(fā)列車j是否按最晚編組結(jié)束時(shí)刻Tzbf(Tzbf=Tfj-Tjf)編組，是為0，否為1；xikj為0-1決策變量，表示到達(dá)列車i中貨車k是否編入出發(fā)列車j，是為1，否為0.

1.4 優(yōu)化模型

基于貨物運(yùn)到期限的單解單編系統(tǒng)的編組站動(dòng)態(tài)配流優(yōu)化模型為

式(8)為車流在編組站停留時(shí)間加權(quán)值最小化的目標(biāo)函數(shù)；式(9)為車流的編組去向約束；式(10)和式(11)分別為到達(dá)列車和出發(fā)列車的解體開(kāi)始時(shí)刻和編組結(jié)束時(shí)刻約束，控制列車盡早解體和盡晚編組，使車流有編入更多出發(fā)列車的可能，其中虛擬到達(dá)列車解體結(jié)束時(shí)刻等于Tjhs，虛擬出發(fā)列車編組結(jié)束時(shí)刻等于Tjhe；式(12)表示車流只能編入編組開(kāi)始時(shí)刻晚于其解體結(jié)束時(shí)刻的出發(fā)列車；式(13)和式(14)分別為出發(fā)列車的編組重量和換長(zhǎng)約束，式(15)表示出發(fā)列車只需滿足重量或換長(zhǎng)1個(gè)編組要求即可；式(16)為車流的在站最大停留時(shí)間約束；式(17)為車流的唯一指派約束；式(18)～式(20)為變量的0-1約束.

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

n個(gè)到達(dá)列車，m個(gè)出發(fā)列車，每個(gè)到達(dá)列車包含k個(gè)貨車的配流方案數(shù)為(mk)n，難以用精確算法求得最優(yōu)解.模擬退火(Simulated Annealing，SA)算法是求解大規(guī)模組合問(wèn)題的有效算法，能夠在理想的時(shí)間內(nèi)求得滿意解，因此設(shè)計(jì)SA算法求解模型.

模型所求目標(biāo)包括列車解編順序和出發(fā)列車車流來(lái)源，可視為雙層結(jié)構(gòu)，同時(shí)，不合理的列車解編順序下，不一定產(chǎn)生可行的配流方案.因此模型求解思路為：上層結(jié)構(gòu)通過(guò)一定的準(zhǔn)則得到合理的列車解編順序，并作為已知條件輸入下層結(jié)構(gòu)以求解出發(fā)列車車流來(lái)源，此時(shí)模型的解編順序已定，可調(diào)用CPLEX求解出發(fā)列車車流來(lái)源，即得到1個(gè)配流方案，通過(guò)SA算法循環(huán)迭代，得到模型優(yōu)化解.

模型中，列車解編順序?qū)ε淞鞯挠绊戵w現(xiàn)在式(9)、式(12)和式(16)，用max(Ki)×m×n的三維0-1矩陣M1、M2和M3分別表示約束式(9)、式(12)和式(16)的約束矩陣，其中式(16)可轉(zhuǎn)化為式(9)和式(12)的形式.定義約束矩陣M以確定上層結(jié)構(gòu)合理的列車解編順序，約束矩陣M的產(chǎn)生規(guī)則為：當(dāng)M1、M2和M3的同一位置值都為1時(shí)，M的該位置取值為1，否則為0.則約束矩陣M某一列的和mj表示對(duì)應(yīng)出發(fā)列車j最大可配入貨車數(shù)量，為每一mj設(shè)定閾值[aj,bj]，當(dāng)所有mj滿足閾值要求，即M滿足閾值要求時(shí)，則得到合理解編順序.

算法具體步驟如下，算法流程如圖1所示.

圖1 模擬退火算法流程圖Fig.1 Simulated annealing algorithm flow diagram

Step1 初始化算法參數(shù)，包括初始溫度Ts，終止溫度Te，溫度衰減系數(shù)γ，馬爾科夫鏈長(zhǎng)度δ，當(dāng)前成功迭代次數(shù)θ等.

Step2 根據(jù)“先到先解，先發(fā)先編”的規(guī)則設(shè)定初始列車解編方案，并調(diào)用CPLEX求解出發(fā)列車車流來(lái)源，以此計(jì)算得到初始目標(biāo)函數(shù)值Z0，記錄當(dāng)前最優(yōu)目標(biāo)函數(shù)值B=Z0.

Step3 采用隨機(jī)二變換的方法生成解編順序鄰域解，隨機(jī)選定當(dāng)前解體順序中的2列列車，交換其解體順序位，采用同樣的方法生成新的編組順序.

Step4 計(jì)算解編順序鄰域解的約束矩陣M，若M滿足閾值要求，轉(zhuǎn)Step5；否則，轉(zhuǎn)Step3.

Step5 求解解編順序鄰域解下的出發(fā)列車車流來(lái)源，以此計(jì)算得到目標(biāo)函數(shù)值Zθ.若Zθ

Step6Tθ=γTθ-1，若Tθ

3 算例分析

某二級(jí)三場(chǎng)編組站解體、編組調(diào)機(jī)均為1臺(tái)，列車到達(dá)作業(yè)時(shí)間為30 min，出發(fā)作業(yè)時(shí)間為30 min，解體作業(yè)時(shí)間為15 min，編組作業(yè)時(shí)間為15 min.到達(dá)車流信息如表1所，出發(fā)車流信息如表2所示，車流運(yùn)到期限信息(由于篇幅原因，僅列舉22302次列車信息)如表3所示.

表1 到達(dá)列車車流數(shù)據(jù)Table 1 Wagon-flow data of arriving trains

表2 出發(fā)列車車流數(shù)據(jù)Table 2 Wagon-flow data of departing trains

在CPU為Inter Core i7-6700HQ，RAM為16G的個(gè)人計(jì)算機(jī)上，采用Matlab2016a編程，經(jīng)過(guò)多組參數(shù)實(shí)驗(yàn)，在初始溫度為99，終止溫度為1，溫度衰減系數(shù)為0.9下，求解得到目標(biāo)函數(shù)值為175 174，算法收斂曲線如圖2所示，列車解編和配流方案如表4～表6所示.

圖2 算法收斂曲線圖Fig.2 Algorithm convergent curve diagram

表4 優(yōu)化列車解體方案Table 4 Optimized train disintegration scheme

表5 優(yōu)化列車編組方案Table 5 Optimized train marshalling scheme

表6 優(yōu)化配流方案Table 6 Optimized wagon-flow allocation scheme

可知，到達(dá)列車的解體順序?yàn)閧1,2,3,4,6,5,8,7,10,9,11,12}，出發(fā)列車的編組順序?yàn)閧2,3,1,4,5,6,8,7,-,9,10,11}，其中41006次列車因?yàn)檐嚵鹘永m(xù)不足而停運(yùn)，同時(shí)所有車流實(shí)際在站停留時(shí)間均未超過(guò)最大在站停留時(shí)間，如表7所示，從而驗(yàn)證了本文模型及算法的有效性.

表7 22101次列車車流在站停留時(shí)間Table 7 Residence time of 22101 train’s wagon-flow

4 結(jié)論

將貨物運(yùn)到期限分配至編組站配流環(huán)節(jié)，保證車流在編組站的最大停留時(shí)限，能夠?qū)崿F(xiàn)在貨物運(yùn)輸主要環(huán)節(jié)上保障運(yùn)到期限.本文基于單解單編的編組站作業(yè)系統(tǒng)，構(gòu)建了調(diào)機(jī)運(yùn)用與配流綜合優(yōu)化的0-1整數(shù)規(guī)劃模型，設(shè)計(jì)了模擬退火算法求解模型，算例分析結(jié)果表明，本文基于運(yùn)到期限構(gòu)建的動(dòng)態(tài)配流模型及算法具有良好的有效性.本文考慮了貨物運(yùn)輸?shù)木幗M站作業(yè)環(huán)節(jié)，考慮貨物運(yùn)輸整個(gè)環(huán)節(jié)以保障運(yùn)到期限是本文的下一步研究方向.