一種面向維修資源配送調度的遺傳–煙花混合算法

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

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

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

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

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

1 問題描述

1.1 配送式資源供應

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

圖1 配送式維修資源供應Fig.1 Distribution type maintenance resource supply

1.2 約束條件

1）時間約束

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

圖2 時間窗分類Fig.2 Time window classification

2）車輛使用性約束

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

① 承載約束

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

② 行駛上限約束

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

③ 使用數(shù)量約束

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

1.3 半開放配送中心

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

2 數(shù)學模型

考慮到計算的方便性以及仿真實驗的可行性，模型采用如下基本假設：

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

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

3)采用同類型的配送車輛，車輛與需求地點之間為一對多的關系；

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

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

6)車輛到達需求地點的時間應在允許的時間范圍內波動，如果車輛在規(guī)定時間之外到達，則會進行處罰，增加一定的供應成本；

7)車輛在每個節(jié)點存在裝卸貨物的時間，稱為服務時間，服務時間在車輛到達后才能開始計時，服務結束后車輛才可以離開。

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

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

對于每個需求節(jié)點vi∈C，有著與其對應的資源需求量qi，裝卸服務時間si，以及供應時間窗口[ei,li]，其中ei是 接受配送的最早開始時間，li是接受配送的最晚時間。

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

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

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

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

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

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

3 遺傳-煙花混合算法

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

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

3.1 染色體編解碼

1）編碼規(guī)則

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

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

2）解碼規(guī)則

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

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

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

3.2 算法基本要素

1）初始種群

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

2）適應度函數(shù)

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

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

3）停止準則

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

4）選擇操作

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

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

5）交叉操作

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

①隨機選擇一對染色體（父代1和父代2），在染色體上再隨機選擇兩個插入點，作為交叉片段的起止位置；

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

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

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

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

6）變異操作

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

7）爆炸算子設計

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

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

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

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

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

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

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

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

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

3.3 混合算法流程

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

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

4 實驗結果與分析

4.1 實驗數(shù)據(jù)與算法參數(shù)

由于本章建立的資源供應調度模型屬于MDVRPTW模型的一個擴展，相較于原模型增加了許多新約束，目前還沒有公開標準數(shù)據(jù)可用于測試驗證。因此，本文引入了國際通用的MDVRPTW公開基準數(shù)據(jù)集[26]，并對其進行了補充與改造。

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

表1 實驗算例基本信息Table 1 Basic information of experimental examples

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

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

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

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

4.2 算法性能對比

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

1）求解質量對比

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

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

表6 目標函數(shù)標準差Table 6 Standard deviation of objective function

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

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

2）求解速度對比

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

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

綜合求解質量和求解速度的結果來看：混合算法求解質量是最好的，其收斂速度也快于煙花算法和遺傳算法，但在運行時間上會略慢于遺傳算法，即混合算法在略微增加了一些運算成本的情況下獲得了更好的求解質量。而增加的運算成本可以通過硬件配置進一步縮小，但對于求解質量，其他兩種算法卻無法靠簡單的硬件升級進行彌補，因此混合算法是3種算法中綜合性能最強的算法。

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

5 結束語

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