陳立云, 盧 昱, 晏 杰, 劉云龍

(1.軍械工程學(xué)院信息工程系,河北石家莊050003; 2.軍械工程學(xué)院,河北石家莊050003)

基于改進(jìn)遺傳算法的彈藥運(yùn)輸車輛調(diào)度問題研究

陳立云1, 盧 昱2, 晏 杰1, 劉云龍1

(1.軍械工程學(xué)院信息工程系,河北石家莊050003; 2.軍械工程學(xué)院,河北石家莊050003)

建立了彈藥運(yùn)輸車輛調(diào)度問題的數(shù)學(xué)模型,針對(duì)傳統(tǒng)遺傳算法求解該問題具有收斂速度慢、易陷入局部極小的缺點(diǎn),提出了一種改進(jìn)的遺傳算法予以求解。在改進(jìn)算法中引入一種基于信息素的遺傳交叉算子,該算子能利用以信息素形式保存的全局信息,從而提高收斂速度;算法中的變異算子采用Relocation、Exchange、2-opt*及2-opt 4種啟發(fā)式搜索算法,盡可能擴(kuò)大搜索范圍。算例分析表明了所提改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題的有效性和可行性。

彈藥運(yùn)輸;車輛調(diào)度;遺傳算法;信息素;交叉算子

戰(zhàn)時(shí)彈藥供應(yīng),是裝備物資供應(yīng)的重要組成部分,是裝備部門最主要的保障任務(wù)。在確定好彈藥分配后,運(yùn)輸車輛的優(yōu)化調(diào)度就成了縮短彈藥供應(yīng)時(shí)間、提高彈藥供應(yīng)效率的重要方法。彈藥運(yùn)輸車輛調(diào)度問題指的是對(duì)彈藥運(yùn)輸車輛確定適當(dāng)?shù)男熊嚶肪€,使它們有序地通過彈藥倉(cāng)庫(kù)及其保障的陣地,在滿足一定的約束條件下(如各個(gè)陣地的彈藥需求量、車輛容量限制、行駛單程限制、時(shí)間限制等),達(dá)到一定的目標(biāo)(如路程最短、時(shí)間盡量少等)。對(duì)于規(guī)模較大的彈藥運(yùn)輸車輛調(diào)度問題,精確求解變得非常困難,所以有必要尋求高效近似的優(yōu)化算法[1]。本文借鑒蟻群算法[2]中采用信息正反饋的機(jī)制,在遺傳算法[3]中引入一種新的基于信息素的遺傳交叉算子[4]1185,同時(shí),變異算子采用了Relocation、Exchange、2-opt*及2-opt 4種啟發(fā)式搜索算法。實(shí)驗(yàn)表明所提改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題的有效性和可行性。

1 彈藥運(yùn)輸車輛調(diào)度的問題描述與建模

彈藥運(yùn)輸車輛調(diào)度的問題可描述如下：假設(shè)在裝備保障地域有1個(gè)彈藥倉(cāng)庫(kù),倉(cāng)庫(kù)共有K輛運(yùn)輸車,向附近的n個(gè)陣地供應(yīng)彈藥,每個(gè)陣地的彈藥需求量為di(i=1,2,…,n),陣地所需的彈藥全部都來自彈藥倉(cāng)庫(kù)。每輛運(yùn)輸車的最大裝載量均為q(q＞di,i=1,2,…,n),能行駛的最大路程為D。每個(gè)陣地只讓1輛運(yùn)輸車對(duì)其運(yùn)輸彈藥。如何確定各個(gè)車輛的行駛路線,使得倉(cāng)庫(kù)向各個(gè)陣地完成一次彈藥配送的時(shí)間最短,即目標(biāo)為使一次配送中時(shí)間消耗最大的行駛路線達(dá)到耗時(shí)盡可能小。

根據(jù)以上的問題描述,建立數(shù)學(xué)模型如下：設(shè)節(jié)點(diǎn)集合U={u0}表示倉(cāng)庫(kù),V={vj|j=1,2,…, n}表示陣地,W=U∪V={wm,m=0,1,2,…,n}表示倉(cāng)庫(kù)和所有陣地,則邊(弧)集A={(wi,wj)| wi,wj∈W,且i≠j}表示車輛在倉(cāng)庫(kù)及其保障的陣地之間可能走過的路徑的集合,每條邊(wi, wj)的距離為cij,車輛在邊(wi,wj)上行駛的速度為sij。設(shè)決策變量為

