基于混合遺傳算法的海軍航空兵場站物資配送車輛調(diào)度智能優(yōu)化

閻 哲, 汪民樂, 汪江鵬, 閆少強, 吳豐軒

(火箭軍工程大學基礎(chǔ)部, 陜西 西安 710025)

0 引 言

海空航空兵戰(zhàn)機執(zhí)行飛行任務(wù),需要海空航空兵場站提供雷彈、航空器材、附屬油料等物資供應(yīng)保障。日常狀態(tài)下,各類物資分別存儲在相應(yīng)的配送中心,在戰(zhàn)機飛行準備階段,場站根據(jù)任務(wù)需求派遣車輛,將其送至指定位置。傳統(tǒng)的配送模式主要依靠調(diào)度人員的工作經(jīng)驗,對配送車輛和物資的配送順序進行簡單籌劃,甚至只告知駕駛員總體的配送需求,由駕駛員自己規(guī)劃配送路線。隨著海軍航空兵改革轉(zhuǎn)型和任務(wù)拓展進一步深入,“多機種”“大批量”飛行保障任務(wù)已成常態(tài),繼續(xù)沿用傳統(tǒng)的配送模式,不僅會造成保障資源的浪費,限制場站飛行保障能力的發(fā)揮,嚴重時還會影響戰(zhàn)機飛行,所以亟需使用更加科學、高效的方法對物資配送問題進行研究。

海軍航空兵場站物資配送問題的關(guān)鍵就是配送車輛調(diào)度優(yōu)化。針對車輛調(diào)度優(yōu)化問題約束要素多、數(shù)據(jù)規(guī)模龐大等特點,許多學者引入智能優(yōu)化算法對該問題進行研究,并取得了不少成果[1-16]。其中,遺傳算法(genetic algorithm, GA)因其思想比較簡單、容易實現(xiàn)且算法特性健壯等優(yōu)點,被廣泛應(yīng)用[17]。但應(yīng)對愈發(fā)復雜的車輛調(diào)度優(yōu)化系統(tǒng),經(jīng)典GA迭代時間長、容易陷入局部最優(yōu)的缺點就越發(fā)凸顯。因此,提高算法收斂性能、預防其早熟成為了研究熱點。文獻[18-22]分別從動態(tài)調(diào)整交叉和變異概率、引入差分變異與粒子群算法的更新規(guī)則、采用精英選擇機制等對GA進行了改進,均取得了不錯的效果,對解決海軍航空兵場站物資配送車輛調(diào)度優(yōu)化問題有很大的借鑒意義。

本文針對海軍航空兵場站物資配送問題,建立了物資配送車輛調(diào)度優(yōu)化模型,在經(jīng)典GA的基礎(chǔ)上引入模擬退火(simulated annealing, SA)算法,提出了混合GA(hybrid GA, HGA)用于求解該模型,實現(xiàn)物資配送車輛調(diào)度的智能優(yōu)化。仿真實驗表明,與經(jīng)典GA相比,HGA取得了更為滿意的優(yōu)化結(jié)果。

1 問題描述

海軍航空兵場站雷彈、航空器材、附屬油料分別儲備在相應(yīng)的配送中心,場站保障人員在戰(zhàn)機地面準備階段將其送至工作點位。因為不同種類的物資由不同保障車輛配送,且相互之間影響較小,所以可把多種物資配送問題簡化成配送一種物資問題來進行研究。

海軍航空兵場站雷彈、航空器材、附屬油料等各種物資的配送問題可以描述為:有N架戰(zhàn)機,分別停在不同停機位上進行地面準備工作,第i架戰(zhàn)機需要場站配送數(shù)量為Xi的物資,有M輛車可用于配送作業(yè)。場站保障指揮中心統(tǒng)籌所有戰(zhàn)機的物資需求,制定詳細的配送方案,明確保障車輛的出車數(shù)量、出車時間和配送順序,在規(guī)定時間內(nèi)完成配送任務(wù)的基礎(chǔ)上,做到保障車輛總數(shù)最少且所有保障車輛行駛的距離總和最小,達到提高保障車輛利用率、節(jié)約保障資源的目標。

2 海軍航空兵場站物資配送車輛調(diào)度優(yōu)化模型

2.1 基本假設(shè)

