樹枝形專用線取送車作業(yè)方案編制優(yōu)化研究

金啟明，李菲菲，劉林忠，張長澤

（蘭州交通大學(xué) 交通運輸學(xué)院，1、2、4 研究生，3 教授 博導(dǎo)，甘肅 蘭州 730070）

0 引言

樹枝形的專用線布置形式在我國鐵路運輸生產(chǎn)中十分常見，貨場和專用線統(tǒng)稱為貨物作業(yè)點（簡稱為作業(yè)點），關(guān)于樹枝形專用線取送車作業(yè)的優(yōu)化研究已有了一定的成果。唐春林等［1］在考慮調(diào)機(jī)牽引質(zhì)量條件下，建立了求解取送順序的優(yōu)化模型并使用蟻群混合模擬退火算法求解。郭垂江等［2-4］針對取送順序優(yōu)化建立了Hamilton 模型，并分別設(shè)計了相應(yīng)的求解算法。陳利君等［5］利用破圈法等圖論知識求解了優(yōu)化取送順序的哈密爾頓模型。完整的取送車作業(yè)方案包括取送批次、取送時機(jī)及取送順序，而上述文獻(xiàn)僅針對取送順序優(yōu)化進(jìn)行研究。李斌等［6］以求解取送批次方案和順序方案為目的，建立了連送帶取作業(yè)模式下的數(shù)學(xué)模型，但考慮到的取送作業(yè)模式較為單一。郭垂江［7］從車站作業(yè)計劃編制系統(tǒng)角度入手，建立基于階段計劃的取送車作業(yè)優(yōu)化模型，但模型沒有考慮到裝卸區(qū)容車能力約束以及調(diào)機(jī)在取送作業(yè)過程中所需要的各種單項作業(yè)時間，導(dǎo)致模型存在著一定程度的局限性。

鑒于現(xiàn)有研究中存在的問題，本文針對樹枝形專用線取送車作業(yè)方案的編制研究，建立了適用于各類取送作業(yè)模式下的統(tǒng)一模型，并提出了取送批次、取送時機(jī)及取送順序的的優(yōu)化方法。

1 優(yōu)化模型

1.1 問題假設(shè)

1）站內(nèi)僅配備一臺取送作業(yè)調(diào)機(jī)；

2）調(diào)機(jī)在各作業(yè)點間的走行耗時為已知；

3）階段計劃內(nèi)各貨物作業(yè)點取送車組的詳細(xì)信息為已知；

4）各車組在貨物作業(yè)點的作業(yè)完畢時刻為已知；

5）階段計劃開始時各專用線的剩余容車空位數(shù)已知；

6）所有待取車組在站內(nèi)的編組時刻已知。

1.2 符號說明定義的參數(shù)如下：N 為取送車作業(yè)有關(guān)的專用線集合，即N={v0，v1，...，vn-1，vn}，其中v0表示車站，n為專用線條數(shù)；N′為送車作業(yè)點集合；N″為取車作業(yè)點集合；Nj為第j批次的作業(yè)點集合；Nds為調(diào)移送車作業(yè)點集合；Ndq為調(diào)移取車作業(yè)點集合；vk、vk'分別為第k次調(diào)移作業(yè)所對應(yīng)的調(diào)移取車、調(diào)移送車作業(yè)點；RVK、RVK′分別為vk、vk'在取送順序方案中的位置。

1.3 數(shù)學(xué)模型由于階段計劃內(nèi)取送作業(yè)內(nèi)容復(fù)雜多樣，單一針對某種作業(yè)模式建立模型難以適用實際生產(chǎn)，故本文建立如下適用于各類取送作業(yè)的數(shù)學(xué)模型：

目標(biāo)函數(shù)Z 為階段計劃內(nèi)的總?cè)∷妥鳂I(yè)時間。式（1）為裝卸區(qū)容車能力約束；式（2）為調(diào)機(jī)牽引能力約束；式（3）表示當(dāng)有調(diào)移作業(yè)時，調(diào)機(jī)需先訪問調(diào)移取車作業(yè)點，后訪問其所對應(yīng)的調(diào)移送車作業(yè)點；式（4）表示每批作業(yè)結(jié)束時刻不能晚于該批次中所有取車車組最早編組時刻；式（5）表示批次開始時刻不得早于待送車組最晚解體完畢時刻；式（6）表示批次開始時刻不得早于前批作業(yè)結(jié)束時刻；式（7）表示首批次開始時刻不得早于該階段計劃的開始時刻。

