基于遺傳蟻群算法的樹枝型鐵路取送車問題優(yōu)化

雷友誠 ，涂祖耀，桂衛(wèi)華，吳志飛，閆福全

(1．中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083；2．湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長沙，410082)

取送車作業(yè)是企業(yè)鐵路貨運站的一項重要工作，對取送車作業(yè)的調(diào)度安排進(jìn)行科學(xué)優(yōu)化可以有效壓縮車輛在貨運站的停留時間，提高企業(yè)鐵路運輸效率，降低企業(yè)鐵路運營成本。取送車問題按專用線布置形式的不同通常分為放射型(或稱為扇形)和樹枝型兩大類[1]。本文主要對樹枝型專用線取送車問題進(jìn)行討論。文獻(xiàn)[2]建立了該問題的樹形結(jié)構(gòu)模型并提出3個優(yōu)化目標(biāo)；文獻(xiàn)[3]將其歸納為旅行商問題，提出了一種啟發(fā)式節(jié)約算法；文獻(xiàn)[4]將其等同為機(jī)器排序問題求解；文獻(xiàn)[5]將其抽象為線性矩陣并用模擬退火算法求解；文獻(xiàn)[6]運用圖論中的漢密爾頓圖將其轉(zhuǎn)化為求權(quán)值最小的漢密爾頓回路問題；文獻(xiàn)[7?8]根據(jù)TSP模型分別用遺傳算法和蟻群算法求解該問題。這些算法模型成熟可行，但隨著裝卸作業(yè)點的增加，問題求解耗時且難度加大，容易產(chǎn)生組合爆炸。本文作者采用一種遺傳算法和蟻群算法融合的遺傳蟻群算法(GACA)，針對大型企業(yè)自備鐵路樹枝形專用線的大規(guī)模取送車作業(yè)問題進(jìn)行優(yōu)化研究，并對算法實現(xiàn)和結(jié)果進(jìn)行了分析。

1 取送車的問題描述

1.1 企業(yè)樹枝型專用線鐵路取送車作業(yè)特點

列車在運達(dá)鐵路貨運站完成解體作業(yè)后會停在編組站上，等待通過軌道衡檢斤并前往各條專用線執(zhí)行裝卸貨任務(wù)，作業(yè)完畢后再原路返回出發(fā)軌道集結(jié)編組，因而存在取送車作業(yè)。樹枝形鐵路專用線的特點是：在一批作業(yè)中間調(diào)車機(jī)車不用返回編組站，各專用線入線時間不同，但取回時間相同，所以，宜采取連送帶取作業(yè)方式。某企業(yè)鐵路貨運站樹枝型鐵路專用線分布如圖1所示。圖中，V0代表編組站即調(diào)車機(jī)車的出發(fā)點，V1～V6代表各專用線的裝卸貨場，路段上的數(shù)字表示調(diào)車機(jī)車在專用線各路段的走行時間。

圖1 樹枝形鐵路專用線布置示意圖(單位：mm)Fig.1 Sketch map of branch-shaped railway sidings

1.2 數(shù)學(xué)模型

在圖1中，將機(jī)車走行路線上的時間權(quán)值加總即得漢密爾頓圖中的各邊權(quán)值，由此得到轉(zhuǎn)化的漢密爾頓圖[6]，如圖2所示。

圖2 樹枝型專用線的漢密爾頓圖Fig.2 Hamilton graph of branch-shaped railway sidings

