基于階段計(jì)劃的取送車調(diào)車作業(yè)計(jì)劃編制優(yōu)化研究

郭垂江

(成都信息工程大學(xué) 物流學(xué)院，四川 成都 610103)

車站階段計(jì)劃是班計(jì)劃分階段3 h或4 h的工作安排，由車站調(diào)度員編制。取送調(diào)車作業(yè)計(jì)劃是根據(jù)階段計(jì)劃安排取送車順序和整個作業(yè)的起止時間，由調(diào)車領(lǐng)導(dǎo)人根據(jù)調(diào)車場內(nèi)待送車輛和裝卸地點(diǎn)待取車輛停留情況進(jìn)行編制。

階段計(jì)劃編制過程中，本階段所必須完成的取送車作業(yè)的車組及車數(shù)可在制定列車配流計(jì)劃時確定，取送車調(diào)車作業(yè)計(jì)劃確定本階段的取送作業(yè)批次、順序、每批作業(yè)的開始時間和延續(xù)時間。不同的取送作業(yè)批次劃分、不同的批次開始作業(yè)時間及批次內(nèi)不同的取送車順序，將會影響配流計(jì)劃的最終實(shí)現(xiàn)。

一批取送調(diào)車作業(yè)是指調(diào)車機(jī)車(以下簡稱調(diào)機(jī))從調(diào)車場(車站)出發(fā)，往相關(guān)貨物作業(yè)點(diǎn)進(jìn)行取、送、調(diào)移作業(yè)后，返回調(diào)車場(車站)的技術(shù)作業(yè)過程。按照實(shí)際作業(yè)內(nèi)容的不同，一批取送車作業(yè)可分為單一送車、單一取車、送取結(jié)合、送兼調(diào)移、取兼調(diào)移、送調(diào)取結(jié)合6種作業(yè)形式。相應(yīng)地，具體的貨物作業(yè)點(diǎn)作業(yè)有取車、送車、連送帶取3種作業(yè)形式。雙重貨物作業(yè)車完成一次貨物作業(yè)的平均貨車停留時間比一次貨物作業(yè)車短，車站應(yīng)盡量利用本站卸空后的空車裝車，以加速車輛周轉(zhuǎn)，因此存在車組從卸車作業(yè)點(diǎn)調(diào)移至相應(yīng)的裝車作業(yè)點(diǎn)的調(diào)移作業(yè)。

針對樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)問題，石紅國等[1]認(rèn)為樹枝形專用線取送車問題是一個求解哈密爾頓最短回路問題，分別對專用線節(jié)點(diǎn)較少和節(jié)點(diǎn)較多的兩種情況下近似求解問題進(jìn)行了研究。黃向榮[2]同樣將其轉(zhuǎn)化為求哈密爾頓最短回路問題, 利用精確算法——最小生成樹算法進(jìn)行求解。雷友誠等[3]建立了大型企業(yè)樹枝形專用線的取送車作業(yè)問題的數(shù)學(xué)模型，利用遺傳蟻群算法(GACA)進(jìn)行求解，并將其與標(biāo)準(zhǔn)蟻群算法(ACA)進(jìn)行比較。李斌等[4]把取送車問題的順序、時間和批次作為一個系統(tǒng)進(jìn)行優(yōu)化，建立適用于多種作業(yè)方式，考慮了調(diào)機(jī)的牽引能力和裝卸區(qū)的容車能力約束的數(shù)學(xué)模型，并提出遺傳蟻群算法求解該取送車優(yōu)化問題。郭垂江等[5-8]將樹枝形專用線取送車順序確定問題轉(zhuǎn)化為求解哈密爾頓最短回路問題，分別利用動態(tài)規(guī)劃算法、C-W節(jié)約改進(jìn)算法、破圈連接法、模擬退火算法求解最優(yōu)解或滿意解。