式(1)為目標(biāo)函數(shù),即使一次配送中時(shí)間消耗最大的行駛路線達(dá)到耗時(shí)盡可能小;式(2)確保每個(gè)陣地只有1輛車運(yùn)輸彈藥;式(3)保證到達(dá)和離開某陣地的車為同一輛;式(4)規(guī)定了每條線路能使用車輛的最大數(shù)目為1;式(5)是車輛的最大行駛距離約束;式(6)保證車輛沒有超載;式(7)定義了決策變量的取值范圍。

2 改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題

本文對(duì)遺傳算法的改進(jìn)主要是2個(gè)方面：一是引入了一種基于信息素的遺傳交叉算子;二是變異算子采用了Relocation、Exchange、2-opt*及2-opt 4種啟發(fā)式搜索算法,采用該改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題的過程如下。

2.1 染色體表示及適應(yīng)度評(píng)價(jià)

使用長(zhǎng)度為n+K+1的整數(shù)串表示染色體,其中n為陣地?cái)?shù),K為線路(車輛)數(shù)量。在染色體中,n個(gè)陣地分別用[1,n]的整數(shù)表示,0表示倉(cāng)庫(kù),并用于將各線路分開[5]。例如1個(gè)染色體為0→2→5→7→0→6→4→1→9→0→8→3→0,它表示第1輛車依次向陣地2、5、7運(yùn)送彈藥,第2輛車依次向陣地6、4、1、9運(yùn)送彈藥,第3輛車類似。

種群中個(gè)體的適應(yīng)度采用基于排序的適應(yīng)度評(píng)價(jià)方法進(jìn)行計(jì)算。計(jì)算適應(yīng)度時(shí),首先將種群中的所有個(gè)體按其中的單條線路消耗時(shí)間最大值由小到大進(jìn)行排序,時(shí)間最短的路線得到序號(hào)1,其余依次類推。則序號(hào)為i的個(gè)體的適應(yīng)度為

其中,Gpop_size為種群規(guī)模,FfitMax為適應(yīng)度的最大值,FfitMin為適應(yīng)度的最小值。本文中,FfitMax和FfitMin分別設(shè)置為1.2和0.8。

2.2 初始種群的生成

按照染色體表示規(guī)則,先采用最近鄰居的原則生成每一輛車的運(yùn)輸路線,再將幾輛車的運(yùn)輸路線連接起來就構(gòu)成了1個(gè)個(gè)體。令r(i)表示車輛供給的第i個(gè)陣地。每一輛車的運(yùn)輸路線構(gòu)造過程如下：① 將倉(cāng)庫(kù)作為起始點(diǎn),即每輛車路線的第一位為“0”,h=1,隨機(jī)選擇1個(gè)陣地作為r(h),h=h+1;②從未被供給過的陣地中選擇距離陣地r(h-1)最近的陣地w作為路線中的第h個(gè)陣地r(h);③檢查車輛為前h個(gè)陣地運(yùn)輸彈藥是否滿足車輛的載容量約束條件,若不滿足,則將陣地w放回到當(dāng)前未被供給過彈藥的陣地集合中,該輛車的路線構(gòu)造完畢,即為0→r(1)→r(2)→…→r(h-1),否則令h=h+1,返回②。最后,將這幾輛車的運(yùn)輸路線連接起來就構(gòu)成1個(gè)個(gè)體,如果構(gòu)造了Kx(Kx＜K)輛車的運(yùn)輸路線后,所有陣地就已經(jīng)可以被供給彈藥了,那么就需要在Kx輛車的運(yùn)輸路線連接起來后,在其尾部補(bǔ)K-Kx+1個(gè)0,一方面統(tǒng)一染色體長(zhǎng)度,另一方面方便下一步對(duì)染色體進(jìn)行變異操作,為沒有安排運(yùn)輸路線的車輛安排運(yùn)輸補(bǔ)給任務(wù),從而尋找問題的優(yōu)化解。

2.3 選擇算子

