采用雙檔案協(xié)同進(jìn)化離散多目標(biāo)煙花算法的低碳疫苗冷鏈優(yōu)化配送*

申曉寧，游 璇，陳慶洲，潘紅麗，黃 遙

(1.南京信息工程大學(xué)自動(dòng)化學(xué)院,江蘇 南京 210044；2.江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心,江蘇 南京 210044；3.江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210044)

1 引言

隨著計(jì)劃免疫和常態(tài)化防疫工作的深入開(kāi)展，疫苗的需求量不斷攀升，疫苗冷鏈物流成為現(xiàn)代物流中的一個(gè)重要分支[1]。因此，低碳疫苗冷鏈優(yōu)化配送已成為亟需解決的一類實(shí)際物流應(yīng)用問(wèn)題。該問(wèn)題對(duì)固定數(shù)量的配送車輛進(jìn)行路徑規(guī)劃，它的成功求解，能使疫苗的冷鏈配送服務(wù)更有秩序、效率更高，及時(shí)滿足各個(gè)地區(qū)的疫苗需求，提高當(dāng)?shù)氐娜嗣窠】蹬c醫(yī)療衛(wèi)生服務(wù)水平，同時(shí)有效減少二氧化碳的排放量，改善周圍大氣環(huán)境。

目前，國(guó)內(nèi)外研究人員已經(jīng)分別對(duì)疫苗的運(yùn)輸策略和配送方式等進(jìn)行了研究。de Carvalho等[2]提出了一個(gè)多目標(biāo)、多周期的混合整數(shù)線性規(guī)劃模型，用于可持續(xù)疫苗供應(yīng)鏈的設(shè)計(jì)和規(guī)劃，并以一家歐洲公司為典型案例進(jìn)行了詳細(xì)研究。基于包括分銷商和零售商的疫苗供應(yīng)鏈，Qi等[3]提出了一個(gè)基本模型研究分銷商通過(guò)冷鏈或非冷鏈運(yùn)輸疫苗的條件和冷鏈運(yùn)輸?shù)牟呗浴｀嵑芠4]根據(jù)疫苗的保存條件、流通特征等，對(duì)長(zhǎng)途和短途的疫苗冷鏈配送問(wèn)題分別進(jìn)行了詳細(xì)的研究，提出了能夠規(guī)避風(fēng)險(xiǎn)且降低成本的運(yùn)輸策略。陳勇等[5]建立了多品種疫苗的共同配送模型，有利于提升疫苗運(yùn)輸?shù)臅r(shí)效性，并減少運(yùn)輸成本。鄭春姣[6]以泰豐生物制品有限公司為例，分析現(xiàn)有疫苗冷鏈配送方案存在的不足，并從組織結(jié)構(gòu)、配送方式和冷藏包裝等方面對(duì)方案進(jìn)行了改進(jìn)，促進(jìn)了公司在疫苗冷鏈業(yè)務(wù)上的發(fā)展。

煙花算法是由譚營(yíng)等[7]在2010年首次提出的一種元啟發(fā)式算法。它模擬煙花在夜空中爆炸的過(guò)程，將煙花爆炸產(chǎn)生的火花看作問(wèn)題的一個(gè)解，將煙花爆炸產(chǎn)生多個(gè)火花的過(guò)程看作其搜索鄰域的過(guò)程。目前，煙花算法已成功應(yīng)用于復(fù)雜網(wǎng)絡(luò)關(guān)鍵點(diǎn)集確定[8]、多區(qū)域電力系統(tǒng)調(diào)度[9]、電能交易[10]等多個(gè)實(shí)際問(wèn)題的求解。本文提出一種雙檔案協(xié)同進(jìn)化離散多目標(biāo)煙花算法，簡(jiǎn)稱DTAMOFWA(Discrete Two-Archive-based Multi-Objective FireWorks Algorithm)。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了改進(jìn)策略的有效性，并將DTAMOFWA與4種已有算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，所提算法在低碳疫苗冷鏈配送問(wèn)題上具有更好的求解性能。

2 低碳疫苗冷鏈配送問(wèn)題的數(shù)學(xué)模型

為了使疫苗在規(guī)定的客戶(包括醫(yī)院、各級(jí)疾控中心、診所等)時(shí)間窗內(nèi)盡快送達(dá)并產(chǎn)生較少的碳排放量，本文將低碳疫苗冷鏈配送問(wèn)題建模為約束多目標(biāo)優(yōu)化模型，最小化運(yùn)輸成本和平均客戶不滿意度，同時(shí)考慮可用車數(shù)量約束、車輛容量約束和模糊時(shí)間窗約束[11]。

2.1 問(wèn)題描述

