李海軍，朱昌鋒

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅蘭州 730070)

放射形鐵路專用線直達(dá)車流取送車問(wèn)題的單親遺傳算法研究＊

李海軍，朱昌鋒

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅蘭州 730070)

專用線最佳取送車順序的確定，有利于減少作業(yè)車在站非生產(chǎn)性停留時(shí)間，加速車輛周轉(zhuǎn)。通過(guò)分析放射形專用線直達(dá)車流取送車作業(yè)特點(diǎn)，構(gòu)造了該問(wèn)題的染色體編碼方式，采用輪盤賭策略進(jìn)行染色體選擇，以作業(yè)車在站最小停留時(shí)間作為適應(yīng)度函數(shù)，設(shè)計(jì)了該問(wèn)題的單親遺傳算法，并結(jié)合算例進(jìn)行計(jì)算，結(jié)果表明，該算法求解直達(dá)車流取送車問(wèn)題取得了較好的效果。

放射形專用線;取送車作業(yè);直達(dá)車流;單親遺傳算法

取送車作業(yè)是較大的貨運(yùn)站、技術(shù)站和大型廠礦企業(yè)專用線的聯(lián)軌站的一項(xiàng)重要工作［1－2］，其效率高低直接關(guān)系到車輛周轉(zhuǎn)和貨物送達(dá)的快慢及運(yùn)輸指標(biāo)的完成［3－4］。

對(duì)于直達(dá)車流取送車問(wèn)題的研究，就放射形專用線，徐忠民等［5］以排列組合理論為基礎(chǔ)，窮舉所有取送方案，直接計(jì)算每一方案的作業(yè)中斷時(shí)間，直至找到中斷時(shí)間最小的方案或計(jì)算完所有方案，但這種方法計(jì)算工作量大，需要逐一計(jì)算每一方案的作業(yè)中斷時(shí)間，當(dāng)中斷時(shí)間不能為零時(shí)，必須計(jì)算全部方案;宋建業(yè)［6］采用表上移動(dòng)法，以取送同序方案為初始狀態(tài)，通過(guò)在方案計(jì)算表上移動(dòng)相鄰送車順序或取車順序，使各作業(yè)地點(diǎn)的中斷時(shí)間最大值降低到最小程度，從而得到一個(gè)最優(yōu)取送順序方案，方法簡(jiǎn)單實(shí)用。李文權(quán)［7］將取車、送車及作業(yè)分成2個(gè)子問(wèn)題單獨(dú)考慮，通過(guò)建立2類排序論模型，給出了放射形專用線上直達(dá)列車取送車計(jì)劃的一個(gè)快速簡(jiǎn)單的算法。王慈光［8］對(duì)放射形專用線非直達(dá)車流取送車問(wèn)題進(jìn)行了研究，給出了送車需要時(shí)間和取車需要時(shí)間計(jì)算公式，提出了送車增量和取車增量概念，算法的設(shè)計(jì)遵循分部求解的思路，以隱枚舉的方法實(shí)現(xiàn)。牟峰等［9］將取送車作業(yè)作為一個(gè)系統(tǒng)進(jìn)行整體考慮，以貨車在站停留的總車小時(shí)消耗最小為優(yōu)化目標(biāo)，建立數(shù)學(xué)模型，設(shè)計(jì)求解的編碼方式，并采用基于云模型的參數(shù)自適應(yīng)蟻群遺傳算法進(jìn)行仿真。

本文根據(jù)鐵路運(yùn)輸組織的特點(diǎn)，研究運(yùn)用單親遺傳算法編碼構(gòu)造求解放射形專用線直達(dá)車流取送車問(wèn)題的具體算法，并對(duì)其運(yùn)算過(guò)程和結(jié)果進(jìn)行分析。

1 建立模型

1.1 問(wèn)題的提出

對(duì)于直達(dá)車流整列到發(fā)、一臺(tái)機(jī)車作業(yè)條件下的放射形專用線取送順序問(wèn)題，其作業(yè)方法為:空車整列到達(dá)車站，在到發(fā)線上進(jìn)行必要的到達(dá)作業(yè)后，機(jī)車將空車分別送往各條專用線裝車，裝完的重車由該機(jī)車先后取回站內(nèi)，編組成列出發(fā)。其作業(yè)特點(diǎn)為:機(jī)車每次送車或取車后都要回到車站。如圖1所示，S代表車站，Li(i=1，2，…)代表專用線，使用一臺(tái)機(jī)車作業(yè)。

圖1 放射形專用線布置示意圖Fig.1 The sketch map of RPTW

