樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案的多目標(biāo)優(yōu)化模型及算法

郭垂江

(湖南鐵路科技職業(yè)技術(shù)學(xué)院 運(yùn)輸管理學(xué)院，湖南 株洲　412006)

車站是鐵路運(yùn)輸生產(chǎn)的基層單位，貨場(chǎng)和專用線是鐵路車站的貨物裝卸作業(yè)地點(diǎn)，可以統(tǒng)稱為貨物作業(yè)點(diǎn)，按其與車站的位置關(guān)系可分為放射形、樹枝形和混合形3類。合理安排調(diào)車機(jī)車(簡(jiǎn)稱為調(diào)機(jī))的取送作業(yè)順序，能使調(diào)機(jī)在最短的時(shí)間內(nèi)完成取送車作業(yè)，從而提高調(diào)機(jī)的使用效率，減少車輛的非作業(yè)等待時(shí)間。

對(duì)于樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案優(yōu)化問題的研究，一般做法是將其轉(zhuǎn)換成求解哈密爾頓圖最短回路問題，部分學(xué)者采用2—交換[1]、最小生成樹算法[2]、動(dòng)態(tài)規(guī)劃方法[3]得到最優(yōu)解，但計(jì)算過程比較復(fù)雜；部分學(xué)者采用遺傳算法[4]等現(xiàn)代智能算法進(jìn)行計(jì)算，得到問題的滿意解。樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)形式有單一取車、單一送車、送車兼調(diào)移車、取車兼調(diào)移車、取送車結(jié)合、送調(diào)取車結(jié)合等6種。目前絕大多數(shù)研究成果沒有把調(diào)移作業(yè)考慮到取送車作業(yè)中，因而所建立的模型難以適應(yīng)鐵路現(xiàn)場(chǎng)復(fù)雜的作業(yè)組織形式，從而影響模型及算法的實(shí)際應(yīng)用。文獻(xiàn)[5—6]認(rèn)為調(diào)移作業(yè)是調(diào)機(jī)訪問相應(yīng)貨物作業(yè)點(diǎn)必須滿足的優(yōu)先關(guān)系，從而將樹枝形專用線取送車作業(yè)優(yōu)化問題轉(zhuǎn)換成滿足所有優(yōu)先權(quán)關(guān)系的哈密爾頓最短回路問題，分別利用改進(jìn)破圈連接法和啟發(fā)式算法進(jìn)行求解，但僅以調(diào)機(jī)取送車總時(shí)間最小為優(yōu)化目標(biāo)，這在一定程度上也存在局限性。文獻(xiàn)[7]分別以調(diào)機(jī)取送車總時(shí)間、車輛的總?cè)刖€車輛小時(shí)和總走行車輛公里最小為優(yōu)化目標(biāo)，較好地反映了樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案優(yōu)化問題的實(shí)質(zhì)，但未對(duì)如何平衡這3個(gè)優(yōu)化目標(biāo)及如何將調(diào)移作業(yè)考慮到模型中做進(jìn)一步的研究。文獻(xiàn)[8]從順序和批次2個(gè)優(yōu)化維度建立了鐵路車站取送車作業(yè)問題一般模型，并提出了解的模塊化構(gòu)造方法，這雖為本問題的研究提供了新的思路，但其求解方法淡化了調(diào)機(jī)取送總時(shí)間最小的優(yōu)化目標(biāo)。

本文針對(duì)樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案的優(yōu)化問題，以調(diào)機(jī)前往相關(guān)貨物作業(yè)點(diǎn)完成1批取送車作業(yè)任務(wù)為背景，以調(diào)機(jī)取送總時(shí)間、車輛的總?cè)刖€車輛小時(shí)和總走行車輛公里的加權(quán)綜合值最小為優(yōu)化目標(biāo)，以調(diào)機(jī)所連掛的車輛數(shù)不能超過其最大牽引能力和調(diào)機(jī)訪問調(diào)移作業(yè)點(diǎn)的先后順序?yàn)榧s束條件，建立兼容6種作業(yè)形式的多目標(biāo)優(yōu)化模型，并將其轉(zhuǎn)化為單目標(biāo)優(yōu)化模型，運(yùn)用搜索能力強(qiáng)的模擬退火算法進(jìn)行求解，在可接受的時(shí)間范圍內(nèi)得到滿意的取送車作業(yè)方案。