低碳疫苗冷鏈配送問(wèn)題的描述如下：存在1個(gè)配送中心(編號(hào)為0)和n個(gè)客戶(編號(hào)為1～n)，由一定數(shù)量的同類型配送車輛對(duì)各個(gè)客戶進(jìn)行配送服務(wù)，目標(biāo)是在滿足約束的條件下使運(yùn)輸?shù)目偝杀竞涂蛻舨粷M意度盡可能地小。配送方案需滿足客戶對(duì)疫苗需求量和模糊時(shí)間窗的要求，每個(gè)子回路中所有客戶的需求量之和不超出配送車輛的容量限制，且實(shí)際配送車輛數(shù)不超過(guò)配送中心可用車輛數(shù)。每輛車從配送中心出發(fā)和回到配送中心時(shí)均需進(jìn)行一定時(shí)間的消毒。配送車輛在疫苗配送過(guò)程中每間隔一定時(shí)間需對(duì)制冷設(shè)備添加一次制冷劑。

2.2 符號(hào)和變量

低碳疫苗冷鏈配送問(wèn)題數(shù)學(xué)模型中的符號(hào)和變量含義如下所示：

n:客戶數(shù)量；

K:可用車輛數(shù)；

Q:運(yùn)輸車輛的最大容量(t)；

w:運(yùn)輸車輛的自身重量(t)；

qi:客戶i的需求量(t)；

dij:從客戶i處到客戶j處的車輛行駛距離(km)；

lij:從客戶i處行駛到客戶j處時(shí)的車輛載重(t)；

vij:從客戶i處到客戶j處的車輛行駛速度(km/h)；

Ce:碳稅(元/噸)；

FE:燃油排放參數(shù)(t/L)；

a:車輛行駛加速度(m/s2)；

g:重力加速度常量(m/s2)；

θij:從客戶i處到客戶j處這一路段的路面坡度；

Cr:滾動(dòng)阻力系數(shù)；

Cd:牽引力系數(shù)；

A:車輛正面表面積(m2)；

ρ:空氣密度(kg/m3)；

P1:單位貨物在行駛單位距離時(shí)制冷產(chǎn)生的碳排放量(t/km)；

P2:每小時(shí)司機(jī)的薪酬(元/小時(shí))；

tdis:車輛在配送中心的消毒時(shí)間(h)；

tsi:車輛在客戶i處的服務(wù)時(shí)間(h)；

P3:制冷劑單價(jià)(元)；

T:添加制冷劑的間隔時(shí)間(h)；

[ETi,LTi]:客戶i可接受的時(shí)間窗；

[ETi′,LTi′]:客戶i期望的時(shí)間窗；

ti:車輛到達(dá)客戶i的時(shí)刻；

t0:車輛的出發(fā)時(shí)刻；

U0:疫苗在出發(fā)時(shí)的品質(zhì)；

σ：疫苗品質(zhì)的衰減指數(shù)。

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

低碳疫苗冷鏈配送問(wèn)題的數(shù)學(xué)模型中，定義決策變量如式(1)和式(2)所示:

(1)

(2)

目標(biāo)函數(shù)和約束條件如式(3)～式(12)所示：

minZ1=C11+C12+C2+C3=

(3)

(4)

(5)

其中，式(3)表示運(yùn)輸成本目標(biāo)函數(shù)，包括油耗碳排放成本C11、制冷碳排放成本C12、司機(jī)薪酬C2和制冷劑成本C3。采用一種綜合的碳排放計(jì)量模型，同時(shí)考慮行駛距離、速度等多種因素對(duì)車輛耗油量的影響，通過(guò)燃油排放參數(shù)與耗油量的乘積獲得車輛在該路段行駛產(chǎn)生的碳排放量[12]。式(4)表示平均客戶不滿意度目標(biāo)函數(shù)，包括平均時(shí)間不滿意度和平均品質(zhì)損失程度。式(5)為車輛到達(dá)客戶i處時(shí)的時(shí)間滿意度。式(6)～(12)為約束條件，式(6)表示每個(gè)客戶只能由一輛車服務(wù)；式(7)和式(8)表示對(duì)于每個(gè)被服務(wù)的客戶點(diǎn)，一定會(huì)有一輛車從某個(gè)地點(diǎn)行駛到該客戶點(diǎn)，并從該客戶點(diǎn)離開(kāi)；式(9)為經(jīng)典的子回路消除約束，保證每輛車的行駛路線中沒(méi)有子回路；式(10)為車輛容量約束；式(11)為車輛數(shù)量約束；式(12)為模糊時(shí)間窗約束。

3 雙檔案協(xié)同進(jìn)化的離散多目標(biāo)煙花算法DTAMOFWA

針對(duì)低碳疫苗冷鏈配送問(wèn)題數(shù)學(xué)模型的特點(diǎn)，本文提出雙檔案協(xié)同進(jìn)化的離散多目標(biāo)煙花算法DTAMOFWA，設(shè)計(jì)了消除車輛數(shù)量和容量約束的解碼方式、部分映射爆炸算子和雙外部檔案協(xié)同進(jìn)化機(jī)制，以提高算法的求解性能。

3.1 個(gè)體編碼和消除車輛約束的解碼方式

