基于離散鯨魚群算法的物資應(yīng)急調(diào)度研究

蔣華偉 郭 陶 楊 震 趙麗科

(糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室(河南工業(yè)大學(xué)) 鄭州 450001)

(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院 鄭州 450001)

1 引言

自然災(zāi)害及重大公共衛(wèi)生事件的發(fā)生會(huì)嚴(yán)重威脅人們的生命財(cái)產(chǎn)安全，并對(duì)社會(huì)生產(chǎn)造成不利影響[1]。為最大限度降低災(zāi)害帶來(lái)的損失，就需要研究和構(gòu)建科學(xué)合理的物資(如糧食)應(yīng)急調(diào)度模型，來(lái)獲取最優(yōu)路徑，減少物資配送時(shí)間，以保證災(zāi)區(qū)救援物資的充足供應(yīng)，從而為開(kāi)展及時(shí)高效的救援工作提供物資保障。

災(zāi)后物資應(yīng)急調(diào)度的本質(zhì)是多種約束條件下的車輛路徑問(wèn)題(Vehicle Routing Problem, VRP)[2]，即具有多配送中心帶時(shí)間窗的VRP。作為經(jīng)典的組合優(yōu)化問(wèn)題，VRP已被證明為NP-hard問(wèn)題[3]，其求解方法主要有精確算法[4,5]和啟發(fā)式算法[6,7]兩類。精確算法針對(duì)具體問(wèn)題建立相應(yīng)的數(shù)學(xué)模型，利用數(shù)學(xué)方法求出問(wèn)題的最優(yōu)解，但其計(jì)算時(shí)間隨問(wèn)題規(guī)模的增大呈爆炸式增長(zhǎng)，因此只能解決規(guī)模相對(duì)較小的問(wèn)題。啟發(fā)式算法是相對(duì)于精確算法提出的，在可接受范圍內(nèi)給出問(wèn)題的解，相比于精確算法，在處理大規(guī)模VRP時(shí)，具有更高的魯棒性、可行性。因此國(guó)內(nèi)外學(xué)者主要采用啟發(fā)式算法對(duì)VRP及其變體問(wèn)題進(jìn)行研究，如在求解帶時(shí)間窗VRP時(shí)，Marinakis等人[8]采用3種不同的自適應(yīng)策略優(yōu)化粒子群算法，分別用于初始解的生成、解的移動(dòng)以及算法參數(shù)的自適應(yīng)調(diào)整，以提高算法的求解性能；此外，Ramachandranpillai等人[9]將改進(jìn)螢火蟲(chóng)算法與脈沖神經(jīng)系統(tǒng)結(jié)合，使其可以快速地搜索解空間，從而提高算法求解的收斂速度。為求解具有多配送中心VRP，Lahyani等人[10]提出了基于混合自適應(yīng)大鄰域搜索算法，算法結(jié)合3種插入、5種移除啟發(fā)式算法和4個(gè)后優(yōu)化局部搜索過(guò)程，來(lái)靈活解決多配送中心VRP；另外，胡蓉等人[11]提出結(jié)合聚類分解策略的增強(qiáng)蟻群算法，將多配送中心問(wèn)題分解為多個(gè)單配送中心問(wèn)題，以控制問(wèn)題的求解規(guī)模。求解多目標(biāo)VRP時(shí)，Zhang等人[12]設(shè)計(jì)了兩個(gè)多目標(biāo)局部搜索算法，結(jié)合兩個(gè)算法并采用附加技術(shù)增強(qiáng)局部搜索算法，提高算法的求解性能；此外，Long等人[13]結(jié)合遺傳算法與局部搜索策略，提出一種基于帕累托的進(jìn)化算法，用于求解多目標(biāo)規(guī)劃問(wèn)題。在求解其他變體問(wèn)題時(shí)，駱劍平等人[14]將改進(jìn)冪律極值動(dòng)力學(xué)優(yōu)化引入混合蛙跳算法，以提高算法求解容量約束VRP的性能；李國(guó)明等人[15]將禁忌搜索與最近鄰算法相結(jié)合，并對(duì)禁忌長(zhǎng)度等進(jìn)行自適應(yīng)調(diào)整，引入自適應(yīng)懲罰系數(shù)，以提高禁忌搜索算法在求解隨機(jī)VRP時(shí)的尋優(yōu)能力和魯棒性；Xiang等人[16]提出基于成對(duì)鄰近學(xué)習(xí)的蟻群算法，用于求解動(dòng)態(tài)VRP，采用成對(duì)鄰近學(xué)習(xí)方法研究變化前的最優(yōu)路徑，并預(yù)測(cè)變化后最優(yōu)路徑中客戶的局部訪問(wèn)順序。上述算法在求解VRP及其變體問(wèn)題時(shí)，針對(duì)不同問(wèn)題的特點(diǎn)設(shè)計(jì)相應(yīng)的算法進(jìn)行求解。在解決算法易陷入局部最優(yōu)這一問(wèn)題時(shí)，主要借助變異操作跳出局部極值，具有很強(qiáng)的隨機(jī)性，無(wú)法保證變異后個(gè)體的優(yōu)劣，并且未充分考慮種群多樣性與算法陷入局部極值間的密切關(guān)系，僅使用適應(yīng)度函數(shù)選擇個(gè)體，因而無(wú)法在算法迭代周期內(nèi)維持高種群多樣性以最大限度發(fā)揮啟發(fā)式算法的優(yōu)勢(shì)。

