樹(shù)枝形鐵路專用線取送車作業(yè)模型及啟發(fā)式算法

?

樹(shù)枝形鐵路專用線取送車作業(yè)模型及啟發(fā)式算法

郭垂江，雷定猷

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075)

摘要:合理安排鐵路專用線取送車順序，有利于提高調(diào)車機(jī)車作業(yè)效率、加速貨車周轉(zhuǎn)。以調(diào)車機(jī)車完成一批調(diào)車作業(yè)任務(wù)后所走行路程最短為優(yōu)化目標(biāo)；為便于區(qū)分，增設(shè)虛擬車站，并以各裝卸作業(yè)點(diǎn)和車站為頂點(diǎn)；以根據(jù)作業(yè)情況不同調(diào)整后的作業(yè)點(diǎn)間距離為線段權(quán)，建立樹(shù)枝形專用線取送車作業(yè)的哈密爾頓圖模型，指出合理的取送車順序?yàn)闈M足所有優(yōu)先權(quán)關(guān)系的哈密爾頓回路。設(shè)計(jì)啟發(fā)式算法進(jìn)行求解，以不同作業(yè)的起點(diǎn)為始點(diǎn)，順或逆時(shí)針確定機(jī)車下一訪問(wèn)作業(yè)點(diǎn)，從而形成不同的初始解，采用局部交換作業(yè)順序規(guī)則對(duì)目前解進(jìn)行改進(jìn)，選擇機(jī)車走行路程最短的路徑為滿意解。其他作業(yè)形式可認(rèn)為是送調(diào)取結(jié)合作業(yè)形式的簡(jiǎn)化形式，所提出的模型及算法同樣適用。

關(guān)鍵詞：鐵路；樹(shù)枝形專用線；取送車；啟發(fā)式算法

合理安排鐵路專用線取送車順序，有利于提高調(diào)車機(jī)車作業(yè)效率、加速貨車周轉(zhuǎn)。專用線按其線路的布置形式不同通常可分為放射形和樹(shù)枝形兩大類。放射形專用線取送車作業(yè)時(shí)向一作業(yè)點(diǎn)取送完車組后必須返回車站才能再去另一作業(yè)點(diǎn)取送車，各線車輛入線時(shí)刻不同，取回站內(nèi)時(shí)刻也不同。樹(shù)枝形專用線在一批作業(yè)中間不必返回車站，各線車輛入線時(shí)刻不同，但取回站內(nèi)時(shí)刻相同。

1問(wèn)題描述

取送車作業(yè)模式有單一送車、單一取車、送取結(jié)合、送兼調(diào)移、取兼調(diào)移和送調(diào)取結(jié)合。單一送車是指調(diào)車機(jī)車將需裝卸的車組逐一送到相應(yīng)的作業(yè)點(diǎn)，然后返回車站。單一取車是指調(diào)車機(jī)車將裝卸完畢的車組逐一取回車站。送取結(jié)合簡(jiǎn)稱“連送帶取”，指在向各作業(yè)點(diǎn)送車的同時(shí)取回裝卸完畢車輛。送兼調(diào)移是指將需裝卸的車組送到相應(yīng)地裝卸地點(diǎn)，同時(shí)完成車組在作業(yè)點(diǎn)間的調(diào)移。取兼調(diào)移機(jī)車去專用線作業(yè)點(diǎn)取出裝卸完畢的車組，同時(shí)完成車輛調(diào)移任務(wù)。送調(diào)取結(jié)合作業(yè)比較復(fù)雜，是指需送車的車組送到相應(yīng)的裝卸點(diǎn)、取出裝卸完畢的車組，在取送車的同時(shí)完成車組在作業(yè)點(diǎn)間的調(diào)移。相關(guān)學(xué)者對(duì)鐵路專用線取送車問(wèn)題進(jìn)行了一定的研究。石紅國(guó)等[1-3]以機(jī)車在作業(yè)點(diǎn)間走行時(shí)間最小為優(yōu)化目標(biāo)，建立了樹(shù)枝形鐵路專用線取送車問(wèn)題的哈密爾頓圖模型，應(yīng)用2-交換、最小生成樹(shù)算法進(jìn)行求解。雷友誠(chéng)等[4-9]以完成一批作業(yè)任務(wù)的機(jī)車走行時(shí)間最小為優(yōu)化目標(biāo)，建立了相應(yīng)的數(shù)學(xué)模型，采用遺傳算法、蟻群算法進(jìn)行求解。以上研究只適應(yīng)于單一取車、單一取出等簡(jiǎn)單作業(yè)形式，難以適應(yīng)鐵路現(xiàn)場(chǎng)復(fù)雜的組合作業(yè)形式。郭垂江等[11]把樹(shù)枝形專用線取(送)車作業(yè)優(yōu)化問(wèn)題轉(zhuǎn)換成哈密爾頓圖最短路問(wèn)題，并松弛為指派問(wèn)題，采用匈牙利算法得到最短回路路長(zhǎng)的下界或最優(yōu)解。若未得到最優(yōu)解，再利用破圈連接法求出滿意的取(送)車順序，然后將模型擴(kuò)展到其他作業(yè)形式。另外封全喜等[12]對(duì)物流配送車輛徑路問(wèn)題進(jìn)行了深入研究，為本文研究提供了很好的借鑒。