1　符號(hào)說明

定義以下參數(shù)：v0為調(diào)車場(chǎng)(車站)；當(dāng)調(diào)機(jī)在所有作業(yè)點(diǎn)作業(yè)完畢返回調(diào)車場(chǎng)(車站)時(shí)，為便于計(jì)算機(jī)編程，此時(shí)調(diào)車場(chǎng)(車站)用vn+1表示。V={vi|i=1，2，…，n}為1批取送車作業(yè)涉及的貨物作業(yè)點(diǎn)的集合。v(h)為解中第h個(gè)位置的作業(yè)點(diǎn)。

dv(i),v(j)和tv(i),v(j)分別為按文獻(xiàn)[6]調(diào)整后的作業(yè)點(diǎn)vi與vj(vi,vj∈V)間的調(diào)機(jī)走行里程和調(diào)機(jī)走行時(shí)間。

2　多目標(biāo)優(yōu)化模型

2.1　基本假設(shè)

(1)1批取送車作業(yè)是指調(diào)機(jī)從調(diào)車場(chǎng)(車站)出發(fā)，經(jīng)過每個(gè)貨物作業(yè)點(diǎn)最多1次，最后返回調(diào)車場(chǎng)(車站)的整個(gè)作業(yè)過程。

(2)調(diào)車場(chǎng)(車站)只配備1臺(tái)調(diào)機(jī)負(fù)責(zé)取送車作業(yè)。

(3)各貨物作業(yè)點(diǎn)待送、待取車數(shù)在作業(yè)前已經(jīng)確定。

(4)各走行線的實(shí)際里程數(shù)、調(diào)機(jī)走行時(shí)間已知；調(diào)機(jī)附掛車輛數(shù)量的多少不影響調(diào)機(jī)在走行線的走行時(shí)間。

(5)調(diào)機(jī)將車組送至貨物作業(yè)點(diǎn)后即離開，不需等待其裝卸作業(yè)完畢后再離開。

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

1)調(diào)機(jī)取送車總時(shí)間最小

調(diào)機(jī)取送車總時(shí)間是指調(diào)機(jī)離開調(diào)車場(chǎng)(車站)時(shí)起，至完成取送作業(yè)任務(wù)后返回調(diào)車場(chǎng)(車站)時(shí)止所延續(xù)的時(shí)間。調(diào)機(jī)取送車總時(shí)間最小的優(yōu)化目標(biāo)函數(shù)z1可表示為

(1)

2)總?cè)刖€車輛小時(shí)最小

總?cè)刖€車輛小時(shí)是指完成1批取送車作業(yè)時(shí)，所有送車作業(yè)的車輛在入線前消耗的車輛小時(shí)之和?？?cè)刖€車輛小時(shí)越大，意味著車輛不能及時(shí)進(jìn)行對(duì)位，從而有可能影響裝卸作業(yè)和其他作業(yè)的及時(shí)進(jìn)行，因此，總?cè)刖€車輛小時(shí)的值越小越好。送車作業(yè)的車輛可分為2部分，第1部分是在調(diào)車場(chǎng)挑選的需送往各貨物作業(yè)點(diǎn)的車輛，第2部分是需要調(diào)移作業(yè)的車輛，即從卸車作業(yè)點(diǎn)取出后送往裝車作業(yè)點(diǎn)的車輛。

對(duì)于第1部分車輛，其總?cè)刖€車輛小時(shí)為

(2)

對(duì)于第2部分車輛，其總?cè)刖€輛車小時(shí)為

(3)

因此總?cè)刖€車輛小時(shí)最小優(yōu)化目標(biāo)函數(shù)z2為以上2部分車輛的入線車輛小時(shí)之和，即