針對(duì)啟發(fā)式算法存在的缺點(diǎn)，以及實(shí)際物資應(yīng)急調(diào)度問(wèn)題龐大的解空間和整體編解碼的復(fù)雜性，本文提出一種改進(jìn)離散鯨魚群算法(Improved Discrete Whale Swarm Algorithm, IDWSA)，對(duì)具有多配送中心帶時(shí)間窗的物資應(yīng)急調(diào)度問(wèn)題(Material Emergency Scheduling Problem with Mul- tiple Distribution Centers and Time Windows, MESPMDCTW)進(jìn)行求解。首先分析問(wèn)題中各種復(fù)雜的約束條件，為其建立嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型；其次，為獲得高質(zhì)量的初始種群，提出混合初始化策略生成初始解，即動(dòng)態(tài)模糊聚類(Dynamic Fuzzy Clustering, DFC)與隨機(jī)生成相結(jié)合；然后設(shè)計(jì)分別以相似配送順序和相同配送中心為比較項(xiàng)的個(gè)體移動(dòng)規(guī)則，采用自適應(yīng)柯西變異算子對(duì)個(gè)體進(jìn)行變異，并提出路徑選擇策略；此外，構(gòu)造全局評(píng)價(jià)函數(shù)，用于評(píng)價(jià)子代個(gè)體對(duì)種群的貢獻(xiàn)度，以避免僅使用適應(yīng)度函數(shù)對(duì)個(gè)體進(jìn)行評(píng)價(jià)時(shí)的局限性，使得算法在迭代后期仍可保持高種群多樣性；最后在Solomon標(biāo)準(zhǔn)測(cè)試集[17]上進(jìn)行仿真實(shí)驗(yàn)，并與其他算法進(jìn)行對(duì)比分析，驗(yàn)證IDWSA的有效性。

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

2.1 問(wèn)題描述

實(shí)際物資應(yīng)急調(diào)度中存在多種復(fù)雜并相互制約的因素，為了簡(jiǎn)化模型本文給出以下約束條件：(1)每個(gè)受災(zāi)點(diǎn)僅能由一個(gè)配送中心的一輛車完成配送任務(wù)；(2)每輛車所訪問(wèn)的各受災(zāi)點(diǎn)的總需求量不可超過(guò)該車輛的最大載重；(3)每輛車的行駛距離不可超出車輛最大行駛里程；(4)所有車輛在完成配送任務(wù)后需返回其始發(fā)配送中心；(5)車輛對(duì)其配送受災(zāi)點(diǎn)的訪問(wèn)時(shí)間不可超過(guò)該受災(zāi)點(diǎn)的最晚送達(dá)時(shí)間。

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

MESPMDCTW問(wèn)題可由有向圖描述，在有向圖中頂點(diǎn)表示配送中心及受災(zāi)點(diǎn)，有向邊表示車輛的可行駛路徑，如圖1所示。

圖1 MESPMDCTW問(wèn)題的有向圖表示

假設(shè)該問(wèn)題的配送中心集合D= {d1,d2,···,dm}；每個(gè)配送中心擁有vi輛車，其中i表示第i個(gè)配送中心，每輛車的最大載重為Q；受災(zāi)點(diǎn)集合R={r1,r2,··,rn}，每個(gè)受災(zāi)點(diǎn)的物資需求量為qj(j=1,2,···,n)。

根據(jù)所述，本文構(gòu)建MESPMDCTW問(wèn)題的數(shù)學(xué)模型如下：

(1)目標(biāo)函數(shù)

MESPMDCTW問(wèn)題的目標(biāo)是使總運(yùn)輸成本最低和使用的車輛數(shù)目最少，其中總運(yùn)輸成本最低可以表示為總運(yùn)輸路徑最短、總服務(wù)時(shí)間最小等，車輛數(shù)目最少可使用車輛費(fèi)用最小化表示。該目標(biāo)函數(shù)用于衡量所生成車輛路徑的優(yōu)劣程度，目標(biāo)函數(shù)值越大表明采用該路徑對(duì)各受災(zāi)點(diǎn)進(jìn)行物資配送時(shí)所耗費(fèi)的代價(jià)越大。

由于各受災(zāi)點(diǎn)對(duì)物資配送時(shí)間具有一定限制，當(dāng)車輛提前或者延時(shí)到達(dá)時(shí)，要對(duì)該車輛進(jìn)行懲罰，即增加其成本。其中ti表示車輛到達(dá)受災(zāi)點(diǎn)i的實(shí)際時(shí)間，ETi，LTi分別表示受災(zāi)點(diǎn)i的最早和最晚訪問(wèn)時(shí)間；a，b分別表示車輛提前到達(dá)和延時(shí)到達(dá)的懲罰系數(shù)，由于不允許延時(shí)到達(dá)，所以b為一個(gè)很大的正數(shù)。

