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

　　摘 要：針對(duì)鯨魚(yú)群算法求解多配送中心帶時(shí)間窗的物資應(yīng)急調(diào)度問(wèn)題時(shí)存在的易陷入局部極值等缺點(diǎn)，該文提出一種改進(jìn)離散鯨魚(yú)群算法(IDWSA)。首先采用混合初始化策略提高初始種群的質(zhì)量;然后構(gòu)建以相似配送順序和相同配送中心為比較項(xiàng)的兩種移動(dòng)規(guī)則，并設(shè)計(jì)自適應(yīng)柯西變異算子和路徑選擇策略對(duì)個(gè)體進(jìn)行移動(dòng);最后構(gòu)造全局評(píng)價(jià)函數(shù)用于選擇個(gè)體以維持種群多樣性。在Solomon標(biāo)準(zhǔn)測(cè)試集上，IDWSA所求最好解的距離與 MAPSO, GA, HACO, ABC相比分別減少了2.25%, 13.4%, 6%, 1.46%，有效縮短了車輛的行駛距離。

　　關(guān)鍵詞：物資應(yīng)急調(diào)度;鯨魚(yú)群算法;全局評(píng)價(jià)函數(shù);柯西變異算子

　　蔣華偉郭陶楊震等-《電子與信息學(xué)報(bào)》2022年

　　自然災(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)離散鯨魚(yú)群算法(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.2 數(shù)學(xué)模型

　　MESPMDCTW問(wèn)題可由有向圖描述，在有向圖中頂點(diǎn)表示配送中心及受災(zāi)點(diǎn)，有向邊表示車輛的可行駛路徑，如圖1所示。假設(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à)越大。

　　其中，I=D∪R，V為車輛集合，cij為從點(diǎn)i到點(diǎn) j所需的成本，fk表示使用第k輛車的固定費(fèi)用， xijkt是決策變量，當(dāng)?shù)趖個(gè)配送中心的第k輛車從點(diǎn) i到點(diǎn)j時(shí)，xijkt為1，否則為0。 (2)容量約束 ∑ i∈I ∑ j∈I xijktqj ≤ Q, t ∈ D (2) 式(2)表示在該車輛行駛路徑上所訪問(wèn)受災(zāi)點(diǎn)的總需求量不超過(guò)其最大載重。 (3)時(shí)間窗約束 Pj = a×max (ETi − ti , 0)+b×max (ti − LTi , 0) (3) 由于各受災(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

　　鯨魚(yú)群算法(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ī)生成一組解作為初始種群，種群中每條鯨魚(yú)代表解空間中的一個(gè)候選解;然后根據(jù)種群中鯨魚(yú)的適應(yīng)度值和位置，依次為每條鯨魚(yú)搜索其 “更優(yōu)且最近”目標(biāo)鯨魚(yú)，即周圍適應(yīng)度更優(yōu)的鯨魚(yú)中距離其最近的鯨魚(yú);最后每條鯨魚(yú)均以其目標(biāo)鯨魚(yú)為導(dǎo)向以某種方式進(jìn)行移動(dòng)，從而產(chǎn)生新一代種群，其向目標(biāo)鯨魚(yú)移動(dòng)的方式如式(7)。 x t+1 i = x t i + rand ( 0, ρ0 · e −η·dXY ) · ( y t i − x t i ) (7) x t+1 i x t i y t i 其中，X為待移動(dòng)鯨魚(yú)的位置信息，Y為X的“更優(yōu)且最近”鯨魚(yú)的位置信息; 和 分別表示鯨魚(yú)X的第i個(gè)元素在第t+1次和第t次迭代后所在的位置， 為鯨魚(yú)Y的第i個(gè)元素在第t次迭代后所在的位置;dXY為鯨魚(yú)X和鯨魚(yú)Y之間的距離;ρ0為超聲波源的強(qiáng)度;η為超聲波衰減系數(shù)，其值由目標(biāo)函數(shù)確定;rand(0,ρ0 ·e–η·dXY)為介于0和ρ0 ·e–η·dXY之間的隨機(jī)數(shù)，一般地ρ0=2，η=–20·ln0.25/dmax。由式(7)可知，當(dāng)鯨魚(yú)X與其“更優(yōu)且最近”鯨魚(yú)Y之間的距離很近時(shí)，鯨魚(yú)X會(huì)積極地向鯨魚(yú)Y隨機(jī)移動(dòng);反之，鯨魚(yú)X會(huì)消極地向鯨魚(yú)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ì)新的鯨魚(yú)個(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。由于基本W(wǎng)SA中的距離公式僅適用于求解連續(xù)性問(wèn)題，而不能直接用于求解離散問(wèn)題，因此根據(jù)MESPMDCTW問(wèn)題的特點(diǎn)及本文設(shè)計(jì)的3層編碼方式，提出一種計(jì)算鯨魚(yú)個(gè)體間相對(duì)距離的方法，如式(8)。

　　其中，DXY表示個(gè)體X與Y之間的相對(duì)距離; 表示個(gè)體X的第i個(gè)位置， 表示個(gè)體Y的第i個(gè)位置;ρ表示距離因子，當(dāng)?shù)趇個(gè)受災(zāi)點(diǎn)在個(gè)體X， Y中所屬車輛配送順序相同時(shí)，其值為0，反之，值為1。

　　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è)體。

　　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)集合大小均衡。