DTAMOFWA采用整數(shù)編碼，對(duì)于包含n個(gè)客戶(編號(hào)為1～n)的問(wèn)題，每個(gè)個(gè)體的編碼均為一串整數(shù)序列，其中每個(gè)整數(shù)的取值在1～n。由于低碳疫苗冷鏈配送問(wèn)題帶有較多強(qiáng)約束條件，導(dǎo)致搜索過(guò)程中容易產(chǎn)生大量不可行解，不利于最優(yōu)配送方案的求解。因此，在DTAMOFWA中設(shè)計(jì)了一種消除車輛數(shù)量和容量約束的解碼方式。首先，對(duì)整數(shù)編碼序列按車輛容量約束和模糊時(shí)間窗約束進(jìn)行解碼，即從配送中心出發(fā)，依次訪問(wèn)編碼中的各個(gè)客戶。若某客戶違反上述2個(gè)約束中的任一個(gè)，則該子回路結(jié)束，并將違反約束的客戶作為下一個(gè)新子回路的第1個(gè)訪問(wèn)對(duì)象，直到所有的客戶均被訪問(wèn)，解碼結(jié)束。此后，判斷子回路數(shù)量，即使用的車輛數(shù)是否超過(guò)問(wèn)題可用車輛數(shù)，若不超過(guò)，則所得解為可行解；若超過(guò)，則對(duì)原整數(shù)編碼個(gè)體僅按車輛容量約束重新解碼，并采用一種新型修復(fù)算子，使得已經(jīng)滿足車輛容量約束的序列進(jìn)一步滿足車輛數(shù)量約束，從而得到僅違反模糊時(shí)間窗約束的解。

該修復(fù)算子對(duì)客戶訪問(wèn)序列按車輛容量約束解碼后，當(dāng)子回路數(shù)量達(dá)到可用車輛數(shù)時(shí)，將剩余未訪問(wèn)的所有客戶放入一個(gè)集合中。對(duì)該集合依次進(jìn)行插入操作和置換操作，刪除滿足特定條件的客戶編號(hào)。若集合變?yōu)榭占瑒t該修復(fù)操作終止；若集合無(wú)法變?yōu)榭占唇?jīng)插入和置換操作后，仍不能同時(shí)滿足車輛數(shù)量和容量約束，則隨機(jī)初始化一串訪問(wèn)序列替代原整數(shù)編碼個(gè)體，并重新解碼。插入操作是指:依次判斷集合中每個(gè)編號(hào)是否能在不違反車輛容量約束的前提下插入某個(gè)已有子回路。若能，則將該編號(hào)插入已有子回路中并將其從集合中刪除；若不能，則保留在集合中等待進(jìn)行置換操作。置換操作是指：對(duì)集合中的每個(gè)編號(hào)，在不違反車輛容量約束的前提下將其與每個(gè)子回路最小客戶需求量對(duì)應(yīng)的編號(hào)進(jìn)行置換。若置換成功，則對(duì)當(dāng)前集合進(jìn)行插入操作；若置換失敗，則將該編號(hào)繼續(xù)留在集合中。以客戶數(shù)量為8，可用車輛數(shù)為3，車輛最大容量為12為例，2種操作如圖1所示。圖1中，qi表示客戶i的需求量，Y1為執(zhí)行操作前的解，0為配送中心的編號(hào)，子回路分別為k1,k2,k3和k4，Y′1為執(zhí)行操作后所得解。

Figure 1 Repair operator for eliminating vehicle quantity constraint and vehicle capacity constraint

本文所提解碼方式能有效消除車輛數(shù)量和容量約束，生成解大部分為可行解，少數(shù)不可行解也可通過(guò)修復(fù)算子將其轉(zhuǎn)化成只違反模糊時(shí)間窗約束的解。該操作大大增加了尋優(yōu)過(guò)程中可行解的獲取數(shù)量，降低了因不可行解數(shù)量大而為搜索帶來(lái)的難度。同時(shí)，算法僅需對(duì)模糊時(shí)間窗約束進(jìn)行處理，提高了算法的搜索效率。

3.2 部分映射爆炸算子

由于低碳疫苗配送問(wèn)題屬于組合優(yōu)化問(wèn)題，原來(lái)求解連續(xù)優(yōu)化問(wèn)題的爆炸算子在本文中并不適用。為了使產(chǎn)生的爆炸火花更均勻地分布在以煙花為圓心、一定幅度為半徑的圓形區(qū)域內(nèi)，充分利用有限的計(jì)算資源進(jìn)行搜索，本文設(shè)計(jì)了部分映射爆炸算子，考慮通過(guò)個(gè)體編碼中發(fā)生變化的編號(hào)個(gè)數(shù)，來(lái)表示決策空間中在煙花周圍產(chǎn)生的位移大小。該算子采用新的爆炸半徑計(jì)算公式，并融合部分映射交叉操作生成固定數(shù)量的爆炸火花。部分映射交叉所選取的編碼片段長(zhǎng)度由所計(jì)算的爆炸半徑?jīng)Q定。

假設(shè)煙花種群大小為N，問(wèn)題決策變量維數(shù)為n，目標(biāo)個(gè)數(shù)為m。所提爆炸算子計(jì)算第i個(gè)煙花Xi的爆炸半徑的方法如下：首先將Xi的m個(gè)目標(biāo)值分別進(jìn)行歸一化并相乘，得到乘積M(Xi)，如式(13)所示;其后，再將M(Xi)歸一化的結(jié)果與決策變量維數(shù)n相乘，以確定Xi的爆炸半徑Ai，即Xi需要發(fā)生爆炸的決策變量個(gè)數(shù)即客戶點(diǎn)個(gè)數(shù)，如式(14)所示：