式(4)表示每個(gè)受災(zāi)點(diǎn)只能由一個(gè)配送中心的一輛車訪問(wèn)，式(5)表示第t個(gè)配送中心服務(wù)的受災(zāi)點(diǎn)的物資總需求量，式(6)表示訪問(wèn)受災(zāi)點(diǎn)j的車輛k流入流出的平衡條件。

3 基本W(wǎng)SA

鯨魚群算法(Whale Swarm Algorithm, WSA)是2017年由Zeng等人[18]基于群體智能提出的一種新元啟發(fā)式算法，經(jīng)大量實(shí)驗(yàn)證明，與遺傳算法(Genetic Algorithm, GA)、差分進(jìn)化算法(Differential Evolution Algorithm, DEA)等綜合對(duì)比，WSA的求解性能更優(yōu)。其基本思想如下：首先在定義域內(nèi)隨機(jī)生成一組解作為初始種群，種群中每條鯨魚代表解空間中的一個(gè)候選解；然后根據(jù)種群中鯨魚的適應(yīng)度值和位置，依次為每條鯨魚搜索其“更優(yōu)且最近”目標(biāo)鯨魚，即周圍適應(yīng)度更優(yōu)的鯨魚中距離其最近的鯨魚；最后每條鯨魚均以其目標(biāo)鯨魚為導(dǎo)向以某種方式進(jìn)行移動(dòng)，從而產(chǎn)生新一代種群，其向目標(biāo)鯨魚移動(dòng)的方式如式(7)。

由式(7)可知，當(dāng)鯨魚X與其“更優(yōu)且最近”鯨魚Y之間的距離很近時(shí)，鯨魚X會(huì)積極地向鯨魚Y隨機(jī)移動(dòng)；反之，鯨魚X會(huì)消極地向鯨魚Y隨機(jī)移動(dòng)。

4 IDWSA算法

WSA主要適用于求解連續(xù)性問(wèn)題，而MESPMDCTW屬于離散問(wèn)題，無(wú)法直接使用它對(duì)問(wèn)題進(jìn)行求解，因此本文對(duì)基本W(wǎng)SA進(jìn)行優(yōu)化，主要改進(jìn)包括：(1)設(shè)計(jì)新的鯨魚個(gè)體編解碼方式，并提出相應(yīng)的個(gè)體間距離計(jì)算方式；(2)為提高初始種群的質(zhì)量及其多樣性提出混合初始化策略；(3)提出自適應(yīng)柯西變異算子，用于更新種群中無(wú)引導(dǎo)個(gè)體的個(gè)體；(4)設(shè)計(jì)路徑選擇策略用于個(gè)體中各受災(zāi)點(diǎn)的重新規(guī)劃；(5)提出以相似配送順序和相同配送中心為比較項(xiàng)的兩種個(gè)體移動(dòng)規(guī)則；(6)構(gòu)造全局評(píng)價(jià)函數(shù)衡量個(gè)體對(duì)種群的貢獻(xiàn)度用于選擇個(gè)體組成子代種群。

IDWSA算法的完整步驟如下：

(1)采用混合初始化策略對(duì)種群進(jìn)行初始化得到大小為n的初始種群pop；

(2)采用式(14)計(jì)算種群中個(gè)體的適應(yīng)度值，并從中選擇適應(yīng)度值最大的個(gè)體作為當(dāng)前種群的最優(yōu)個(gè)體，記為best。

(3)尋找種群中每個(gè)個(gè)體的“更優(yōu)且最近”個(gè)體Y，對(duì)于個(gè)體X，若Y存在，則分別根據(jù)以相似配送順序和相同配送中心為比較項(xiàng)的移動(dòng)規(guī)則對(duì)X進(jìn)行移動(dòng)，獲得兩個(gè)子代個(gè)體；若Y不存在，則對(duì)X分別進(jìn)行兩次自適應(yīng)柯西變異，獲得兩個(gè)子代個(gè)體；對(duì)種群中所有個(gè)體操作后，獲得大小為2n的子代種群new_pop；

(4)分別采用式(14)和式(16)計(jì)算子代種群new_pop中每個(gè)個(gè)體的適應(yīng)度值和貢獻(xiàn)度，從中選擇適應(yīng)度值最大的個(gè)體記為new_best并與種群pop中的best作比較，保留適應(yīng)度值大的個(gè)體記為best，然后根據(jù)個(gè)體的貢獻(xiàn)度，從new_pop中選擇貢獻(xiàn)度最大的前n–1個(gè)個(gè)體與個(gè)體best組成子代種群pop。

(5)判斷是否滿足終止條件，若不滿足則返回步驟(2)，反之則進(jìn)行步驟(6)。

