李猛，和偉輝，毛攀登，齊小剛，劉立芳

（1.西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710071; 2.西安衛(wèi)星測(cè)控中心, 陜西 西安 710049; 3.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 陜西 西安 710071）

自主維修保障模式是未來(lái)裝備維修保障的發(fā)展方向[1]，但我軍現(xiàn)有維修保障體系與自主維修保障模式還存在較大的差距，現(xiàn)行軍隊(duì)體制中各軍區(qū)、各兵種以及各部隊(duì)單位之間的維修資源的調(diào)度中存在很多不合理現(xiàn)象，這對(duì)我軍裝備維修保障的能力與速度都造成了不利的影響[2]。而資源供應(yīng)的敏捷性會(huì)直接影響到維修保障的效率，我軍自主維修保障研究中急需解決的問題之一就是如何根據(jù)設(shè)備健康管理(prognostics health management, PHM)系統(tǒng)的預(yù)測(cè)信息，聯(lián)合多個(gè)資源庫(kù)存中心，制定合理高效的配送調(diào)度方案，對(duì)多個(gè)部隊(duì)維修基地進(jìn)行快速可靠的資源供應(yīng)保障。

在現(xiàn)代化自主維修保障系統(tǒng)中，對(duì)維修資源多采用配送式供應(yīng)保障模式，將庫(kù)存成本高的維修物資實(shí)行統(tǒng)一存儲(chǔ)與管理，以縮短軍需物資冗長(zhǎng)的供應(yīng)鏈，實(shí)現(xiàn)對(duì)各級(jí)部隊(duì)單位的直達(dá)式供應(yīng)[3]。其主要核心是根據(jù)PHM提供的預(yù)測(cè)信息，計(jì)算具體的資源需求，確定保障資源的配送時(shí)間，然后通過合理的供應(yīng)路線設(shè)計(jì)，控制資源的調(diào)度成本，從而獲得全局最優(yōu)的資源保障渠道。

目前，對(duì)配送式資源供應(yīng)保障模式的研究涉及交通運(yùn)輸、供應(yīng)鏈優(yōu)化以及物流管理等領(lǐng)域，并且在時(shí)間上存在一定的約束，因此屬于帶時(shí)間窗的多站點(diǎn)車輛路徑問題問題(multi-depot vehicle routing problem with time-windows, MDVRPTW)。過去的幾十年間，國(guó)內(nèi)外的學(xué)者已對(duì)經(jīng)典RCPSP(resource-constrained project scheduling problem)模型及其求解算法進(jìn)行了深入的研究,由于大規(guī)模的調(diào)度[4-7]為NP-hard問題，目前對(duì)MDVRPTW問題的研究多集中在啟發(fā)式算法的優(yōu)化上[8-16]，本文將配送中心設(shè)為半開放式，然后在遺傳算法和煙花算法的基礎(chǔ)上，提出了一種混合算法，充分結(jié)合了兩種算法在全局搜索和局部搜索的優(yōu)點(diǎn)，具有更高的搜索效率，可以在短時(shí)間內(nèi)得到更優(yōu)的調(diào)度方案。

1 問題描述

1.1 配送式資源供應(yīng)

自主維修保障中為減小高技術(shù)裝備維修資源的庫(kù)存成本[17-19]，資源主要在庫(kù)存配送中心集中存儲(chǔ)，采用如圖1所示的配送式供應(yīng)模式：各級(jí)維修單位計(jì)劃開展維修活動(dòng)時(shí)，需向庫(kù)存配送中心提出具體的資源需求，調(diào)度決策者會(huì)根據(jù)全局資源的分布情況，在滿足需求數(shù)量和抵達(dá)時(shí)間的約束條件下，將各種資源供應(yīng)至需求地點(diǎn)。

圖1 配送式維修資源供應(yīng)Fig.1 Distribution type maintenance resource supply

1.2 約束條件

1）時(shí)間約束