(13)

i=1,2,…,N

(14)

其中，fs(Xi)、fsmax和fsmin分別表示煙花Xi的第s個(gè)目標(biāo)值、當(dāng)前種群中所有N個(gè)煙花在第s個(gè)目標(biāo)上的最大值和最小值；M(Xi)為各目標(biāo)歸一化后結(jié)果的乘積；Mmax和Mmin為當(dāng)前種群中所有N個(gè)煙花對(duì)應(yīng)乘積中的最大值和最小值;[·]表示四舍五入取整操作。根據(jù)式(14)計(jì)算煙花的爆炸半徑，當(dāng)某個(gè)煙花靠近一個(gè)極端解，即某一目標(biāo)值很小時(shí)，歸一化后的乘積較小，因此得到的爆炸半徑也較小；當(dāng)2個(gè)目標(biāo)值都較大時(shí)，歸一化后的乘積較大，因此得到的爆炸半徑也較大；當(dāng)2個(gè)目標(biāo)值均比較折衷時(shí)，此時(shí)煙花在目標(biāo)空間上處于當(dāng)前Pareto前沿的中間位置。若該煙花更靠近坐標(biāo)原點(diǎn)，說(shuō)明其更接近真實(shí)Pareto最優(yōu)前沿(最小化問(wèn)題)，歸一化后的乘積較小，得到的爆炸半徑較小；若該煙花離最優(yōu)前沿較遠(yuǎn)，則歸一化后的乘積與前一種情況相比較大，得到的爆炸半徑相對(duì)較大。根據(jù)上述原理，所提爆炸半徑計(jì)算公式能夠合理地控制不同適應(yīng)度煙花的爆炸半徑，使得適應(yīng)度較好的煙花實(shí)現(xiàn)較小范圍的精細(xì)搜索，適應(yīng)度較差的煙花實(shí)現(xiàn)較大范圍的搜索。

令每個(gè)煙花產(chǎn)生4種爆炸半徑的爆炸火花，其爆炸半徑如式(15)所示：

(15)

每個(gè)爆炸火花的爆炸半徑確定后，對(duì)每個(gè)煙花，將編碼中的配送中心0刪除，得到一串客戶的訪問(wèn)序列。隨機(jī)選取4個(gè)其它煙花的客戶訪問(wèn)序列，分別與當(dāng)前煙花進(jìn)行部分映射交叉操作。ri1,ri2,ri3和ri4分別為每次交叉所選取的片段長(zhǎng)度，交叉后按各自原配送中心位置解碼可得到2個(gè)爆炸火花。以客戶數(shù)量為8的序列為例，設(shè)爆炸半徑即交叉選取的片段長(zhǎng)度為4，則部分映射爆炸算子的操作過(guò)程如圖2所示。X1和X2為2個(gè)煙花個(gè)體;子回路為k1,k2和k3;B1和B2為X1和X2的客戶訪問(wèn)序列。B′1和B′2為將部分片段交叉后得到的客戶訪問(wèn)序列。此時(shí)，B′1未交叉的部分與已交叉部分有重復(fù)的客戶點(diǎn)，B′2也是如此。根據(jù)圖2中的映射關(guān)系，將B′1和B′2未交叉部分的重復(fù)客戶點(diǎn)分別進(jìn)行替換，得到2個(gè)沒(méi)有重復(fù)客戶點(diǎn)的客戶訪問(wèn)序列S1和S2，最后按X1和X2的配送中心位置解碼得到2個(gè)爆炸火花E1和E2。

Figure 2 Partial mapping explosion operator

所提部分映射爆炸算子通過(guò)控制煙花的爆炸半徑，交換煙花個(gè)體中不同長(zhǎng)度的片段，使得個(gè)體之間能夠進(jìn)行不同程度的信息交流，讓煙花根據(jù)自身特點(diǎn)在范圍不同的區(qū)域內(nèi)進(jìn)行搜索，從而實(shí)現(xiàn)了算法在局部尋優(yōu)和全局尋優(yōu)之間的平衡。但是，由于該算子只對(duì)客戶訪問(wèn)序列進(jìn)行操作，配送中心的位置保持不變，限制了種群的多樣性。

3.3 雙外部檔案協(xié)同進(jìn)化機(jī)制

一些已有的多目標(biāo)優(yōu)化算法中處理約束的方法是直接將搜索過(guò)程產(chǎn)生的不可行解淘汰，只對(duì)可行解進(jìn)行操作。但是，該方法不僅會(huì)丟失不可行解中的有用信息，且還可能導(dǎo)致種群同化現(xiàn)象嚴(yán)重。另外，在約束優(yōu)化問(wèn)題中，在可行域邊界的不可行解約束違反程度較小，若在其附近進(jìn)行局部搜索，則易于得到大量可行解。為解決上述問(wèn)題，本文采用可行解檔案和不可行解檔案協(xié)同進(jìn)化機(jī)制，如圖3所示。DTAMOFWA設(shè)置了可行解檔案和不可行解檔案2個(gè)不重疊的外部檔案，分別保存可行解和不可行解中的精英個(gè)體。