(6)獲得最終種群pop，從中選擇適應(yīng)度值最大的個(gè)體作為問(wèn)題的最終解。

4.1 個(gè)體編解碼及距離計(jì)算方式

MESPMDCTW問(wèn)題中每個(gè)受災(zāi)點(diǎn)可以由任意配送中心的任意車輛配送，且其在車輛中的配送順序是隨機(jī)的，因此該問(wèn)題具有龐大的解空間，為了減小搜索空間，提高算法的搜索效率，本文提出3層編碼方式，包括配送中心編碼(Distribution Coding, DC)、車輛編碼(Vehicle Coding, VC)和順序編碼(Sequential Coding, SC)，如圖2所示。其中，DC值為對(duì)應(yīng)受災(zāi)點(diǎn)所屬配送中心，VC值為與DC對(duì)應(yīng)的受災(zāi)點(diǎn)的車輛號(hào)，SC為與VC段對(duì)應(yīng)的該受災(zāi)點(diǎn)在車輛中的配送順序。

解碼時(shí)，首先由DC確定受災(zāi)點(diǎn)所屬配送中心，然后由VC確定同一配送中心下各受災(zāi)點(diǎn)的配送車輛，最后根據(jù)SC確定車輛訪問(wèn)各受災(zāi)點(diǎn)的順序。圖2中該示例表示受災(zāi)點(diǎn)1，2，4，6，7由配送中心1的兩輛車配送，第1輛車訪問(wèn)順序?yàn)?，6，7，第2輛車訪問(wèn)順序?yàn)?，2；受災(zāi)點(diǎn)3，5，8，9由配送中心2的兩輛車配送，第1輛車訪問(wèn)順序?yàn)?，8，第2輛車訪問(wèn)順序?yàn)?，5。

圖2 3層編碼示例

由于基本W(wǎng)SA中的距離公式僅適用于求解連續(xù)性問(wèn)題，而不能直接用于求解離散問(wèn)題，因此根據(jù)MESPMDCTW問(wèn)題的特點(diǎn)及本文設(shè)計(jì)的3層編碼方式，提出一種計(jì)算鯨魚個(gè)體間相對(duì)距離的方法，如式(8)。

4.2 混合初始化策略

高質(zhì)量的初始種群不僅能加快算法的收斂速度，而且可產(chǎn)生質(zhì)量更優(yōu)的最終解。目前，對(duì)種群進(jìn)行初始化的方法有全局最小化處理時(shí)間規(guī)則[19]、MinEnd啟發(fā)式規(guī)則[20]、全局搜索和局部搜索方法[21]等。但這些種群初始化方法均是基于車間調(diào)度問(wèn)題提出的，并不適用于本文問(wèn)題。因此為提高初始種群的質(zhì)量并保持其多樣性，防止種群在迭代中過(guò)早喪失多樣性而陷入局部極值，根據(jù)MESPMDCTW問(wèn)題的特點(diǎn)，本文提出混合初始化策略，即結(jié)合DFC和隨機(jī)生成方法，按照一定比例生成初始種群，如圖3所示。

圖3中，初始種群中35%的個(gè)體由DFC算法生成，65%的個(gè)體隨機(jī)生成。在隨機(jī)生成個(gè)體時(shí)，首先生成一個(gè)兩倍大的臨時(shí)種群，然后根據(jù)適應(yīng)度函數(shù)計(jì)算臨時(shí)種群中個(gè)體的適應(yīng)度值，選擇適應(yīng)度值最大的前12.5%的個(gè)體組成隨機(jī)生成部分25%的個(gè)體，最后從剩余87.5%的個(gè)體中隨機(jī)選擇個(gè)體作為隨機(jī)生成部分40%的個(gè)體。

圖3 混合初始化策略

DFC主要根據(jù)各受災(zāi)點(diǎn)位置、訪問(wèn)時(shí)間窗及服務(wù)時(shí)間，進(jìn)行相似性分析，使同一類別的受災(zāi)點(diǎn)距離最近且各受災(zāi)點(diǎn)訪問(wèn)時(shí)間重疊最小，以此將所有受災(zāi)點(diǎn)劃分為與配送中心數(shù)相同的幾類。此外，為防止各配送中心所分配受災(zāi)點(diǎn)數(shù)極度不均勻?qū)е抡w配送效率降低，本文在對(duì)各受災(zāi)點(diǎn)進(jìn)行聚類后，對(duì)形成的受災(zāi)點(diǎn)集合進(jìn)行均衡化處理，使得每類受災(zāi)點(diǎn)數(shù)大致相同，即當(dāng)某一類受災(zāi)點(diǎn)數(shù)較多時(shí)，根據(jù)式(9)選擇部分受災(zāi)點(diǎn)將其移向數(shù)目相對(duì)較少的受災(zāi)點(diǎn)集合，循環(huán)移動(dòng)直至達(dá)到各受災(zāi)點(diǎn)集合大小均衡。