現(xiàn)在的問(wèn)題是，如何合理確定取送車順序，使得直達(dá)列車在車站的總停留時(shí)間最小。

1.2 模型建立

假定車站銜接n條專用線，分別標(biāo)記為1，2，…，n，調(diào)車機(jī)車一次向?qū)Ｓ镁€的作業(yè)地點(diǎn)送車或取車的走行時(shí)間為(i=1，2，…，n)，通過(guò)寫實(shí)，此時(shí)間標(biāo)準(zhǔn)是已知的。當(dāng)各作業(yè)地點(diǎn)所需的貨物作業(yè)時(shí)間均大于其取送車時(shí)間時(shí)，各地點(diǎn)的貨物裝卸作業(yè)是與調(diào)機(jī)向其他地點(diǎn)取送作業(yè)平行地進(jìn)行。送車過(guò)程完畢即可進(jìn)行取車作業(yè)，且在車輛取送過(guò)程中為各地點(diǎn)所提供的貨物作業(yè)時(shí)間都能滿足需要時(shí)，顯然，直達(dá)列車的作業(yè)停留總時(shí)間將有最小值，

否則，將產(chǎn)生調(diào)機(jī)等待貨物作業(yè)完畢的取送車中斷時(shí)間t中斷，于是直達(dá)列車作業(yè)停留總時(shí)間將增加到

式中，t中斷為該取送順序方案下各貨物作業(yè)地點(diǎn)所要求的中斷時(shí)間中的最大值，即

就是說(shuō)，保證t中斷有最小值的取送車順序方案，即為最佳取送車順序方案。則有以直達(dá)列車作業(yè)停留總時(shí)間最小為優(yōu)化目標(biāo)的放射形專用線取送車問(wèn)題的數(shù)學(xué)模型:

2 算法設(shè)計(jì)

2.1 編碼表示

根據(jù)專用線取送車問(wèn)題的特點(diǎn)，采用符號(hào)編碼的方法。將各作業(yè)地點(diǎn)的序號(hào)按取(送)車順序連接在一起，就可構(gòu)成一個(gè)表示取(送)順序的個(gè)體。X:［1，2，…，n］。本問(wèn)題取送作業(yè)包括互相聯(lián)系的送車和取車2個(gè)過(guò)程，所以記送車順序?yàn)槿旧w的X部分，取車順序?yàn)閅部分。如圖2為一個(gè)取送方案的編碼，該編碼X部分表示送車順序，Y部分表示取車順序(此部分基因排列可由適應(yīng)度函數(shù)的設(shè)計(jì)得到)。即送車順序?yàn)?－2－3－1，取車順序?yàn)?－3－4－1。

圖2 取送車問(wèn)題編碼示意圖Fig.2 The sketch figure of coding for RPTW

2.2 初始種群的產(chǎn)生

由于遺傳算法的群體型操作需要，所以必須為遺傳操作準(zhǔn)備一個(gè)由若干初始解組成的初始群體。眾多的個(gè)體組成了群體，在遺傳算法處理流程中，繼編碼設(shè)計(jì)后的任務(wù)是初始群體的設(shè)定，并以此為起點(diǎn)逐代進(jìn)化直到按某種進(jìn)化停止準(zhǔn)則終止進(jìn)化過(guò)程，由此得到最后一代(或群體)。

本問(wèn)題中，在規(guī)模為POP_SIZE種群中，每個(gè)染色體的X部分即為基因(作業(yè)地點(diǎn))的隨機(jī)排列。

2.3 適應(yīng)度函數(shù)的設(shè)計(jì)

取送車問(wèn)題的適應(yīng)度函數(shù)計(jì)算算法如下:

Step 1 初始化currentTime，intervalTime= 0;

Step 2 遍歷染色體X部分的所有基因位，計(jì)算各作業(yè)地點(diǎn)的完工時(shí)間 job［j］.completeTime=currentTime+job［j］.runTime+ job［j］.operTime，currentTime;

Step 3 按先作業(yè)完先取的原則確定取車順序，此順序即為染色體的Y部分;

Step 4 計(jì)算適應(yīng)度函數(shù)值OBJECTIVE［i］。如果當(dāng)前取車時(shí)間與當(dāng)前作業(yè)地點(diǎn)取車走行時(shí)間之和小于此點(diǎn)作業(yè)完工時(shí)刻，即currentTime+fetch［k］.runTime ＜ fetch［k］.sendCtime，會(huì)產(chǎn)生機(jī)車中斷時(shí)間intervalTime=fetch［k］.sendC-time － currentTime － fetch［k］.runTime。更新currentTime+=2* fetch［k］.runTime+intervalTime;則適應(yīng)度函數(shù)值 OBJECTIVE［i］ =currentTime。

