閻 哲, 汪民樂(lè), 汪江鵬, 閆少?gòu)?qiáng), 吳豐軒
(火箭軍工程大學(xué)基礎(chǔ)部, 陜西 西安 710025)
??蘸娇毡鴳?zhàn)機(jī)執(zhí)行飛行任務(wù),需要??蘸娇毡鴪?chǎng)站提供雷彈、航空器材、附屬油料等物資供應(yīng)保障。日常狀態(tài)下,各類物資分別存儲(chǔ)在相應(yīng)的配送中心,在戰(zhàn)機(jī)飛行準(zhǔn)備階段,場(chǎng)站根據(jù)任務(wù)需求派遣車輛,將其送至指定位置。傳統(tǒng)的配送模式主要依靠調(diào)度人員的工作經(jīng)驗(yàn),對(duì)配送車輛和物資的配送順序進(jìn)行簡(jiǎn)單籌劃,甚至只告知駕駛員總體的配送需求,由駕駛員自己規(guī)劃配送路線。隨著海軍航空兵改革轉(zhuǎn)型和任務(wù)拓展進(jìn)一步深入,“多機(jī)種”“大批量”飛行保障任務(wù)已成常態(tài),繼續(xù)沿用傳統(tǒng)的配送模式,不僅會(huì)造成保障資源的浪費(fèi),限制場(chǎng)站飛行保障能力的發(fā)揮,嚴(yán)重時(shí)還會(huì)影響戰(zhàn)機(jī)飛行,所以亟需使用更加科學(xué)、高效的方法對(duì)物資配送問(wèn)題進(jìn)行研究。
海軍航空兵場(chǎng)站物資配送問(wèn)題的關(guān)鍵就是配送車輛調(diào)度優(yōu)化。針對(duì)車輛調(diào)度優(yōu)化問(wèn)題約束要素多、數(shù)據(jù)規(guī)模龐大等特點(diǎn),許多學(xué)者引入智能優(yōu)化算法對(duì)該問(wèn)題進(jìn)行研究,并取得了不少成果[1-16]。其中,遺傳算法(genetic algorithm, GA)因其思想比較簡(jiǎn)單、容易實(shí)現(xiàn)且算法特性健壯等優(yōu)點(diǎn),被廣泛應(yīng)用[17]。但應(yīng)對(duì)愈發(fā)復(fù)雜的車輛調(diào)度優(yōu)化系統(tǒng),經(jīng)典GA迭代時(shí)間長(zhǎng)、容易陷入局部最優(yōu)的缺點(diǎn)就越發(fā)凸顯。因此,提高算法收斂性能、預(yù)防其早熟成為了研究熱點(diǎn)。文獻(xiàn)[18-22]分別從動(dòng)態(tài)調(diào)整交叉和變異概率、引入差分變異與粒子群算法的更新規(guī)則、采用精英選擇機(jī)制等對(duì)GA進(jìn)行了改進(jìn),均取得了不錯(cuò)的效果,對(duì)解決海軍航空兵場(chǎng)站物資配送車輛調(diào)度優(yōu)化問(wèn)題有很大的借鑒意義。
本文針對(duì)海軍航空兵場(chǎng)站物資配送問(wèn)題,建立了物資配送車輛調(diào)度優(yōu)化模型,在經(jīng)典GA的基礎(chǔ)上引入模擬退火(simulated annealing, SA)算法,提出了混合GA(hybrid GA, HGA)用于求解該模型,實(shí)現(xiàn)物資配送車輛調(diào)度的智能優(yōu)化。仿真實(shí)驗(yàn)表明,與經(jīng)典GA相比,HGA取得了更為滿意的優(yōu)化結(jié)果。
海軍航空兵場(chǎng)站雷彈、航空器材、附屬油料分別儲(chǔ)備在相應(yīng)的配送中心,場(chǎng)站保障人員在戰(zhàn)機(jī)地面準(zhǔn)備階段將其送至工作點(diǎn)位。因?yàn)椴煌N類的物資由不同保障車輛配送,且相互之間影響較小,所以可把多種物資配送問(wèn)題簡(jiǎn)化成配送一種物資問(wèn)題來(lái)進(jìn)行研究。
海軍航空兵場(chǎng)站雷彈、航空器材、附屬油料等各種物資的配送問(wèn)題可以描述為:有N架戰(zhàn)機(jī),分別停在不同停機(jī)位上進(jìn)行地面準(zhǔn)備工作,第i架戰(zhàn)機(jī)需要場(chǎng)站配送數(shù)量為Xi的物資,有M輛車可用于配送作業(yè)。場(chǎng)站保障指揮中心統(tǒng)籌所有戰(zhàn)機(jī)的物資需求,制定詳細(xì)的配送方案,明確保障車輛的出車數(shù)量、出車時(shí)間和配送順序,在規(guī)定時(shí)間內(nèi)完成配送任務(wù)的基礎(chǔ)上,做到保障車輛總數(shù)最少且所有保障車輛行駛的距離總和最小,達(dá)到提高保障車輛利用率、節(jié)約保障資源的目標(biāo)。
為了將海軍航空兵場(chǎng)站物資配送車輛調(diào)度問(wèn)題抽象為最優(yōu)化數(shù)學(xué)模型,建立基本假設(shè)如下:
(1) 每架戰(zhàn)機(jī)的物資需求已知;
(2) 戰(zhàn)機(jī)和配送中心位置已知,相互之間路徑唯一,距離固定;
(3) 保障車輛性能已知,車速和最大載荷固定不變;
(4) 戰(zhàn)機(jī)單次需求量小于運(yùn)輸車最大載荷,且每架戰(zhàn)機(jī)必須且只能被一輛車配送一次,不能由多輛車分批輸送;
(5) 受領(lǐng)任務(wù)前,配送車輛在配送中心待命。受領(lǐng)任務(wù)后,配送車輛從配送中心出發(fā),配送完成后返回配送中心;
(6) 卸載物資需要一定時(shí)間;
(7) 不考慮天氣、人員、機(jī)械故障、道路堵塞等其他因素的影響。
物資配送模型參數(shù)定義如下:
N:需要被配送物資的戰(zhàn)機(jī)數(shù)量;
i,j:戰(zhàn)機(jī)編號(hào),也是該戰(zhàn)機(jī)所在停機(jī)位的編號(hào),i,j∈(1,2,…,N),且i≠j,i,j=0時(shí)代表配送中心;
M:可參與配送任務(wù)的車輛數(shù);
m:配送車輛編號(hào),m∈(1,2,…,M);
Dij:戰(zhàn)機(jī)i到戰(zhàn)機(jī)j的距離;
Tij:配送車輛從戰(zhàn)機(jī)i行駛到戰(zhàn)機(jī)j所需的時(shí)間;
C:車輛固定使用成本;
Cd:車輛單位距離行駛成本;
v:車輛行駛速度;
Z:車輛最大載荷;
Xi:第i架戰(zhàn)機(jī)的物資需求量,且maxXi≤Z;
P,Q:很大的常數(shù);
xijm:車輛m從戰(zhàn)機(jī)i行駛到j(luò)時(shí)為1,否則為0。
在規(guī)定時(shí)間完成配送任務(wù)的基礎(chǔ)上,以動(dòng)用車輛最少、車輛總行駛距離最短為目標(biāo)建立數(shù)學(xué)模型如下:
(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)為目標(biāo)函數(shù),表示在規(guī)定時(shí)間內(nèi)完成配送任務(wù),且動(dòng)用車輛最少,車輛總行駛路徑最短,本質(zhì)上是總配送成本最低;式(2)表示參與配送的車輛數(shù)小于或等于所有物資配送車輛總數(shù);式(3)和式(4)表示每架戰(zhàn)機(jī)必須且只能接受一輛車的物資配送服務(wù);式(5)表示物資配送車輛從配送中心出發(fā)完成任務(wù)后再回到配送中心;式(6)表示保障車輛單程物資配送總量不超過(guò)其最大載荷;式(7)表示物資配送的時(shí)間窗約束;式(8)表示物資配送車輛行駛時(shí)間與物資配送距離和車輛行駛速度的關(guān)系;式(9)表示物資配送車輛從戰(zhàn)機(jī)i行駛到戰(zhàn)機(jī)j的時(shí)間約束;式(10)表示車輛當(dāng)前承載的物資數(shù)量不小于下一架戰(zhàn)機(jī)的需求;式(11)表示xijk的取值是0或1;式(12)表示違反時(shí)間窗懲罰,如果物資配送時(shí)間超出時(shí)間窗約束,就給予一定懲罰。
GA由美國(guó)Michigan大學(xué)Holland教授創(chuàng)立[23-24],提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架。但作為一種新型仿生類隨機(jī)尋優(yōu)算法,GA的局部搜索能力較差,解決這個(gè)問(wèn)題的一個(gè)有效途徑就是將其與傳統(tǒng)的基于問(wèn)題知識(shí)的啟發(fā)式搜索算法相結(jié)合構(gòu)成改進(jìn)GA[25-26]。
SA算法來(lái)源于固體退火原理,是一種基于概率的隨機(jī)尋優(yōu)算法。根據(jù)Metropolis準(zhǔn)則,適應(yīng)度更優(yōu)的新個(gè)體可直接替代當(dāng)前個(gè)體,否則以一定概率保留當(dāng)前個(gè)體。隨著退火過(guò)程的進(jìn)行,溫度逐漸降低,非優(yōu)新個(gè)體被接收的概率也隨之減小。SA算法因其逐步歸零的突跳性,可有效避免陷入局部最優(yōu)[26],但其收斂速度較慢,運(yùn)算代價(jià)非常大,所以很少被單獨(dú)使用[27-28]。
HGA基于經(jīng)典GA“優(yōu)勝劣汰”的運(yùn)算機(jī)制,引入SA算法非優(yōu)解的保留策略,讓進(jìn)化得到的子種群和其鄰域中的潛在優(yōu)秀個(gè)體再次組合,不僅進(jìn)一步增強(qiáng)了算法的局部搜索能力,同時(shí)還保持了GA自身較強(qiáng)的全局搜索特性。兩種算法跳出局部最優(yōu)的示意圖如圖1所示。
圖1 跳出局部最優(yōu)Fig.1 Jumping out of local optimum
編碼是將問(wèn)題轉(zhuǎn)化到遺傳空間的過(guò)程。為應(yīng)對(duì)不同問(wèn)題的求解需求,學(xué)者們提出了二進(jìn)制編碼、整數(shù)編碼、自然數(shù)編碼、矩陣編碼等多種編碼方式。海軍航空兵場(chǎng)站物資配送車輛調(diào)度優(yōu)化問(wèn)題是基于次序的組合優(yōu)化,問(wèn)題解的結(jié)構(gòu)比較特殊,因此選擇自然數(shù)編碼來(lái)求解。
假設(shè)有N架戰(zhàn)機(jī)等待物資配送,有M輛車可參與配送任務(wù),構(gòu)建的染色體長(zhǎng)度為N+M-1,染色體編碼串可表示為(i11,i12,…,i1a,m1,i21,i22,…,i2b,m2,…,mM-1,im1,im2,…,imc),其中i表示戰(zhàn)機(jī)編號(hào),a+b+…+c=N,m1,m2,…,mM-1∈(N,M+N-1]均代表配送中心。以10架戰(zhàn)機(jī)、4輛車為例,編碼串可表示為(5,6,12,1,3,4,2,11,9,10,8,13,7)。
解碼是編碼的逆過(guò)程,即將染色體的編碼向量映射為滿足全部約束條件的可行解的過(guò)程。由編碼過(guò)程可知,任意兩個(gè)m之間的自然數(shù)串代表1輛車的配送路徑,所以字符串(5,6,12,1,3,4,2,11,9,10,8,13,7)代表了4輛車的配送路徑,如圖2所示。
圖2 解碼過(guò)程示意圖Fig.2 Schematic diagram of decoding process
第1輛車從保障中心出發(fā),先后為5號(hào)、6號(hào)戰(zhàn)機(jī)配送物資再返回;第2輛車從保障中心出發(fā),先后為1號(hào)、3號(hào)、4號(hào)、2號(hào)戰(zhàn)機(jī)配送物資再返回;第3輛車從保障中心出發(fā),先后為9號(hào)、10號(hào)、8號(hào)戰(zhàn)機(jī)配送物資再返回;第4輛車從保障中心出發(fā),為7號(hào)戰(zhàn)機(jī)配送物資再返回。4條路徑共同組成一個(gè)完整的物資配送方案。
初始種群可以調(diào)用randperm函數(shù)隨機(jī)生成,但這樣很容易出現(xiàn)劣解,初始種群的質(zhì)量得不到保證,很有可能影響到算法的效率,因此本文選擇類似路徑構(gòu)造的方法來(lái)構(gòu)建初始種群,具體步驟如下。
步驟 1構(gòu)造一條空路徑,隨機(jī)選擇1架未插入的戰(zhàn)機(jī)作為路徑起始點(diǎn);
步驟 2遍歷剩余未插入的戰(zhàn)機(jī),選擇1架滿足載重和時(shí)間窗要求的戰(zhàn)機(jī)插入;
步驟 3重復(fù)步驟2,直到?jīng)]有滿足條件的戰(zhàn)機(jī)為止;
步驟 4重復(fù)步驟1~步驟3,直到所有戰(zhàn)機(jī)均被插入;
步驟 5將上述路徑首尾連接生成一條染色體,不同路徑間依次使用自然數(shù)m1,m2,…,mM-1∈(N,M+N-1]分割,未使用的m放至染色體尾部。
步驟 6將步驟1~步驟5循環(huán)NIND次,得到初始種群。
自然界里的個(gè)體是否可以存活下去,取決于其自身適應(yīng)自然環(huán)境的能力,這個(gè)能力就是這個(gè)個(gè)體的適應(yīng)度。同理,在GA中,一個(gè)染色體是否可以遺傳下去,也是取決于這個(gè)染色體自身的適應(yīng)度值,適應(yīng)度值越高,則遺傳下去的可能性就越大。本文選取目標(biāo)函數(shù)的倒數(shù)作為適用度函數(shù),適應(yīng)度函數(shù)Fit(f(i,j,k))的表達(dá)式如下:
(13)
遺傳操作的作用是實(shí)現(xiàn)優(yōu)勝劣汰,讓生命力強(qiáng)(即適應(yīng)度高)的染色體遺傳到下一代并進(jìn)行進(jìn)化。遺傳操作包含3個(gè)基本算子,分別是選擇算子、交叉算子和變異算子[29]。
3.4.1 選擇算子
選擇算子是在種群中篩選出可以遺傳至下一代的個(gè)體,本文選擇簡(jiǎn)單易于實(shí)現(xiàn)的輪盤賭選擇算子,其基本思路是通過(guò)種群中個(gè)體染色體適應(yīng)度值的大小來(lái)確定其遺傳至下一代的可能性,適應(yīng)度值越高的個(gè)體被選擇的可能性越大,適應(yīng)度值越低的個(gè)體被選擇的可能性越小。
3.4.2 交叉算子
交叉算子就是將兩個(gè)父輩個(gè)體進(jìn)行基因重組交換,從而產(chǎn)生適應(yīng)度更高的子代個(gè)體。本文染色體的基因代表是接受配送服務(wù)戰(zhàn)機(jī)的編號(hào),而每架戰(zhàn)機(jī)必須且只能接受一輛車的物資配送服務(wù)。如果對(duì)兩個(gè)父輩個(gè)體直接進(jìn)行交叉操作,則很容易在子代染色體上產(chǎn)生重復(fù)基因,這樣的子代染色體是無(wú)效的。為了避免這種情況的發(fā)生,本文選擇部分匹配交叉的方式進(jìn)行交叉操作,即在兩點(diǎn)交叉的基礎(chǔ)上建立匹配關(guān)系,對(duì)重復(fù)基因進(jìn)行替換,以消除沖突,得到兩條有效染色體。
3.4.3 變異算子
自然界中的基因會(huì)受多種因素影響而發(fā)生突變,GA中的變異算子就是讓染色體現(xiàn)有的基因發(fā)生突變,以增加種群染色體基因的多樣性。變異算子可以避免算法早熟收斂,提高遺傳操作的全局尋優(yōu)能力。
SA操作的目的是拓展算法局部搜索的能力,主要分為生成鄰域解和判斷接納新解兩部分。
3.5.1 生成鄰域解
對(duì)于遺傳操作生成的新種群,隨機(jī)選擇交換、逆轉(zhuǎn)或插入的方式生成鄰域解。
交換操作:如圖3所示,隨機(jī)選擇染色體的兩個(gè)位置,交換兩個(gè)位置上的元素,對(duì)于一條長(zhǎng)度為8的染色體“12345678”,隨機(jī)選擇了位置2和位置7,交換后的染色體變?yōu)榱恕?7345628”。
圖3 交換操作示意圖Fig.3 Schematic diagram of exchange operation
逆轉(zhuǎn)操作:如圖4所示,隨機(jī)選擇染色體的兩個(gè)位置,對(duì)兩個(gè)位置之間的元素進(jìn)行逆序排列,對(duì)于一條長(zhǎng)度為8的染色體“12345678”,隨機(jī)選擇了位置2和位置7,逆轉(zhuǎn)后的染色體變?yōu)椤?7654328”。
圖4 逆轉(zhuǎn)操作示意圖Fig.4 Schematic diagram of reverse operation
插入操作:如圖5所示,隨機(jī)選擇染色體的兩個(gè)位置,抽取第1個(gè)位置上的元素插入到第2個(gè)元素后面,對(duì)于一條長(zhǎng)度為8的染色體“12345678”,隨機(jī)選擇了位置2和位置7,逆轉(zhuǎn)后的染色體變?yōu)椤?3456728”。
圖5 插入操作示意圖Fig.5 Schematic diagram of insert operation
3.5.2 判斷接納新解
引用Metropolis準(zhǔn)則對(duì)生成的鄰域解進(jìn)行甄別,保留其中潛在的優(yōu)秀個(gè)體。其中,Metropolis準(zhǔn)則可表示為
(14)
式中:xbefore代表子種群中的舊解;xafter代表鄰域解;T0為初始溫度;k為冷卻因子。若鄰域中的新解的適應(yīng)度值高于舊解,則無(wú)條件保留新解,否則根據(jù)兩者的適應(yīng)度值差值概率公式p=exp(-Δf/(kT0))來(lái)判斷是否選擇該個(gè)體。
本文通過(guò)預(yù)設(shè)進(jìn)化代數(shù)來(lái)控制算法的終止,這樣可以有效求解算法的精度和運(yùn)行時(shí)間。算法運(yùn)行過(guò)程中,每一次迭代進(jìn)化后,都會(huì)判斷其是否達(dá)到預(yù)設(shè)值。如果達(dá)到,算法停止,輸出最優(yōu)解;如果沒(méi)有達(dá)到,則算法繼續(xù)運(yùn)行。
HGA的基本流程如下。
步驟 1設(shè)定初始參數(shù),主要包括種群數(shù)、迭代次數(shù)、遺傳操作概率、初始溫度、冷卻因子等;
步驟 2初始化種群;
步驟 3計(jì)算種群個(gè)體適應(yīng)度值;
步驟 4判斷遺傳運(yùn)算終止條件,選擇繼續(xù)運(yùn)算或輸出最優(yōu)解;
步驟 5對(duì)初始種群進(jìn)行選擇、交叉、變異3種遺傳操作,得到子種群;
步驟 6通過(guò)隨機(jī)概率選擇不同方法,生成隨機(jī)鄰域解,即新解;
步驟 7計(jì)算新解適應(yīng)度值并與舊解比較,若新解適應(yīng)度更高,直接用新解替換舊解,如果新解適應(yīng)度低,則按照exp(-Δf/(kT0))是否大于隨機(jī)值random(0,1)的方式保留新解,Δf為新解與舊解的差值;
步驟 8判斷SA運(yùn)算終止條件,選擇重復(fù)步驟6和步驟7或執(zhí)行步驟3。
具體的算法流程如圖6所示。
圖6 HGA流程圖Fig.6 Flowchart of HGA
為驗(yàn)證模型可行性,對(duì)比算法的改進(jìn)效果,分別使用經(jīng)典GA和HGA對(duì)戰(zhàn)機(jī)數(shù)為30、50、100的物資配送任務(wù)進(jìn)行模擬運(yùn)算。戰(zhàn)機(jī)物資配送需求表如表1所示,包含物資配送中心和戰(zhàn)機(jī)點(diǎn)位坐標(biāo)、物資需求、物資接收時(shí)間窗以及物資卸載時(shí)間等信息。
表1 戰(zhàn)機(jī)物資配送需求
使用裝有Inter(R)Core(TM)i-79750H 8核2.6 GHz CPU的電腦對(duì)模型進(jìn)行計(jì)算。設(shè)定初始種群個(gè)數(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,單個(gè)車輛最大裝載重量為20 t,車輛行駛速度為5 000 m/h。為使結(jié)果更加客觀公正,每種算法各運(yùn)行20次,求其平均值進(jìn)行對(duì)比,運(yùn)算結(jié)果如表2所示,HGA求解出的方案路線如圖7~圖9所示,計(jì)算100架戰(zhàn)機(jī)任務(wù)的優(yōu)化過(guò)程如圖10所示。
表2 運(yùn)算結(jié)果
圖7 30架戰(zhàn)機(jī)物資配送方案路線圖Fig.7 Route map for materiel distribution of 30 fighters
圖8 50架戰(zhàn)機(jī)物資配送方案路線圖Fig.8 Route map for materiel distribution of 50 fighters
圖9 100架戰(zhàn)機(jī)物資配送方案路線圖Fig.9 Route map for materiel distribution of 100 fighters
圖10 優(yōu)化過(guò)程示意圖Fig.10 Schematic diagram of optimization process
分析運(yùn)算結(jié)果不難發(fā)現(xiàn),HGA的運(yùn)算時(shí)間基本保持在200~330 s,是經(jīng)典GA的4~5倍,但在可接收的范圍之內(nèi)。對(duì)比車輛數(shù)目和車輛總行駛距離,HGA均優(yōu)于經(jīng)典GA,而且隨著戰(zhàn)機(jī)數(shù)量的增加,優(yōu)化的效果更加明顯。圖10中,藍(lán)色曲線代表經(jīng)典GA的優(yōu)化過(guò)程,紅色曲線代表HGA的優(yōu)化過(guò)程。迭代50次之前,兩種運(yùn)算結(jié)果差別不大,經(jīng)典GA在極少時(shí)間優(yōu)于HGA;迭代50次之后,HGA全時(shí)間段優(yōu)于GA。從曲線的變化趨勢(shì)來(lái)看,藍(lán)色曲線有多個(gè)位置變成水平直線,這就意味著運(yùn)算陷入了局部最優(yōu),紅色曲線基本沒(méi)有變成水平直線的情況,但有少部分逆增長(zhǎng)的位置,這就是SA操作起到了作用,突破了算法陷入局部最優(yōu)的僵局。整體而言,改進(jìn)后的HGA比經(jīng)典GA的表現(xiàn)更加優(yōu)秀。
本文以提高海軍航空兵場(chǎng)站物資配送效率、減少工作成本為目標(biāo),在時(shí)間窗和車輛載重的約束下構(gòu)建了數(shù)學(xué)模型,提出了引入SA操作的HGA。對(duì)比實(shí)驗(yàn)表明,所提算法優(yōu)于經(jīng)典GA,達(dá)到了配送車輛調(diào)度智能優(yōu)化的需要。本文建立的調(diào)度模型受限于任務(wù)已知、且無(wú)外界突發(fā)狀況干擾的情況,但在現(xiàn)實(shí)保障工作中,飛行計(jì)劃還會(huì)受到天氣、戰(zhàn)機(jī)狀態(tài)、航空管制等多種因素的影響,飛行保障需求也會(huì)隨之變更,后續(xù)可針對(duì)動(dòng)態(tài)保障需求進(jìn)行進(jìn)一步研究。