本文討論鐵路車站樹(shù)枝形專用線的取送車問(wèn)題：即如何優(yōu)化調(diào)車機(jī)車運(yùn)用，使其在完成一批專用線的取送作業(yè)后所走行的路程最短。主要研究送調(diào)取結(jié)合作業(yè)形式，其他作業(yè)形式可認(rèn)為是送調(diào)取結(jié)合作業(yè)形式的簡(jiǎn)化形式。下面結(jié)合一個(gè)典型案例說(shuō)明整個(gè)模型建立及求解過(guò)程。

2模型建立

圖1為一車站專用線布置圖，v1為車站，v2，v3，…，v11為貨物裝卸作業(yè)點(diǎn)，數(shù)字為道岔岔心與作業(yè)點(diǎn)(車站)間實(shí)際路程。車站配備1臺(tái)調(diào)車機(jī)車負(fù)責(zé)專用線的取送車作業(yè)，一批調(diào)車作業(yè)的作業(yè)任務(wù)如表1第1和第2列所示。

圖1　樹(shù)枝形專用線布置圖Fig.1 Layout of branch-shaped railway siding

把問(wèn)題構(gòu)造成完備圖G=[V,A,C]，如圖2，V={v0,v1,...,v11}，v0為增設(shè)的虛擬車站，v1為鐵路車站，vi(i=2,3,...,11)為貨物作業(yè)點(diǎn)；A={(vi,vj)|vi,vj∈V}，(vi,vj)為連接作業(yè)點(diǎn)(車站)間的邊；C={lij|i,j=0,1,2,...,11}，lij為機(jī)車在作業(yè)點(diǎn)(車站)間的機(jī)車走行距離, 規(guī)定l01=l10=0。

圖2　哈密爾頓圖Fig.2 Hamilton graph

若調(diào)車機(jī)車把車站v1的車組送往作業(yè)點(diǎn)vk，則調(diào)車機(jī)車必須先在車站v1連掛車組，然后才能送往作業(yè)點(diǎn)vk，即機(jī)車訪問(wèn)優(yōu)先權(quán)為v1φvk(φ表示優(yōu)先于)。

若作業(yè)點(diǎn)vi至作業(yè)點(diǎn)vj調(diào)移車組，則調(diào)車機(jī)車必須先在作業(yè)點(diǎn)vi連掛車組，然后才能送往作業(yè)點(diǎn)vj，即機(jī)車訪問(wèn)優(yōu)先權(quán)為viφvj。

考慮作業(yè)點(diǎn)需同時(shí)取送的特殊情況，即假設(shè)需往把車站v1向作業(yè)點(diǎn)vi送車進(jìn)行裝(卸)，同時(shí)需把作業(yè)點(diǎn)vi裝(卸)完畢的車輛取回車站v1。即存在優(yōu)先關(guān)系為：v1φvi，viφv1。為避免以上矛盾，增加虛擬車站v0，則以上必須滿足的優(yōu)先關(guān)系為：v1φvi，viφv0。