已知編組場只有1臺調(diào)機(jī)，調(diào)車機(jī)車向各專用線的裝卸作業(yè)點送車，并且規(guī)定僅經(jīng)過每個作業(yè)點1次，最后調(diào)機(jī)返回編組站。這里只討論送車順序，因為送車順序決定了取車順序，調(diào)車機(jī)車送完車回到編組站再沿著已經(jīng)搜索到的最優(yōu)路徑進(jìn)行取車作業(yè)。由以上分析知本問題變成旅行商問題，即在賦權(quán)無向圖G中找到調(diào)機(jī)總走行時間最少的漢密爾頓回路。于是，把問題構(gòu)造成網(wǎng)絡(luò)圖[3]，以G=[V，A，C]表示。其中：V={0，1，…，n}表示調(diào)機(jī)要經(jīng)過的作業(yè)點，V0為編組站；A={(i，j)|i，j=0，1，…，n，i≠j}表示調(diào)機(jī)可能走過線路段集合；C={cij(i，j)∈A}，cij表示調(diào)機(jī)經(jīng)過對應(yīng)弧段(i，j)所需時間，包括調(diào)機(jī)在(i，j)純走行時間及在(i，j)作業(yè)點進(jìn)行摘掛、對貨位等作業(yè)所需時間，通過寫實查定，這些時間標(biāo)準(zhǔn)是已知的。設(shè)變量：

以調(diào)車機(jī)車總行走時間t最小為優(yōu)化目標(biāo)，樹枝形鐵路專用線最優(yōu)取送順序問題的數(shù)學(xué)模型如下。

(1) 目標(biāo)函數(shù)，取送調(diào)車作業(yè)調(diào)機(jī)總走行時間t：

(2) 約束條件。

2 遺傳算法與蟻群算法融合的基本思想

取送車作業(yè)優(yōu)化問題屬于典型的NP完全問題，采用經(jīng)典的數(shù)學(xué)方法很難求出其精確解。遺傳算法(GA)具有快速的全局搜索能力，但同時它對系統(tǒng)中的反饋信息利用不夠，而且當(dāng)求解到一定范圍時往往進(jìn)行多余的冗余迭代，而使得求精確解效率低[9]。蟻群算法(ACA)具有分布、并行、全局收斂能力，但由于初期信息素匱乏，導(dǎo)致算法速度慢[10]。

將遺傳算法與蟻群算法的優(yōu)勢融合，形成遺傳蟻群算法(GACA)來有效解決取送車組合優(yōu)化問題。融合后的算法其基本思路是：首先利用遺傳算法的隨機(jī)搜索、快速性、全局收斂性等特點，產(chǎn)生有關(guān)問題的初始信息素分布；然后，利用蟻群算法的并行性、正反饋機(jī)制以及求解效率高等特性求出精確解。這種融合后的遺傳蟻群算法比蟻群算法所用時間少、效率高，在求解效率上比遺傳算法的高。

3 GACA算法設(shè)計

3.1 GACA算法中遺傳算法的設(shè)計

3.1.1 染色體編碼

在進(jìn)行搜索之前，先將問題解數(shù)據(jù)表示成遺傳空間的基因型串?dāng)?shù)據(jù)結(jié)構(gòu)，每個基因代表1個序列編號。G＝(a0，a1，a2，…，an，a0)表示染色體，代表一個送車方案，其中基因ai(i=1，2，…，n)為 [1，n]之間的一個互不重復(fù)的自然數(shù)，它表示第ai個裝卸作業(yè)點在調(diào)車機(jī)車送車路徑中的順序為i。

3.1.2 初始種群生成

為了使取車的等待時間減少，在送車時盡量使裝卸量大的作業(yè)點排在送車順序的前面。借用輪盤賭[11]的思想生成新個體，先計算所有作業(yè)點的裝卸貨量的總和，再計算每個作業(yè)點裝卸貨量在總裝卸貨量所占的比例，所占比例高的作業(yè)點有較大的概率排在送車順序的前面，由此產(chǎn)生一組取送車方案Gj(j=1，2，…，k)。Gj各不相同，這k個染色體構(gòu)成第1代種群。

3.1.3 適應(yīng)度評估

適應(yīng)度函數(shù)采用取送車作業(yè)總時間t的倒數(shù)，即f=1/t。在算法前期，對一些適應(yīng)度較高的個體進(jìn)行控制，降低其適應(yīng)度，保持種群的多樣性，在算法后期對個體的適應(yīng)度適當(dāng)放大，提高個體之間的競爭性。

