李晟東，徐長安，呂紅霞*,c，李文新

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

0 引 言

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

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

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

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

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

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

1.1 建模分析

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

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

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

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

(2)約束條件.

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

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

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

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

1.2 模型假設(shè)

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

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

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

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

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

1.3 符號說明

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

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

1.4 優(yōu)化模型

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

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

2 算法設(shè)計

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

模型所求目標(biāo)包括列車解編順序和出發(fā)列車車流來源，可視為雙層結(jié)構(gòu)，同時，不合理的列車解編順序下，不一定產(chǎn)生可行的配流方案.因此模型求解思路為：上層結(jié)構(gòu)通過一定的準(zhǔn)則得到合理的列車解編順序，并作為已知條件輸入下層結(jié)構(gòu)以求解出發(fā)列車車流來源，此時模型的解編順序已定，可調(diào)用CPLEX求解出發(fā)列車車流來源，即得到1個配流方案，通過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時，M的該位置取值為1，否則為0.則約束矩陣M某一列的和mj表示對應(yīng)出發(fā)列車j最大可配入貨車數(shù)量，為每一mj設(shè)定閾值[aj,bj]，當(dāng)所有mj滿足閾值要求，即M滿足閾值要求時，則得到合理解編順序.

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

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

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

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

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

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

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

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

3 算例分析

某二級三場編組站解體、編組調(diào)機均為1臺，列車到達(dá)作業(yè)時間為30 min，出發(fā)作業(yè)時間為30 min，解體作業(yè)時間為15 min，編組作業(yè)時間為15 min.到達(dá)車流信息如表1所，出發(fā)車流信息如表2所示，車流運到期限信息(由于篇幅原因，僅列舉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的個人計算機上，采用Matlab2016a編程，經(jīng)過多組參數(shù)實驗，在初始溫度為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á)列車的解體順序為{1,2,3,4,6,5,8,7,10,9,11,12}，出發(fā)列車的編組順序為{2,3,1,4,5,6,8,7,-,9,10,11}，其中41006次列車因為車流接續(xù)不足而停運，同時所有車流實際在站停留時間均未超過最大在站停留時間，如表7所示，從而驗證了本文模型及算法的有效性.

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

4 結(jié)論

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