若調(diào)車機(jī)車把作業(yè)點(diǎn)vl的車組取回車站v1，則調(diào)車機(jī)車必須先在作業(yè)點(diǎn)vl連掛車組，然后才能送往車站v1，即機(jī)車訪問(wèn)優(yōu)先權(quán)為vlφv1。為與作業(yè)點(diǎn)需同時(shí)取送的分析統(tǒng)一，機(jī)車訪問(wèn)優(yōu)先權(quán)記為vlφv0。

通過(guò)以上分析，調(diào)車機(jī)車要完成所有的取送車及調(diào)移任務(wù)，必須滿足相應(yīng)的優(yōu)先關(guān)系。上例作業(yè)任務(wù)必須滿足的優(yōu)先關(guān)系如表1中的第4列。

將車站v1視作哈密爾頓圖的出發(fā)頂點(diǎn)，每1個(gè)作業(yè)點(diǎn)看作1個(gè)需要經(jīng)過(guò)1次的哈密爾頓圖頂點(diǎn)，如果找到恰好經(jīng)過(guò)各點(diǎn)并滿足以上所有優(yōu)先關(guān)系并回到車站v1的1條回路，就得到1個(gè)可行的取送車作業(yè)方案。哈密爾頓回路的路長(zhǎng)為機(jī)車在各線段上機(jī)車走行距離lij的加總，總走行距離最短的可行哈密爾頓回路即為最優(yōu)的取送車順序。

表1　取送調(diào)車作業(yè)任務(wù)

3機(jī)車走行路程的討論

因?yàn)闃?shù)枝形專用線所有的裝卸線為盡頭線，摘下連掛在機(jī)車上的車組時(shí)，必須保證所摘下的車組處在最外方位置。在取送車作業(yè)過(guò)程中，需進(jìn)行調(diào)整車組的順序，以便能摘下車組，因此機(jī)車在兩作業(yè)點(diǎn)的距離lij不能簡(jiǎn)單地認(rèn)為是線段之間的實(shí)際距離之和，可能因?qū)嶋H作業(yè)情況不同而需進(jìn)行調(diào)整。下面對(duì)取送車作業(yè)存在的作業(yè)情況進(jìn)行分析。

3.1取后送(送后取)

如圖3，現(xiàn)假設(shè)調(diào)車機(jī)車需連掛若干車組從作業(yè)點(diǎn)vk將一車組取出后，再將另一車組送往作業(yè)點(diǎn)vi。

第1種作業(yè)情況機(jī)車的作業(yè)過(guò)程為：調(diào)車機(jī)車推送車組至作業(yè)點(diǎn)vk，連掛需取出的車組，牽出至點(diǎn)a，推進(jìn)運(yùn)行至作業(yè)點(diǎn)vj所在的裝卸線，在警沖標(biāo)e處停車，在需摘下的車組前摘鉤后，牽引運(yùn)行至點(diǎn)c，推送進(jìn)入作業(yè)點(diǎn)vi所在的裝卸線，至vi處摘下車組，牽引剩余的車輛至點(diǎn)c，轉(zhuǎn)線至e處連接已停放的車輛，牽出過(guò)點(diǎn)a。

第2種作業(yè)情況機(jī)車的作業(yè)過(guò)程為：調(diào)車機(jī)車推送車組在警沖標(biāo)b處停車，單機(jī)(也可能連掛著若干車輛)去作業(yè)點(diǎn)vk取出車組后，返回b處連掛原來(lái)放置的車輛，推送至作業(yè)點(diǎn)vi，摘下相應(yīng)的車組后返回點(diǎn)a。

雖然調(diào)車機(jī)車需在兩道岔區(qū)往返走行，但其走行距離相對(duì)貨物線長(zhǎng)度是很短的，所以完成該作業(yè)任務(wù)的機(jī)車走行距離可近似為2(l1+l2+l3)。相應(yīng)地，圖3中vi至點(diǎn)vk的機(jī)車走行距離可認(rèn)為是l2+l1+l3。