這里采用輪盤賭選擇策略從種群中選擇個(gè)體進(jìn)行交叉。種群中個(gè)體的被選擇概率采用按比例的適應(yīng)度分配方法,即適應(yīng)度為fi的個(gè)體fi,其被選擇的概率為

2.4 交叉算子

早期的遺傳交叉算子在生成子個(gè)體時(shí),通常只考慮各陣地的位置或它們之間的順序,這類算子可以看作是“盲目”交叉。另外一些交叉算子在構(gòu)造子個(gè)體時(shí)只能利用一些局部信息,如邊的長(zhǎng)度、鄰接關(guān)系,而很少利用可能會(huì)有助于產(chǎn)生較優(yōu)個(gè)體的全局信息。這里引入基于信息素[6]的遺傳交叉算子,該算子在構(gòu)造子個(gè)體時(shí)不僅能利用局部信息,還可以利用以信息素形式保存的全局信息。

交叉時(shí),基于信息素的交叉算子首先隨機(jī)選擇1個(gè)陣地i作為子個(gè)體中的第一個(gè)陣地,然后在其2個(gè)父代個(gè)體中搜索陣地i,以獲取其前后的陣地(稱之為鄰居)。顯然,鄰居最多包含4個(gè)陣地。交叉算子將從鄰居中未被供給過的陣地中,選取距離陣地i運(yùn)輸時(shí)間最短的一個(gè)作為子個(gè)體的下一個(gè)陣地[4,7]。如果鄰居中的陣地都已經(jīng)被訪問過,算子將按照下述偽隨機(jī)比例的原則選擇下一個(gè)陣地j[4,8]。

式中：S為未被供給過的陣地集合;τij(t)表示第t代個(gè)體的邊(wi,wj)上的信息素值;ηij=sij/cij為從陣地i到陣地j的可見度,即車輛在2個(gè)陣地間運(yùn)輸時(shí)間的倒數(shù);α是調(diào)節(jié)信息素值和可見度之間相對(duì)重要性的參數(shù);q為隨機(jī)生成的小數(shù),q0(0≤q0≤1)為一參數(shù);隨機(jī)變量J服從下面的概率分布[4]1185

選擇完陣地j后,檢查該車輛為當(dāng)前選擇的幾個(gè)陣地運(yùn)輸彈藥是否滿足車輛的載容量約束條件,若滿足,則繼續(xù)按照前述的交叉方法構(gòu)造子個(gè)體;若不滿足,則將子個(gè)體染色體中陣地j的位置放入“0”,并在“0”的后面從未被補(bǔ)給過彈藥的陣地中隨機(jī)選擇1個(gè)作為子個(gè)體中的下一個(gè)陣地,然后繼續(xù)按照前述的交叉方法構(gòu)造子個(gè)體。上述過程重復(fù)進(jìn)行,直至所有陣地都被供給一次,這樣一個(gè)子個(gè)體構(gòu)造完畢。按照上述規(guī)則,基于信息素的交叉算子將以q0的概率選擇“最合適”的陣地作為子個(gè)體中的下一個(gè)陣地,而以(1-q0)的概率按照式(11)所定義的概率分布進(jìn)行隨機(jī)選擇。

信息素按照“最大-最小螞蟻系統(tǒng)”中的機(jī)制進(jìn)行初始化和更新。在算法的起始階段,各邊的信息素值均被初始化為τmax,并在整個(gè)運(yùn)算過程中,信息素值被限制在區(qū)間[τmin,τmax]之間。τmax和τmin定義如下[4]1185：

式中：常數(shù)ρ(0＜ρ＜1)為信息素的持久度;f(sgb)為全體父代個(gè)體中的最優(yōu)路線sgb的消耗時(shí)間;n為陣地總數(shù)。

在遺傳算法每代運(yùn)算結(jié)束后,各邊的信息素值將按式(14)進(jìn)行更新：

可見,只有包含在全體父代個(gè)體中的最優(yōu)路線中的邊上的信息素才會(huì)得到加強(qiáng)。

2.5 變異算子