2.4 選擇操作

實(shí)現(xiàn)步驟如下:

Step 4 采用模擬賭盤［10］操作(即生成0到1之間的隨機(jī)數(shù)r與每個(gè)個(gè)體遺傳到下一代群體的概率進(jìn)行匹配)。若r∈［qi－1，qr］，則選擇個(gè)體xi，(i=1，2，…，M)，q0=0，來(lái)確定各個(gè)個(gè)體是否遺傳到下一代群體中。

2.5 變異操作

本問(wèn)題是符號(hào)編碼，編碼字符集為 {1，2，3，4，…，n}，變異操作就是用這個(gè)字符集中的一個(gè)隨機(jī)指定的且與原基因值不相同的符號(hào)去替換變異點(diǎn)上的原有符號(hào)。具體步驟如下:

Step 1 遍歷所有個(gè)體，如果myu()產(chǎn)生的(0，1)區(qū)間的隨機(jī)數(shù)小于變異概率P_MUTATION，則隨機(jī)產(chǎn)生(0，N)(N為作業(yè)地點(diǎn)數(shù))的2個(gè)位置;

Step 2 用shuffle()交換2個(gè)位置，更新適應(yīng)度函數(shù)值OBJECTIVE［i］。

2.6 進(jìn)化策略

為使遺傳進(jìn)化過(guò)程能夠不斷向理想的優(yōu)化方向前進(jìn)，本算法綜合采用如下控制性進(jìn)化策略。evaluation()遍歷所有個(gè)體，找到適應(yīng)度函數(shù)值OBJECTIVE［i］最小的個(gè)體(取送車問(wèn)題的目標(biāo)是取送作業(yè)過(guò)程花費(fèi)最短)，將此個(gè)體始終放在種群的第1位。

2.7 終止準(zhǔn)則

采用目標(biāo)值變化控制準(zhǔn)則，當(dāng)連續(xù)G代個(gè)體最優(yōu)目標(biāo)函數(shù)值不發(fā)生變化時(shí)，終止算法。

3 算例分析

鐵路某車站連接專用線8條(分別編號(hào)1，2，…，8)，該站僅有一臺(tái)調(diào)車機(jī)車擔(dān)當(dāng)取送作業(yè)，各作業(yè)地點(diǎn)的機(jī)車走行時(shí)間、貨物作業(yè)時(shí)間已知，如表1所示，要求確定最合理的取送車順序，使從送車開(kāi)始到取車完了的時(shí)間最小。

表1 各作業(yè)地點(diǎn)走行時(shí)間和作業(yè)時(shí)間Table 1 Running and operating time of each private line min

應(yīng)用上述遺傳算法，種群規(guī)模:N=30，變異概率:Pm=0.01，最大終止代數(shù):100。經(jīng)過(guò)多次迭代，得到的最佳送車順序:4 8 5 3 6 1 7 2，取車順序:8 4 5 6 3 1 7 2。從送車開(kāi)始到取車完畢的時(shí)間為400 min，調(diào)車機(jī)車等待裝卸的取送中斷時(shí)間t中斷=0 min，計(jì)算過(guò)程及結(jié)果表明算法的效果較好。

4 結(jié)論

放射形專用線直達(dá)車流取送車順序優(yōu)化，能減少貨車周轉(zhuǎn)時(shí)間，壓縮作業(yè)車待送、待取等非生產(chǎn)性停留時(shí)間，因而對(duì)本問(wèn)題的研究具有重要意義。由于問(wèn)題本身的NP性質(zhì)，當(dāng)作業(yè)點(diǎn)數(shù)較多，規(guī)模較大時(shí)，組合方案數(shù)急劇增長(zhǎng)，文獻(xiàn)［5］采用的窮舉搜索算法將難以實(shí)現(xiàn)。本文根據(jù)取送車作業(yè)特點(diǎn)，利用遺傳算法的原理和方法，對(duì)最佳取送順序進(jìn)行了具體的算法設(shè)計(jì)，并編程運(yùn)算，算例表明在貨物作業(yè)地點(diǎn)較多時(shí)，可以獲得較好的效果。

［1］宋建業(yè)，謝金寶.鐵路行車組織基礎(chǔ)［M］.北京:中國(guó)鐵道出版社，2006.

SONG Jian-ye，XIE Jin-bao.Organization of train operation［M］.Beijing:China Railway Publishing House，2006.

［2］朱昌鋒.基于Cross－efficiency DEA的中間站運(yùn)營(yíng)績(jī)效分析［J］.鐵道科學(xué)與工程學(xué)報(bào)，2010，7(6):95－98.