為了將海軍航空兵場站物資配送車輛調(diào)度問題抽象為最優(yōu)化數(shù)學模型,建立基本假設(shè)如下:

(1) 每架戰(zhàn)機的物資需求已知;

(2) 戰(zhàn)機和配送中心位置已知,相互之間路徑唯一,距離固定;

(3) 保障車輛性能已知,車速和最大載荷固定不變;

(4) 戰(zhàn)機單次需求量小于運輸車最大載荷,且每架戰(zhàn)機必須且只能被一輛車配送一次,不能由多輛車分批輸送;

(5) 受領(lǐng)任務(wù)前,配送車輛在配送中心待命。受領(lǐng)任務(wù)后,配送車輛從配送中心出發(fā),配送完成后返回配送中心;

(6) 卸載物資需要一定時間;

(7) 不考慮天氣、人員、機械故障、道路堵塞等其他因素的影響。

2.2 參數(shù)定義

物資配送模型參數(shù)定義如下:

N:需要被配送物資的戰(zhàn)機數(shù)量;

i,j:戰(zhàn)機編號,也是該戰(zhàn)機所在停機位的編號,i,j∈(1,2,…,N),且i≠j,i,j=0時代表配送中心;

M:可參與配送任務(wù)的車輛數(shù);

m:配送車輛編號,m∈(1,2,…,M);

Dij:戰(zhàn)機i到戰(zhàn)機j的距離;

Tij:配送車輛從戰(zhàn)機i行駛到戰(zhàn)機j所需的時間;

C:車輛固定使用成本;

Cd:車輛單位距離行駛成本;

v:車輛行駛速度;

Z:車輛最大載荷;

Xi:第i架戰(zhàn)機的物資需求量,且maxXi≤Z;

P,Q:很大的常數(shù);

xijm:車輛m從戰(zhàn)機i行駛到j(luò)時為1,否則為0。

2.3 數(shù)學模型

在規(guī)定時間完成配送任務(wù)的基礎(chǔ)上,以動用車輛最少、車輛總行駛距離最短為目標建立數(shù)學模型如下:

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

xijm(Z-Xi-Xj)≥0, ?i,j∈{1,2,…,N};

?m∈{1,2,…,M}

(10)

xijm∈{0,1}, ?i,j∈{1,2,…,N};?m∈{1,2,…,M}

(11)

(12)

以上模型中,式(1)為目標函數(shù),表示在規(guī)定時間內(nèi)完成配送任務(wù),且動用車輛最少,車輛總行駛路徑最短,本質(zhì)上是總配送成本最低;式(2)表示參與配送的車輛數(shù)小于或等于所有物資配送車輛總數(shù);式(3)和式(4)表示每架戰(zhàn)機必須且只能接受一輛車的物資配送服務(wù);式(5)表示物資配送車輛從配送中心出發(fā)完成任務(wù)后再回到配送中心;式(6)表示保障車輛單程物資配送總量不超過其最大載荷;式(7)表示物資配送的時間窗約束;式(8)表示物資配送車輛行駛時間與物資配送距離和車輛行駛速度的關(guān)系;式(9)表示物資配送車輛從戰(zhàn)機i行駛到戰(zhàn)機j的時間約束;式(10)表示車輛當前承載的物資數(shù)量不小于下一架戰(zhàn)機的需求;式(11)表示xijk的取值是0或1;式(12)表示違反時間窗懲罰,如果物資配送時間超出時間窗約束,就給予一定懲罰。

3 HGA設(shè)計

GA由美國Michigan大學Holland教授創(chuàng)立[23-24],提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架。但作為一種新型仿生類隨機尋優(yōu)算法,GA的局部搜索能力較差,解決這個問題的一個有效途徑就是將其與傳統(tǒng)的基于問題知識的啟發(fā)式搜索算法相結(jié)合構(gòu)成改進GA[25-26]。

SA算法來源于固體退火原理,是一種基于概率的隨機尋優(yōu)算法。根據(jù)Metropolis準則,適應(yīng)度更優(yōu)的新個體可直接替代當前個體,否則以一定概率保留當前個體。隨著退火過程的進行,溫度逐漸降低,非優(yōu)新個體被接收的概率也隨之減小。SA算法因其逐步歸零的突跳性,可有效避免陷入局部最優(yōu)[26],但其收斂速度較慢,運算代價非常大,所以很少被單獨使用[27-28]。