3.1.4 自然選擇

采用最優(yōu)保存的選擇策略，將每代種群按個體適應(yīng)度分為N1，N2和N3部分，適應(yīng)度最大的N1個個體直接復(fù)制到下一代群體，N2個中間個體進(jìn)行交叉變異，適應(yīng)度最小的N3個個體直接淘汰，并在一定概率上按啟發(fā)式知識產(chǎn)生N3個新個體以保持種群的規(guī)模。

3.1.5 交叉重組

在選擇操作之后，根據(jù)選擇概率Pc選擇個體進(jìn)行交叉重組。交叉規(guī)則采用PMX法[12]，處理方法如下：設(shè)父代的2個染色體為Ga=(0 8 4 5 6 7 1 3 2 0)，Gb=(0 7 8 1 2 3 5 4 6 0)。隨機(jī)選擇交配區(qū)域如下：Ga=(0 8 4 5|6 7 1|3 2 0)→Ga'=(0 8 4 1|2 3 5|7 6 0)，Gb=(0 7 8 1|2 3 5|4 6 0)→Gb'=(0 3 8 5|6 7 1|4 2 0)。

從上述變換可知：PMX交叉算子能夠有效地繼承雙親的部分基因成分，實現(xiàn)了進(jìn)化過程中的遺傳功能。

3.1.6 變異算子

根據(jù)變異概率PM對染色體進(jìn)行變異操作，取送車問題要求在同一路徑中不能有重復(fù)的作業(yè)點(開始結(jié)點和終止結(jié)點除外)。一般的變異算子可能會導(dǎo)致非法路徑產(chǎn)生，為了不引入非法路徑，本文選用逆轉(zhuǎn)變異[13]的優(yōu)化策略。

3.2 GACA算法中遺傳算法與蟻群算法的銜接

通過遺傳算法可以得到若干組優(yōu)化送車路徑，這些路徑?jīng)Q定了蟻群算法的初始信息素分布，在初始t0時刻，作業(yè)點(i，j)間的信息素生成規(guī)則如下：

其中，Gbetter為遺傳算法中得到若干組較優(yōu)送車路徑；τC為根據(jù)取送車作業(yè)優(yōu)化問題規(guī)模(如裝卸作業(yè)點數(shù)量)給定的一個信息素常數(shù)；τG為遺傳算法求解出的若干組優(yōu)化解轉(zhuǎn)換的信息素值。

3.3 GACA算法中蟻群算法的設(shè)計

在GACA算法中，蟻群算法采用最大?最小螞蟻系統(tǒng)[14]，該系統(tǒng)有以下2個特點：

(1) 充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)的解，在每次循環(huán)之后，只有1只螞蟻進(jìn)行信息素更新。這只螞蟻可能是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻(迭代最優(yōu)的螞蟻，Iteration-best ant)，也可能是找出從實驗開始以來最優(yōu)解的螞蟻(Global-best ant)。

(2) 為避免搜索的停滯，在每個解的元素(在TSP中是每條邊)上的信息素軌跡量的值域范圍被限制在區(qū)域[τmin，τmax]內(nèi)。

這種算法在防止算法過早停滯以及有效性方面較蟻群系統(tǒng)[15?18](Ant colony system, ACS)算法有較大的改進(jìn)。

在蟻群算法中，每個螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則來選擇下一作業(yè)點。在路徑建立過程中，螞蟻通過應(yīng)用局部更新來修改已訪問路徑上的信息素量。一旦螞蟻都完成了它們的路徑，應(yīng)用全局更新規(guī)則再次對路徑上的信息素量進(jìn)行修改。信息素值全局更新和局部更新規(guī)則如下。

3.3.1 狀態(tài)轉(zhuǎn)移規(guī)則