(4)

3)總走行車輛公里最小

總走行車輛公里是指完成1批取送車作業(yè)時(shí)所有車輛的走行公里之和?？傋咝熊囕v公里越大，意味著將耗費(fèi)更多的調(diào)機(jī)動(dòng)力，也增大了調(diào)車作業(yè)的難度，可見，總走行車輛公里的值也越小越好。因此，總走行車輛公里最小優(yōu)化目標(biāo)函數(shù)z3為

(5)

設(shè)以上3個(gè)目標(biāo)的權(quán)重系數(shù)分別為α1，α2，α3；它們的取值區(qū)間均為[0，1]，且應(yīng)滿足α1+α2+α3=1。對(duì)于具體問題， 可采用多次實(shí)驗(yàn)的方法，在解比較穩(wěn)定區(qū)域內(nèi)選取合理的權(quán)重系數(shù)。由此可通過線性加權(quán)將樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。其目標(biāo)函數(shù)值z(mì)為

z=min(α1z1+α2z2+α3z3)

(6)

2.3　約束條件

1)調(diào)機(jī)牽引輛數(shù)約束

受調(diào)機(jī)牽引能力的限制，調(diào)機(jī)所連掛的車輛數(shù)不能超過其最大牽引輛數(shù)Q，即

(7)

2)調(diào)機(jī)訪問調(diào)移作業(yè)點(diǎn)先后順序的約束

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

(8)

3　模型求解算法

本文建立的優(yōu)化模型是一特殊的哈密爾頓圖最短回路問題的數(shù)學(xué)描述，屬于NP問題，采用模擬退火算法進(jìn)行求解[9-11]。

采用自然數(shù)作為解的編碼序列，例如某個(gè)解為0 1 3 2 4 5 7 6 8 10 9 11，表示調(diào)機(jī)從調(diào)車場(chǎng)(車站)出發(fā)，依次訪問作業(yè)點(diǎn)v1，v3，v2，v4，v5，v7，v6，v8，v10，v9，然后再返回調(diào)車場(chǎng)(車站)。

模擬退火算法對(duì)初始解的要求并不高，可任意構(gòu)造1個(gè)滿足調(diào)移優(yōu)先關(guān)系的解作為初始解。按照對(duì)任一調(diào)移對(duì)(vk,vk′)，在作業(yè)點(diǎn)vk未訪問前不訪問作業(yè)點(diǎn)vk′的原則，很容易得到初始可行解。

在開始時(shí)，退火過程的初始溫度必須足夠高，以確保系統(tǒng)能移動(dòng)到所有可能的狀態(tài)。

在特定溫度下，當(dāng)循環(huán)達(dá)到一定的上限，即馬爾科夫鏈長度L時(shí)，必須進(jìn)行降溫操作。采用的退火策略為指數(shù)降溫，即Tu=λTu-1(u=1,2,3,…)，其中Tu為第u次迭代時(shí)的溫度，λ為溫度下降率。因溫度的變化很有規(guī)律，并與參數(shù)λ直接相關(guān)，即在溫度高時(shí)溫度下降快，在溫度低時(shí)溫度下降變緩，因此很適合本文所研究的問題。

解的評(píng)價(jià)可將第1個(gè)約束條件式(7)轉(zhuǎn)化為懲罰函數(shù)，再將目標(biāo)函數(shù)式(6)與懲罰函數(shù)的累加之和作為解的評(píng)價(jià)函數(shù)f(S)。 設(shè)M為1個(gè)足夠大的正數(shù)，則調(diào)機(jī)牽引輛數(shù)約束的罰函數(shù)為

(9)

相應(yīng)地，解的評(píng)價(jià)函數(shù)為

f(S)=min(α1z1+α2z2+α3z3)+

pv(h))-Q, 0]

(10)