按以上方法對(duì)先送后取作業(yè)進(jìn)行分析，可得出同樣的結(jié)論。

圖3　取后送(送后取)作業(yè)過(guò)程分析圖Fig.3 Process analysis of wagons’ placing-in after it’s taking-out (taking-out after it’s placing-in)

3.2調(diào)移

調(diào)移車輛就是調(diào)機(jī)往一個(gè)作業(yè)點(diǎn)的取出卸空的車組，然后送往另一作業(yè)點(diǎn)進(jìn)行裝車。一次調(diào)移作業(yè)可認(rèn)為是一次取車作業(yè)和一次送車作業(yè)的結(jié)合。如圖4，假設(shè)調(diào)車機(jī)車需從作業(yè)點(diǎn)vi調(diào)移空車至作業(yè)點(diǎn)vk，不失一般性，調(diào)移過(guò)程中還要執(zhí)行其它作業(yè)任務(wù)(假設(shè)是向vj點(diǎn)送車)。機(jī)車的作業(yè)過(guò)程為：調(diào)車機(jī)車推送車輛過(guò)警沖標(biāo)處e點(diǎn)后停輪，選擇合適的車輛位置摘鉤，牽引車組(或單機(jī))至點(diǎn)a，然后推送至點(diǎn)vi連掛需調(diào)移的空車，牽引返回至點(diǎn)a轉(zhuǎn)線至點(diǎn)e連掛原來(lái)放置的車輛，執(zhí)行vj點(diǎn)送車任務(wù)，完成后牽引至點(diǎn)c，送作業(yè)點(diǎn)vi的空車至作業(yè)點(diǎn)vk，然后牽引返回點(diǎn)a。可以看出，由于需保證車組能順利摘下，機(jī)車走行過(guò)程中須在道岔周圍折返，但機(jī)車在岔區(qū)的走行距離相對(duì)貨物線長(zhǎng)度是比較短的，所以調(diào)車機(jī)車執(zhí)行此次調(diào)移任務(wù)的走行路程可近似為2(l1+l2+l3+l4)。相應(yīng)地，圖4中vi至點(diǎn)vk的機(jī)車走行距離可認(rèn)為是l2+l1+l4。

圖4　調(diào)移作業(yè)過(guò)程分析圖Fig.4 Process analysis graph of transferring operation

3.3作業(yè)點(diǎn)連送帶取

現(xiàn)假設(shè)在向作業(yè)點(diǎn)vi送車的同時(shí)，取出已經(jīng)裝卸完畢的車組如圖5所示。作業(yè)點(diǎn)連送帶取在實(shí)際工作中存在2種情況：一是機(jī)車將車組送到作業(yè)點(diǎn)vi后，等待車組裝(卸)完后再將其取出，機(jī)車需在作業(yè)點(diǎn)vi前等待；二是機(jī)車將車組送到作業(yè)點(diǎn)vi后，取出其他已裝(卸)完畢的車組，此種情況機(jī)車需越線調(diào)車。顯然，第1種情況不會(huì)增加機(jī)車的走行路程，只會(huì)增加機(jī)車的作業(yè)時(shí)間。下面對(duì)第2種作業(yè)情況進(jìn)行深入分析。

機(jī)車的作業(yè)過(guò)程為：首先機(jī)車推送車輛過(guò)警沖標(biāo)c，在合適的位置摘鉤后，牽引部分車輛至點(diǎn)a，轉(zhuǎn)線去作業(yè)點(diǎn)vi連掛裝卸完畢的車組，返回點(diǎn)a，推送至點(diǎn)c與原來(lái)摘下的車輛連掛，在合適的位置摘鉤(使要送的車組露出)，牽引運(yùn)行至點(diǎn)a，推送運(yùn)行至作業(yè)點(diǎn)vi，摘下車組后返回點(diǎn)a，推送運(yùn)行至點(diǎn)c與原來(lái)摘下的車輛連掛。由于要保證車組能順利摘下，機(jī)車須在道岔區(qū)折返，但其走行距離相對(duì)貨物線長(zhǎng)度是很短的，所以機(jī)車完成該作業(yè)任務(wù)的走行距離可近似為4l1。因此在構(gòu)造機(jī)車走行