在t時刻，位于作業(yè)點i的第k只螞蟻選擇下一作業(yè)點j的規(guī)則及在作業(yè)點i和j間的轉(zhuǎn)移概率 )(tPk ij如下：

上述規(guī)則被稱為偽隨機(jī)比例規(guī)則。其中，q為在[0，1]區(qū)間均勻分布的隨機(jī)數(shù)；q0為參數(shù)(0≤q0≤1)，若q≤q0，則按先驗知識選擇路徑。τij(t)表示2個作業(yè)點i和j間的信息素值，α(α＞0)表示路徑軌跡的相對重要性，β(β＞0)表示路徑能見度的相對重要性，allowedk={0，1，…，n}表示螞蟻k下一步可以選擇的作業(yè)點集；ηij=1/dij表示邊(i，j)的能見度，dij表示機(jī)車在作業(yè)點i和j間的走行時間。

3.3.2 信息素的全局更新規(guī)則

在蟻群系統(tǒng)中，只有全局最優(yōu)的螞蟻才被允許釋放信息素，全局更新在所有螞蟻都完成它們的1次路徑搜索之后執(zhí)行，更新公式如下：

Δτij(t)表示在t時刻作業(yè)點i,j間信息素的增加量：

其中：ρ(0＜ρ＜1)表示信息素?fù)]發(fā)參數(shù)；Lbest為到目前為止找出的全局最優(yōu)路徑。由式(9)可知：只有那些屬于全局最優(yōu)路徑的邊上的信息素才會得到增強(qiáng)。

3.3.3 信息素的局部更新規(guī)則

在搜索路徑的同時，每只螞蟻應(yīng)用局部更新規(guī)則對它們經(jīng)過的邊進(jìn)行激素更新，更新公式如下：

其中：Q為螞蟻在經(jīng)過路徑(i，j)上釋放的每單位長度的信息素量，若螞蟻經(jīng)過路徑(i，j) ，則進(jìn)行信息素的更新。

綜上所述，用遺傳蟻群算法解決取送車調(diào)車作業(yè)優(yōu)化問題的流程如圖3所示。

圖3 遺傳蟻群算法的實現(xiàn)流程Fig.3 Procedure graph of GACA

4 實例計算與結(jié)果分析

已知某企業(yè)鐵路編組場(編號0)連接專用線14條(編號1～14)。該貨運站僅有1臺調(diào)車機(jī)車擔(dān)當(dāng)取送作業(yè)，現(xiàn)有14列車組要送往各專用線進(jìn)行裝卸作業(yè)，已知機(jī)車在編組站各作業(yè)點之間的走行時間Cij(見表1)。

分別運用標(biāo)準(zhǔn)蟻群算法(ACA)和遺傳蟻群算法(GACA)對上例問題進(jìn)行仿真，各自獨立運行20次。用15個互不重復(fù)的0～14的自然數(shù)構(gòu)建1個染色體，表示1種送車方案。GACA算法的參數(shù)設(shè)置包括：限定總迭代次數(shù)NCmax=200為結(jié)束條件，遺傳算法迭代次數(shù)為80(固定)，群體規(guī)模N=50，PC=95%，PM=5%。蟻群算法中各路徑信息素初值τC設(shè)為60，τG=2，轉(zhuǎn)移概率公式中α=1，β=5。軌跡更新公式中ρ=0.7，Q=1 000。ACA算法中的參數(shù)設(shè)置同GACA算法中的蟻群部分。運用MATLAB語言上機(jī)求解，GACA得到最優(yōu)的送車順序為 0—2—1—3—7—9—8—14—12—13—6—11—4—5—10—0,送車消耗總行走時分為1.035×104s≈173 min。最優(yōu)解優(yōu)化逼近過程的對比仿真結(jié)果如圖4所示。記錄在GACA算法每個階段的優(yōu)化解分布如表2所示。