Figure 3 Schematic diagram of the coevolutionary mechanism of two external archives

對(duì)不可行解檔案實(shí)施可行性搜索，可能生成新的可行解和不可行解。為了避免對(duì)同一個(gè)不可行解進(jìn)行重復(fù)搜索，若不可行解檔案中的個(gè)體數(shù)量大于煙花種群規(guī)模N，則每次從不可行解檔案中隨機(jī)選擇N個(gè)個(gè)體進(jìn)行可行性搜索；否則，對(duì)不可行解檔案中的所有個(gè)體進(jìn)行可行性搜索。按照3.1節(jié)消除車輛數(shù)量和容量約束的解碼方式進(jìn)行解碼，種群中的不可行解均只違反模糊時(shí)間窗約束。因此，可行性搜索策略對(duì)某個(gè)配送方案中違反時(shí)間窗約束程度最大的子回路，按客戶可接受到達(dá)時(shí)間進(jìn)行排序，所得的新配送方案稱為可行性搜索火花。為了防止產(chǎn)生的新解相似度過(guò)高，導(dǎo)致出現(xiàn)早熟收斂的情況，所提可行性搜索策略每次僅對(duì)違反約束程度最大的一個(gè)子回路進(jìn)行調(diào)整。以客戶數(shù)量為8，車輛數(shù)為3的序列為例，可行性搜索如圖4所示。其中，k1為違反時(shí)間窗約束程度最大的子回路。編號(hào)下方的時(shí)間為客戶的可接受到達(dá)時(shí)間，優(yōu)先選擇可接受到達(dá)時(shí)間早的客戶，以降低不可行解的約束違反程度。

Figure 4 Feasibility search strategy

對(duì)于不可行解檔案經(jīng)可行性搜索后產(chǎn)生的可行解，將其與子代中的非支配個(gè)體共同進(jìn)行目標(biāo)驅(qū)動(dòng)的啟發(fā)式擴(kuò)展搜索。該搜索操作利用問(wèn)題目標(biāo)中包含的啟發(fā)信息——碳排放量和客戶不滿意度，將個(gè)體中碳排放和客戶不滿意度最大的子回路的客戶編號(hào)重新排序。排序時(shí)依次選擇碳排放量或客戶不滿意度最小的路段終點(diǎn)編號(hào)作為下一個(gè)訪問(wèn)客戶。經(jīng)過(guò)該操作后，用所得解更新可行解檔案，使其在可行空間不斷向Pareto最優(yōu)前沿進(jìn)化。此外，利用可行性搜索產(chǎn)生的不可行解，根據(jù)時(shí)間窗約束違反程度更新不可行解檔案，使其在約束空間向可行區(qū)域不斷移動(dòng)，達(dá)到2個(gè)外部檔案協(xié)同進(jìn)化的效果。若不可行解檔案規(guī)模超過(guò)預(yù)設(shè)外部檔案的最大規(guī)模，依次選取其中約束違反程度最小的解進(jìn)入不可行解檔案；否則，不可行解檔案保持不變。

采用雙外部檔案協(xié)同進(jìn)化機(jī)制，能夠充分利用不可行解中的有用信息不斷推進(jìn)搜索進(jìn)程，提高搜索效率。此外，由于可行性搜索沒(méi)有對(duì)子回路中的客戶進(jìn)行增刪操作，因此得到的新配送方案依然不違反車輛的容量和數(shù)量約束。

3.4 算法的求解步驟

步驟1初始化。對(duì)問(wèn)題模型及算法中的變量和相關(guān)參數(shù)進(jìn)行初始化設(shè)置。均勻隨機(jī)生成規(guī)模為N的煙花種群POP(POPulation)，根據(jù)消除車輛約束的解碼方式進(jìn)行解碼，并計(jì)算其目標(biāo)向量。將POP中的可行解加入可行檔案Feasible，不可行解加入不可行解檔案Infeasible。設(shè)置當(dāng)前目標(biāo)評(píng)價(jià)次數(shù)Eva=N，最大目標(biāo)評(píng)價(jià)次數(shù)為Evamax。

步驟2部分映射爆炸算子。每個(gè)煙花根據(jù)4種不同的爆炸半徑通過(guò)部分映射交叉操作產(chǎn)生8個(gè)爆炸火花。更新Eva=Eva+ 8*N。

步驟3變異算子。對(duì)每個(gè)煙花編碼進(jìn)行隨機(jī)的兩點(diǎn)交換操作。更新Eva=Eva+N。

步驟4將爆炸火花和變異火花中的非支配解加入NDS(Non-Dominated Set)，并將其中的不可行解加入Infeasible。

步驟5對(duì)Infeasible進(jìn)行可行性搜索，得到可行性搜索火花，其中可行解集為F，不可行解集為I，將Infeasible更新為I。更新Eva=Eva+N。

