潘東亮

（神華包神鐵路有限責(zé)任公司 科技信息部，包頭 014014）

專用線取送車作業(yè)是鐵路貨運(yùn)站的一項(xiàng)重要工作內(nèi)容。合理地安排取送車順序，有利于加速車輛的周轉(zhuǎn)，縮短車輛的非生產(chǎn)停留時(shí)間，從而有效地提高鐵路貨物運(yùn)輸?shù)男?。對于求解樹枝型專用線取送車優(yōu)化問題，提出了很多方法，也取得了一定的成果，其中遺傳算法的貢獻(xiàn)尤為顯著。遺傳算法（Genetic Algorithm-GA）是借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。遺傳算法作為一種搜索算法有著無可比擬的優(yōu)點(diǎn)，表現(xiàn)在魯棒性強(qiáng)、全局搜索、并行性和高效性。

（1）文獻(xiàn)[1]和文獻(xiàn)[2]將取送車作業(yè)問題轉(zhuǎn)化成旅行商問題，以調(diào)車機(jī)車行走時(shí)間最短為優(yōu)化目標(biāo)，采用固定的交叉概率和變異概率，降低了搜索到問題最優(yōu)解的效率；

（2）文獻(xiàn)[3]和文獻(xiàn)[4]利用哈密爾頓圖求解樹枝型專用線取送問題，該方法簡單直觀，但是當(dāng)問題的規(guī)模較大時(shí)，卻難以找到最優(yōu)解；

（3）文獻(xiàn)[5]以調(diào)車機(jī)車在整個(gè)取送作業(yè)中總耗時(shí)最少為最優(yōu)目標(biāo)，提高了鐵路貨物運(yùn)輸?shù)男剩侵磺蟮昧怂蛙図樞?，沒有求得取車順序，當(dāng)以調(diào)車機(jī)車在整個(gè)取送車作業(yè)中總耗時(shí)最少為最優(yōu)目標(biāo)時(shí)，取車順序不是簡單地由送車順序決定的，取車順序與裝卸車時(shí)間有很大的關(guān)系。

上述文獻(xiàn)都將取車作業(yè)和送車作業(yè)分離開，沒有把它們看成是一個(gè)完整的作業(yè)，這樣不利于合理地安排取送車計(jì)劃。結(jié)合以上文獻(xiàn)的成果，對樹枝型專用線取送車問題進(jìn)行了更深一步的研究，將取送車作業(yè)看成是一個(gè)完整的作業(yè)，不但得到送車順序，而且得到取車順序，同時(shí)建立了以調(diào)車機(jī)車在整個(gè)取送車作業(yè)中總耗時(shí)最少為最優(yōu)目標(biāo)的數(shù)學(xué)模型。采用改進(jìn)的遺傳算法求解該問題，能夠得到合理的取送車順序，從而得到問題的最優(yōu)解或近似最優(yōu)解。

1 樹枝型專用線取送車問題的描述

1.1 樹枝型專用線取送車的特點(diǎn)

樹枝型專用線取送車作業(yè)的特點(diǎn)是：調(diào)車機(jī)車向某一專用線送取車完成之后不必返回車站，就能去其他專用線送取車，各專用線車輛的入線時(shí)刻不同，取回站內(nèi)的時(shí)刻相同。本文討論的樹枝型專用線如圖1。

圖1 樹枝型專用線布置示意圖

圖1中V0代表調(diào)車機(jī)車的出發(fā)點(diǎn)和終點(diǎn)，Vi（i=1, 2,……, 8）代表各專用線的作業(yè)地點(diǎn)，ti（i=1, 2, ……, 15）代表調(diào)車機(jī)車在各路段的行走時(shí)間，這是已知的條件。由于現(xiàn)實(shí)中的取送車作業(yè)還受人為、天氣等眾多因素所影響，為了便于問題的討論，還需做如下假設(shè)：