在保證滿足調(diào)移作業(yè)點(diǎn)訪問優(yōu)先權(quán)要求的前提下，為擴(kuò)大解的搜索范圍，依次運(yùn)用以下3種方法構(gòu)建新的鄰域解。例如，對(duì)于作業(yè)任務(wù)要求的將作業(yè)點(diǎn)v2的車輛調(diào)移至作業(yè)點(diǎn)v4，在目前的解中，可采用如下3種方法實(shí)現(xiàn)。

(1) 裝車點(diǎn)位置固定，卸車點(diǎn)位置前后移動(dòng)。如圖1所示，保持作業(yè)點(diǎn)v4的位置不變，將作業(yè)點(diǎn)v2插入到目前位置與調(diào)車場(chǎng)v0之間的任何位置，如v0和v3之間，或者將其插入到目前位置與作業(yè)點(diǎn)v4之間的任何位置，如v7和v8之間，從而得到1個(gè)新的鄰域解。

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

(2)卸車點(diǎn)位置固定，裝車點(diǎn)位置前后移動(dòng)。如圖2所示，保持作業(yè)點(diǎn)v2的位置不變，將作業(yè)點(diǎn)v4插入到其目前位置與調(diào)車場(chǎng)v11之間的任意位置，如v9和v10之間，或者將其插入到取車作業(yè)點(diǎn)v2與目前位置之間的任何位置，如v1和v7之間，從而得到1個(gè)新的鄰域解。

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

(3)2—交換。如圖3所示，若作業(yè)點(diǎn)v1和v6之間沒有調(diào)移作業(yè)任務(wù)，則交換v1和v6這2個(gè)作業(yè)點(diǎn)的位置，就可得到1個(gè)新的鄰域解。

圖3　解2—交換圖

算法終止條件：當(dāng)溫度低于某值ε時(shí)，則算法終止。

算法步驟如下。

Step 1: 選取初始溫度T0，溫度下降率λ，終止條件ε，馬爾科夫鏈L，任意生成1個(gè)初始可行解S0。

Step 2: 在當(dāng)前溫度Tu下，對(duì)l=1,2,…,L依次運(yùn)用3種鄰域解的構(gòu)造方法對(duì)當(dāng)前解進(jìn)行擾動(dòng)，隨機(jī)產(chǎn)生1個(gè)新的鄰域解S′。

Step 3: 計(jì)算Δf=f(S′)-f(S)。 若Δf≤0， 則接受S′作為新的當(dāng)前解， 即S=S′; 否則， 若exp(Δf/T)>rand(0，1)， 則S=S′； 否則，保留當(dāng)前解S。

Step 4: 根據(jù)溫度衰減函數(shù)Tu=λTu-1下降溫度。判斷此時(shí)溫度是否滿足算法終止條件；若滿足則轉(zhuǎn)Step 5；否則，轉(zhuǎn)Step 2。

Step 5: 輸出滿意的取送車作業(yè)方案。

4　算　例

某鐵路車站貨物作業(yè)點(diǎn)布置情況如圖4。圖4中：w為道岔岔心；數(shù)字為各點(diǎn)(調(diào)車場(chǎng)(車站)、道岔岔心、作業(yè)點(diǎn))間的實(shí)際里程/時(shí)間(需要說明的是，因?yàn)榧俣ㄕ{(diào)機(jī)走行速度不變，為了計(jì)算簡(jiǎn)便明了，所以取2點(diǎn)間調(diào)機(jī)走行里程與走行時(shí)間相同)。1批取送車作業(yè)內(nèi)容見表1；根據(jù)表1得到各貨物作業(yè)點(diǎn)的取送車輛數(shù)見表2；按照文獻(xiàn)[6]的方法，調(diào)整后的作業(yè)點(diǎn)間調(diào)機(jī)走行里程和走行時(shí)間見表3(為避免產(chǎn)生環(huán)，點(diǎn)本身間的數(shù)據(jù)取足夠大的正數(shù)80)。

圖4　某鐵路車站貨物作業(yè)點(diǎn)的布置示意圖