4.3 自適應(yīng)柯西變異算子

WSA中個(gè)體的優(yōu)化是以其“更優(yōu)且最近”個(gè)體為引導(dǎo)的，但種群中存在某些不具有引導(dǎo)個(gè)體的個(gè)體，為了對(duì)它們進(jìn)行更新，根據(jù)式(12)的柯西變異算子，本文改進(jìn)提出了式(13)所示的自適應(yīng)柯西變異算子。

其中，xij為個(gè)體i的第j維位置，n為種群大小，C是由t=1的柯西分布函數(shù)產(chǎn)生的隨機(jī)數(shù)，[xmin,xmax]是各受災(zāi)點(diǎn)的編號(hào)區(qū)間。

WSA中個(gè)體的運(yùn)動(dòng)以其“更優(yōu)且最近”個(gè)體為引導(dǎo)，隨著個(gè)體的不斷移動(dòng)，種群中個(gè)體不斷收斂。在算法迭代前期，個(gè)體位置分散，種群平均位置較大，隨著個(gè)體不斷地向最優(yōu)解方向移動(dòng)，種群平均位置逐漸變小，算法逐漸收斂，因此種群平均位置變化與算法收斂特性是一致的，采用種群平均位置作為控制變異步長(zhǎng)的參數(shù)有利于提高算法在迭代前期的搜索能力，并能在后期加快算法的收斂速度。

4.4 路徑選擇策略

鯨魚個(gè)體向其“更優(yōu)且最近”個(gè)體移動(dòng)時(shí)，為了在其引導(dǎo)個(gè)體周圍進(jìn)行細(xì)致的搜索，以最大概率尋找區(qū)域內(nèi)最優(yōu)個(gè)體，本文提出路徑選擇策略，使個(gè)體根據(jù)該策略向其引導(dǎo)個(gè)體移動(dòng)，其基本思想如表1。首先根據(jù)引導(dǎo)個(gè)體即“更優(yōu)且最近”個(gè)體確定配送中心及各受災(zāi)點(diǎn)之間的路徑權(quán)值矩陣W，若節(jié)點(diǎn)相鄰則將兩節(jié)點(diǎn)之間的路徑權(quán)值置為1，反之則置0；根據(jù)當(dāng)前已生成路徑的最后一個(gè)節(jié)點(diǎn)，從未被訪問(wèn)的受災(zāi)點(diǎn)集合S中選擇與最后一個(gè)節(jié)點(diǎn)相連權(quán)值最大的受災(zāi)點(diǎn)，作為下一個(gè)要訪問(wèn)的受災(zāi)點(diǎn)，以此循環(huán)直至未被訪問(wèn)的受災(zāi)點(diǎn)集合S為空。

表1 路徑選擇策略

4.5 個(gè)體移動(dòng)策略

IDWSA中，鯨魚個(gè)體向其“更優(yōu)且最近”個(gè)體移動(dòng)，采用適應(yīng)度函數(shù)式(14)衡量其質(zhì)量。該適應(yīng)度函數(shù)是基于MESPMD CTW的目標(biāo)函數(shù)式(1)構(gòu)建的，主要有3個(gè)影響因素，分別為個(gè)體X所表示的路徑總距離、X所使用的總車輛數(shù)以及X中車輛訪問(wèn)所有受災(zāi)點(diǎn)的總延遲時(shí)間，用于從每代種群中選擇質(zhì)量最優(yōu)即適應(yīng)度值最大的個(gè)體。

由于MESPMDCTW屬于離散問(wèn)題，基本W(wǎng)SA中的個(gè)體移動(dòng)方式無(wú)法使用，因此本文提出以相似配送順序和相同配送中心為比較項(xiàng)的兩種個(gè)體移動(dòng)規(guī)則，具體的移動(dòng)規(guī)則如圖4所示。

圖4 個(gè)體移動(dòng)規(guī)則

為了說(shuō)明個(gè)體移動(dòng)規(guī)則，圖5給出了基于相似配送順序的個(gè)體移動(dòng)示例。圖5中，個(gè)體Y為個(gè)體X的引導(dǎo)個(gè)體，在個(gè)體X和Y中，受災(zāi)點(diǎn)3，9都位于對(duì)應(yīng)車輛的第1個(gè)訪問(wèn)順序，受災(zāi)點(diǎn)5，6都位于對(duì)應(yīng)車輛的第2個(gè)訪問(wèn)順序，它們具有相同的配送順序，因此將受災(zāi)點(diǎn)3，5，6，9根據(jù)其在引導(dǎo)個(gè)體Y中的位置復(fù)制到新個(gè)體Z中；然后隨機(jī)生成兩個(gè)整數(shù)P1=2和P2=5，將引導(dǎo)個(gè)體Y中索引P1和P2之間(不包括P2)的受災(zāi)點(diǎn)復(fù)制到Z中相應(yīng)位置；最后將X中剩余受災(zāi)點(diǎn)依次復(fù)制到Z中。

圖5 基于相似配送順序的個(gè)體移動(dòng)示例