（1）送往各專用線車輛的作業(yè)時(shí)間是已知的，其他輔助作業(yè)時(shí)間忽略不計(jì)；（2）有且僅有一輛調(diào)車機(jī)車負(fù)責(zé)一次取送車作業(yè)。

1.2 樹枝型專用線取送車數(shù)學(xué)模型

數(shù)學(xué)模型建立的好壞直接影響到是否能正確地搜索到問題的最優(yōu)解。本文追求的最優(yōu)目標(biāo)是調(diào)車機(jī)車在一次作業(yè)中耗時(shí)最少，將取送作業(yè)看成是一次完整的作業(yè)，所以調(diào)車機(jī)車在一次作業(yè)中的耗時(shí)由送取車時(shí)間和等待完成作業(yè)時(shí)間決定，由此得到樹枝型專用線取送車數(shù)學(xué)模型：

其中，tij代表調(diào)車機(jī)車從專用線i到專用線j的行走時(shí)間（i=0, 1, 2,……, n；j=0,1, 2,……, n；n代表專用線），由于調(diào)車機(jī)車從站內(nèi)出發(fā)，最后回到站內(nèi)，所以一共有2n+1項(xiàng)tij，這樣就能保證把送往各專用線的車輛都能取回；tn'代表等待作業(yè)完成時(shí)間。設(shè)tn代表調(diào)車機(jī)車第2次到達(dá)專用線n與第1次到達(dá)專用線n的時(shí)間差，tn''代表調(diào)車機(jī)車第2次到達(dá)專用線n用的時(shí)間，tn'代表調(diào)車機(jī)車第1次到達(dá)專用線n用的時(shí)間，Tn代表專用線n的作業(yè)時(shí)間，則有如下關(guān)系：

如果Tn>tn，則調(diào)車機(jī)車取回專用線n的車輛時(shí)，等待作業(yè)完成時(shí)間公式如下：

如果Tn

2 改進(jìn)的遺傳算法求解樹枝型專用線取送車問題

2.1 初始種群的生成

用（0,a1, a2,……, an-1,an, a1, a2,……, an-1, an,0）表示一條染色體，基因ai（i=1, 2, ……, n）為[1, n]之間互不重復(fù)的自然數(shù)，代表專用線。例如：染色體（0, 1, 2, 3, 2, 3, 1, 0），第1個(gè)0代表調(diào)車機(jī)車從站內(nèi)出發(fā)開始作業(yè)，第2個(gè)0代表調(diào)車機(jī)車完成作業(yè)回到站內(nèi)；第1個(gè)1代表調(diào)車機(jī)車將車輛送到專用線1，第2個(gè)1代表調(diào)車機(jī)車將車輛從專用線1取回，那么這條染色體的送車順序就是1、2、3，取車順序是2、3、1。

由于遺傳算法的初始種群隨機(jī)產(chǎn)生，優(yōu)良染色體較少，極大地降低了算法的搜索效率。為提高算法的搜索效率，算法按照以下步驟生成染色體。

（1）送車時(shí)將作業(yè)量大的專用線盡量排在前面，作業(yè)量小的專用線排在后面；取車時(shí)將作業(yè)量小的專用線盡量排在前面，作業(yè)量大的專用線排在后面，減少調(diào)車機(jī)車的等待時(shí)間。

（2）設(shè)種群規(guī)模為M，則產(chǎn)生2 M個(gè)染色體，計(jì)算每條染色體的適應(yīng)度，按照適應(yīng)度大小將2 M個(gè)染色體進(jìn)行排序，保留前M個(gè)染色體作為初始種群，淘汰后M個(gè)染色體。

2.2 適應(yīng)度函數(shù)

在遺傳算法中，用適應(yīng)度來確定某個(gè)體能進(jìn)行遺傳操作的概率。適應(yīng)度較大的個(gè)體遺傳到下一代的概率大，而適應(yīng)度較小的個(gè)體遺傳到下一代的概率就小。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。本文求解的最優(yōu)目標(biāo)是調(diào)車機(jī)車在一次作業(yè)中耗時(shí)最少，所以適應(yīng)度函數(shù)f(x)為：