作業(yè)點(diǎn)作業(yè)內(nèi)容作業(yè)點(diǎn)作業(yè)內(nèi)容v1送車2輛v6取車2輛v2取空車2輛并調(diào)移至v4v7取空車1輛并調(diào)移至v10v3取車3輛v8送車2輛v4送由作業(yè)點(diǎn)調(diào)移的空車2輛v9取車3輛v5送車1輛、取車1輛v10送由作業(yè)點(diǎn)調(diào)移的空車1輛

表2　各貨物作業(yè)點(diǎn)的取、送車數(shù)

表3調(diào)車場(chǎng)(車站)及貨物作業(yè)點(diǎn)間的調(diào)機(jī)走行里程/時(shí)間

起點(diǎn)不同終點(diǎn)間的調(diào)機(jī)走行里程/時(shí)間v0v1v2v3v4v5v6v7v8v9v10v08043474148605256444135v14380203255675963494842v24720803659616367535246v34132368053655761474640v44855595380324246484741v560676165321025458605953v65259635742548030525145v75663676146583080565549v84449534748605256801521v94148524647595155158020v103542464041534549212080

(11)

從表4可知：選取的初始溫度T0越高、馬爾科夫鏈長度L越長、終止溫度ε越低，則所得到解的質(zhì)量也越高；取T0=1×106，ε=0.001，L=100時(shí)，所得到解的平均質(zhì)量最高，但需要37.783 s的計(jì)算時(shí)間在鐵路實(shí)際運(yùn)用時(shí)卻略偏大。

表4　參數(shù)不同取值時(shí)算法的計(jì)算結(jié)果比較

按照必須在可接受的時(shí)間范圍內(nèi)得到質(zhì)量較高取送車方案的要求，經(jīng)綜合權(quán)衡，在鐵路實(shí)際運(yùn)用中初始溫度T0可選105～106數(shù)量級(jí)的數(shù)值,終止溫度ε選10-3數(shù)量級(jí)的數(shù)值；相對(duì)而言，馬爾科夫鏈長度L對(duì)算法的計(jì)算效率影響較大，必須慎重選取，經(jīng)試驗(yàn)認(rèn)為取L=10～50較為合適。

本案例的作業(yè)任務(wù)包括了作業(yè)點(diǎn)的送車、取車、連送帶取和調(diào)移作業(yè)等所有的作業(yè)類型，若1批取送車作業(yè)涉及更多的貨物作業(yè)點(diǎn)，也只是增加貨物作業(yè)點(diǎn)的數(shù)量，計(jì)算時(shí)間雖有所增加，但模型和算法是適用的，只要算法輸入?yún)?shù)選擇合理，即可實(shí)現(xiàn)解質(zhì)量與計(jì)算效率的較好平衡。若1批取送車作業(yè)涉及的作業(yè)點(diǎn)較少，可認(rèn)為是本文案例的簡(jiǎn)化或特殊形式，模型和算法同樣是適用的。因此，本文所提出的模型和算法是有效的、合理的。

5　結(jié)　語

本文所建立的樹枝形貨物作業(yè)點(diǎn)取送車作業(yè)方案的多目標(biāo)優(yōu)化模型，以調(diào)機(jī)取送總時(shí)間、總?cè)刖€車輛小時(shí)和總走行車輛公里的加權(quán)綜合值最小為優(yōu)化目標(biāo)，較以往的研究成果更符合鐵路車站作業(yè)實(shí)際。根據(jù)模型的特征，構(gòu)造了模擬退火算法對(duì)其進(jìn)行求解。將模型及算法應(yīng)用于本文的案例中并多次試驗(yàn)表明：所建立的模型能較好地描述了取送車作業(yè)方案的編制要求和作業(yè)實(shí)際；模擬退火算法能滿足模型求解和現(xiàn)場(chǎng)需求，只要選取的參數(shù)合理，解的質(zhì)量和計(jì)算時(shí)間均可控制在適合運(yùn)輸生產(chǎn)需要的范圍之內(nèi)，從而驗(yàn)證了模型和算法的可行性和優(yōu)越性。下一步可將取送車作業(yè)方案優(yōu)化放在整個(gè)車站作業(yè)計(jì)劃系統(tǒng)中進(jìn)行研究，以服務(wù)于編制高質(zhì)量的車站作業(yè)計(jì)劃。