為提高算法的性能,用局部搜索模塊代替簡(jiǎn)單的變異算子。本算法的局部搜索模塊包括4種啟發(fā)式搜索算法：Relocation、Exchange、2-opt*以及2-opt。Relocation操作將1個(gè)陣地從其所在的路線中刪除,并將之插入另外一條路線, Exchange操作交換位于不同路線中的2個(gè)陣地, 2-opt*操作交換2條路線的后段部分,2-opt操作替換當(dāng)前路線中的2條不相鄰的邊以找出更好的路線[9-10]。前3種方法用于路線間的操作,最后一種方法用于路線內(nèi)的改進(jìn)。變異算子的局部搜索模塊依次執(zhí)行Relocation、Exchange、2-opt*和2-opt 4種操作,嘗試所有可能的交換,從而發(fā)現(xiàn)更好的線路。

綜合以上描述,本文提出的改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題的流程,如圖1所示。

圖1 改進(jìn)遺傳算法的流程圖

3 算例與分析

假設(shè)有一個(gè)彈藥倉(cāng)庫(kù)部署在配置地域,負(fù)責(zé)向附近的20處陣地供應(yīng)彈藥,這20處陣地的編號(hào)依次為1～20,它們對(duì)彈藥的需求量組成的向量為(0.8,1.2,1.5,0.9,0.7,1.05,0.7,2.1,1.7, 0.6,0.8,2.1,1.1,0.6,1.3,1.5,2.3,0.9,1.9, 1.4)(單位：t),倉(cāng)庫(kù)和陣地之間的距離組成的向量為(2,3,1.5,5,6,5.5,10.8,6.1,5.6,6.4,7, 2.5,5.3,7.3,6.2,1.6,7.5,8.2,5.8,7.4)(單位：km),陣地與陣地之間的距離組成的矩陣為C20×20=(cij)20×20,cij表示陣地i與陣地j之間的距離,單位為km,C20×20為對(duì)角線元素為0的對(duì)稱矩陣。

倉(cāng)庫(kù)有5輛運(yùn)輸車,每輛車的載重為8 t,車輛在倉(cāng)庫(kù)與陣地之間平均行駛速度組成的向量為(37,44,43,35,40,38,42,38,35,40,38,42,40, 35,40,38,42,35,37,40)(單位：km/h),車輛在陣地與陣地之間的各段路徑上的平均行駛速度組成的矩陣為S20×20=(sij)20×20,sij表示車輛在陣地i與陣地j之間的路徑上的平均行駛速度,單位為km/h,S20×20為對(duì)角線元素為0的對(duì)稱矩陣。下面給出C20×20與S20×20。

算法用matlab 7.0實(shí)現(xiàn),在Intel Pentium Dual-Core E5200 2.5GHz CPU、4G內(nèi)存的臺(tái)式機(jī)、Windows XP SP3環(huán)境上運(yùn)行。參數(shù)設(shè)置如下：種群規(guī)模Gpop_size=30;變異概率Pm=0.2;算法迭代100代終止,基于信息素的遺傳交叉算子中的各參數(shù)分別設(shè)置為：q0=0.9、ρ=0.95、α=2。計(jì)算得到的最后一代的最優(yōu)個(gè)體如表1所示,可知向各個(gè)陣地完成一次彈藥運(yùn)輸?shù)臅r(shí)間為19 min。

表1 計(jì)算結(jié)果

現(xiàn)比較相同參數(shù)設(shè)置下本文的改進(jìn)遺傳算法與文獻(xiàn)[5]的遺傳算法的求解效果。2種算法程序分別重復(fù)運(yùn)算20次,其結(jié)果如表2所示。

表2 2種算法的20次試驗(yàn)對(duì)比數(shù)據(jù)

從表2可知,改進(jìn)遺傳算法更容易找到最優(yōu)的彈藥運(yùn)輸路線,其得到的解的波動(dòng)性也較小,這說明了改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題的有效性。但是在算法單次運(yùn)行的平均耗時(shí)上,由于改進(jìn)遺傳算法中變異算子采用了Relocation、Exchange、2-opt*及2-opt 4種啟發(fā)式搜索算法,因此改進(jìn)遺傳算法要比文獻(xiàn)[5]中的遺傳算法的平均耗時(shí)多2倍以上。在實(shí)際應(yīng)用中,可以根據(jù)具體需要選用其中1種算法。

4 結(jié) 論