取送車系統(tǒng)是鐵路車站調(diào)度系統(tǒng)中一個子系統(tǒng)，它與車站其他作業(yè)系統(tǒng)聯(lián)系緊密，孤立地對該系統(tǒng)進(jìn)行理論研究難以取得具有較高應(yīng)用價值的成果。本文從整個車站作業(yè)計(jì)劃編制系統(tǒng)角度研究取送車調(diào)車作業(yè)計(jì)劃編制問題，以完成階段內(nèi)所有批次取送車作業(yè)所耗的時間最小為優(yōu)化目標(biāo)，考慮貨物作業(yè)的車組的最遲返回車站時間約束、解體時刻約束、批次開始時刻約束、調(diào)機(jī)能力約束和調(diào)移作業(yè)所要求的調(diào)機(jī)訪問優(yōu)先權(quán)等約束，建立了基于階段計(jì)劃的取送車調(diào)車作業(yè)計(jì)劃編制優(yōu)化模型，運(yùn)用改進(jìn)的禁忌搜索算法確定滿意的取送車作業(yè)順序、批次劃分及取送時間，研究成果有助于編制更加實(shí)用的取送車調(diào)車機(jī)車運(yùn)用計(jì)劃，為車站綜合自動化系統(tǒng)的作業(yè)計(jì)劃智能編制提供理論支持。

1 研究假設(shè)

由于鐵路車站作業(yè)場景比較復(fù)雜，本文研究是在以下假設(shè)條件下進(jìn)行的：

(1)車站所銜接的貨物裝卸地點(diǎn)呈樹枝形分布。

(2)由1臺調(diào)車機(jī)車負(fù)責(zé)車站的取送車作業(yè)。

(3)調(diào)車機(jī)車在各貨物作業(yè)點(diǎn)(車站)間的走行時間已知。

(4)所有車組所接續(xù)的出發(fā)列車及編組開始時刻在階段計(jì)劃中已確定。

(5)所有車組解體到相應(yīng)調(diào)車線的時刻已確定。

(6)各貨物作業(yè)點(diǎn)在階段內(nèi)需取送的車組及車輛數(shù)在階段計(jì)劃中已確定。

2 符合說明

(1)參數(shù)符號

(2)變量符號

3 目標(biāo)函數(shù)

每批調(diào)機(jī)取送車時間是指每批作業(yè)時，調(diào)機(jī)離開調(diào)車場(車站)起，至完成該批取送作業(yè)任務(wù)后返回調(diào)車場(車站)止所延續(xù)的時間，而調(diào)機(jī)取送車總時間為階段內(nèi)所有批次調(diào)機(jī)取送車時間之和。所有批次調(diào)機(jī)取送車總時間越少，意味著調(diào)機(jī)作業(yè)效率越高，在階段內(nèi)作業(yè)批次間有更多的時間間隔進(jìn)行休整或進(jìn)行其他調(diào)車活動，因此本文以調(diào)車機(jī)車完成階段內(nèi)所有批次取送調(diào)車作業(yè)任務(wù)的取送車作業(yè)總時間最小為優(yōu)化目標(biāo)。調(diào)機(jī)取送車作業(yè)總時間由調(diào)機(jī)在貨物作業(yè)點(diǎn)(調(diào)車場或車站)間的走行時間和調(diào)機(jī)到達(dá)貨物作業(yè)點(diǎn)時由于車輛未裝卸完畢需等待的時間組成。優(yōu)化目標(biāo)為

(1)

4 約束條件

4.1 車流接束時間約束

因貨物作業(yè)點(diǎn)呈樹枝形分布，所以每批貨物作業(yè)的車組取回時刻是相同的，不管車組集中出發(fā)還是分散出發(fā)，都需滿足所有車組的最晚出發(fā)時刻，否則將會影響相應(yīng)列車的正點(diǎn)出發(fā)。因此要求該批作業(yè)的取回時刻須不大于該批所有車組的編組開始時刻，即

(2)

4.2 可選擇車組時間約束

一批作業(yè)可選擇送往貨物作業(yè)點(diǎn)的車組只能從送車前已經(jīng)在調(diào)車場(車站)集結(jié)的車輛中選擇。每批含有送車的取送車作業(yè)開始時刻須大于送車組的解體完畢時刻，即

(3)

4.3 批次開始時刻約束

一批取送車作業(yè)的開始時刻不能早于上一批次的取送車完畢調(diào)機(jī)返回調(diào)車場(車站)的時刻，第1批取送車作業(yè)開始時刻不能早于本階段開始時刻，即

(4)

(5)

4.4 機(jī)車牽引重量約束

取送車作業(yè)受調(diào)機(jī)牽引能力的限制，每一批調(diào)車作業(yè)過程中調(diào)機(jī)所連掛的車輛數(shù)不能超過其最大牽引能力,即

(6)