供應(yīng)調(diào)度中的時(shí)間有效性約束一般采用時(shí)間窗口描述，根據(jù)決策者對(duì)供應(yīng)時(shí)間準(zhǔn)確性和供應(yīng)成本之間的偏好，可以分為如圖2所示的3種時(shí)間窗。圖2(a)表示硬時(shí)間窗：車輛必須在規(guī)定時(shí)間段 (e,l)之內(nèi)將資源送達(dá)需求地點(diǎn)，需求地在這個(gè)時(shí)間段之外將拒絕接收資源，其中P(t)為懲罰函數(shù)，在硬時(shí)間窗之外的懲罰值M是一個(gè)很大的值。圖2(b)表示軟時(shí)間窗：配送中各種突發(fā)情況可能導(dǎo)致配送車輛無(wú)法在規(guī)定時(shí)間內(nèi)到達(dá)，但需求地點(diǎn)對(duì)此可以接受，不過需要按照一定規(guī)則處以一定的懲罰，圖2(b)即一種可能的懲罰函數(shù)。圖2(c)將硬、軟兩種時(shí)間窗相結(jié)合，形成了混合型時(shí)間窗：在規(guī)定的時(shí)間段 (e,l)之內(nèi)將資源送達(dá)會(huì)直接接受，在規(guī)定時(shí)間段之外的一個(gè)較小的區(qū)間內(nèi)送達(dá)，如 (a,e)或 (l,b)，則在加以一定懲罰后接受維修資源，但在 (a,b)之外將不再接受資源的供應(yīng)。

圖2 時(shí)間窗分類Fig.2 Time window classification

2）車輛使用性約束

車輛是維修資源供應(yīng)過程中調(diào)度的主要執(zhí)行者，對(duì)于車輛本身的許多固有屬性，常常存在一些硬性的約束，具體如下：

① 承載約束

每輛配送車輛的運(yùn)載能力都是有限的，在配送的過程中，通常不允許實(shí)際的裝載量超過車輛的承載限制，承載限制一般考慮為車輛的最大承重重量或車輛的最大資源容納數(shù)量。

② 行駛上限約束

車輛在行駛過程中會(huì)產(chǎn)生成本與損耗，如油耗、器械磨損、人員體力損耗等，若這些成本或損耗達(dá)到一定的閾值，則車輛須返回進(jìn)行保養(yǎng)與休整。此外，考慮到配送任務(wù)的均衡性，應(yīng)該禁止超長(zhǎng)配送路線的出現(xiàn)，需要對(duì)車輛設(shè)置行駛上限，車輛必須在行駛時(shí)間或行駛路程到達(dá)行駛上限之前返回配送中心。

③ 使用數(shù)量約束

實(shí)際配送中不可能存在無(wú)限多的配送車輛，因此需要對(duì)每個(gè)配送中心的實(shí)際可用車輛數(shù)目加以限制，車輛動(dòng)用數(shù)量必須小于當(dāng)前空閑的車輛數(shù)。

1.3 半開放配送中心

基本的配送式供應(yīng)[20]保障中一般要求車輛回到其出發(fā)的配送中心，這種模式下車輛使用率不高，并且配送中心之間沒有聯(lián)系和互動(dòng)，資源也無(wú)法共享。基于此，本文研究半開方式的配送中心：車輛從配送中心a出發(fā)并完成配送任務(wù)后，可以根據(jù)距離因素自行選擇是否返回原配送中心a；若選擇不返回原配送中心a，而是另一個(gè)配送中心b，則配送中心b在該車輛返回后，擁有該車輛的使用權(quán)，后續(xù)可以為該車輛安排配送中心b的配送任務(wù)。此外，配送中心自己也可以作為一個(gè)需求地點(diǎn)，從而可以實(shí)現(xiàn)配送中心之間的資源共享和互相保障，使得供應(yīng)保障體系更加高效且可靠。由于配送中心的半開放性，本文引入了車位的概念，增加了如下兩條約束原則：僅當(dāng)配送中心擁有的車輛數(shù)目小于配送中心車位數(shù)目時(shí)，才允許新的車輛返回該配送中心；車輛應(yīng)選擇距離路線末端最近的，且具有多余停車位的配送中心返回。

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