2.3 遺傳操作

2.3.1 選擇運(yùn)算

選擇運(yùn)算采用精英比例選擇。記憶當(dāng)前最優(yōu)的個(gè)體，用它來替換本代群體經(jīng)過交叉、變異后適應(yīng)度最低的個(gè)體，對其他群體進(jìn)行比例選擇運(yùn)算。這種選擇運(yùn)算的優(yōu)勢是個(gè)體適應(yīng)度大小與個(gè)體被選擇的概率成正比，利于種群的優(yōu)化，能保證搜索到問題的最優(yōu)解。

2.3.2 交叉運(yùn)算

交叉運(yùn)算采用兩點(diǎn)交叉。在（1，染色體長度-2）之間隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，交換待交叉兩條染色體兩個(gè)交叉點(diǎn)之間的基因，得到兩條新的染色體。判斷新的染色體是否合法，如果合法進(jìn)入后續(xù)的運(yùn)算；不合法將兩條新的染色體調(diào)整成合法的染色體，進(jìn)入后續(xù)的運(yùn)算。本文采用自適應(yīng)的交叉概率。設(shè)f為某條染色體的適應(yīng)度，favg為種群的平均適應(yīng)度，隨機(jī)產(chǎn)生（0,1）之間的小數(shù)r1，（0.5, 1.0）之間的小數(shù)r2。

（1）當(dāng)f≥favg，r1r2，染色體不參加交叉運(yùn)算；

（2）當(dāng)fr2時(shí)，染色體參加交叉運(yùn)算，r1

染色體采用自然數(shù)編碼，交叉運(yùn)算容易產(chǎn)生非法染色體，但是交叉運(yùn)算能產(chǎn)生很多新的染色體，極大地維護(hù)了種群的多樣性，為更新種群、搜索到最優(yōu)解做出了巨大貢獻(xiàn)。設(shè)待交叉的兩條染色體為A、B，交叉后的染色體為A'、B'，交叉點(diǎn)為3和6，交叉結(jié)果如下：

A'（0,1,3,4,5,2,1,4,5,2,3,0）B'（0,3,1,2,5,4,1,3,5,2,4,0）

A（0,1,3,2,5,4,1,4,5,2,3,0）B（0,3,1,4,5,2,1,3,5,2,4,0）

2.3.3 變異運(yùn)算

變異運(yùn)算采用基本位變異。本文采用固定的變異概率。如果是取送結(jié)合的作業(yè)方式，在（1，染色體長度-2）之間隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，交換兩點(diǎn)的基因。設(shè)待變異的染色體為A，變異后的染色體為A'，變異點(diǎn)為2和6，變異結(jié)果如下：

如果是取送分離的作業(yè)方式，則隨機(jī)產(chǎn)生（0,1）之間的小數(shù)r1，當(dāng)r1≥0.5時(shí)，兩個(gè)變異點(diǎn)在（1，染色體長度/2-1）之間產(chǎn)生；當(dāng)r1<0.5時(shí)，兩個(gè)變異點(diǎn)在（染色體長度/2，染色體長度-2）之間產(chǎn)生，然后按照取送結(jié)合的變異方式進(jìn)行變異。

2.4 算法流程圖

按照改進(jìn)的遺傳算法，可以解決樹枝型專用線取送車優(yōu)化問題，算法流程圖如圖2。

圖2 算法流程圖

3 仿真實(shí)驗(yàn)與結(jié)果分析

假設(shè)某車站銜接樹枝型專用線7條，且該站僅有一臺調(diào)車機(jī)車擔(dān)當(dāng)取送車作業(yè)?，F(xiàn)有一批列車組要送往各專用線進(jìn)行作業(yè)，各專用線作業(yè)完成之后，調(diào)車機(jī)車要將列車取回，同時(shí)回到出發(fā)點(diǎn)。已知調(diào)車機(jī)車到各專用線的走行時(shí)間，如表1所示。各專用線的作業(yè)時(shí)間如表2所示。