4.5 調(diào)移作業(yè)優(yōu)先權(quán)約束

假如階段計(jì)劃內(nèi)取送車作業(yè)中存在調(diào)移作業(yè)，則調(diào)機(jī)必須首先訪問卸車作業(yè)點(diǎn)取出空車，再送往相應(yīng)的裝車作業(yè)點(diǎn)進(jìn)行裝車，所以存在調(diào)機(jī)訪問這2個作業(yè)點(diǎn)先后順序的約束，即

(7)

(8)

(9)

5 求解方法

求解基于階段計(jì)劃的取送車調(diào)車作業(yè)計(jì)劃編制優(yōu)化模型的重點(diǎn)和難點(diǎn)在于尋找最優(yōu)的取送作業(yè)的作業(yè)順序及批次。將階段計(jì)劃內(nèi)所有作業(yè)涉及的車組視為一個整體時，取送車作業(yè)的完整方案包含1個取送車作業(yè)順序方案和1個取送車作業(yè)批次劃分方案。顯然，貨物作業(yè)點(diǎn)數(shù)為n的取送車作業(yè)問題對應(yīng)n!個取送車作業(yè)順序方案，1個取送車作業(yè)順序方案又對應(yīng)2n-1個取送車作業(yè)批次方案。因此，貨物作業(yè)點(diǎn)數(shù)為n的取送車作業(yè)問題實(shí)際上擁有n!×2n-1個完整的取送車作業(yè)方案(無論方案是否可行)。另一方面，哈密爾頓圖最短回路問題是NP問題，樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案問題是具有特殊形式的哈密爾頓圖最短回路問題，按照問題的歸約關(guān)系，取送車作業(yè)方案優(yōu)化問題也應(yīng)是NP問題，因此必須采用高效的啟發(fā)式算法求解，以在可接受的時間內(nèi)得到滿意解或最優(yōu)解[9-11]。

本文采用以下思路進(jìn)行求解：首先按照初始解的構(gòu)造規(guī)則產(chǎn)生滿足調(diào)移作業(yè)貨物作業(yè)點(diǎn)優(yōu)先關(guān)系的初始取送車順序和批次劃分；然后應(yīng)用禁忌搜索算法和文獻(xiàn)[6]所述的啟發(fā)式算法對取送車順序和批次劃分進(jìn)行循環(huán)優(yōu)化，得到滿意的取送車順序、批次劃分和開始時刻[12-18]。

(1)禁忌搜索算法求解思路

利用禁忌搜索算法求解樹枝形貨物作業(yè)點(diǎn)基于階段計(jì)劃的取送車調(diào)車作業(yè)計(jì)劃編制優(yōu)化模型的實(shí)現(xiàn)步驟為:

Step1選取一個初始解Snow并計(jì)算相應(yīng)的評價值f(Snow)；令禁忌表H=?。

Step2若滿足終止準(zhǔn)則，轉(zhuǎn)Step 4；否則，在Snow的鄰域N(Snow)中選出滿足禁忌要求的候選集，轉(zhuǎn)Step 3。

Step4輸出計(jì)算結(jié)果，停止。

各車組最早可能取送時刻si為

(10)

(2)初始解的構(gòu)造

首先將一日時間轉(zhuǎn)化為[0,1 440]中的數(shù)字，按照以下規(guī)則產(chǎn)生模型的初始解：

① 根據(jù)式(10)計(jì)算得到各項(xiàng)取送車作業(yè)的si值，按si值從小到大對階段計(jì)劃所涉及的貨物作業(yè)點(diǎn)進(jìn)行排序，若幾個貨物作業(yè)點(diǎn)的si值相同，就按照車組的數(shù)量的從大到小進(jìn)行排序。

② 調(diào)移作業(yè)點(diǎn)對遵循卸車作業(yè)點(diǎn)未訪問前裝車作業(yè)點(diǎn)不訪問的原則進(jìn)行排序。

這樣就得到了一個能完成階段計(jì)劃規(guī)定的取送車作業(yè)且滿足式(7)的貨物作業(yè)點(diǎn)全排列，并將每項(xiàng)取送作業(yè)單獨(dú)設(shè)定為1個取送車作業(yè)批次，即初始批次數(shù)m=n，這樣，可得到一個滿足式(7)的初始解。

(3)鄰域的構(gòu)造方法

