基于資源可用度的編組站配流模型

薛 鋒，趙 蕾，楊麗蓉

(1.西南交通大學(xué)a.交通運(yùn)輸與物流學(xué)院，b.綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，成都610031；2.深圳市城市交通規(guī)劃設(shè)計(jì)研究中心有限公司，廣東深圳518021)

0 引 言

編組站作業(yè)計(jì)劃與執(zhí)行任務(wù)的資源之間存在映射關(guān)系，資源的安排使用具有計(jì)劃性.不同的資源，其歷史作業(yè)完成情況存在一定差異，在同等情況下，將作業(yè)交由可用度較高的資源執(zhí)行，能夠在較大程度上保障作業(yè)按時(shí)完成，縮小車(chē)站因單項(xiàng)作業(yè)未完成造成的生產(chǎn)延誤傳播范圍，從而提高作業(yè)計(jì)劃的兌現(xiàn)率.

國(guó)內(nèi)外對(duì)于編組站資源利用及配流優(yōu)化問(wèn)題的研究比較豐富.在編組站資源利用方面，陳亞男[1]確定編組站固定設(shè)施能力協(xié)調(diào)評(píng)價(jià)指標(biāo)，并構(gòu)建了編組站固定設(shè)施能力協(xié)調(diào)評(píng)價(jià)模型；康健等[2]提出一種基于資源可用度的集群作業(yè)調(diào)度算法，為編組站資源的利用提供了很好的借鑒；國(guó)外在解決編組站列車(chē)改編或排序時(shí)，通常將各資源視作約束，轉(zhuǎn)化為數(shù)學(xué)問(wèn)題進(jìn)行求解[3-4].在編組站配流方面，王慈光[5]將編組站配流問(wèn)題轉(zhuǎn)化為運(yùn)輸問(wèn)題，建立了靜態(tài)配流問(wèn)題的網(wǎng)絡(luò)模型并進(jìn)行求解；薛鋒等[6]在定義配流時(shí)間間隔和有效交換配流列車(chē)等概念，建立了雙向編組站靜態(tài)配流的雙層多目標(biāo)決策模型，并用禁忌搜索算法進(jìn)行求解；趙軍[7]將調(diào)度任務(wù)問(wèn)題轉(zhuǎn)換為運(yùn)輸指派問(wèn)題，并在此基礎(chǔ)上設(shè)計(jì)了新的模型；郭瑞等[8]主要分析了單向的單推單溜配流模型，并構(gòu)建了以各出發(fā)列車(chē)獲取最多車(chē)流為目標(biāo)的多階段配流推理算法.

上述關(guān)于編組站資源的研究主要從編組站能力查定、設(shè)施設(shè)備能力評(píng)價(jià)方面進(jìn)行分析，很少涉及到編組站資源的可用性度量，而在編組站配流優(yōu)化方面，又缺乏基于資源可用度視角的研究.本文從編組站資源可用性度量入手，以編組站整體資源可用度最大為目標(biāo)，建立基于資源可用度的配流模型，并進(jìn)行驗(yàn)證分析.

1 編組站資源可用度計(jì)算方法

編組站實(shí)體資源可劃分為到達(dá)系統(tǒng)資源、解體系統(tǒng)資源、車(chē)流集結(jié)系統(tǒng)資源、編組系統(tǒng)資源和發(fā)車(chē)系統(tǒng)資源.資源x在t時(shí)段的資源可用度A(x)t計(jì)算公式為

式中：A′(x)t為t時(shí)間段內(nèi)資源x的可信度[9].

式中：pyw為歷史統(tǒng)計(jì)得到的資源x執(zhí)行作業(yè)延誤率；為t時(shí)間段內(nèi)資源x由于車(chē)站按照施工計(jì)劃進(jìn)行施工被占用的時(shí)間；、t表示時(shí)段長(zhǎng)；為資源x被車(chē)站施工所占用的概率；為t時(shí)間段內(nèi)資源x由于故障而進(jìn)行緊急維修施工所占用的時(shí)間；Tx為資源x的預(yù)計(jì)使用年限；εt為t時(shí)間段內(nèi)資源使用情況在計(jì)算可信度時(shí)所占的比重；A′(x)t-1為t-1時(shí)間段內(nèi)資源x的可信度.