考慮到計(jì)算的方便性以及仿真實(shí)驗(yàn)的可行性，模型采用如下基本假設(shè)：

1）資源數(shù)量充足，全局的維修資源庫(kù)存能夠滿足全局的資源需求；

2）車輛由一個(gè)配送中心出發(fā)后返回到多個(gè)配送中心中的一個(gè)，每輛車不得重復(fù)調(diào)度；

3)采用同類型的配送車輛，車輛與需求地點(diǎn)之間為一對(duì)多的關(guān)系；

4)運(yùn)輸?shù)缆窢顩r和車流量忽略不計(jì)，道路距離按直線距離計(jì)算，單位距離的行駛時(shí)間為單位時(shí)間；

5)每個(gè)配送中心存在固定數(shù)量的車位，可用車位數(shù)不足時(shí)，車輛不能在該配送中心?？?；

6)車輛到達(dá)需求地點(diǎn)的時(shí)間應(yīng)在允許的時(shí)間范圍內(nèi)波動(dòng)，如果車輛在規(guī)定時(shí)間之外到達(dá)，則會(huì)進(jìn)行處罰，增加一定的供應(yīng)成本；

7)車輛在每個(gè)節(jié)點(diǎn)存在裝卸貨物的時(shí)間，稱為服務(wù)時(shí)間，服務(wù)時(shí)間在車輛到達(dá)后才能開始計(jì)時(shí)，服務(wù)結(jié)束后車輛才可以離開。

由于配送中心以及需求地點(diǎn)位置的分散性，協(xié)同供應(yīng)調(diào)度模型可以看作一個(gè)完全無(wú)向圖G=(V,A)， 其 中 ，V={v1,···vN,vN+1,···vN+M}為 節(jié) 點(diǎn)集，代表了配送中心或需求地點(diǎn)，其位置用二維坐標(biāo) (X,Y)表示；為弧集，代表了節(jié)點(diǎn)之間的距離長(zhǎng)度。

在節(jié)點(diǎn)集V中，C={c1,c2,···,cN}={v1,v2,···,vN}代表N個(gè)需求地點(diǎn),D={d1,d2,···,dM}={vN+1,vN+2,···,vN+M}代表M個(gè)配送中心。在弧集A中，每個(gè)弧(vi,vj)∈A代表兩個(gè)節(jié)點(diǎn)之間的路徑，與之對(duì)應(yīng)的參數(shù)c11代表兩者之間的距離。

對(duì)于每個(gè)需求節(jié)點(diǎn)vi∈C，有著與其對(duì)應(yīng)的資源需求量qi，裝卸服務(wù)時(shí)間si，以及供應(yīng)時(shí)間窗口[ei,li]，其中ei是 接受配送的最早開始時(shí)間，li是接受配送的最晚時(shí)間。

對(duì)于每個(gè)配送中心節(jié)點(diǎn)vi∈D，有著于其對(duì)應(yīng)的車輛數(shù)目 |Kd|和車位數(shù)目 |Pd|，在沒有需求和配送服務(wù)時(shí)，配送中心的資源需求量和服務(wù)時(shí)間都為 0，即qi=si=0。

每個(gè)配送中心的車輛集合表示為K={k1,k2,···,kL}，其中L是車輛數(shù)目，車輛有其對(duì)應(yīng)的負(fù)荷量Qk，最大工作時(shí)間Tk，動(dòng)用成本和單位距離行駛成本。記車輛k到達(dá)節(jié)點(diǎn)i的時(shí)間為k，車輛在節(jié)點(diǎn)i的服務(wù)開始時(shí)間為aki，車輛的累計(jì)工作時(shí)長(zhǎng)為 πk。

由于采用了軟時(shí)間窗進(jìn)行建模，懲罰函數(shù)以時(shí)間的線性函數(shù)的形式表示，因此模型引入了早到單位時(shí)間懲罰成本Cearl和遲到單位時(shí)間懲罰成本Clat，以及提前、推遲到達(dá)節(jié)點(diǎn)i的時(shí)間差和。當(dāng)車輛早于時(shí)間窗的開啟時(shí)刻或晚于時(shí)間窗的關(guān)閉時(shí)刻到達(dá)時(shí)，會(huì)增加調(diào)度成本，增加的成本等于對(duì)應(yīng)的單位時(shí)間懲罰成本與時(shí)差的乘積。