表1 調(diào)車機(jī)車到各專用線的走行時(shí)間

表2 專用線作業(yè)時(shí)間

利用遺傳算法和本文提出的改進(jìn)遺傳算法分別求解樹枝型專用線取送車優(yōu)化問題，要求確定合理的取送車順序，使得調(diào)車機(jī)車在一次完整的作業(yè)中（包括取和送）耗時(shí)最少。設(shè)種群規(guī)模為50，進(jìn)化代數(shù)為100，改進(jìn)的遺傳算法采用本文提出的自適應(yīng)交叉概率，遺傳算法的交叉概率為0.8，變異概率都為0.02，對取送車分離的作業(yè)方式分別進(jìn)行100次實(shí)驗(yàn)，算法效果對比如表3所示。

表3 兩種算法對比圖

由表3可以看出改進(jìn)的遺傳算法搜索效率和準(zhǔn)確率明顯優(yōu)于遺傳算法，驗(yàn)證了改進(jìn)算法的有效性。利用改進(jìn)的遺傳算法求得調(diào)車機(jī)車在一次完整的作業(yè)中最少的耗時(shí)為280，同時(shí)得到多條最優(yōu)取送車順序，記錄了其中的10條最優(yōu)取送車順序，如表4所示，作業(yè)時(shí)間包括機(jī)車取送車走行時(shí)間和等待作業(yè)完成時(shí)間。

由表4可以看出，雖然10種不同的取送車計(jì)劃都能使調(diào)車機(jī)車在一次完整的作業(yè)中耗時(shí)最少，但是機(jī)車的走行時(shí)間卻不完全相同。如果不但追求調(diào)車機(jī)車在一次完整的作業(yè)中耗時(shí)最少，而且希望機(jī)車的走行時(shí)間最少，則可以選擇方案8和方案10；還可以根據(jù)專用線的具體情況選擇不同的方案，因此利用改進(jìn)的遺傳算法求解樹枝型專用線取送車優(yōu)化問題利于鐵路貨運(yùn)站效率的提高。

表4 最優(yōu)的取送車順序

4 結(jié)束語

本文結(jié)合樹枝型鐵路專用線取送車的作業(yè)特點(diǎn)，建立了取送結(jié)合的作業(yè)模型，而不同于以往研究者只單方面研究送車作業(yè)或者取車作業(yè)。取送結(jié)合的作業(yè)方式符合現(xiàn)代鐵路運(yùn)輸?shù)男枨?，同時(shí)有利于加速車輛的周轉(zhuǎn)，縮短了車輛的非生產(chǎn)停留時(shí)間。本文改進(jìn)的遺傳算法提高初始種群的適應(yīng)度，優(yōu)良的個(gè)體在種群中被遺傳的概率大，不良的個(gè)體被遺傳的概率小，從而提高了算法的搜索效率。仿真實(shí)驗(yàn)驗(yàn)證了模型和算法的優(yōu)越性。由此可見，利用改進(jìn)的遺傳算法求解樹枝型專用線取送車優(yōu)化問題有較大的潛力。

[1]雷友誠，涂祖耀．基于遺傳蟻群算法的樹枝型鐵路取送車問題優(yōu)化[J].中南大學(xué)學(xué)報(bào)，2011，42（8）：2356-2362．

[2]楊運(yùn)貴，王慈光．樹枝行鐵路專用線取送車問題的遺傳算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2008，44（12）：210-211．

[3]張 健，宋建業(yè). 貨物作業(yè)車取送模型的優(yōu)化[J]. 鐵道貨運(yùn)，2008，26（10）.

[4]余少鶴，李夏苗. 貨物作業(yè)車取送模型及算法研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2002，24（12）：46-48.

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

[6]楊 浩. 鐵路運(yùn)輸組織學(xué)[M]. 北京：中國鐵道出版社，2006：157-163.

[7]周 明，孫樹棟. 遺傳算法原理及應(yīng)用[M]. 北京：國防工業(yè)出版社，1998：11-24.