式(1)與式(2)中αt與εt為時(shí)變參數(shù)，據(jù)文獻(xiàn)[9]相關(guān)研究可知，αt與εt的計(jì)算方法為

A″(x)t為資源空閑度，表示資源x在t時(shí)間段內(nèi)處于空閑狀態(tài)的時(shí)間比例，計(jì)算公式為

式中：nt表示在時(shí)段t內(nèi)實(shí)際執(zhí)行的作業(yè)量；Nt表示時(shí)段t內(nèi)資源的理論最大作業(yè)能力.

在編組站資源可用度計(jì)算的過(guò)程中，據(jù)文獻(xiàn)[10]所述利用率法計(jì)算編組站到發(fā)場(chǎng)通過(guò)能力、駝峰解體能力和峰尾編組能力.

2 基于資源可用度的編組站配流模型構(gòu)建

充分考慮編組站到發(fā)線、駝峰、調(diào)車(chē)機(jī)車(chē)等各種設(shè)施設(shè)備資源在不同時(shí)段的工作強(qiáng)度，得到各設(shè)施設(shè)備在不同時(shí)段的動(dòng)態(tài)可用度，在此基礎(chǔ)上，確定編組站配流方案.

2.1 模型目標(biāo)函數(shù)

根據(jù)編組站階段計(jì)劃配流問(wèn)題的實(shí)際情況，配流模型的優(yōu)化目標(biāo)設(shè)置為以下3個(gè)：

(1)配流成功的自編始發(fā)列車(chē)等級(jí)權(quán)重之和最大[11]；

(2)車(chē)流在編組站的平均停留時(shí)間最少[12]；

(3)優(yōu)先使用可用度較大的資源.

根據(jù)上述思路設(shè)置目標(biāo)函數(shù)為式(6)～式(8).

式中：Aij為系統(tǒng)i內(nèi)并聯(lián)資源j在階段內(nèi)的可用度；nj為階段內(nèi)系統(tǒng)i中可用度最小的一類(lèi)資源的總量；nQ表示解體系統(tǒng)和編組系統(tǒng).

單個(gè)資源j在階段內(nèi)可用度Aj的計(jì)算公式為

2.2 模型的約束條件

在編組站配流過(guò)程中，需要考慮的約束關(guān)系主要包括作業(yè)先后次序、作業(yè)規(guī)定、作業(yè)時(shí)間等.

(1)作業(yè)次序約束.

到達(dá)列車(chē)技術(shù)作業(yè)與解體作業(yè)和解體調(diào)機(jī)之間占用關(guān)系約束為

出發(fā)列車(chē)技術(shù)作業(yè)與編組作業(yè)及編組調(diào)機(jī)之前占用關(guān)系約束為

(2)作業(yè)時(shí)間約束.

列車(chē)的出發(fā)時(shí)間tfj應(yīng)晚于出發(fā)技術(shù)作業(yè)結(jié)束時(shí)間，約束為

(3)各類(lèi)資源的約束.

編組站配流屬于資源限制的動(dòng)態(tài)調(diào)度問(wèn)題，調(diào)機(jī)、技術(shù)作業(yè)人員等為總量已知的固定資源，車(chē)流為總量未知的動(dòng)態(tài)資源，因而存在解體調(diào)機(jī)、編組調(diào)機(jī)等資源約束.

式(20)表示在任意時(shí)間，被作業(yè)占用的作業(yè)系統(tǒng)數(shù)不超過(guò)作業(yè)系統(tǒng)的總量，單個(gè)作業(yè)系統(tǒng)只能最多被1項(xiàng)作業(yè)占用.

車(chē)流存量約束為

(4)其他邏輯約束.

當(dāng)?shù)竭_(dá)列車(chē)解體作業(yè)、出發(fā)列車(chē)編組作業(yè)實(shí)施，且滿(mǎn)足車(chē)站編組的車(chē)流去向規(guī)定時(shí)，才能實(shí)現(xiàn)車(chē)流的接續(xù)，存在約束為

若列車(chē)fj可編入車(chē)流組號(hào)為k的車(chē)流資源，取=1；反之，取0.