[1]石紅國，彭其淵，郭寒英.樹枝型專用線取送車問題的哈密爾頓圖解法[J].中國鐵道科學(xué)，2005，26(2):132-135.

(SHI Hongguo,PENG Qiyuan,GUO Hanying. An Algorithm by Using Hamilton Graph to Resolve Wagons’ Placing-In and Taking-Out on Branch-Shaped Sidings[J]. China Railway Science,2005,26(2):132-135.in Chinese)

[2]黃向榮.樹枝形專用線取送車的模型及算法研究[J].蘭州交通大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，26(3): 51-54.

(HUANG Xiangrong. Model of Wagons Placing-In and Taking-Out on Brand-Shaped Sidings and the Calculating Method[J]. Journal of Lanzhou Jiaotong University：Natural Sciences,2007,26(3):51-54. in Chinese)

[3]郭垂江，雷定猷.鐵路車站取送車作業(yè)圖論模型及算法分析[J].華東交通大學(xué)學(xué)報(bào)，2014，31(1)：102-107.

(GUO Chuijiang,LEI Dingyou.Model and Algorithm of Wagons’ Placing-In and Taking-Out in Railway Station[J].Journal of East China Jiaotong University,2014，31(1)：102-107. in Chinese)

[4]楊運(yùn)貴，王慈光，薛鋒.樹枝形鐵路專用線取送車問題的遺傳算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(12):210-211,214.

(YAN Yungui,WANG Ciguang,XUE Feng. Study on Genetic Algorithm for Railway Placing-In and Taking-Out of Wagons in Branch-Shaped Private Siding[J].Computer Engineering and Applications,2008,44(12):210-211,214.in Chinese)

[5]GUO Chuijiang, LEI Dingyou. Model of Wagons’ Placing-In and Taking-Out Problem in a Railway Station and Its Heuristic Algorithm[J]. Mathematical Problems in Engineering， 2014(8):1-8.

[6]郭垂江，雷定猷.樹枝形鐵路專用線取送車作業(yè)模型及啟發(fā)式算法[J].鐵道科學(xué)與工程學(xué)報(bào)，2015,12(1)：208-213.

(GUO Chuijiang,LEI Dingyou. Wagons’ Placing-In and Taking-Out Model in Branch-Shaped Railway and Its Heuristic Algorithm[J].Journal of Railway Science and Engineering, 2015,12(1)：208-213. in Chinese)

[7]王慈光.運(yùn)輸模型及優(yōu)化[M].1版.北京:中國鐵道出版社,2004：15-21.

[8]牟峰, 王慈光, 牟從凱. 鐵路車站取送車作業(yè)問題一般模型解的構(gòu)造方法[J].中國鐵道科學(xué)，2012，33(5):105-113.

(MU Feng,WANG Ciguang,MU Congkai.A Method for Generating Solutions of the Generic Model for Taking-Out and Placing-In Wagons in Railway Station[J]. China Railway Science,2012,33 (5):105-113.in Chinese)

[9]李金忠，夏潔武，曾小薈,等.多目標(biāo)模擬退火算法及其應(yīng)用研究進(jìn)展[J].計(jì)算機(jī)工程與科學(xué)，2013，35(8):77-88.

(LI Jinzhong,XIA Jiewu,ZENG Xiaohui, et al. Survey of Multi-Objective Simulated Annealing Algorithm and Its Applications[J].Computer Engineering & Science,2013，35(8):77-88. in Chinese)

[10]SUMAN Balram. Study of Simulated Annealing Based Algorithms for Multi-Objective Optimization of a Constrained Problem [J]. Computers & Chemical Engineering，2004,28(9):1849-1871.

[11]SUMAN B, Kumar P. A Survey of Simulated Annealing as a Tool for Single and Multi-Objective Optimization[J]. Journal of the Operational Research Society,2006,57:1143-1160.