可隨機(jī)采用以下規(guī)則構(gòu)造鄰域解：

① 調(diào)移作業(yè)的卸車點(diǎn)、裝車點(diǎn)前后跨批次移動

如圖1(a)所示，階段計(jì)劃要求將作業(yè)點(diǎn)的車輛調(diào)移至作業(yè)點(diǎn)。保持裝車點(diǎn)的所在批次和位置不變，在目前解中可將卸車點(diǎn)的位置插入到裝車點(diǎn)所在位置前任何位置。如位置插入到v8前，則隨機(jī)將v2、v0一起插入到v8之前得圖1(b)所示的解；隨機(jī)將v2、v0一起插入到v8之后得圖1(c)所示的解。再保持卸車點(diǎn)v2的所在位置和批次不變，在目前解中可將作業(yè)點(diǎn)v4插入到卸車點(diǎn)v2所在位置后的任何位置，圖2(a) 表示將作業(yè)點(diǎn)v4插入到v9前，則隨機(jī)將v4、v0一起插入到v9之前得圖2(b)所示的解，隨機(jī)將v4、v0一起插入到v9之后得圖2(c)所示的解。最后運(yùn)用文獻(xiàn)[6]的啟發(fā)式算法對每個批次內(nèi)的貨物作業(yè)點(diǎn)順序進(jìn)行優(yōu)化，從而得到1個新的鄰域解。

圖1 卸車點(diǎn)位置前后移動圖

圖2 裝車點(diǎn)位置前后移動圖

② 非調(diào)移作業(yè)的貨物作業(yè)點(diǎn)前后跨批次移動

如圖3(a)所示，貨物作業(yè)點(diǎn)v6為非調(diào)移作業(yè)的貨物作業(yè)點(diǎn)，可將其移至其他任何一個位置，如將貨物作業(yè)點(diǎn)v6插入作業(yè)點(diǎn)v10前，則將v6、v0一起插入到v10之前得如圖3(b)所示的解，將v6、v0一起插入到v10之后得圖3(c)所示的解。最后運(yùn)用文獻(xiàn)[6]的啟發(fā)式算法對每個批次內(nèi)的貨物作業(yè)點(diǎn)順序進(jìn)行優(yōu)化，即可得到1個新的鄰域解。

圖3 非調(diào)移貨物作業(yè)點(diǎn)位置前后移動

③ 2-交換

如圖4所示，v6和v7為任意2個貨物作業(yè)點(diǎn)，若點(diǎn)v6和v7為非調(diào)移作業(yè)的貨物作業(yè)點(diǎn)，可交換v6和v7的位置和所在批次，再運(yùn)用文獻(xiàn)[6]的啟發(fā)式算法對每個批次內(nèi)的貨物作業(yè)點(diǎn)順序進(jìn)行優(yōu)化，即可得到1個新的鄰域解。

圖4 解2-交換圖

解的評價可把約束條件式(6)轉(zhuǎn)化成懲罰函數(shù)，再把目標(biāo)函數(shù)式與懲罰函數(shù)累積起來作為解的評價函數(shù)f(S)，即

(11)

式中：M為足夠大的正數(shù)。

(4)迭代終止準(zhǔn)則

迭代終止準(zhǔn)則采用最大迭代步數(shù)Lmax，當(dāng)?shù)綌?shù)達(dá)到Lmax時，輸出滿意的取送車順序、批次劃分和起止時間等。

(5)禁忌對象的確定

禁忌對象是指禁忌表中被禁的局部最優(yōu)解，本文將每次迭代得到的最好解作為禁忌對象放入禁忌表中。

(6)禁忌長度的確定

禁忌長度是指被禁對象不允許被選取的迭代步數(shù)，本文取禁忌長度為一個常數(shù)。

(7)候選集合的確定

本文將從當(dāng)前解的鄰域中隨機(jī)選擇若干個鄰居作為候選集合。

6 算例分析

某鐵路技術(shù)站貨物作業(yè)點(diǎn)布置情況如圖5所示，w1,w2,…,w9為道岔岔心；v0為調(diào)車場；v1,…,v10為貨物作業(yè)點(diǎn)，數(shù)字為各點(diǎn)(調(diào)車場、道岔岔心、作業(yè)點(diǎn))間的機(jī)車走行時間。設(shè)tvi,vi′=0，這樣可保證連送帶取貨物作業(yè)不另產(chǎn)生調(diào)機(jī)走行時間。