最后，引入了本文供應(yīng)調(diào)度模型中最重要決策變量xkij，它用于判斷車輛k的行駛路線，若車輛k從節(jié)點(diǎn)i駛向節(jié)點(diǎn)j，則xkij=1；否則xkij=0。

根據(jù)以上的模型描述與符號(hào)定義，可對(duì)資源協(xié)同供應(yīng)調(diào)度模型進(jìn)行如下的公式化歸納：

其中：式（1）的目標(biāo)函數(shù)為最小化調(diào)度總成本，等式右邊第1項(xiàng)對(duì)所有車輛的行駛成本求和，第2項(xiàng)對(duì)所有車輛的固定成本求和，第3項(xiàng)計(jì)算總的時(shí)間成本；約束（2）要求從每個(gè)配送中心出發(fā)的車輛數(shù)量不超過可用車數(shù)；約束（3）確保每個(gè)需求地僅被一輛車服務(wù)一次；約束（4）表示每輛車從一個(gè)配送中心，并在一個(gè)配送中心結(jié)束；約束（5）確保了車輛k的行程路徑上各個(gè)需求地點(diǎn)已連接；約束（6）表示車輛不能直接從配送中心i到配送中心j；約束（7）表示車輛數(shù)量返回每個(gè)配送中心的數(shù)量不超過配送中心的車位數(shù)量；約束（8）描述了節(jié)點(diǎn)的訪問順序，若車輛k直接從節(jié)點(diǎn)出發(fā)i到節(jié)點(diǎn)j，則節(jié)點(diǎn)j的到達(dá)時(shí)間必須等于上個(gè)節(jié)點(diǎn)的服務(wù)開始時(shí)間+服務(wù)時(shí)間+行駛時(shí)間；約束（9）確保車輛k在節(jié)點(diǎn)i處的啟動(dòng)服務(wù)時(shí)間晚于或等于其到達(dá)間；約束（10）確保車輛服務(wù)路徑上的需求總數(shù)量小于車輛負(fù)載；約束（11）確保車輛實(shí)際工作時(shí)長(zhǎng)（終點(diǎn)配送中心的到達(dá)時(shí)間-起始配送中心離開時(shí)間）小于最大工作時(shí)長(zhǎng)；約束（12）表示決策變量的范圍；約束（13）和約束（14）分別計(jì)算車輛k提前、推遲到達(dá)需求地點(diǎn)i的時(shí)間差。

3 遺傳-煙花混合算法

供應(yīng)調(diào)度問題是經(jīng)典的NP-hard問題，精確算法可以求得問題的最優(yōu)解，但其時(shí)間復(fù)雜度卻不適用大規(guī)模問題的求解，近年來(lái)的相關(guān)研究多集中在啟發(fā)式算法的創(chuàng)新上。

遺傳算法(genetic algorithm, GA)[21-23]是一種經(jīng)典的群智能算法，針對(duì)建立的資源供應(yīng)調(diào)度模型，本文提出了一種遺傳-煙花混合算法為改善遺傳算法容易“早熟”的缺陷，引入了煙花算法[24-25]中的爆炸操作，擴(kuò)大了遺傳算法的局部搜索范圍，從而加快了對(duì)最優(yōu)解的搜索速度，提高了算法的求解性能，下面對(duì)該算法進(jìn)行詳細(xì)的介紹。

3.1 染色體編解碼

1）編碼規(guī)則

對(duì)于資源協(xié)同供應(yīng)調(diào)度模型，代表模型可行解的染色體應(yīng)該含有資源配送中心信息、維修地點(diǎn)信息、車輛使用信息、車輛的路徑信息等。因此，本文設(shè)計(jì)了如圖3所示的編碼方案，使用自然數(shù)表示的二維向量，其中第一維向量為需求地點(diǎn)ID的全排列，其元素不能存在重復(fù)，而第二維向量為需求地點(diǎn)對(duì)應(yīng)的配送中心ID，其元素可以相同。

