郭垂江

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

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

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

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

1　符號說明

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

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

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

2.1　基本假設(shè)

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

(3)

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

(4)

3)總走行車輛公里最小

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

(5)

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

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è)點先后順序的約束

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

(8)

3　模型求解算法

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

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

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

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

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

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

(9)

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

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

pv(h))-Q, 0]

(10)

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

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

圖1　卸車點位置前后移動圖

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

圖2　裝車點位置前后移動

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

圖3　解2—交換圖

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

算法步驟如下。

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

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

Step 3: 計算Δ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下降溫度。判斷此時溫度是否滿足算法終止條件；若滿足則轉(zhuǎn)Step 5；否則，轉(zhuǎn)Step 2。

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

4　算　例

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

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

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

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

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

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

(11)

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

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

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

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

5　結(jié)　語

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

[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é)報：自然科學(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é)報，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]楊運貴，王慈光，薛鋒.樹枝形鐵路專用線取送車問題的遺傳算法研究[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é)報，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ō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ī)工程與科學(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.