距離矩陣時(shí)，須相應(yīng)地在點(diǎn)vi所在行、列中增加長(zhǎng)度l1。如表1作業(yè)任務(wù)中因作業(yè)點(diǎn)v6需連送帶取作業(yè)，本案例認(rèn)為機(jī)車連送帶取屬于第2種情況，因此構(gòu)造機(jī)車走行距離矩陣時(shí)，需在v6所在的行和列上分別增加11。

圖5　作業(yè)點(diǎn)連取帶送作業(yè)過(guò)程分析圖Fig.5 Operation process analysis graph of wagons’ placing-in combined with taking-out in the same site

因?yàn)楣軤栴D圖所有頂點(diǎn)沒(méi)有環(huán)，最短路徑問(wèn)題為極小化問(wèn)題，所以可令機(jī)車點(diǎn)間走行距離lii=M(i=0,1,…,11，M是足夠大的正數(shù))。表1案例設(shè)置M=80。

綜上，得到表1案例的作業(yè)點(diǎn)間機(jī)車走行路程系數(shù)如表2。

表2　車站作業(yè)點(diǎn)(車站、虛車站)間機(jī)車走行路程

4啟發(fā)式算法

為得到滿意的取送車方案，設(shè)計(jì)以下啟發(fā)式算法對(duì)模型進(jìn)行求解[13-16]，計(jì)算步驟如下：

Step1 不區(qū)分作業(yè)任務(wù)的始點(diǎn)和終點(diǎn)，通過(guò)最小生成樹(shù)的方法(MST)構(gòu)造一個(gè)通過(guò)n+1個(gè)頂點(diǎn)的最小生成樹(shù)T0；

Step2 選擇任何一個(gè)作業(yè)任務(wù)的起點(diǎn)作為出發(fā)點(diǎn)，順時(shí)針訪問(wèn)所有的作業(yè)點(diǎn)，最后返回v0。訪問(wèn)時(shí)按以下兩個(gè)原則選擇即將訪問(wèn)點(diǎn)。①以前訪問(wèn)過(guò)的作業(yè)點(diǎn)不訪問(wèn)；②任何起點(diǎn)還未訪問(wèn)的終點(diǎn)不訪問(wèn)。可得到的路徑T1；

Step3 按下文所述的方法進(jìn)行局部交換作業(yè)順序，改進(jìn)路徑T1；

Step4 逆時(shí)針重復(fù)Step2和Step3,選擇最短距離的路徑T1；

局部交換作業(yè)順序規(guī)則如圖6，i，j，k，m為相鄰作業(yè)點(diǎn)，在滿足dij+dkm-dik-djm>0且點(diǎn)k不是一個(gè)起點(diǎn)為j的作業(yè)任務(wù)終點(diǎn)的條件下，圖6(b)要優(yōu)于圖6(a)。需要說(shuō)明的是，必須以上條件都滿足的條件下才能交換，第1個(gè)條件能使機(jī)車走行距離縮短；第2個(gè)條件能保證路徑的合法性。

圖6　局部位置交換圖Fig.6 Local position exchange graph

在計(jì)算表1案例時(shí)，首先利用避圈法得到圖2的最小生成樹(shù)如圖7。

圖7　最小生成樹(shù)Fig.7 Minimum spanning tree

執(zhí)行步驟2。如選擇作業(yè)任務(wù)v3→v5的起點(diǎn)v3作為出發(fā)點(diǎn)，順時(shí)針訪問(wèn)所有的作業(yè)點(diǎn)，最后返回點(diǎn)v0，得到可行的取送車順序T1為：v1→v3→v4→v5→v6→v7→v8→v9→v10→v11→v2→v0，路程長(zhǎng)為428。執(zhí)行Step3局部交換作業(yè)順序，如交換T1中的v6，v7位置，l56+l78-l57-l68=-38<0，說(shuō)明交換不能改進(jìn)路徑。同樣地交換T1其它所有相鄰作業(yè)點(diǎn)，均不能改進(jìn)徑路。其他的方案計(jì)算可借助計(jì)算機(jī)進(jìn)行。