圖3 染色體編碼方式示意Fig.3 Chromosome coding method

2）解碼規(guī)則

由于染色體編碼使用了需求地的直接排列，但卻沒有設(shè)置分割車輛信息的基因位置，因此需在解碼階段對(duì)車輛路徑進(jìn)行具體的劃分。為了最大化車輛使用效率，應(yīng)使用盡量少的車輛來(lái)完成資源的配送，染色體解碼被分為了如下兩個(gè)步驟：

① 整體調(diào)度路徑提取。根據(jù)配送中心的ID，將同一配送中心對(duì)應(yīng)的基因按照從左到右的順序依次提取，然后組合成為一條新的“子染色體”，稱為整體調(diào)度路徑，該路徑記錄了該配送中心負(fù)責(zé)保障的所有需求地點(diǎn)的配送順序。

② 車輛行駛路徑劃分。對(duì)于每一條整體調(diào)度路徑，根據(jù)各種約束條件，按照從左到右的順序，將其需求地向量的元素依次加入一個(gè)有序集合，該有序集合稱為車輛行駛路徑。在加入新需求地時(shí)，若違反了模型的約束條件（如車輛運(yùn)載能力、行駛時(shí)間等），則設(shè)置當(dāng)前車輛路徑終點(diǎn)為最近的配送中心，然后另起一個(gè)新的有序集合，繼續(xù)為剩余的需求地劃分車輛路徑，直至當(dāng)前整體調(diào)度路徑中所有需求地都?xì)w入了對(duì)應(yīng)的車輛行駛路徑。

3.2 算法基本要素

1）初始種群

根據(jù)上述編碼方案，按照給定的配送中心和需求地信息，隨機(jī)產(chǎn)生固定數(shù)量(Popsize)的染色體，即可作為混合算法的初始種群。Popsize的大小往往決定了算法的搜索性能，一般需根據(jù)模型輸入數(shù)據(jù)的規(guī)模進(jìn)行調(diào)整，從而保證種群基因的多樣性。

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

對(duì)于本文的保障資源供應(yīng)調(diào)度模型，其優(yōu)化目標(biāo)是使維修資源供應(yīng)調(diào)度方案的總成本最小，算法的目標(biāo)函數(shù)即是調(diào)度總成本，因此適應(yīng)度函數(shù)可用倒數(shù)函數(shù)形式表示，即

式中： C ost(i)為 種群中個(gè)體i的目標(biāo)函數(shù)值； f it(i)即個(gè)體i的染色體所對(duì)應(yīng)的適應(yīng)度， f it(i)越大，被選則的幾率就越大。

3）停止準(zhǔn)則

對(duì)于本文提出的混合算法，其主體結(jié)構(gòu)依舊是遺傳算法，只需設(shè)置一個(gè)迭代次數(shù)的上限Maxgen，當(dāng)算法的迭代次數(shù)達(dá)到該閾值時(shí)候，結(jié)束程序，輸出當(dāng)前的滿意解即可。

4）選擇操作

首先通過精英保留策略直接保留最優(yōu)秀的個(gè)體：根據(jù)適應(yīng)度的大小對(duì)當(dāng)前種群中的個(gè)體降序排列，將一定數(shù)量的優(yōu)秀個(gè)體直接放入子代種群。對(duì)于剩下的個(gè)體采用輪盤賭策略進(jìn)行選擇，具體流程為：先通過式（16）計(jì)算保留概率P(xi)，然后對(duì)所有個(gè)體的保留概率累加，得到個(gè)體的累計(jì)概率分布刻度區(qū)間，最后在(0，1]區(qū)間內(nèi)產(chǎn)生Gap×Popsize個(gè)隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)掉落的刻度區(qū)間確定被選中的染色體。

式中： f it(xi)表 示個(gè)體xi的 適應(yīng)度；P(xi)表示個(gè)體xi的保留概率。

5）交叉操作