步驟6對(duì)NDS和F的并集實(shí)施目標(biāo)驅(qū)動(dòng)的啟發(fā)式擴(kuò)展搜索，得到擴(kuò)展搜索火花SS(Search Sparks)。更新Eva=Eva+ 2*|NDS|。

步驟7更新種群。分別根據(jù)Pareto支配概念和ε支配概念[13],用NDS和SS的并集更新POP和Feasible。若規(guī)模超出最大預(yù)設(shè)值，則根據(jù)擁擠距離對(duì)POP和Feasible進(jìn)行裁剪。使用I更新Infeasible。

步驟8選擇策略。從POP和Feasible中各隨機(jī)選擇N/2個(gè)個(gè)體，若Feasible中個(gè)體數(shù)量小于N/2，則用POP中的個(gè)體補(bǔ)充。在選出的煙花種群中隨機(jī)選擇一個(gè)個(gè)體，計(jì)算該個(gè)體與其他煙花的相似度，即個(gè)體編碼中對(duì)應(yīng)位置編號(hào)相同的位置個(gè)數(shù)。將相似度高于80%的個(gè)體進(jìn)行隨機(jī)長(zhǎng)度的循環(huán)移位操作。

步驟9終止條件。若Eva≤Evamax，則轉(zhuǎn)移到步驟2；否則循環(huán)結(jié)束，輸出Feasible。

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

本文所有實(shí)驗(yàn)均在Intel(R)Core(TM)i5-10210U CPU@1.60 GHz，運(yùn)行內(nèi)存為12 GB的計(jì)算機(jī)上采用Matlab R2019a軟件運(yùn)行。根據(jù)對(duì)實(shí)際疫苗冷鏈配送過(guò)程的調(diào)研，生成不同規(guī)模的4個(gè)仿真實(shí)例，以驗(yàn)證3種改進(jìn)策略的有效性和所提算法DTAMOFWA的整體性能。所有對(duì)比算法均在仿真實(shí)例上分別進(jìn)行30次獨(dú)立實(shí)驗(yàn)，每次實(shí)驗(yàn)的最大目標(biāo)函數(shù)評(píng)價(jià)次數(shù)Evamax為50 000。實(shí)驗(yàn)中采用反世代距離IGD(Inverted Generational Distance)[14]和超體積HV(HyperVolume)[15]作為綜合性能評(píng)價(jià)指標(biāo)，對(duì)于計(jì)算HV時(shí)所需的參考點(diǎn)獲取方式如下：將所有算法求得的非支配解在各目標(biāo)上的最差值(最小化問(wèn)題為最大值，最大化問(wèn)題為最小值)分別放大1.5倍。將所有算法運(yùn)行30次所得的全部非支配解合并成一個(gè)新的解集，再?gòu)脑摻饧写_定出所有的Pareto非支配解作為該問(wèn)題的近似Pareto最優(yōu)解集。DTAMOFWA的種群規(guī)模N設(shè)置為10，可行解檔案和不可行解檔案的最大規(guī)模設(shè)置為100。

4.1 仿真實(shí)例的生成

本文低碳疫苗冷鏈配送問(wèn)題是一個(gè)實(shí)際場(chǎng)景中的應(yīng)用問(wèn)題，由于無(wú)法獲取到實(shí)際工程數(shù)據(jù)，因此根據(jù)對(duì)相關(guān)領(lǐng)域的調(diào)研，在一定參數(shù)范圍內(nèi)隨機(jī)生成了4個(gè)不同規(guī)模的仿真實(shí)例，分別記為C-n15-k6、C-n20-k8、C-n35-k15和C-n55-k23。其中可用車輛數(shù)的估算方式如式(16)所示[16]。

(16)

其中，μ表示配送任務(wù)難度，實(shí)驗(yàn)中設(shè)置μ=0.5；車輛的最大容量Q=15 t。各仿真實(shí)例中客戶位置的橫縱坐標(biāo)均在[0,200]內(nèi)隨機(jī)產(chǎn)生，配送中心的坐標(biāo)為[100,100]。在[1,5]的整數(shù)范圍內(nèi)隨機(jī)生成每個(gè)客戶的需求量，并設(shè)置相應(yīng)的時(shí)間窗限制和服務(wù)時(shí)間。構(gòu)造一個(gè)(n+1)維的方陣表示編號(hào)為0～n的地點(diǎn)中任意兩點(diǎn)間路段的行駛速度，速度大小均在[30,50]均勻隨機(jī)生成，單位為km/h。低碳疫苗冷鏈配送問(wèn)題模型中的參數(shù)設(shè)置如表1所示[17,18]。

4.2 改進(jìn)策略的有效性驗(yàn)證