HGA基于經(jīng)典GA“優(yōu)勝劣汰”的運算機制,引入SA算法非優(yōu)解的保留策略,讓進化得到的子種群和其鄰域中的潛在優(yōu)秀個體再次組合,不僅進一步增強了算法的局部搜索能力,同時還保持了GA自身較強的全局搜索特性。兩種算法跳出局部最優(yōu)的示意圖如圖1所示。

圖1 跳出局部最優(yōu)Fig.1 Jumping out of local optimum

3.1 編碼與解碼

編碼是將問題轉(zhuǎn)化到遺傳空間的過程。為應(yīng)對不同問題的求解需求,學者們提出了二進制編碼、整數(shù)編碼、自然數(shù)編碼、矩陣編碼等多種編碼方式。海軍航空兵場站物資配送車輛調(diào)度優(yōu)化問題是基于次序的組合優(yōu)化,問題解的結(jié)構(gòu)比較特殊,因此選擇自然數(shù)編碼來求解。

假設(shè)有N架戰(zhàn)機等待物資配送,有M輛車可參與配送任務(wù),構(gòu)建的染色體長度為N+M-1,染色體編碼串可表示為(i11,i12,…,i1a,m1,i21,i22,…,i2b,m2,…,mM-1,im1,im2,…,imc),其中i表示戰(zhàn)機編號,a+b+…+c=N,m1,m2,…,mM-1∈(N,M+N-1]均代表配送中心。以10架戰(zhàn)機、4輛車為例,編碼串可表示為(5,6,12,1,3,4,2,11,9,10,8,13,7)。

解碼是編碼的逆過程,即將染色體的編碼向量映射為滿足全部約束條件的可行解的過程。由編碼過程可知,任意兩個m之間的自然數(shù)串代表1輛車的配送路徑,所以字符串(5,6,12,1,3,4,2,11,9,10,8,13,7)代表了4輛車的配送路徑,如圖2所示。

圖2 解碼過程示意圖Fig.2 Schematic diagram of decoding process

第1輛車從保障中心出發(fā),先后為5號、6號戰(zhàn)機配送物資再返回;第2輛車從保障中心出發(fā),先后為1號、3號、4號、2號戰(zhàn)機配送物資再返回;第3輛車從保障中心出發(fā),先后為9號、10號、8號戰(zhàn)機配送物資再返回;第4輛車從保障中心出發(fā),為7號戰(zhàn)機配送物資再返回。4條路徑共同組成一個完整的物資配送方案。

3.2 初始種群生成

初始種群可以調(diào)用randperm函數(shù)隨機生成,但這樣很容易出現(xiàn)劣解,初始種群的質(zhì)量得不到保證,很有可能影響到算法的效率,因此本文選擇類似路徑構(gòu)造的方法來構(gòu)建初始種群,具體步驟如下。

步驟 1構(gòu)造一條空路徑,隨機選擇1架未插入的戰(zhàn)機作為路徑起始點;

步驟 2遍歷剩余未插入的戰(zhàn)機,選擇1架滿足載重和時間窗要求的戰(zhàn)機插入;

步驟 3重復步驟2,直到?jīng)]有滿足條件的戰(zhàn)機為止;

步驟 4重復步驟1～步驟3,直到所有戰(zhàn)機均被插入;

步驟 5將上述路徑首尾連接生成一條染色體,不同路徑間依次使用自然數(shù)m1,m2,…,mM-1∈(N,M+N-1]分割,未使用的m放至染色體尾部。

步驟 6將步驟1～步驟5循環(huán)NIND次,得到初始種群。

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

自然界里的個體是否可以存活下去,取決于其自身適應(yīng)自然環(huán)境的能力,這個能力就是這個個體的適應(yīng)度。同理,在GA中,一個染色體是否可以遺傳下去,也是取決于這個染色體自身的適應(yīng)度值,適應(yīng)度值越高,則遺傳下去的可能性就越大。本文選取目標函數(shù)的倒數(shù)作為適用度函數(shù),適應(yīng)度函數(shù)Fit(f(i,j,k))的表達式如下:

(13)

3.4 遺傳操作

遺傳操作的作用是實現(xiàn)優(yōu)勝劣汰,讓生命力強(即適應(yīng)度高)的染色體遺傳到下一代并進行進化。遺傳操作包含3個基本算子,分別是選擇算子、交叉算子和變異算子[29]。