本文對(duì)染色體編碼中的兩個(gè)維度采用了不同的交叉方法。第一維編碼向量是需求地編碼的全排列，具有唯一性，簡(jiǎn)單的交叉方法非常容易產(chǎn)生不可行解，因此本文采用的交叉方法為部分匹配交叉法 (partially matching crossover，PMX)。以圖4為例，其具體步驟如下：

①隨機(jī)選擇一對(duì)染色體（父代1和父代2），在染色體上再隨機(jī)選擇兩個(gè)插入點(diǎn)，作為交叉片段的起止位置；

②根據(jù)插入點(diǎn)的位置，交換兩個(gè)父代中的基因片段，并根據(jù)交換的具體基因建立一個(gè)兩兩映射關(guān)系集合。例如，在圖4交換的基因片段中，存在 11-7、1-（2-12）-10、8-6、4-（9）-14 4 個(gè)對(duì)應(yīng)關(guān)系；

圖4 交叉操作流程示意Fig.4 Cross-operation flow diagram

③對(duì)交換基因片段后產(chǎn)生的預(yù)備子代進(jìn)行沖突檢測(cè)與修復(fù)。以預(yù)備子代1為例，交換之后存在重復(fù)基因7、1、6、14。而通過映射關(guān)系可知，這4個(gè)重復(fù)基因依次與基因11、10、8、14匹配，按照該映射規(guī)則進(jìn)行替換，預(yù)備子代1中的基因7、1、6、14被替換為了基因 11、10、8、14，從而得到了無(wú)重復(fù)基因的子代1。預(yù)備子代2也按照同樣的方法根據(jù)映射關(guān)系進(jìn)行修復(fù)即可。

編碼第二維向量為配送中心信息，不具有唯一性，允許元素的重復(fù)出現(xiàn)。因此本文采用簡(jiǎn)單的兩點(diǎn)交叉策略，將父代中虛線所指的配送中心編碼片段兩兩交換即可，如圖4中虛線所示。

6）變異操作

混合算法中變異操作采用簡(jiǎn)單的兩點(diǎn)交換策略，在種群中以一定變異概率隨機(jī)選擇一定數(shù)量的個(gè)體進(jìn)行基因交換，具體步驟十分簡(jiǎn)單：對(duì)選中的個(gè)體，隨機(jī)選擇其染色體上的兩個(gè)基因作為交換點(diǎn)，然后交換它們的位置即可。

7）爆炸算子設(shè)計(jì)

在煙花算法中爆炸操作即為一次鄰域搜索過程，且適應(yīng)度值較好的煙花在較小的范圍內(nèi)產(chǎn)生較多的火花粒子，稱為“局部煙花”，適應(yīng)度值較差的煙花在較大的范圍內(nèi)產(chǎn)生較少的火花粒子，稱為“全局煙花”。遺傳算法種群中適應(yīng)度最好的個(gè)體含有更為優(yōu)秀的遺傳信息，在很大程度上能夠引導(dǎo)算法的收斂方向，因此可以看作一個(gè)產(chǎn)生“局部煙花”的最佳爆炸點(diǎn)；而適應(yīng)度最差的個(gè)體由于其包含了和優(yōu)秀個(gè)體差異程度最大的遺傳信息，能夠使得種群的遺傳信息更加多樣化，因此可以看作產(chǎn)生“全局煙花”的一個(gè)較好爆炸點(diǎn)。

由于本文染色體中需求地和配送中心兩個(gè)向量的生成規(guī)則不同，因此爆炸算子也需要對(duì)不同維度的向量分別進(jìn)行操作，才能保證生成新個(gè)體的正確性，具體的操作分為圖5所示的4種策略。對(duì)于第一維的需求地向量，爆炸算子采用一種隨機(jī)混合方案，對(duì)每一次的爆炸操作，隨機(jī)采用單點(diǎn)交換、插入與反轉(zhuǎn)3種策略中的一種執(zhí)行，如圖5中(a)、(b)、(c)所示；而對(duì)于第二維的配送中心向量，由于無(wú)需考慮沖突檢測(cè)，在上述3種策略之外，還加入了多點(diǎn)變異策略，如圖5(d)。