針對(duì)應(yīng)用問(wèn)題的特點(diǎn)，本文共提出了3種改進(jìn)策略。為了驗(yàn)證改進(jìn)策略的有效性，分別改變DTAMOFWA的相應(yīng)策略，得到3種對(duì)比算法。首先，將相鄰配送中心之間的編碼作為一個(gè)子回路，用這種解碼方式替換本文所提消除車輛約束的解碼方式，得到對(duì)比算法DTAMOFWA-D。其次，將DTAMOFWA的部分映射爆炸算子替換為已有離散煙花算法DMOFWA[19]的爆炸算子，得到對(duì)比算法DTAMOFWA-E。最后，在算法搜索過(guò)程中直接淘汰所有不可行解，只對(duì)可行解進(jìn)行操作，得到對(duì)比算法DTAMOFWA-V。所有算法的種群規(guī)模N均設(shè)為10。實(shí)驗(yàn)結(jié)果如表2所示，表中mean和std分別表示評(píng)價(jià)指標(biāo)的平均值和標(biāo)準(zhǔn)差，每組數(shù)據(jù)的最佳值加粗表示；“+”“-”“=”為顯著性水平為0.05的Wilcoxon秩和檢驗(yàn)結(jié)果，分別表示本文算法顯著優(yōu)于、劣于對(duì)比算法以及與對(duì)比算法沒(méi)有顯著差別。

Table 1 Parameter settings in the model of low-carbon cold chain distribution of vaccines

由表2可知，DTAMOFWA在4個(gè)仿真實(shí)例上的IGD和HV平均值均為最佳；在C-n15-k6和C-n20-k8上的IGD標(biāo)準(zhǔn)差最優(yōu);同時(shí)在C-n20-k8上的HV標(biāo)準(zhǔn)差最優(yōu);在剩余實(shí)例上IGD和HV標(biāo)準(zhǔn)差與最優(yōu)值也十分接近。Wilcoxon秩和檢驗(yàn)結(jié)果也顯示DTAMOFWA在IGD和HV上均顯著優(yōu)于其它對(duì)比算法。由此表明3種改進(jìn)策略均是可行且有效的，都能在一定程度上提高DTAMOFWA的收斂性和多樣性。DTAMOFWA的解碼方式能夠消除車輛約束，使得解碼后的解大部分為可行解或僅違反時(shí)間窗約束的解，避免了大量不可行解對(duì)搜索進(jìn)程的干擾。部分映射爆炸算子能夠增強(qiáng)對(duì)局部區(qū)域的搜索，更好地實(shí)現(xiàn)全局搜索和局部搜索之間的平衡，提高了算法的求解精度。DTAMOFWA采用雙外部檔案協(xié)同進(jìn)化機(jī)制，保留尋優(yōu)過(guò)程中產(chǎn)生的約束違反程度較小的不可行解。利用可行性搜索產(chǎn)生的可行解輔助可行解檔案進(jìn)行尋優(yōu)，同時(shí)利用可行性搜索產(chǎn)生的不可行解更新不可行解檔案，引導(dǎo)其逐漸向可行域移動(dòng)，不可行解中的有用信息因此得以利用，提高了算法的求解效率。DTAMOFWA對(duì)不可行解檔案進(jìn)行可行性搜索的策略，消除或降低了個(gè)體對(duì)模糊時(shí)間窗約束的違反程度，有利于加速生成質(zhì)量更高的可行解。

Table 2 Comparison results of verifying the effectiveness of three improved strategies on IGD and HV

4.3 所提算法的性能驗(yàn)證

本節(jié)實(shí)驗(yàn)使用的對(duì)比算法包括3種文獻(xiàn)中已有的求解帶時(shí)間窗約束車輛路徑問(wèn)題的算法HMOEA(Hybrid Multi-Objective Evolutionary Algorithm)[20]、hybrid DE algorithm(hybrid Differential Evolution algorithm)[21]和MOEA-FCS(Multi-Objective Evolutionary Algorithm with Fast Convergence Strategy)[22]。此外，將DTAMOFWA的多目標(biāo)處理框架改為與已有多目標(biāo)煙花算法S-MOFWA[23]相同的框架，編碼方式、個(gè)體生成方式及約束處理方法保留不變，由此得到第4種對(duì)比算法，記為S-DMOFWA。由于對(duì)比算法對(duì)可用車輛數(shù)沒(méi)有限制，因此統(tǒng)一在對(duì)比算法中使用本文所提消除車輛約束的解碼方式。實(shí)驗(yàn)中DTAMOFWA和S-DMOFWA的種群規(guī)模設(shè)置為10，其余算法的種群規(guī)模為100。實(shí)驗(yàn)結(jié)果如表3所示。