圖5 某鐵路技術(shù)站貨物作業(yè)點(diǎn)布置示意圖

某工作日0:00至03:00間階段計(jì)劃內(nèi)取送車作業(yè)的貨物作業(yè)點(diǎn)、車數(shù)、解體完畢時刻、裝卸完畢時刻、編組開始時刻等數(shù)據(jù)見表1，需進(jìn)行的調(diào)移任務(wù)為：貨物作業(yè)點(diǎn)v3需調(diào)移3輛至v6，貨物作業(yè)點(diǎn)v5需調(diào)移2輛至v7。調(diào)機(jī)最大牽引輛數(shù)為25輛。制定本階段內(nèi)合理的取送車作業(yè)的順序、批次及其起止時間。

表1 某工作日00:00至03:00間取送調(diào)車作業(yè)內(nèi)容

表2 滿意解的時間指標(biāo)

(1)不同的禁忌長度條件下解的比較

保持其他參數(shù)值不變，采用不同的禁忌長度對以上算例進(jìn)行多次測試，得到的算法平均運(yùn)行時間和調(diào)機(jī)總作業(yè)時間比較見表3。

表3 不同的禁忌長度條件下解的比較

由表3可知，不同的禁忌長度參數(shù)設(shè)置對運(yùn)行時間影響不大?？傮w來說禁忌長度越長，所花費(fèi)的運(yùn)行時間越長，可能是搜索可行解難度增大的原因。不同的禁忌長度參數(shù)設(shè)置對得到的滿意解質(zhì)量有一定影響，禁忌長度越長，所得到的解質(zhì)量越高，但禁忌長度設(shè)置為比25更大的數(shù)值時，最終解的質(zhì)量提升不大。

(2)不同的最大迭代步數(shù)條件下解的比較

保持其他參數(shù)值不變，采用不同的最大迭代步數(shù)對算例進(jìn)行多次測試，得到的算法平均運(yùn)行時間和調(diào)機(jī)總作業(yè)時間比較見表4。

表4 不同的最大迭代步數(shù)條件下解的比較

由表4可知，所設(shè)置的最大迭代步數(shù)越大，所得到的解質(zhì)量也越高，但算法運(yùn)行時間越長。設(shè)置45步以上的迭代步數(shù)對最終解的質(zhì)量影響不大，可認(rèn)為算法已基本收斂。

在鐵路實(shí)際生產(chǎn)中，調(diào)機(jī)階段內(nèi)所承擔(dān)取送調(diào)車任務(wù)的作業(yè)點(diǎn)數(shù)量一般不是很大，所以以上案例具有一定的代表性。通過對以上案例進(jìn)行測試，計(jì)算時間也可控制在合理范圍之內(nèi)，因此本文所建立的模型和設(shè)計(jì)的算法是可行和有效的。

7 結(jié)論

本文針對階段內(nèi)取送車調(diào)車作業(yè)計(jì)劃編制問題，以調(diào)車機(jī)車總走行時間最小為優(yōu)化目標(biāo)，綜合考慮了每批作業(yè)最晚必須返回車站時刻、車組解體完畢時刻、批次開始時刻、調(diào)機(jī)最大編掛能力和調(diào)移作業(yè)所要求的調(diào)機(jī)訪問優(yōu)先權(quán)約束，全面地描述了鐵路車站樹枝形貨物作業(yè)點(diǎn)的取送車方案問題實(shí)質(zhì)，建立了基于階段計(jì)劃的樹枝形貨物作業(yè)點(diǎn)取送車調(diào)車作業(yè)計(jì)劃的優(yōu)化模型，以禁忌搜索算法為求解主框架進(jìn)行求解。案例驗(yàn)證表明，所建立的模型和設(shè)計(jì)的算法是可行的和有效的，遵循結(jié)合階段計(jì)劃編制取送車調(diào)車作業(yè)計(jì)劃的思路能使階段計(jì)劃更有應(yīng)用價值。下一步將考慮不同貨物作業(yè)點(diǎn)布置形式、裝卸點(diǎn)作業(yè)容量、多取送調(diào)車機(jī)車等作業(yè)場景進(jìn)行深入研究，以適應(yīng)現(xiàn)場復(fù)雜的設(shè)備特點(diǎn)和作業(yè)組織形式。