3.4.1 選擇算子

選擇算子是在種群中篩選出可以遺傳至下一代的個體,本文選擇簡單易于實現(xiàn)的輪盤賭選擇算子,其基本思路是通過種群中個體染色體適應(yīng)度值的大小來確定其遺傳至下一代的可能性,適應(yīng)度值越高的個體被選擇的可能性越大,適應(yīng)度值越低的個體被選擇的可能性越小。

3.4.2 交叉算子

交叉算子就是將兩個父輩個體進行基因重組交換,從而產(chǎn)生適應(yīng)度更高的子代個體。本文染色體的基因代表是接受配送服務(wù)戰(zhàn)機的編號,而每架戰(zhàn)機必須且只能接受一輛車的物資配送服務(wù)。如果對兩個父輩個體直接進行交叉操作,則很容易在子代染色體上產(chǎn)生重復基因,這樣的子代染色體是無效的。為了避免這種情況的發(fā)生,本文選擇部分匹配交叉的方式進行交叉操作,即在兩點交叉的基礎(chǔ)上建立匹配關(guān)系,對重復基因進行替換,以消除沖突,得到兩條有效染色體。

3.4.3 變異算子

自然界中的基因會受多種因素影響而發(fā)生突變,GA中的變異算子就是讓染色體現(xiàn)有的基因發(fā)生突變,以增加種群染色體基因的多樣性。變異算子可以避免算法早熟收斂,提高遺傳操作的全局尋優(yōu)能力。

3.5 SA操作

SA操作的目的是拓展算法局部搜索的能力,主要分為生成鄰域解和判斷接納新解兩部分。

3.5.1 生成鄰域解

對于遺傳操作生成的新種群,隨機選擇交換、逆轉(zhuǎn)或插入的方式生成鄰域解。

交換操作:如圖3所示,隨機選擇染色體的兩個位置,交換兩個位置上的元素,對于一條長度為8的染色體“12345678”,隨機選擇了位置2和位置7,交換后的染色體變?yōu)榱恕?7345628”。

圖3 交換操作示意圖Fig.3 Schematic diagram of exchange operation

逆轉(zhuǎn)操作:如圖4所示,隨機選擇染色體的兩個位置,對兩個位置之間的元素進行逆序排列,對于一條長度為8的染色體“12345678”,隨機選擇了位置2和位置7,逆轉(zhuǎn)后的染色體變?yōu)椤?7654328”。

圖4 逆轉(zhuǎn)操作示意圖Fig.4 Schematic diagram of reverse operation

插入操作:如圖5所示,隨機選擇染色體的兩個位置,抽取第1個位置上的元素插入到第2個元素后面,對于一條長度為8的染色體“12345678”,隨機選擇了位置2和位置7,逆轉(zhuǎn)后的染色體變?yōu)椤?3456728”。

圖5 插入操作示意圖Fig.5 Schematic diagram of insert operation

3.5.2 判斷接納新解

引用Metropolis準則對生成的鄰域解進行甄別,保留其中潛在的優(yōu)秀個體。其中,Metropolis準則可表示為

(14)

式中:xbefore代表子種群中的舊解;xafter代表鄰域解;T0為初始溫度;k為冷卻因子。若鄰域中的新解的適應(yīng)度值高于舊解,則無條件保留新解,否則根據(jù)兩者的適應(yīng)度值差值概率公式p=exp(-Δf/(kT0))來判斷是否選擇該個體。

3.6 算法終止條件

本文通過預設(shè)進化代數(shù)來控制算法的終止,這樣可以有效求解算法的精度和運行時間。算法運行過程中,每一次迭代進化后,都會判斷其是否達到預設(shè)值。如果達到,算法停止,輸出最優(yōu)解;如果沒有達到,則算法繼續(xù)運行。

3.7 算法流程

HGA的基本流程如下。

步驟 1設(shè)定初始參數(shù),主要包括種群數(shù)、迭代次數(shù)、遺傳操作概率、初始溫度、冷卻因子等;

步驟 2初始化種群;

步驟 3計算種群個體適應(yīng)度值;

步驟 4判斷遺傳運算終止條件,選擇繼續(xù)運算或輸出最優(yōu)解;

步驟 5對初始種群進行選擇、交叉、變異3種遺傳操作,得到子種群;

