放射形鐵路專用線直達車流取送車問題的單親遺傳算法研究＊

李海軍，朱昌鋒

(蘭州交通大學交通運輸學院，甘肅蘭州 730070)

放射形鐵路專用線直達車流取送車問題的單親遺傳算法研究＊

李海軍，朱昌鋒

(蘭州交通大學交通運輸學院，甘肅蘭州 730070)

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

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

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

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

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

1 建立模型

1.1 問題的提出

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

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

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

1.2 模型建立

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

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

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

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

2 算法設計

2.1 編碼表示

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

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

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

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

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

2.3 適應度函數(shù)的設計

取送車問題的適應度函數(shù)計算算法如下:

Step 1 初始化currentTime，intervalTime= 0;

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

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

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

2.4 選擇操作

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

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

2.5 變異操作

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

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

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

2.6 進化策略

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

2.7 終止準則

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

3 算例分析

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

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

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

4 結(jié)論

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

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

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

［2］朱昌鋒.基于Cross－efficiency DEA的中間站運營績效分析［J］.鐵道科學與工程學報，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)整背景下運到期限計算方法的改進［J］.鐵道科學與工程學報，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］陳伯羽.鐵路編組場線路固定使用方案優(yōu)選方法研究［J］.鐵道科學與工程學報，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］徐忠民，孔慶鈐.直達列車取送順序的優(yōu)化［J］.北方交通大學學報，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è).直達列車多點裝卸取送順序優(yōu)化的表上移動法［J］.蘭州鐵道學院學報:自然科學版，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).放射狀專用線直達列車取送車問題的算法［J］.西南交通大學學報，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］王慈光.放射形專用線非直達車流取送車問題研究［J］.交通運輸工程與信息學報，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］牟 峰，王慈光，楊運貴.放射形專用線非直達車流取送車模型及算法［J］.鐵道學報，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］玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京:清華大學出版社，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

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

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