由表3可知，針對(duì)不同規(guī)模的仿真實(shí)例，DTAMOFWA在IGD和HV上均獲得了最佳平均值和標(biāo)準(zhǔn)差。根據(jù)Wilcoxon秩和檢驗(yàn)結(jié)果可知，DTAMOFWA在所有仿真實(shí)例上的IGD和HV的平均值和標(biāo)準(zhǔn)差均顯著優(yōu)于4種對(duì)比算法的。可見(jiàn)，DTAMOFWA能夠搜索到收斂精度更高、分布更加寬廣、支配的目標(biāo)空間體積更大的Pareto最優(yōu)前沿，且算法的求解穩(wěn)定性更佳。這是因?yàn)椋?1)DTAMOFWA通過(guò)消除車輛約束的解碼方式，將問(wèn)題轉(zhuǎn)化為僅帶有模糊時(shí)間窗約束的問(wèn)題，降低了其求解難度;(2)部分映射爆炸算子生成分布較為均勻的爆炸火花，實(shí)現(xiàn)了對(duì)煙花周圍局部區(qū)域的精細(xì)搜索，提高了算法的收斂性;(3)利用可行性搜索產(chǎn)生的不可行解更新不可行解檔案，保留約束違反程度較小的個(gè)體，提高了不可行解轉(zhuǎn)化為可行解的概率；(4)對(duì)不可行解檔案進(jìn)行可行性搜索后，使產(chǎn)生的可行解參與可行解檔案中目標(biāo)驅(qū)動(dòng)的啟發(fā)式擴(kuò)展搜索，既能增加解的多樣性，又能強(qiáng)化算法對(duì)于當(dāng)前Pareto前沿附近區(qū)域的局部搜索，使得算法的求解精度得到提高。因此，本文所提算法在每次求解過(guò)程中都能對(duì)整個(gè)可行域進(jìn)行充分的探索和利用，同時(shí)挖掘不可行解的有用信息，使算法盡可能找到更多的可行非支配解。

Table 3 Comparison results of DTAMOFWA and other algorithms on IGD and HV

為了直觀地比較各算法的收斂速度及精度，以C-n20-k8為例，所有算法的IGD和HV隨目標(biāo)評(píng)價(jià)次數(shù)變化的收斂曲線如圖5所示。在每種算法運(yùn)行過(guò)程中，每500次目標(biāo)評(píng)價(jià)次數(shù)對(duì)IGD和HV值進(jìn)行一次采樣，因此在一個(gè)收斂曲線中共有100個(gè)數(shù)據(jù)點(diǎn)。由圖5可知，在C-n20-k8上，所提算法DTAMOFWA的IGD和HV收斂精度均高于對(duì)比算法的，收斂速度也較快。在迭代初期，算法HMOEA的IGD和HV取值均最小，下降速度也超過(guò)了DTAMOFWA的，但不久后它的取值基本保持在一個(gè)較差水平。這是由于其種群規(guī)模大于DTAMOFWA的，初始解的多樣性比較好，但經(jīng)過(guò)一定的迭代次數(shù)后，種群開(kāi)始陷入局部最優(yōu)，導(dǎo)致所得Pareto前沿曲線在此之后基本不變。由圖5還可觀察到，HMOEA和hybrid DE algorithm的IGD值均在迭代前期出現(xiàn)了退化現(xiàn)象。原因可能是這2種算法缺乏精英保留機(jī)制，導(dǎo)致某些適應(yīng)度較好的解被淘汰。所提算法DTAMOFWA由于采用有效的約束處理機(jī)制，充分利用可行解和不可行解中的重要進(jìn)化信息，使得可行解檔案和不可行解檔案不斷更新和進(jìn)化。同時(shí)，變異算子使其具備一定的跳出局部最優(yōu)的能力。因此，DTAMOFWA能夠在前期和中期以較快的速度收斂到精度較高的近似Pareto最優(yōu)前沿，并在后期保持穩(wěn)定，具有更好的收斂性和多樣性。在其它仿真實(shí)例上獲取的IGD和HV收斂曲線也能得到類似的結(jié)論。

綜上，本文所提算法是一種能有效處理約束的多目標(biāo)元啟發(fā)式算法，在不同規(guī)模的低碳疫苗冷鏈配送問(wèn)題中均表現(xiàn)出了較好的收斂性和多樣性，求解準(zhǔn)確且穩(wěn)定，并具有良好的可擴(kuò)展性。

Figure 5 IGD and HV convergence curves of five algorithms on C-n20-k8

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

本文建立了低碳疫苗冷鏈配送問(wèn)題的約束多目標(biāo)優(yōu)化模型。該模型以最小化企業(yè)運(yùn)輸成本和平均客戶不滿意度作為優(yōu)化目標(biāo)，同時(shí)滿足可用車數(shù)量約束、車輛容量約束和模糊時(shí)間窗約束，更貼合實(shí)際應(yīng)用，但同時(shí)也增加了問(wèn)題求解的難度。針對(duì)該模型強(qiáng)約束條件多的特點(diǎn)，提出了一種雙檔案協(xié)同進(jìn)化的離散多目標(biāo)煙花算法。該算法設(shè)計(jì)了3種改進(jìn)策略：采用消除車輛約束的解碼方式，部分映射爆炸算子，以及雙外部檔案協(xié)同進(jìn)化的機(jī)制。在規(guī)模遞增的4個(gè)仿真實(shí)例中，分別驗(yàn)證了各改進(jìn)策略的有效性，并將所提算法與4種已有算法進(jìn)行對(duì)比實(shí)驗(yàn)。結(jié)果表明，所提算法在收斂性和多樣性方面均優(yōu)于對(duì)比算法，且對(duì)問(wèn)題規(guī)模具有可擴(kuò)展性，適用于求解低碳疫苗冷鏈配送問(wèn)題這類約束多目標(biāo)優(yōu)化問(wèn)題。