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

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

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

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

1 取送車的問題描述

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

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

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

1.2 數(shù)學模型

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

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

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

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

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

(2) 約束條件。

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

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

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

3 GACA算法設計

3.1 GACA算法中遺傳算法的設計

3.1.1 染色體編碼

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

3.1.2 初始種群生成

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

3.1.3 適應度評估

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

3.1.4 自然選擇

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

3.1.5 交叉重組

在選擇操作之后，根據(jù)選擇概率Pc選擇個體進行交叉重組。交叉規(guī)則采用PMX法[12]，處理方法如下：設父代的2個染色體為Ga=(0 8 4 5 6 7 1 3 2 0)，Gb=(0 7 8 1 2 3 5 4 6 0)。隨機選擇交配區(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)了進化過程中的遺傳功能。

3.1.6 變異算子

根據(jù)變異概率PM對染色體進行變異操作，取送車問題要求在同一路徑中不能有重復的作業(yè)點(開始結點和終止結點除外)。一般的變異算子可能會導致非法路徑產(chǎ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)化解轉換的信息素值。

3.3 GACA算法中蟻群算法的設計

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

(1) 充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)的解，在每次循環(huán)之后，只有1只螞蟻進行信息素更新。這只螞蟻可能是找出當前循環(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ù)狀態(tài)轉移規(guī)則來選擇下一作業(yè)點。在路徑建立過程中，螞蟻通過應用局部更新來修改已訪問路徑上的信息素量。一旦螞蟻都完成了它們的路徑，應用全局更新規(guī)則再次對路徑上的信息素量進行修改。信息素值全局更新和局部更新規(guī)則如下。

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

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

上述規(guī)則被稱為偽隨機比例規(guī)則。其中，q為在[0，1]區(qū)間均勻分布的隨機數(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表示機車在作業(yè)點i和j間的走行時間。

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

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

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

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

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

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

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

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

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

4 實例計算與結果分析

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

分別運用標準蟻群算法(ACA)和遺傳蟻群算法(GACA)對上例問題進行仿真，各自獨立運行20次。用15個互不重復的0～14的自然數(shù)構建1個染色體，表示1種送車方案。GACA算法的參數(shù)設置包括：限定總迭代次數(shù)NCmax=200為結束條件，遺傳算法迭代次數(shù)為80(固定)，群體規(guī)模N=50，PC=95%，PM=5%。蟻群算法中各路徑信息素初值τC設為60，τG=2，轉移概率公式中α=1，β=5。軌跡更新公式中ρ=0.7，Q=1 000。ACA算法中的參數(shù)設置同GACA算法中的蟻群部分。運用MATLAB語言上機求解，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)化逼近過程的對比仿真結果如圖4所示。記錄在GACA算法每個階段的優(yōu)化解分布如表2所示。

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

為驗證 GACA算法在大規(guī)模取送車作業(yè)問題上應用的可行性，分別運用標準蟻群算法(ACA)和遺傳蟻群算法(GACA)對裝卸點大規(guī)模增加的情況進行仿真，對比結果如表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)解演化對比結果Fig.4 Comparison of optimal solution between GACA and ACA

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

5 結論

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

(2) 遺傳算法與蟻群算法結合后，在算法的收斂速度加快的同時，蟻群算法中的參數(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]. 西南交通大學學報, 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)濟, 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]. 成都大學學報:自然科學版, 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] 潘靈巧, 林志安. 關于樹枝型專用線取送車問題的探討[J].內(nèi)蒙古科技與經(jīng)濟, 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]. 中國鐵道科學, 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]. 計算機工程與應用, 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] 李智. 基于改進型蟻群算法的貨物作業(yè)車取送模型優(yōu)化[J].鐵道運輸與經(jīng)濟, 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] 李敏強, 徐博藝, 寇紀松. 遺傳算法與神經(jīng)網(wǎng)絡的結合[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]. 計算機研究與發(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]. 計算機工程與應用, 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] 余伶俐, 蔡自興. 改進混合離散粒子群的多種優(yōu)化策略算法[J].中南大學學報: 自然科學版, 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.