4.6 全局評(píng)價(jià)函數(shù)

對(duì)于種群中的個(gè)體X，在對(duì)其進(jìn)行1次移動(dòng)后會(huì)產(chǎn)生2個(gè)子代個(gè)體，則完成1輪搜索后，種群規(guī)模將變成原來(lái)的兩倍。由于個(gè)體是向其“更優(yōu)且最近”個(gè)體移動(dòng)的，當(dāng)采用適應(yīng)度函數(shù)選擇個(gè)體時(shí)，隨著迭代次數(shù)增加，個(gè)體之間距離逐漸縮小，使個(gè)體逐漸聚集在某一區(qū)域，種群多樣性降低，從而使算法陷入局部極值，難以求出問(wèn)題最優(yōu)解。因此為了維持種群多樣性，使算法在進(jìn)行迭代求解時(shí)可以在問(wèn)題的較大解空間上進(jìn)行搜索，本文基于個(gè)體的適應(yīng)度值構(gòu)造了如式(16)所示的全局評(píng)價(jià)函數(shù)，用于衡量個(gè)體對(duì)整個(gè)種群的貢獻(xiàn)程度，從而在算法迭代期間對(duì)個(gè)體進(jìn)行選擇以組成新的子代種群。

全局評(píng)價(jià)函數(shù)涉及子代個(gè)體、父代個(gè)體及整個(gè)種群的適應(yīng)度值，在計(jì)算個(gè)體x對(duì)種群的貢獻(xiàn)度時(shí)，綜合考慮其父代個(gè)體在父代種群中的影響程度、個(gè)體x在子代種群中的優(yōu)劣程度以及父代個(gè)體向其引導(dǎo)個(gè)體移動(dòng)生成個(gè)體x時(shí)的優(yōu)化程度。根據(jù)貢獻(xiàn)度選擇個(gè)體時(shí)，由于不僅考慮當(dāng)前個(gè)體x的適應(yīng)度值，同時(shí)考慮其父代個(gè)體所產(chǎn)生的影響，使得適應(yīng)度值大的個(gè)體其貢獻(xiàn)度不一定大，因此對(duì)于適應(yīng)度值較小但可能位于最優(yōu)解區(qū)域的個(gè)體x仍有機(jī)會(huì)被選擇，從而擴(kuò)大算法的搜索空間。采用全局評(píng)價(jià)函數(shù)選擇個(gè)體，根據(jù)個(gè)體的貢獻(xiàn)度在每次迭代時(shí)對(duì)個(gè)體進(jìn)行選擇，使生成的子代種群中個(gè)體間具有較大的差異性，即種群個(gè)體分布在問(wèn)題解空間的較大區(qū)域，從而不會(huì)使算法過(guò)早陷入局部最優(yōu)，且每次迭代中都會(huì)保留當(dāng)前種群中適應(yīng)度值最大的個(gè)體，因此可以在最大限度維持種群多樣性的情況下求得問(wèn)題的最好解。

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

為驗(yàn)證IDWSA求解MESPMDCTW的有效性，本文在Solomon標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，該數(shù)據(jù)集主要分為6類：C1，C2，R1，R2，RC1和RC2，共56個(gè)測(cè)試集。其中C類是聚類數(shù)據(jù)，R類數(shù)據(jù)是隨機(jī)分布的，RC類數(shù)據(jù)則是C類和R類的混合數(shù)據(jù)。由于本文問(wèn)題涉及多配送中心這一約束條件，因此本文選取隨機(jī)分布的R類測(cè)試集中的R101進(jìn)行仿真實(shí)驗(yàn)，并在上述數(shù)據(jù)集中添加3個(gè)配送中心，其余數(shù)據(jù)保持不變，添加的配送中心位置信息如表2。

表2 數(shù)據(jù)集配送中心信息

本文所有實(shí)驗(yàn)均使用python 3.7語(yǔ)言編寫，在pyCharm上編譯，并在Intel(R) Core(TM) i5-8500T CPU @ 2.10GHz 2.11 GHz Windows 10操作系統(tǒng)上運(yùn)行。為了衡量算法的性能，文中使用了多個(gè)評(píng)價(jià)指標(biāo)，其含義如表3所示。

表3 評(píng)價(jià)指標(biāo)及含義

5.1 參數(shù)選取

采用IDWSA對(duì)問(wèn)題求解時(shí)，參數(shù)的選取對(duì)算法性能具有一定影響，本文所提出的IDWSA的參數(shù)主要有：種群大小和算法迭代次數(shù)。為最大限度發(fā)揮IDWSA的優(yōu)勢(shì)，需要對(duì)算法參數(shù)進(jìn)行分析，以選取最優(yōu)參數(shù)。為此本文分別在種群大小為20，30，40和迭代次數(shù)為10，15，20，25，30，35時(shí)進(jìn)行仿真實(shí)驗(yàn)，每組實(shí)驗(yàn)分別進(jìn)行20次，其結(jié)果如表4，圖6，7所示。