從圖4和表2可知：蟻群算法(ACA)由于初期信息素不足，求解速度慢，搜索過早停滯；而GACA算法在經(jīng)歷了80代的遺傳算法快速全局搜索之后，蟻群算法再利用遺傳算法遺留的路徑信息素進(jìn)行分布式搜索，找到了更滿意的解。GACA算法由于在遺傳算法中使用基于知識的初始種群，不僅加快了蟻群算法的速度，而且以一定的概率收斂于最優(yōu)解；遺傳算法與蟻群算法的融合對蟻群算法中的參數(shù)調(diào)整大大減低，大大減少了盲目實驗的次數(shù)。

為驗證 GACA算法在大規(guī)模取送車作業(yè)問題上應(yīng)用的可行性，分別運用標(biāo)準(zhǔn)蟻群算法(ACA)和遺傳蟻群算法(GACA)對裝卸點大規(guī)模增加的情況進(jìn)行仿真，對比結(jié)果如表3所示。

由表3可以看出：隨著裝卸作業(yè)點個數(shù)的增加，GACA的尋優(yōu)性能明顯優(yōu)于 ACA，不僅收斂速度更快，而且找到的最優(yōu)解也更令人滿意。

表1 編組場與各作業(yè)點間的行走時間Table 1 Travel time between marshalling yard and operating points min

表2 GACA算法優(yōu)化解數(shù)據(jù)的逼近過程Table 2 Process of optimal data approximation of GACA algorithm min

圖4 GACA和ACA的最優(yōu)解演化對比結(jié)果Fig.4 Comparison of optimal solution between GACA and ACA

表3 算法規(guī)模擴(kuò)大時GACA和ACA的對比仿真結(jié)果Table 3 Comparison of simulation results between GACA and ACA when scale of algorithm increases

5 結(jié)論

(1) 經(jīng)過遺傳算法的初步搜索并生成初始信息素分布，增強(qiáng)了蟻群算法的正反饋機(jī)制，使得蟻群算法中的參數(shù)調(diào)整程度大大降低。

(2) 遺傳算法與蟻群算法結(jié)合后，在算法的收斂速度加快的同時，蟻群算法中的參數(shù)α，β和ρ對取送車問題規(guī)模變化的敏感度降低，提高了算法的魯棒性。

(3) 在蟻群算法階段使用最大?最小螞蟻系統(tǒng)(MMAS)，而且同時采用信息素的局部更新和全局更新規(guī)則，使得算法在一定程度上避免陷入局部最優(yōu)。

[1] 彭其淵, 王慈光.鐵路行車組織[M].北京: 中國鐵道出版社,2007: 62?63.PENG Qi-yuan, WANG Ci-guang. Train operation organization[M]. Beijing: China Railway Publishing House,2007: 62?63.

[2] 王慈光. 樹枝型專用線取送車問題的研究[J]. 西南交通大學(xué)學(xué)報, 1996, 31(6): 675?680.WANG Ci-guang. A study on placing-in and taking-out of wagons on brached-shaped sidings[J]. Journal of Southwest Jiaotong University, 1996, 31(6): 675?680.

[3] 余少鶴, 李夏苗. 貨物作業(yè)車取送車模型及算法研究[J]. 鐵道運輸與經(jīng)濟(jì), 2002, 24(12): 46?48.YU Shao-he, LI Xia-miao. The model of placing-in and taking-out for working wagons and the calculation methods[J].Railway Transport and Economy, 2002, 24(12): 46?48.

[4] 敬媛媛. 樹枝型專用線取送車算法的研究[J]. 成都大學(xué)學(xué)報:自然科學(xué)版, 1998, 17(4): 36?42.JING Yuan-yuan. A study on the sequence of placing-in and taking-out wagons of branch-shaped siding line[J]. Journal of Chengdu University: Natural Science Edition, 1998, 17(4):36?42.