列車(chē)軸重或換長(zhǎng)應(yīng)在《站細(xì)》規(guī)定的范圍內(nèi)，存在約束為

式中：zfj為列車(chē)fj的換長(zhǎng)或軸重要求，當(dāng)列車(chē)存在不同軸重或換長(zhǎng)情況時(shí)，存在區(qū)間，表示軸重或換長(zhǎng)的上下限.

綜上所述，基于資源可用度的編組站配流模型的目標(biāo)函數(shù)為

約束如式(10)～式(26)所示.

2.3 模型求解

首先采用分解模型、分層求解方法來(lái)降低求解難度，對(duì)模型中的部分困難約束進(jìn)行處理，然后給出初始車(chē)流接續(xù)方案，并使用遺傳算法對(duì)模型中的解編作業(yè)次序和調(diào)機(jī)安排問(wèn)題進(jìn)行求解.具體求解思路如下.

(1)困難約束的處理.

將時(shí)間窗約束式(20)轉(zhuǎn)換為

通過(guò)轉(zhuǎn)換，γi與γj取值都為1時(shí)，Ti與Tj需至少相差Tij；γi與γj取值不都為1時(shí)，Ti與Tj之差無(wú)要求.

類(lèi)似地，對(duì)變量ζij進(jìn)行處理，即

當(dāng)列車(chē)di的編組完成時(shí)間早于列車(chē)fj的編組開(kāi)始時(shí)間時(shí)，通過(guò)式(31)計(jì)算可得ζij=1；反之，ζij=0，符合約束要求.

(2)模型的求解思路.

Step1 分層優(yōu)化，記目標(biāo)函數(shù)式(27)和式(28)為maxf1，minf2；以maxf1為目標(biāo)，得到初始配流解X0，記f1(X0)=obj(f0).

Step2 采用帶初始解的迭代算法求解思想，設(shè)X0為第2層優(yōu)化初始解，以minf2為目標(biāo)，增加約束f1(X)≥obj(f0)，求解得到X1，更新初始配流方案X0=X1.

Step3 根據(jù)Step2求解得初始配流方案X0，以minf2為適應(yīng)度函數(shù)，調(diào)用遺傳算法求解，確定可行調(diào)機(jī)運(yùn)用方案，記

Step4 如果obj(f0)=obj(f1)，初始可行解為[X0,X0′]；否則，轉(zhuǎn)Step1求解1個(gè)新的配流初始解X0，再重復(fù)Step2～Step4，直至得到初始可行解

Step5 鎖定調(diào)機(jī)作業(yè)時(shí)間，采用枚舉法搜索可行的調(diào)機(jī)使用方案，應(yīng)用分割檢驗(yàn)法縮減計(jì)算時(shí)間，得到解區(qū)域X″.

Step6 將X″帶入maxf3，從中選取最優(yōu)解為X?，得到模型最終解.

3 算例分析

選用文獻(xiàn)[11]中調(diào)車(chē)場(chǎng)存車(chē)信息、到達(dá)列車(chē)車(chē)流信息及自編始發(fā)列車(chē)車(chē)流信息進(jìn)行計(jì)算.某編組站采用雙推雙溜的解體方式，有2臺(tái)解體調(diào)機(jī)，3臺(tái)編組調(diào)機(jī)，調(diào)車(chē)場(chǎng)最大容車(chē)數(shù)為4 000輛，到達(dá)技術(shù)作業(yè)時(shí)間60 min，解體作業(yè)時(shí)間30 min，編組作業(yè)時(shí)間60 min，出發(fā)技術(shù)作業(yè)時(shí)間30 min.根據(jù)前文所述求解方法，確定各出發(fā)列車(chē)的車(chē)流來(lái)源如表1所示.

表1 出發(fā)列車(chē)車(chē)流來(lái)源Table 1 The traffic flow sources of departure train

設(shè)12:00-19:00解編調(diào)機(jī)期望維護(hù)時(shí)間如表2和3所示.

表2 解體調(diào)機(jī)維護(hù)計(jì)劃Table 2 The break-up shunting engine maintenance plan(min)

表3 編組調(diào)機(jī)維護(hù)計(jì)劃Table 3 The marshalling engine maintenance plan(min)

