金啟明，李菲菲，劉林忠，張長(zhǎng)澤

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

0 引言

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

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

1 優(yōu)化模型

1.1 問(wèn)題假設(shè)

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

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

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

4）各車(chē)組在貨物作業(yè)點(diǎn)的作業(yè)完畢時(shí)刻為已知；

5）階段計(jì)劃開(kāi)始時(shí)各專(zhuān)用線(xiàn)的剩余容車(chē)空位數(shù)已知；

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

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

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

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

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

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

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

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

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

圖1 某初始取送批次方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.2 算法步驟描述

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

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

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

Step4 若Xnext 的評(píng)價(jià)值優(yōu)于Xbest 的評(píng)價(jià)值，令Xbest=Xnext。

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

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

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

3 算例仿真

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

圖1 某車(chē)站專(zhuān)用線(xiàn)布置示意圖

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

表2 各專(zhuān)用線(xiàn)在階段計(jì)劃開(kāi)始時(shí)的剩余容車(chē)位

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

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

4 結(jié)論

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

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