理論上，算法所求問(wèn)題最好解的質(zhì)量應(yīng)該與種群規(guī)模和迭代次數(shù)呈嚴(yán)格正相關(guān)，但由于WSA具有不穩(wěn)定性，在同一實(shí)驗(yàn)條件下對(duì)問(wèn)題進(jìn)行多次求解時(shí)，其所求解的質(zhì)量具有一定差別，這一問(wèn)題從表4也可看出。此外由圖6可以看出，隨著種群規(guī)模增加，IDWSA所求最好解的距離逐漸減小，但其降低的幅度較小；同時(shí)隨著迭代次數(shù)增加，算法所求最好解的質(zhì)量有所增加，但兩者之間不具有嚴(yán)格的正相關(guān)性。

表4 不同參數(shù)下算法所求解的質(zhì)量

此外，從圖7可以看出，隨著迭代次數(shù)增加，不同種群大小下算法的運(yùn)算時(shí)間都呈明顯遞增趨勢(shì)。結(jié)合圖6和圖7可知，不同種群大小下所求解的質(zhì)量差異較小，但在相同迭代次數(shù)下，其運(yùn)算時(shí)間相差較大，且隨著迭代次數(shù)增加，算法的運(yùn)算時(shí)間大幅度增長(zhǎng)。在種群大小為20和迭代次數(shù)為30時(shí)，算法平均運(yùn)算時(shí)間處于46.79 s左右，在可接受范圍內(nèi)可求出問(wèn)題最好解，因而在進(jìn)行后續(xù)實(shí)驗(yàn)時(shí)，本文選擇種群大小20、迭代次數(shù)30作為最優(yōu)參數(shù)。

圖6 不同種群規(guī)模和不同迭代次數(shù)下所求最好解

圖7 不同迭代次數(shù)和不同種群規(guī)模下的求解時(shí)間

5.2 混合初始化策略有效性分析

初始解的質(zhì)量對(duì)后續(xù)問(wèn)題的求解至關(guān)重要，為驗(yàn)證本文所提混合初始化策略的有效性，本文構(gòu)建了式(17)用于衡量算法迭代過(guò)程中種群的多樣性。

其中，i，j表示種群中第i和第j個(gè)個(gè)體，dij表示個(gè)體i與j之間的距離，D表示種群多樣性，其值越大表示種群多樣性越好。

分別采用混合初始化策略、DFC與隨機(jī)生成方式生成初始解，結(jié)果如表5所示。

由表5可知，采用混合初始化策略生成初始種群，其種群多樣性位于僅采用動(dòng)態(tài)模糊聚類和隨機(jī)生成的初始種群之間，且其初始種群的平均最好解、平均最差解及平均解均優(yōu)于動(dòng)態(tài)模糊聚類和隨機(jī)生成；此外，采用混合初始化策略所求問(wèn)題最終解的平均最好解、平均最差解及平均解也均優(yōu)于動(dòng)態(tài)模糊聚類和隨機(jī)生成，由此可表明混合初始化策略有助于算法求得質(zhì)量更優(yōu)的可行解。

表5 3種種群初始化方式結(jié)果對(duì)比

5.3 全局評(píng)價(jià)函數(shù)的有效性

為驗(yàn)證全局評(píng)價(jià)函數(shù)在IDWSA中的有效性，分別使用適應(yīng)度函數(shù)和全局評(píng)價(jià)函數(shù)選擇個(gè)體并對(duì)其種群多樣性進(jìn)行計(jì)算分析，結(jié)果如圖8，表6所示。

從圖8可以看出，采用適應(yīng)度函數(shù)選擇個(gè)體，在迭代5次時(shí)，種群多樣性就已大幅度降低，表明種群中個(gè)體在迭代初期便快速聚集在某一較小區(qū)域，且在迭代過(guò)程中種群多樣性一直降低，由此可知采用適應(yīng)度函數(shù)選擇個(gè)體時(shí)算法易過(guò)早陷入局部最優(yōu)，從而難以求出全局最優(yōu)解。采用全局評(píng)價(jià)函數(shù)選擇個(gè)體，與適應(yīng)度函數(shù)相比，在迭代5次時(shí)，其種群多樣性降低幅度較小，且在迭代后期種群多樣性逐漸趨于穩(wěn)定即算法逐漸收斂時(shí)，其種群多樣性仍遠(yuǎn)高于適應(yīng)度函數(shù)，由此可知采用全局評(píng)價(jià)函數(shù)選擇個(gè)體時(shí)，算法在問(wèn)題解空間的較大區(qū)域內(nèi)尋找可行解，使算法求得全局最優(yōu)解的可能性大幅度增加。

圖8 不同迭代次數(shù)下種群多樣性