圖5 爆炸算子示意Fig.5 Flow chart of explosion operator

爆炸算子中的爆炸數(shù)量Si和爆炸半徑Ri的計(jì)算規(guī)則為

式中：Ssum為預(yù)設(shè)的爆炸火花數(shù)；A為爆炸半徑的基值； f t(xi)為個(gè)體xi的適應(yīng)度； f tmax與 f tmin分別為進(jìn)行爆炸操作的個(gè)體中的最大適應(yīng)度值與最小適應(yīng)度值；N為進(jìn)行爆炸操作的個(gè)體的數(shù)量。

爆炸半徑規(guī)定了爆炸操作時(shí)進(jìn)行鄰域搜索的范圍，對(duì)于本文的自然數(shù)編碼方案，爆炸半徑可以對(duì)應(yīng)為爆炸操作的最大執(zhí)行次數(shù)，即對(duì)于煙花i，需要隨機(jī)進(jìn)行1~Ri次爆炸操作才可以得到一個(gè)新的火花。

由于在遺傳算法階段進(jìn)行了相關(guān)變異操作，為避免不必要的運(yùn)算，本文爆炸算子沒有考慮高斯變異火花。由于爆炸數(shù)量根據(jù)個(gè)體的適應(yīng)度計(jì)算的，具有一定的不確定性，因此本文對(duì)Si設(shè)置了上下界：

式中：Smax與Smin分別為的預(yù)先設(shè)置的最大、最小爆炸火花數(shù)量。

最后為了保證種群規(guī)模不變，規(guī)定每次保留Smin個(gè)火花作為爆炸算子產(chǎn)生的新個(gè)體，加入遺傳算法的種群中，進(jìn)行混合算法的下一輪迭代。

3.3 混合算法流程

混合算法的基本流程如圖6所示，分為初始化、遺傳進(jìn)化和爆炸優(yōu)化3個(gè)階段。

圖6 遺傳–煙花混合算法流程圖Fig.6 Flow chart of genetic-firework hybrid algorithm

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與算法參數(shù)

由于本章建立的資源供應(yīng)調(diào)度模型屬于MDVRPTW模型的一個(gè)擴(kuò)展，相較于原模型增加了許多新約束，目前還沒有公開標(biāo)準(zhǔn)數(shù)據(jù)可用于測(cè)試驗(yàn)證。因此，本文引入了國(guó)際通用的MDVRPTW公開基準(zhǔn)數(shù)據(jù)集[26]，并對(duì)其進(jìn)行了補(bǔ)充與改造。

實(shí)驗(yàn)從Cordeau數(shù)據(jù)集中選擇10個(gè)具有代表性的基礎(chǔ)實(shí)例，為其增加了車輛、車位和工作時(shí)長(zhǎng)限制，得到了A1~A5和B1~B5兩組共10個(gè)實(shí)驗(yàn)算例，如表1。對(duì)于A、B兩組數(shù)字序號(hào)相同的算例，其節(jié)點(diǎn)地理分布是完全相同的，但A組算例具有較窄的時(shí)間窗口，B組算例具有較寬的時(shí)間窗口。

表1 實(shí)驗(yàn)算例基本信息Table 1 Basic information of experimental examples

為了便于對(duì)比，相關(guān)變量及參數(shù)的取值如表2，參數(shù)測(cè)試候選值和最終取值見表3。

表2 模型參數(shù)值設(shè)置Table 2 Model parameter value setting

表3 混合算法參數(shù)Table 3 Hybrid algorithm parameters

遺傳-煙花混合算法是一種啟發(fā)式算法，啟發(fā)參數(shù)的好壞往往決定了算法的性能。因此本文使用表1中的算例進(jìn)行了參數(shù)評(píng)估。

4.2 算法性能對(duì)比

單個(gè)的算例的運(yùn)行結(jié)果具有一定的局限性，為了進(jìn)一步對(duì)比算法的求解性能，本文對(duì)遺傳算法、煙花算法以及混合算法在同樣的硬件條件下，對(duì)表1中的10個(gè)算例分別進(jìn)行了對(duì)比實(shí)驗(yàn)。為了保障實(shí)驗(yàn)的公平性，對(duì)于相同的算例，3種算法的候選解規(guī)模、迭代次數(shù)以及初始種群都設(shè)置完全相同。