針對(duì)彈藥運(yùn)輸車輛調(diào)度問題,本文建立了其數(shù)學(xué)模型,并提出了1種改進(jìn)的遺傳算法予以求解。在遺傳算法中引入了1種基于信息素的遺傳交叉算子,該算子在構(gòu)造子個(gè)體時(shí)可以利用以信息素形式保存的全局信息;算法中的變異算子采用了Relocation、Exchange、2-opt*及2-opt 4種啟發(fā)式搜索算法,盡可能擴(kuò)大搜索范圍。通過一個(gè)算例的計(jì)算表明,采用本文所提出的改進(jìn)遺傳算法求解彈藥運(yùn)輸車輛調(diào)度問題得到了更好的解,具有有效性和可行性。

References)

[1]談曉勇,劉秋菊.應(yīng)急配送車輛調(diào)度優(yōu)化研究綜述與展望[J].計(jì)算機(jī)應(yīng)用研究,2012,29(9)：3212-3215,3220.

[2]ELLABIB I,CALAMAI P,BASIR O.Exchange strategiesfor multiple ant colony system[J].Information Sciences, 2007,177(5)：1248-1264.

[3]NGUYEN H D,YOSHIHARA I,YAMAMORI K.Implementation of an effective hybrid GA for large scale traveling salesman problems[J].IEEE Transactions on Systems,Man and Cybernetics,2007,37(1)：92-99.

[4]趙方庚,李蘇劍,孫江生,等.求解TSP問題的一種基于信息素的遺傳交叉算子[J].北京科技大學(xué)學(xué)報(bào),2008,30(10)：1184-1187.

[5]鐘石泉,王雪蓮.多車場(chǎng)集送一體化車輛調(diào)度問題及其遺傳算法研究[J].西安電子科技大學(xué)學(xué)報(bào)：社會(huì)科學(xué)版,2009,19 (1)：63-68.

[6]孫曉瑩,徐紅霞.基于蟻群算法的煤礦運(yùn)輸車輛調(diào)度應(yīng)用研究[J].煤炭技術(shù),2012,31(7)：140-142.

[7]CHEN R,GEN M.Crossover on intensive search and traveling salesman problem[J].Computer&Industrial Engineering,1994,27(1)：485-488.

[8]GAMBARDELLA L M,DORIGO M.Solving symmetric and asymmetric TSPs by ant colonies[C]//Proceedings of IEEE International Conference on Evolutionary Computation. IEEE,1996：622-627.

[9]CHIANG C W,LEE W P,HEH J S.A 2-opt based differential evolution for global optimization[J].Applied Soft Computing,2010,10(4)：1200-1207.

[10]ENGELS C,MANTHEY B.Average-case approximation ratio of the 2-opt algorithm for the TSP[J].Operations Research Letters,2009,37(2)：83-84.

(編輯：李江濤)

Study of Scheduling Problem of Ammunition Transport Vehicles Based on Improved Genetic Algorithm

CHEN Liyun1, LU Yu2, YAN Jie1, LIU Yunlong1

(1.Department of Information Engineering,Ordnance Engineering College,Shijiazhuang Hebei 050003,China; 2.Ordnance Engineering College,Shijiazhuang Hebei 050003,China)

The mathematic model is built for scheduling problem of ammunition transport vehicles,and an improved genetic algorithm is put forward to solve the problem considering the defects of the traditional genetic algorithm in solving the problem which include the slow convergent speed and easy convergence to a local minimum point.A genetic crossover operator based on pheromone is introduced in the improved algorithm,and the operator can utilize the global information saved by the form of pheromone to improve the convergence speed.The mutation operator in the algorithm adopts four heuristic search algorithms to extend the search scope as much as possible which are Relocation,Exchange,2-opt*and 2-opt.The example analysis shows that the proposed and improved genetic algorithm is effective and feasible in solving the scheduling problem of ammunition transport vehicles.

ammunition transport;vehicle scheduling;genetic algorithm;pheromone;crossover operator

E 951.3

2095-3828(2014)02-0106-06

ADOI10.3783/j.issn.2095-3828.2014.02.025

2013-09-26

陳立云(1969-),男,副教授,博士.主要研究方向：裝備保障信息化.jack20030552@oec.mtn.