同時(shí)，由表6可知，在運(yùn)算時(shí)間大致相同的情況下，采用全局評(píng)價(jià)函數(shù)所求問(wèn)題最好解優(yōu)于采用適應(yīng)度函數(shù)所求的最好解，且其最大偏差和平均偏差均大于適應(yīng)度函數(shù)，表明全局評(píng)價(jià)函數(shù)在維持高種群多樣性的同時(shí)可搜索到高質(zhì)量的可行解，由此驗(yàn)證了本文所提全局評(píng)價(jià)函數(shù)的有效性。

表6 兩種函數(shù)求得可行解

5.4 算法對(duì)比分析

為驗(yàn)證IDWSA求解MESPMDCTW的有效性，本文采用IDWSA進(jìn)行仿真計(jì)算，同時(shí)使用文獻(xiàn)[8]中的多自適應(yīng)粒子群優(yōu)化(Multi Adaptive Particle Swarm Optimi- zation, MAPSO)算法、文獻(xiàn)[22]中的遺傳算法(Genetic Algorithm, GA)、文獻(xiàn)[23]中的混合蟻群(Hybrid Ant Colony Optimi- zation, HACO)算法以及文獻(xiàn)[24]中的人工蜂群(Artificial Bee Colony, ABC)算法對(duì)本文問(wèn)題進(jìn)行求解，并將5種算法的計(jì)算結(jié)果進(jìn)行對(duì)比分析，結(jié)果如圖9所示。

由圖9可知，在20次實(shí)驗(yàn)中，IDWSA所求最好解的質(zhì)量與MAPSO, GA, HACO和ABC相比，具有明顯提升，其最好解距離與MAPSO, GA,HACO, ABC相比分別減少了2.25%, 13.4%, 6%,1.46%，且所求平均最好解、平均最差解以及平均解均優(yōu)于MAPSO, GA, HACO和ABC，由此可以看出IDWSA在求解物資應(yīng)急調(diào)度問(wèn)題時(shí)可以縮短車輛行駛的總距離，從而減少運(yùn)輸成本和配送時(shí)間。此外，從圖9還可以看出，IDWSA所求解的平均偏差與最大偏差均大于MAPSO, GA, HACO和ABC，這表明IDWSA所求最好解與平均解以及最差解之間的差距較大，種群在迭代后期仍保持較高的個(gè)體間差異性，從而提高算法求得全局最優(yōu)解的概率。

圖9 5種算法實(shí)驗(yàn)結(jié)果對(duì)比

在相同實(shí)驗(yàn)條件下，IDWSA, MAPSO, GA,HACO和ABC的平均運(yùn)算時(shí)間分別為46.16 s,22.6 s, 3.8 s, 5.43 s和7.7 s。IDWSA的平均運(yùn)算時(shí)間遠(yuǎn)大于MAPSO, GA, HACO和ABC，其中種群移動(dòng)更新所用時(shí)間為43.52 s，占總運(yùn)算時(shí)間的94.3%，由此可知，父代個(gè)體在向其引導(dǎo)個(gè)體移動(dòng)時(shí)，為獲得高質(zhì)量的子代個(gè)體，在引導(dǎo)個(gè)體周圍進(jìn)行細(xì)致的搜索，因此耗費(fèi)了大量時(shí)間，這也是后續(xù)研究中需要解決的問(wèn)題。

6 結(jié)論

本文針對(duì)物資應(yīng)急調(diào)度背景下的MESPMDCTW問(wèn)題，提出了一種改進(jìn)離散鯨魚群算法(IDWSA)。綜合考慮了影響算法性能的可能因素，分別從種群初始化方式、鯨魚子代個(gè)體生成方式及個(gè)體選擇方式3個(gè)方面改進(jìn)鯨魚群算法，結(jié)果表明，本文研究的IDWSA可以對(duì)車輛行駛路徑進(jìn)行合理規(guī)劃，縮短車輛行駛總距離，減少物資配送時(shí)間，從而有效解決物資應(yīng)急調(diào)度問(wèn)題。

通過(guò)在Solomon標(biāo)準(zhǔn)測(cè)試集上進(jìn)行仿真計(jì)算，結(jié)論如下：(1)根據(jù)不同種群規(guī)模和迭代次數(shù)下所求解的質(zhì)量與運(yùn)算時(shí)間，選取種群大小20、迭代次數(shù)30作為算法的最優(yōu)參數(shù)。(2)混合初始化策略所生成初始種群的多樣性介于動(dòng)態(tài)模糊聚類和隨機(jī)生成之間，且初始種群和其所求問(wèn)題最終解的平均最好解、平均最差解及平均解均優(yōu)于二者，驗(yàn)證了混合初始化策略的有效性。(3)采用全局評(píng)價(jià)函數(shù)選擇個(gè)體，所生成子代種群的多樣性降低幅度較小，且在迭代后期其種群多樣性仍高于適應(yīng)度函數(shù)，表明全局評(píng)價(jià)函數(shù)可有效維持種群多樣性。(4)與MAPSO, GA, HACO和ABC相比，IDWSA所求問(wèn)題最好解的距離分別減少了2.25%, 13.4%, 6%,1.46%，并且可在一定程度上降低所求解為局部最優(yōu)解的概率。