1）求解質(zhì)量對(duì)比

為了綜合對(duì)比算法的求解質(zhì)量，記錄3種算法10次運(yùn)行結(jié)果中目標(biāo)函數(shù)的最優(yōu)值、平均值以及標(biāo)準(zhǔn)差分別如表4、表5和表6所示。

表5 目標(biāo)函數(shù)平均值Table 5 Average value of objective function

表6 目標(biāo)函數(shù)標(biāo)準(zhǔn)差Table 6 Standard deviation of objective function

對(duì)比表4和5中的目標(biāo)函數(shù)值可以明顯看出，在絕大部分算例上，無(wú)論是最優(yōu)值還是平均值，混合算法都比遺傳算法和煙花算法要小，這說(shuō)明混合算法具有最好的求解質(zhì)量，得到的滿意解更加逼近實(shí)際最優(yōu)解，得到了調(diào)度成本最小的方案。

表4 目標(biāo)函數(shù)最優(yōu)值Table 4 Optimal value of objective function

2）求解速度對(duì)比

為了綜合對(duì)比算法的求解速度，分別統(tǒng)計(jì)3種算法在各算例上10次運(yùn)行結(jié)果中初次找到滿意解時(shí)的平均迭代次數(shù)及平均運(yùn)行時(shí)長(zhǎng)（單位：s），如圖7所示。

圖7 初次找到滿意解的平均迭代次數(shù)Fig.7 Average number of iterations to find a satisfactory solution for the first time

綜合求解質(zhì)量和求解速度的結(jié)果來(lái)看：混合算法求解質(zhì)量是最好的，其收斂速度也快于煙花算法和遺傳算法，但在運(yùn)行時(shí)間上會(huì)略慢于遺傳算法，即混合算法在略微增加了一些運(yùn)算成本的情況下獲得了更好的求解質(zhì)量。而增加的運(yùn)算成本可以通過硬件配置進(jìn)一步縮小，但對(duì)于求解質(zhì)量，其他兩種算法卻無(wú)法靠簡(jiǎn)單的硬件升級(jí)進(jìn)行彌補(bǔ)，因此混合算法是3種算法中綜合性能最強(qiáng)的算法。

從理論上對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，由于遺傳算法種群中適應(yīng)度最好的個(gè)體其包含更為優(yōu)秀的遺傳信息，對(duì)其進(jìn)行爆炸操作能在很大程度上能夠引導(dǎo)算法的收斂方向，而適應(yīng)度最差的個(gè)體由于包含了和優(yōu)秀個(gè)體差異程度最大的遺傳信息，能夠使得種群的遺傳信息更加豐富，從而擴(kuò)大了局部搜索的范圍。對(duì)兩種算法進(jìn)行混合，充分結(jié)合了遺傳算法全局搜索能力強(qiáng)和煙花算法局部搜索能力強(qiáng)的特點(diǎn)，使得混合算法在收斂速度和搜索范圍上都得到了改善，從而能夠以更快的速度得到更小成本的調(diào)度方案，這對(duì)于實(shí)際的資源供應(yīng)調(diào)度具有重要的經(jīng)濟(jì)效益。

5 結(jié)束語(yǔ)

本文針對(duì)建立的維修資源供應(yīng)調(diào)度模型，本文提出了一種遺傳-煙花混合算法?；旌纤惴ㄔ谶z傳算法的基礎(chǔ)上，引入了煙花爆炸算子，使得種群優(yōu)秀個(gè)體的數(shù)量增多，增強(qiáng)了算法的局部尋優(yōu)能力。通過仿真對(duì)比實(shí)驗(yàn)，結(jié)果表明本文提出的混合算法可以得到成本更低的調(diào)度方案，同時(shí)具有更快的收斂速度，并且適用于各種規(guī)模的資源供應(yīng)調(diào)度需求。