　　diff(p, A,B) = ∑ d (p, A) − d (p, B) (d (p, A) − d (p, B)) − d (p, A) d (p, B) (9) 其中，d(p,A)、d(p,B)分別表示受災(zāi)點(diǎn)p與A類受災(zāi)點(diǎn)、B類受災(zāi)點(diǎn)的距離，diff(p,A,B)表示受災(zāi)點(diǎn)p與 A類和B類受災(zāi)點(diǎn)集合距離的差值，其值越大表示將受災(zāi)點(diǎn)p從A劃分到B的可能性越大。

　　完整的DFC過(guò)程如下：

　　(1)數(shù)據(jù)預(yù)處理。由于各受災(zāi)點(diǎn)之間距離和時(shí)間指標(biāo)的度量單位不同，因此采用式(10)對(duì)數(shù)據(jù)進(jìn)行歸一化處理。 xik = xik − xk sk (i = 1, 2, ..., n; k = 1, 2, ..., m) (10) sk = √ 1 n ∑n i=1 (xik − xk) 2 xk = 1 n ∑n i=1 xik 其中，xik表示第i個(gè)受災(zāi)點(diǎn)的第k個(gè)分量的值，， 。

　　(2)構(gòu)建模糊矩陣R。根據(jù)各受災(zāi)點(diǎn)之間的距離、受災(zāi)點(diǎn)的訪問(wèn)時(shí)間窗及其服務(wù)時(shí)間，利用式 (11)計(jì)算受災(zāi)點(diǎn)之間的相似性系數(shù)，并構(gòu)造模糊相似矩陣。 sij = ∑m k=1 |xik − xi | · |xjk − xj | vuut ∑m k=1 (xik − xi) 2 · vuut∑m k=1 (xjk − xj ) 2 + 1 e t i e+t i s−t j l (11) t i e t i s t j l 其中，xik，xjk分別表示受災(zāi)點(diǎn)i和j的第k個(gè)分量，即坐標(biāo)值; ， 分別表示受災(zāi)點(diǎn)i的最早開(kāi)始時(shí)間和服務(wù)時(shí)間， 表示受災(zāi)點(diǎn)j的最晚開(kāi)始時(shí)間， sij為受災(zāi)點(diǎn)i和j之間的相似性系數(shù)，其值越大表明越相似。

　　(3)計(jì)算模糊矩陣R的傳遞閉包t(R)。令R2= RºR，再令R4=R2 ºR2，···，直到滿足R2 l= Rl ºRl與Rl相等，即為t(R)，仍記為R。其中，º表示矩陣相乘。 (4)選擇截取水平 λ ，利用 λ-截矩陣Rλ對(duì)樣本進(jìn)行分類。 (5)采用式(9)對(duì)聚類結(jié)果進(jì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)柯西變異算子。 X = X + η · C (0, 1) (12)

　　其中， η 為控制變異步長(zhǎng)的常數(shù)，C(0,1)是由t=1的柯西分布函數(shù)產(chǎn)生的隨機(jī)數(shù)。????? Xij = Xij + xj · C (xmin, xmax) xj = (∑n i=1 xij) /n (13) 其中，xi j為個(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 路徑選擇策略

　　鯨魚(yú)個(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為空。

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

　　IDWSA中，鯨魚(yú)個(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è)體。 fitness(X) = 1 dist + α × PW + β × P (t) (14) 其中，dist表示個(gè)體X的總行駛距離;PW表示所使用車輛數(shù)量的影響因子，是個(gè)很大的常數(shù);α用于衡量個(gè)體X中使用的總車輛數(shù)k與可用車輛數(shù) K間的關(guān)系，若k>K，則α=|k–K|，反之α=k/K; β為總服務(wù)時(shí)間的影響因子，0<β<1，P(t)為車輛延時(shí)訪問(wèn)的懲罰函數(shù)，其中t為個(gè)體X中車輛延時(shí)配送的總時(shí)長(zhǎng)，表達(dá)式如式(15)。

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

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

　　對(duì)于種群中的個(gè)體X，在對(duì)其進(jìn)行一次移動(dòng)后會(huì)產(chǎn)生兩個(gè)子代個(gè)體，則完成一輪搜索后，種群規(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)行選擇以組成新的子代種群。 E (x) = f x X F i−1 × e fx−F i F i × 1 1 + e − fx−fx X fX Y −fx X + fitness(x) (16) f x X f X Y F i−1 其中， 表示個(gè)體x對(duì)應(yīng)的父代個(gè)體X的適應(yīng)度值， 表示父代個(gè)體X的引導(dǎo)個(gè)體Y的適應(yīng)度值，為父代種群中所有個(gè)體的平均適應(yīng)度值，fx為子代種群中個(gè)體x的適應(yīng)度值，F(xiàn) i為子代種群中所有個(gè)體適應(yīng)度值的累加和。

　　全局評(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。本文所有實(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所示。

　　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)性。

　　此外，從圖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ù)。

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

　　初始解的質(zhì)量對(duì)后續(xù)問(wèn)題的求解至關(guān)重要，為驗(yàn)證本文所提混合初始化策略的有效性，本文構(gòu)建了式(17)用于衡量算法迭代過(guò)程中種群的多樣性。 D = ?? ∑ i ∑ j dij ?? /( popsize · n 2 ) (17) 其中，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 全局評(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)解的可能性大幅度增加。同時(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ù)的有效性。

　　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)解的概率。在相同實(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)離散鯨魚(yú)群算法(IDWSA)。綜合考慮了影響算法性能的可能因素，分別從種群初始化方式、鯨魚(yú)子代個(gè)體生成方式及個(gè)體選擇方式3個(gè)方面改進(jìn)鯨魚(yú)群算法，結(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)解的概率。