2 取送車作業(yè)方案的尋優(yōu)方法

本文的尋優(yōu)思路如下：將取送批次劃分和取送作業(yè)順序同步優(yōu)化，然后確定各批次的最佳取送時機(jī)。

2.1 各車組最早允許取送作業(yè)時間ti對于車站（調(diào)車場）中的待送車組，最早可以進(jìn)行取送作業(yè)的時間ti 為該車組在車站（調(diào)車場）的解體完畢時刻；對于其他取送作業(yè)車組，最早可以進(jìn)行取送作業(yè)的時間ti為該車組在作業(yè)點的貨物作業(yè)完畢時刻。

2.2 取送批次優(yōu)化

1）構(gòu)造初始批次方案。將車組所對應(yīng)的作業(yè)點按最早允許的取送作業(yè)時間從小到大排列，含調(diào)移作業(yè)時排序要滿足式（3）約束。將每項取送作業(yè)單獨劃分為1 個批次，即批次數(shù)m 等于階段內(nèi)所有取送作業(yè)的數(shù)量，這樣既可得到一個滿足約束式（3）的初始批次方案。例如圖1 表示某階段內(nèi)包含6 項取送作業(yè)的初始批次方案。

圖1 某初始取送批次方案

2）取送批次優(yōu)化。批次優(yōu)化需在滿足約束條件式（2）與（4）的前提下，盡可能地減少批次數(shù)。本文設(shè)計了逐次合并的批次優(yōu)化方法，具體步驟簡述如下：

Step1初始化批次優(yōu)化計數(shù)器M=1。

Step2 若當(dāng)前已優(yōu)化完最后一個批次，轉(zhuǎn)Step4；否則判斷批次M 與批次M+1 中的作業(yè)是否滿足約束（2），若不滿足則將不滿足的批次移動至該作業(yè)點所對應(yīng)的取車作業(yè)批次之后，更新所有批次編號并重新進(jìn)行Step2；若批次M與批次M+1中的作業(yè)均滿足裝卸區(qū)容車能力約束則轉(zhuǎn)Step3。

Step3 將批次M 與批次M+1 合并（記為新的批次M），如果合并的兩個批次中含同一個作業(yè)點，則將該作業(yè)點合為一個作業(yè)點。對合并后的批次利用禁忌搜索優(yōu)化取送順序，判斷是否能夠滿足約束式（2）與（4），若滿足約束則保留新的批次與順序方案并重新進(jìn)行步驟Step2；否則不保留本次合并方案，令M=M+1并轉(zhuǎn)Step2。

Step4 批次優(yōu)化結(jié)束。

通過上述步驟劃分初始批次即可得到滿足約束條件式（1）、（2）、（4）的批次方案。

2.3 取送順序優(yōu)化

2.3.1禁忌搜索算法設(shè)計

1）解的形式。取送順序解的形式為一維數(shù)組序列，元素從左至右為調(diào)機(jī)依次訪問的作業(yè)點順序。

2）初始解。初始解為批次合并后的順序方案。

3）鄰域結(jié)構(gòu)與領(lǐng)域解。本文所采取的鄰域結(jié)構(gòu)是根據(jù)2-opt 定義的，即交換某兩個元素的相對位置，鄰域解的具體構(gòu)造規(guī)則如下：

對于無調(diào)移作業(yè)或調(diào)移作業(yè)點對不在同一批次的情況，可隨機(jī)挑選兩個非0 元素互換位置構(gòu)成新領(lǐng)域解。

對于調(diào)移作業(yè)點對在同一批次的情況，隨機(jī)挑選以下規(guī)則進(jìn)行鄰域解的構(gòu)造。

（1）調(diào)移取車作業(yè)點的移動：將調(diào)移取車作業(yè)點與其所對應(yīng)的調(diào)移送車作業(yè)前的某個元素交換位置。

（2）調(diào)移送車作業(yè)點的移動：將調(diào)移送車作業(yè)點與其所對應(yīng)的調(diào)移取車作業(yè)后的某個元素交換位置。

（3）非調(diào)移作業(yè)點的移動：隨機(jī)挑選兩個非調(diào)移作業(yè)點交換位置。