步驟 6通過隨機概率選擇不同方法,生成隨機鄰域解,即新解;

步驟 7計算新解適應(yīng)度值并與舊解比較,若新解適應(yīng)度更高,直接用新解替換舊解,如果新解適應(yīng)度低,則按照exp(-Δf/(kT0))是否大于隨機值random(0,1)的方式保留新解,Δf為新解與舊解的差值;

步驟 8判斷SA運算終止條件,選擇重復步驟6和步驟7或執(zhí)行步驟3。

具體的算法流程如圖6所示。

圖6 HGA流程圖Fig.6 Flowchart of HGA

4 算例分析

為驗證模型可行性,對比算法的改進效果,分別使用經(jīng)典GA和HGA對戰(zhàn)機數(shù)為30、50、100的物資配送任務(wù)進行模擬運算。戰(zhàn)機物資配送需求表如表1所示,包含物資配送中心和戰(zhàn)機點位坐標、物資需求、物資接收時間窗以及物資卸載時間等信息。

表1 戰(zhàn)機物資配送需求

使用裝有Inter(R)Core(TM)i-79750H 8核2.6 GHz CPU的電腦對模型進行計算。設(shè)定初始種群個數(shù)為200,遺傳迭代次數(shù)為500,交叉概率為0.9,變異概率為0.05,代溝為0.9,SA操作迭代次數(shù)為200,初始溫度為100,冷卻因子為0.99,交換操作概率為0.2,逆轉(zhuǎn)操作概率為0.5,插入操作概率為0.3。可調(diào)度最大車輛數(shù)為25,單個車輛最大裝載重量為20 t,車輛行駛速度為5 000 m/h。為使結(jié)果更加客觀公正,每種算法各運行20次,求其平均值進行對比,運算結(jié)果如表2所示,HGA求解出的方案路線如圖7～圖9所示,計算100架戰(zhàn)機任務(wù)的優(yōu)化過程如圖10所示。

表2 運算結(jié)果

圖7 30架戰(zhàn)機物資配送方案路線圖Fig.7 Route map for materiel distribution of 30 fighters

圖8 50架戰(zhàn)機物資配送方案路線圖Fig.8 Route map for materiel distribution of 50 fighters

圖9 100架戰(zhàn)機物資配送方案路線圖Fig.9 Route map for materiel distribution of 100 fighters

圖10 優(yōu)化過程示意圖Fig.10 Schematic diagram of optimization process

分析運算結(jié)果不難發(fā)現(xiàn),HGA的運算時間基本保持在200～330 s,是經(jīng)典GA的4～5倍,但在可接收的范圍之內(nèi)。對比車輛數(shù)目和車輛總行駛距離,HGA均優(yōu)于經(jīng)典GA,而且隨著戰(zhàn)機數(shù)量的增加,優(yōu)化的效果更加明顯。圖10中,藍色曲線代表經(jīng)典GA的優(yōu)化過程,紅色曲線代表HGA的優(yōu)化過程。迭代50次之前,兩種運算結(jié)果差別不大,經(jīng)典GA在極少時間優(yōu)于HGA;迭代50次之后,HGA全時間段優(yōu)于GA。從曲線的變化趨勢來看,藍色曲線有多個位置變成水平直線,這就意味著運算陷入了局部最優(yōu),紅色曲線基本沒有變成水平直線的情況,但有少部分逆增長的位置,這就是SA操作起到了作用,突破了算法陷入局部最優(yōu)的僵局。整體而言,改進后的HGA比經(jīng)典GA的表現(xiàn)更加優(yōu)秀。

5 結(jié)束語

本文以提高海軍航空兵場站物資配送效率、減少工作成本為目標,在時間窗和車輛載重的約束下構(gòu)建了數(shù)學模型,提出了引入SA操作的HGA。對比實驗表明,所提算法優(yōu)于經(jīng)典GA,達到了配送車輛調(diào)度智能優(yōu)化的需要。本文建立的調(diào)度模型受限于任務(wù)已知、且無外界突發(fā)狀況干擾的情況,但在現(xiàn)實保障工作中,飛行計劃還會受到天氣、戰(zhàn)機狀態(tài)、航空管制等多種因素的影響,飛行保障需求也會隨之變更,后續(xù)可針對動態(tài)保障需求進行進一步研究。