計(jì)算得到未考慮資源可用度的列車(chē)解體作業(yè)安排，以下簡(jiǎn)稱(chēng)為調(diào)整前解體計(jì)劃，如表4所示.同理，可得調(diào)整前列車(chē)編組計(jì)劃，如表5所示.

表4 調(diào)整前的到達(dá)列車(chē)解體計(jì)劃Table 4 The break-up plan of arrival train before adjustment

表5 調(diào)整前的出發(fā)列車(chē)編組計(jì)劃Table 5 The marshalling plan of departure train before adjustment

由表4和表5可以看出，未考慮資源可用度指標(biāo)時(shí)，無(wú)法滿(mǎn)足解編調(diào)機(jī)維護(hù)需要，如40281次列車(chē)于13:51開(kāi)始占用2號(hào)調(diào)機(jī)，于14:21釋放調(diào)機(jī)資源.

以車(chē)站階段內(nèi)整體資源可用度最大為作業(yè)資源調(diào)整的目標(biāo)，對(duì)各作業(yè)所占用的資源進(jìn)行調(diào)整.調(diào)整后的解編計(jì)劃如表6和表7所示.

調(diào)整前后解體和編組作業(yè)的調(diào)機(jī)使用發(fā)生了較大程度的變化，這主要是由于在調(diào)整后，解編調(diào)機(jī)的使用考慮了其在不同時(shí)段的可用度情況，調(diào)整前后解編系統(tǒng)資源可用度對(duì)比如圖1和圖2所示.

通過(guò)表6和表7中調(diào)整前后的解編調(diào)機(jī)安排與表2和表3所示調(diào)機(jī)期望維護(hù)時(shí)間可知，與調(diào)整前相比，調(diào)整后解編調(diào)機(jī)的使用安排在一定程度上考慮了解編調(diào)機(jī)的期望維護(hù)計(jì)劃，能夠在一定程度上提高解編作業(yè)完成的概率.由圖1和圖2可以看出，調(diào)整后解編系統(tǒng)資源可用度增幅均在5%以上；在時(shí)段3～8(14:00-20:00)內(nèi)，調(diào)整后編組系統(tǒng)的資源可用度與調(diào)整前相比均得到較大增加，該時(shí)段內(nèi)編組系統(tǒng)的資源可用度增幅約為18.9%，能夠在一定程度上提高解編計(jì)劃完成的概率.

表6 調(diào)整后到達(dá)列車(chē)解體調(diào)機(jī)安排Table 6 The break-up shunting engine plan of arrival train after adjustment

表7 調(diào)整后出發(fā)列車(chē)編組調(diào)機(jī)安排Table 7 The marshalling engine plan of departure train after adjustment

圖1 調(diào)整前后各時(shí)段解體系統(tǒng)資源可用度Fig.1 The resource availability of break-up system of before and after each period

圖2 調(diào)整前后各時(shí)段編組系統(tǒng)資源可用度Fig.2 The resource availability of marshalling system of before and after each period

4 結(jié) 論

本文考慮編組站資源可用度，并以編組站整體資源可用度最大為目標(biāo)之一，建立了基于資源可用度的編組站配流模型，通過(guò)算例分析驗(yàn)證，可以得出：

(1)編組站實(shí)體資源在不同時(shí)段的可用性存在一定的差異，可根據(jù)編組站實(shí)體資源的歷史作業(yè)狀態(tài)計(jì)算資源的可用度.

(2)將編組站作業(yè)交由可用度較高的資源執(zhí)行，能夠在一定程度上增大作業(yè)按計(jì)劃完成的概率.

(3)通過(guò)模型的優(yōu)化，能夠在一定程度上根據(jù)資源不同時(shí)段的期望維護(hù)計(jì)劃對(duì)作業(yè)占用的資源進(jìn)行一定的調(diào)整，將編組站作業(yè)交由可用度較高的資源執(zhí)行，提高編組站整體資源的可用度.實(shí)例分析表明.調(diào)整后解編系統(tǒng)資源可用度增幅均在5%以上，編組系統(tǒng)資源可用度的改善更加明顯，在一定程度上提高了解編計(jì)劃完成的概率.