利用MATLAB 7.0 編制程序，利用本文提出的啟發(fā)式算法得到的滿意解為：v1→v4→v2→v3→v8→v7→v5→v6→v11→v10→v9→v0，路長(zhǎng)為：396。另利用窮舉法得到最優(yōu)解為：v1→v4→v2→v3→v5→v6→v7→v8→v9→v10→v11→v0，路長(zhǎng)為：394。本文的案例與參考文獻(xiàn)[11]的案例是相同的，文獻(xiàn)[11]得到的滿意解為：v1→v10→v7→v8→v3→v2→v11→v5→v6→v9→v4→v0(因標(biāo)號(hào)不同，表達(dá)方式與原文有差異)，總路長(zhǎng)為472。可見(jiàn)，本文所設(shè)計(jì)的啟發(fā)式算法是比較優(yōu)越的。

5結(jié)論

1)若要以機(jī)車走行時(shí)間最少為優(yōu)化目標(biāo)，因機(jī)車在調(diào)車過(guò)程中要進(jìn)行轉(zhuǎn)線、對(duì)位等作業(yè)，需多次在線路上加減速，因此計(jì)算時(shí)要對(duì)各項(xiàng)作業(yè)時(shí)間進(jìn)行嚴(yán)格查定，方可適應(yīng)要求。

2)本文的啟發(fā)式算法中的局部交換是采用2-交換的方法進(jìn)行的，還可以采用3-交換、k-交換等方法，但一定要保證交換后取送車順序的有效性。

參考文獻(xiàn)：

[1] 石紅國(guó)，彭其淵，郭寒英.樹(shù)枝型專用線取送車問(wèn)題的哈密爾頓圖解法[J].中國(guó)鐵道科學(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]. Chian Railway Science,2005,26(2):132-135.

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

WANG Ciguang. Transport model and optimization[M].1st Edition. Beijing:China Railway Publishing House,2004.

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

HUANG Xiangrong. Model of wagons placing-in and taking-out on branch-shaped sidings and the calculating method [J].Journal of Lanzhou Jiaotong University(Natural Sciences),2007,26(3): 51-54.