ZHU Chang-feng.Analysis of operation efficiency for railway intermediary stations based on Cross－efficiency DEA［J］.Journal of Railway Science and Engineering，2010，7(6):95－98.

［3］朱昌鋒.鐵路生產(chǎn)力布局調(diào)整背景下運(yùn)到期限計(jì)算方法的改進(jìn)［J］.鐵道科學(xué)與工程學(xué)報(bào)，2010，7(4):111－115.

ZHU Chang-feng.A study of time limit of freight transport calculating method under adjusting of railway productivity distributing condition［J］.Journal of Railway Science and Engineering，2010，7(4):111 －115.

［4］陳伯羽.鐵路編組場(chǎng)線路固定使用方案優(yōu)選方法研究［J］.鐵道科學(xué)與工程學(xué)報(bào)，2006，3(6):80 －82.

CHEN Bo-yu.Studying of optimization of fixed usage plan for railway marshalling yard tracks［J］.Journal of Railway Science and Engineering，2006，3(6):80 －82.

［5］徐忠民，孔慶鈐.直達(dá)列車取送順序的優(yōu)化［J］.北方交通大學(xué)學(xué)報(bào)，1988(2):70－74.

XU Zhong-min，KONG Qing-qian.Optimization of sequencing for placing－in and taking－out of wagon groups of through goods train［J］.Journal of Beifang Jiaotong U-niversity，1988(2):70－74.

［6］宋建業(yè).直達(dá)列車多點(diǎn)裝卸取送順序優(yōu)化的表上移動(dòng)法［J］.蘭州鐵道學(xué)院學(xué)報(bào):自然科學(xué)版，2002(1):76－79.

SONG Jian-ye.Method for optimization of car－groupsending－and－fetching schedule［J］.Journal of Lanzhou Railway Institute:Natural Science Edition，2002(1):76－79.

［7］李文權(quán).放射狀專用線直達(dá)列車取送車問(wèn)題的算法［J］.西南交通大學(xué)學(xué)報(bào)，1995(5):503 －508.

LI Wen-quan.An algorithm for the problem of fetching and delivering vehicles of through－running train on radial individual line［J］.Journal of Southwest Jiaotong U-niversity，1995(5):503 －508.

［8］王慈光.放射形專用線非直達(dá)車流取送車問(wèn)題研究［J］.交通運(yùn)輸工程與信息學(xué)報(bào)，2006，4(3):16 －23.

WANG Ci-guang.Study of collection and delivery shunting of non－through wagon flow on actinoid private line［J］.Journal of Transportation Engineering and Information，2006，4(3):16 －23.

［9］牟 峰，王慈光，楊運(yùn)貴.放射形專用線非直達(dá)車流取送車模型及算法［J］.鐵道學(xué)報(bào)，2009(3):2－5.

MU Feng，WANG Ci-guang，YANG Yun-gui.Model and algorithm of taking－out and placing－in shunting of non－ through wagon flow on actinoid private lines［J］.Journal of the China Railway Society，2009(3):2 －5.

［10］玄光男，程潤(rùn)偉.遺傳算法與工程優(yōu)化［M］.北京:清華大學(xué)出版社，2004.

GEN Mitsuo，CHEN Run-wei.Genetic algorithms and engineering optimization［M］.Beijing:Tsinghua University Press，2004.

Study of through wagon flow on single－parent genetic algorithm for railway placing－in and taking－out of wagons in actinoid private line

LI Hai-jun，ZHU Chang-feng

(School of Traffic and Transportation，Lanzhou Jiaotong University，Lanzhou 730070，China)

Optimal order of placing－ in and taking－ out of wagons is in favour of reducing wagons non－productivity time in station and accelerating wagons turnaround.According to the analysis of characteristics of the operations on placing－ in and taking－ out of wagons in actinoid private line，this paper proposed a chromosome presentation and realized the genetic algorithm for the problem.Combined with an example，the results illustrated that this algorithm could find the optimal or nearly optimal solution to the placing－ in and taking－ out of wagons in actinoid private line problem effectively.

actinoid private line;operations on placing－ in and taking－ out of wagons;through wagon flow;single－parent genetic algorithm

U291.2

A

1672－7029(2011)06－0114－04

2011－11－25

教育部“春暉計(jì)劃”資助項(xiàng)目(Z2005－1－62008);蘭州交通大學(xué)青年科學(xué)研究基金項(xiàng)目

李海軍(1978－)，男，青海樂(lè)都人，講師，博士研究生，從事交通運(yùn)輸系統(tǒng)優(yōu)化研究