[5] 潘靈巧, 林志安. 關(guān)于樹枝型專用線取送車問題的探討[J].內(nèi)蒙古科技與經(jīng)濟(jì), 2008(6): 288?289.PAN Ling-qiao, LIN Zhi-an. The discussion of the sequence of placing-in and taking-out wagons of branch-shaped siding line[J].Inner Mongolia Science Technology & Economy, 2008(6):288?289.

[6] 石紅國, 彭其淵, 郭寒英. 樹枝型專用線取送車問題的哈密爾頓圖解法[J]. 中國鐵道科學(xué), 2005, 26(2): 132?135.SHI Hong-guo, PENG Qi-yuan, GUO Han-yin. 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.

[7] 楊云貴, 王慈光, 薛峰. 樹枝型專用線取送車問題的遺傳算法研究[J]. 計算機(jī)工程與應(yīng)用, 2008, 44(12): 210?211.YANG Yun-gui, WANG Ci-guang. Study on genetic algorithm for railway placing-in and taking-out wagons in branch-shaped private silding[J]. Computer Engineering and Applications, 2008,44(12): 210?211.

[8] 李智. 基于改進(jìn)型蟻群算法的貨物作業(yè)車取送模型優(yōu)化[J].鐵道運輸與經(jīng)濟(jì), 2004, 26(4): 73?76.LI Zhi. Optimization of Placing-in and taking-out wagon operation model based on enhanced ant colony algorithm[J].Railway Transport and Economy, 2004, 26(4): 73?76.

[9] 李敏強(qiáng), 徐博藝, 寇紀(jì)松. 遺傳算法與神經(jīng)網(wǎng)絡(luò)的結(jié)合[J]. 系統(tǒng)工程與實踐, 1999, 19(2): 65?69.LI Ming-qiang, XU Bo-yi, KOU Ji-song. On the combination of genetic algorithms and neural networks[J]. Systems Engineering Theory & Practice, 1999, 19(2): 65?69.

[10] 吳慶洪, 張紀(jì)會, 徐心和. 具有變異特征的蟻群算法[J]. 計算機(jī)研究與發(fā)展, 1999, 36(10): 1240?1245.WU Qing-hong, ZHANG Ji-hui, XU Xin-he. An ant colony algorithm with mutation features[J]. Journal of Computer Research and Development, 1999, 36(10): 1240?1245.

[11] 陳有青, 徐蔡星, 鐘文亮, 等. 一種改進(jìn)選擇算子的遺傳算法[J]. 計算機(jī)工程與應(yīng)用, 2008, 44(2): 44?49.CHEN You-qing, XU Cai-xing, ZHONG Wen-liang, et al.Genetic algorithm with improved selection operator[J].Computer Engineering and Applications, 2008, 44(2): 44?49

[12] Goldberg D E, Jr Lingle R. Alleles, loci and the traveling salesman problem[C]//Second Int Conf on Genetic Algorithms and Their Applications Pittsburgh, 1985: 154?159.

[13] 余伶俐, 蔡自興. 改進(jìn)混合離散粒子群的多種優(yōu)化策略算法[J].中南大學(xué)學(xué)報: 自然科學(xué)版, 2009, 40(4): 1047?1053.YU Ling-li, CAI Zi-xing. Multiple optimization strategies for improving hybrid discrete particle swarm[J]. Journal of Central South University: Science and Technology, 2009, 40(4):1047?1053.

[14] Stutzle T, Hoos H H. MAX-MIN ant system[J]. Future Generation Computer System, 2000, 16(8): 889?914.

[15] Dorigo M, Gambardella Luca Maria. Ant colony: a cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary, 1997, 1(1): 53?66.

[16] Chang P C, Huang W H, Ting C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert Systems with Applications, 2010, 37:1863?1878.

[17] Lee Z J, Su S F, Chuang C C, et al. Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment[J]. Applied Soft Computing, 2008, 8: 55?78.

[18] Chen S M, Chien C Y. Parallelized genetic ant colony systems for solving the traveling salesman problem[J]. Expert Systems with Applications, 2011, 38: 3873?3883.