4）候選集：在生成的鄰域解中隨機(jī)選2nj 個滿足約束式（2）的解構(gòu)成候選集。

5）禁忌表H：禁忌表采用一維數(shù)組的形式對禁忌對象進(jìn)行存儲。

6）解的評價函數(shù)：本文以取送作業(yè)時間作為解的評價值。

7）禁忌長度l：文中各禁忌對象初始的l=2nj。當(dāng)某禁忌對象重復(fù)出現(xiàn)在禁忌表中時增加該禁忌對象的禁忌長度l 以避免陷入局部循環(huán)，每重復(fù)出現(xiàn)一次l增加2。

8）特赦規(guī)則：在迭代過程中遇到所有候選解均在禁忌表中時，選取禁忌表中評價值最好的解進(jìn)行解禁。

9）終止條件：本文以最大迭代次數(shù)3nj 作為算法的終止條件，當(dāng)?shù)螖?shù)達(dá)到3nj時算法停止迭代。

2.3.2 算法步驟描述

Step1 初始化禁忌表H 為空集；將初始解記為Xnext作為迭代的起點，令Xbest=Xnext。

Step2 根據(jù)Xnext 生成候選集，在候選集中挑選評價值最優(yōu)且不在H中的解記為Xnext。

Step3 將禁忌表中所有禁忌對象的禁忌長度減1，再將禁忌長度為0 的禁忌對象從H 中刪除，將Xnext加入到H中并賦予其新的禁忌長度。

Step4 若Xnext 的評價值優(yōu)于Xbest 的評價值，令Xbest=Xnext。

Step5 若當(dāng)前滿足終止條件則停止計算，輸出Xbest；否則返回Step2。

2.4 取送時機(jī)優(yōu)化本文提出臨時取送時機(jī)和最優(yōu)取送時機(jī)的概念：

通過利用本文所描述的取送批次、取送順序、取送時機(jī)的優(yōu)化方法，即可得到滿足模型中所有約束條件且取送作業(yè)總時間為最小的取送車作業(yè)方案。

3 算例仿真

某車站共有10 條專用線呈樹枝形布置，具體布置信息如圖2 所示。（圖中數(shù)字為調(diào)機(jī)的走行時間，單位min。階段內(nèi)需完成的取送車作業(yè)信息如表1所示，各專用線的剩余容車空位如表2 所示。Q=30，tt=3 min，td=4 min，ts=3 min，tf=2 min。試制定取送車作業(yè)方案，使總?cè)∷妥鳂I(yè)時間最小。

圖1 某車站專用線布置示意圖

表1 某日0:00至4:00間取送車作業(yè)信息

表2 各專用線在階段計劃開始時的剩余容車位

算 例 在Intel Xeon 3.40GHz 的PC 端，運 用Microsoft Visual C++編程進(jìn)行求解。運行程序求得的最佳結(jié)果見表3。從求得的結(jié)果可以看出該階段的取送作業(yè)共劃分為兩個批次：批次1 的開始時刻為0:08，結(jié)束時刻為1:40，作業(yè)持續(xù)了92 min；批次2的開始時刻為2:11，結(jié)束時刻為3:21，作業(yè)持續(xù)了70 min。階段計劃內(nèi)總的取送作業(yè)時間為162 min，程序共運行了10 次，最短運算時長為1.012 s，最長運算時長為1.547 s，平均運算時長1.3 s。通過仿真算例計算結(jié)果可看出：求得的取送作業(yè)方案符合題目要求，程序的運算時長可以接受。

表3 算例仿真結(jié)果

4 結(jié)論

1）與傳統(tǒng)模型相比，本文將取送批次、時機(jī)及順序綜合考慮進(jìn)行優(yōu)化，同時考慮了貨物作業(yè)點容車能力、調(diào)機(jī)牽引能力、每批取送作業(yè)最早開始時刻及最晚結(jié)束時刻等約束條件，并將調(diào)機(jī)在取送作業(yè)過程中產(chǎn)生的一些單項作業(yè)時間納入模型，使得所建立的模型更符合實際作業(yè)要求。

2）本文提出的尋優(yōu)算法能夠在合理的時間內(nèi)得到較優(yōu)的取送車作業(yè)方案，在保證完成取送任務(wù)前提下縮短調(diào)機(jī)取送作業(yè)時間，提高階段計劃內(nèi)的取送作業(yè)效率。