郭垂江

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

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

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

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

1　符號說明

定義以下參數(shù)：v0為調(diào)車場(車站)；當調(diào)機在所有作業(yè)點作業(yè)完畢返回調(diào)車場(車站)時，為便于計算機編程，此時調(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)分別為按文獻[6]調(diào)整后的作業(yè)點vi與vj(vi,vj∈V)間的調(diào)機走行里程和調(diào)機走行時間。

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

2.1　基本假設

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

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

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

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

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

2.2　目標函數(shù)

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

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

(1)

2)總入線車輛小時最小

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

對于第1部分車輛，其總入線車輛小時為

(2)

對于第2部分車輛，其總入線輛車小時為

(3)

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

(4)

3)總走行車輛公里最小

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

(5)

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

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

(6)

2.3　約束條件

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

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

(7)

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

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

(8)

3　模型求解算法

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

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

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

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

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

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

(9)

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

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

pv(h))-Q, 0]

(10)

在保證滿足調(diào)移作業(yè)點訪問優(yōu)先權要求的前提下，為擴大解的搜索范圍，依次運用以下3種方法構建新的鄰域解。例如，對于作業(yè)任務要求的將作業(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è)任務，則交換v1和v6這2個作業(yè)點的位置，就可得到1個新的鄰域解。

圖3　解2—交換圖

算法終止條件：當溫度低于某值ε時，則算法終止。

算法步驟如下。

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

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

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

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

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

4　算　例

某鐵路車站貨物作業(yè)點布置情況如圖4。圖4中：w為道岔岔心；數(shù)字為各點(調(diào)車場(車站)、道岔岔心、作業(yè)點)間的實際里程/時間(需要說明的是，因為假定調(diào)機走行速度不變，為了計算簡便明了，所以取2點間調(diào)機走行里程與走行時間相同)。1批取送車作業(yè)內(nèi)容見表1；根據(jù)表1得到各貨物作業(yè)點的取送車輛數(shù)見表2；按照文獻[6]的方法，調(diào)整后的作業(yè)點間調(diào)機走行里程和走行時間見表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)機走行里程/時間

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

(11)

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

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

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

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

5　結　語

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

[1]石紅國，彭其淵，郭寒英.樹枝型專用線取送車問題的哈密爾頓圖解法[J].中國鐵道科學，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].蘭州交通大學學報：自然科學版，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].華東交通大學學報，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].計算機工程與應用，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].鐵道科學與工程學報，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è)問題一般模型解的構造方法[J].中國鐵道科學，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]李金忠，夏潔武，曾小薈,等.多目標模擬退火算法及其應用研究進展[J].計算機工程與科學，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.