[4] 雷友誠(chéng),涂祖耀,桂衛(wèi)華，等.基于遺傳蟻群算法的樹(shù)枝型鐵路取送車問(wèn)題優(yōu)化[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，48(2):2356-2361.

LEI Youcheng, TU Zuyao, GUI Weihua, et al. Optimization of placing-in and taking-out wagons on branch-shaped railway lines based on genetic and ant colony algorithm[J].Journal of Central South University(Science and Technology) ,2011,48(2):2356-2361.

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

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．

[6] 李海軍，朱昌鋒.放射形鐵路專用線直達(dá)車流取送車問(wèn)題的單親遺傳算法研究[J].鐵道科學(xué)與工程學(xué)報(bào)，2011,8(6)：114-117.

LI Haijun, ZHU Changfeng. Study of through wagon flow on single-parent genetic algorithm for railway placing-in and taking-out of wagons in atinoid private line[J].Journal of Railway Science and Engineering，2011,8(6)：114-117.

[7] 王雅琳，李開(kāi)峰，馬杰，等．遺傳算法在企業(yè)鐵路取送調(diào)車作業(yè)優(yōu)化中的應(yīng)用[J]．系統(tǒng)工程．2007，25(3)：94-99.

WANG Yalin, LI Kaifeng, MA Jie, et al. Application of genetic algorithm to optimal for placing-in and taking-out of wagons at enterprise[J]. Systems Engineering, 2007，25(3)：94-99.

[8] 李智.基于改進(jìn)型蟻群算法的貨物作業(yè)車取送模型優(yōu)化[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2004，26(4)：73-76.

LI Zhi．Optimization of placing-in apd taking-out wagon operation model based on enhanced ant colony algorithm[J]．Railway Transport and Economy，2004，26(4)：73-76．

[9] 李斌，董昱，孫云霞.樹(shù)枝形專用線取送車優(yōu)化問(wèn)題的研究[J].鄭州大學(xué)學(xué)報(bào)(工學(xué)版)，2014，35(1):20-24.

LI Bin, DONG Yu, SUN Yun-xia. Research on PTW on branch-shaped sidings[J].Journal of Zhengzhou University (Engineering Science), 2014，35(1):20-24.

[10] 鄧連波，史峰，莫輝輝.物流配送車輛路徑問(wèn)題多代競(jìng)爭(zhēng)遺傳算法[J].鐵道科學(xué)與工程學(xué)報(bào)，2005,2(5)：75-79.

DENG Lianbo, SHI Feng, MO Huihui. Multi-generation compete genetic algorithms for logistics distribution vehicle routing problem. [J].Journal of Railway Science and Engineering，2005,2(5)：75-79.

[11] 郭垂江，雷定猷.樹(shù)枝形專用線取送車問(wèn)題哈密爾頓圖模型及算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2014,14(3)：105-109.

GUO Chuijiang, LEI Dingyou. Hamilton model and algorithm for placing-in and taking-out wagon problem on branch-shaped siding[J].Journal of Transportation Systems Engineering and Information Technology, 2014,14(3):105-109.

[12] 封全喜，劉誠(chéng).物流配送車輛路徑問(wèn)題的并行遺傳算法研究[J].鐵道科學(xué)與工程學(xué)報(bào)，2005,2(4)：88-91.

FENG Quanxi, LIU Cheng. The study of parallel genetic algorithm for vehicle routing problem of logistic distribution[J].Journal of Railway Science and Engineering，2005,2(4):88-91.

[13] Renaud M, Stefan R, Fabien L, et al. A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes[J]. European Journal of Operational Research, 2014(236):849-862.

[14] Rais A, Alvelos F, Carvalho S M. New mixed integer-programming model for the pickup-and-delivery problem with transshipment[J]. European Journal of Operational Research, 2014,235(3):530-539.

[15] Rego C, Gamboa D, Glover F, et al. Traveling salesman problem heuristics: Leading methods, implementations and latest advances[J]. European Journal of Operational Research, 2011,211(3):427-441.

[16] Jacques R. A heuristic for the pickup and delivery traveling salesman problem[J]. Computers & Operations Research, 2000(27)：905-916.

Wagons' placing-in and taking-out model in branch-shaped

railway and its heuristic algorithm

GUO Chuijiang, LEI Dingyou

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

Abstract:Reasonable arrangement on sequence of wagons' placing-in and taking-out in railway siding is beneficial to improve the efficiency of shunting locomotive, and is conductive to accelerate wagons turnover. It was taken as an objective to minimize the locomotive's running distance after completing a series of shunting operations. In order to distinguish them with ease, virtual stations were added. Taking loading and unloading sites and stations as vertices, and considering the adjusted distance between operation sites according to different operation situations as weights, the graph model of wagons' placing-in and taking-out in branch-shaped railway siding was formulated. Rational placing-in and taking-out sequences were Hamilton loops which satisfy all priorities. A heuristic algorithm was designed to solve it. Taking origination of different operation as the starting point, different initial solutions were formulated through determining the next operating point according to clockwise or counterclockwise direction. The current solutions were improved with local exchange rules, and the route with shortest distance was selected as the satisfied solution. Other forms could be considered as simplified forms of wagons' placing-in, taking-out and transferring combination. The model and algorithm proposed in this paper are also applicable for them.

Key words:railway; branch-shaped railway siding; wagons' placing-in and taking-out; heuristic algorithm

中圖分類號(hào)：U292.13

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-7029(2015)01-0208-06

通訊作者：郭垂江(1980-)，湖南武岡人，博士研究生，從事車站運(yùn)輸組織優(yōu)化研究；E-mail: guochuijiang@sina.com

*收稿日期：2014-07-25