基于改進(jìn)鯨魚優(yōu)化算法的畜禽廢棄物運(yùn)輸路徑優(yōu)化問題

路雪剛， 張雪花*， 張夢(mèng)桃

(1.天津工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院， 天津 300387； 2.北京郵電大學(xué)經(jīng)濟(jì)管理學(xué)院， 北京 100876)

改革開放40多年來，中國(guó)畜禽養(yǎng)殖業(yè)迅速發(fā)展，已成為農(nóng)村經(jīng)濟(jì)發(fā)展的重要支柱產(chǎn)業(yè)之一[1]。隨著畜禽養(yǎng)殖技術(shù)的不斷提高，畜禽養(yǎng)殖業(yè)體量不斷擴(kuò)大，上下游產(chǎn)業(yè)鏈不配套不合理，導(dǎo)致畜禽養(yǎng)殖廢棄物成為農(nóng)村環(huán)境的重要來源。有關(guān)數(shù)據(jù)表明，目前中國(guó)畜禽養(yǎng)殖廢棄物年產(chǎn)量接近40億t，每年至少有約16億t不能得到妥善處理[2]，而在畜禽養(yǎng)殖廢棄物資源化利用過程中，落后的收集與運(yùn)輸方式是其瓶頸環(huán)節(jié)。

隨著計(jì)算機(jī)技術(shù)的發(fā)展，快遞送貨[3]、自動(dòng)引導(dǎo)車(automated guided vehicle，AGV)[4]、應(yīng)急物資配送[5]等問題已經(jīng)成為車輛路徑優(yōu)化問題(vehicle routing problem, VRP)的延伸領(lǐng)域，并且使用解決VRP的方法將新領(lǐng)域的“舊”問題進(jìn)行有效解決。通過對(duì)畜禽養(yǎng)殖廢棄物處理中心的分析發(fā)現(xiàn)，其運(yùn)輸問題屬于經(jīng)典的車輛路徑優(yōu)化問題，通過對(duì)VRP領(lǐng)域又一新的延伸，同時(shí)也為類似處理中心的畜禽廢棄物運(yùn)輸問題提供一種新的解決思路。

對(duì)于畜禽養(yǎng)殖廢棄物問題，國(guó)內(nèi)外許多專家進(jìn)行了研究。甘俊偉等[6]運(yùn)用熵權(quán)法從政策要素、市場(chǎng)要素、技術(shù)要素和認(rèn)為要素4個(gè)方面建立了畜禽養(yǎng)殖廢棄物回收的影響因素指標(biāo)體系，并提出相應(yīng)對(duì)策；陳秋紅等[7]深入探討了禽養(yǎng)殖廢棄物資源化利用的演進(jìn)階段及相關(guān)政策演變規(guī)律，針對(duì)目前存在的問題提出相關(guān)建議；Jagtap等[8]研究發(fā)現(xiàn)目前常用的處理方法包括用作動(dòng)物飼料、厭氧消化、堆肥、焚燒，以及最糟糕的填埋和廢水處理，其研究提出利用低價(jià)值廢物并將其轉(zhuǎn)化為高價(jià)值食品配料的過程在整個(gè)商業(yè)運(yùn)營(yíng)中系統(tǒng)地增加了價(jià)值；Angelika等[9]介紹了過氧化鈣作為綠色氧化劑和殺菌劑在畜禽糞便處理中的應(yīng)用。研究表明，氧化鈣可以作為一種環(huán)境友好的氧化劑和殺微生物劑的牲畜廢物；Oliveira等[10]對(duì)肉雞生產(chǎn)中氨排放的影響因素、測(cè)量方法和幾個(gè)國(guó)家已經(jīng)進(jìn)行的排放清單進(jìn)行綜述，介紹了在家禽糞便中產(chǎn)生氨的主要化學(xué)工藝，并提供了一些有助于減少氨排放的做法。

高效的智能優(yōu)化算法有助于合理調(diào)配資源，提供更科學(xué)的路徑策略，國(guó)內(nèi)許多專家、學(xué)者對(duì)車輛路徑優(yōu)化問題做了研究。Elham等[11]以城市固體廢棄物收集為背景，研究了帶有中間設(shè)施的多艙容性弧路徑問題，并將鯨魚優(yōu)化算法(whale optimization algorithm, WOA)進(jìn)行改進(jìn)對(duì)所提問題進(jìn)行求解，通過實(shí)例仿真驗(yàn)證其改進(jìn)算法能夠獲得更高質(zhì)量的解；Zhang等[12]研究了冷鏈配送問題，構(gòu)建軟時(shí)間窗模型的冷鏈物流車輛路徑優(yōu)化模型，對(duì)傳統(tǒng)遺傳算法的變異算子進(jìn)行改進(jìn)，通過實(shí)驗(yàn)表明改進(jìn)遺傳算法能夠以較低的代價(jià)找到路徑；任騰等[13]研究生鮮電商的配送路徑問題，重點(diǎn)關(guān)注道路擁堵情況和客戶滿意度，建立了以總成本最小化的車輛路徑優(yōu)化模型，在蟻群算法的基礎(chǔ)上引入禁忌搜索算子，提高了其對(duì)問題的求解性能；尚猛等[14]首次使用WOA求解車輛路徑優(yōu)化問題，針對(duì)標(biāo)準(zhǔn)WOA在迭代過程中求解精度不高、容易陷入局部最優(yōu)解的問題，使用隨機(jī)慣性權(quán)重及非均勻變異策略進(jìn)行改進(jìn)，并通過實(shí)驗(yàn)證明所提算法能夠有效降低物流配送成本。

綜上，目前關(guān)于畜禽養(yǎng)殖廢棄物研究主要集中在以下3個(gè)方面：一是技術(shù)層面，包括養(yǎng)殖污染負(fù)荷的估算評(píng)估與污染處理技術(shù)、資源環(huán)境承載力研究等；二是經(jīng)濟(jì)學(xué)層面，研究畜禽養(yǎng)殖戶行為動(dòng)機(jī)與養(yǎng)殖布局變遷的經(jīng)濟(jì)學(xué)分析；三是政策及管理層面，主要涉及畜禽養(yǎng)殖污染防控、促進(jìn)資源再利用的政策與管理機(jī)制等。但是，鮮有對(duì)于畜禽養(yǎng)殖廢棄物的運(yùn)輸問題進(jìn)行研究。在智能優(yōu)化算法方面，本文對(duì)鯨魚優(yōu)化算法進(jìn)行改進(jìn)，目前鯨魚優(yōu)化算法用于求解路徑優(yōu)化問題較少，另外標(biāo)準(zhǔn)的鯨魚優(yōu)化算法只能求解連續(xù)函數(shù)，而所研究的問題屬于離散型問題。

故現(xiàn)借鑒經(jīng)典的車輛路徑優(yōu)化問題，結(jié)合畜禽養(yǎng)殖廢棄物的特點(diǎn)，構(gòu)建畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型，并提出改進(jìn)鯨魚優(yōu)化算法(improved whale optimization algorithm, IWOA)，具體改進(jìn)策略為：采用基于反向?qū)W習(xí)策略優(yōu)化初始種群，以提高初始解集質(zhì)量；使用升序排列(ranked order value，ROV)轉(zhuǎn)換機(jī)制將標(biāo)準(zhǔn)WOA算法在包圍獵物、攻擊獵物和搜索獵物3個(gè)階段產(chǎn)生的小數(shù)轉(zhuǎn)化為可具體實(shí)現(xiàn)的整數(shù)方案；為提高算法的全局搜索能力和收斂能力，將得到的初始方案進(jìn)行K-means聚類分析，篩選出較為優(yōu)秀的個(gè)體，對(duì)優(yōu)秀個(gè)體進(jìn)行基于位置的交叉(position-based crossover，PBX)操作和逆序變異操作；為解決標(biāo)準(zhǔn)WOA容易跳出最優(yōu)解的缺陷，引入精英保留策略。以期通過優(yōu)化收運(yùn)路徑，降低運(yùn)輸成本，助力農(nóng)業(yè)可持續(xù)發(fā)展。

1 畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型 的構(gòu)建

1.1 模型的描述與假設(shè)條件

畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型可以描述為：在某一區(qū)域內(nèi)，有一輛或多輛運(yùn)輸車從畜禽廢棄物處理中心出發(fā)，依次前往多個(gè)隨機(jī)分布的畜禽養(yǎng)殖廠，中途車輛滿載時(shí)需返回畜禽廢棄物處理中心卸載，直至把所有畜禽廢棄物運(yùn)輸完，最終車輛回到畜禽廢棄物處理中心。由于畜禽養(yǎng)殖廠數(shù)量較多且位置分布隨機(jī)，運(yùn)輸路線不唯一，需要在眾多路線中，尋找出運(yùn)輸總距離最短的方案，提高運(yùn)輸效率。

為便于研究且保證問題的科學(xué)性，做出以下假設(shè)。

假設(shè)1所研究區(qū)域內(nèi)，僅有1個(gè)畜禽廢棄物處理中心，有m個(gè)畜禽養(yǎng)殖廠，并且所有畜禽養(yǎng)殖廠的位置及廢棄物產(chǎn)生量提前已知。

假設(shè)2運(yùn)輸車輛有最大載重限制，不能超載，且從畜禽廢棄物處理中心駛出，最終回到畜禽廢棄物處理中心。

假設(shè)3每個(gè)畜禽養(yǎng)殖廠之間都互通，并且都能直接到達(dá)畜禽廢棄物處理中心，采用歐式距離進(jìn)行計(jì)算。

假設(shè)4每一輛運(yùn)輸車可以經(jīng)過多個(gè)畜禽養(yǎng)殖廠，但一個(gè)畜禽養(yǎng)殖廠產(chǎn)生的廢棄物只能由一輛運(yùn)輸車收集。

假設(shè)5研究領(lǐng)域內(nèi)的畜禽廢棄物種類相同，可存放在一輛運(yùn)輸車內(nèi)。

在經(jīng)典車輛路徑優(yōu)化問題上拓展，其中假設(shè)1～假設(shè)4為經(jīng)典問題的假設(shè)條件，參見文獻(xiàn)[15]。此外，由于畜禽廢棄物分類較多，包括病死畜禽[1]、畜禽糞污[16]等，為驗(yàn)證IWOA求解畜禽養(yǎng)殖廢棄物運(yùn)輸路徑問題，假設(shè)處理的畜禽廢棄物為同一種類，可存放在一輛運(yùn)輸車內(nèi)，實(shí)際運(yùn)輸中對(duì)不同種類畜禽廢棄物的運(yùn)輸，只需對(duì)本文算法分別運(yùn)行即可解決。

1.2 主要符號(hào)說明

使用整數(shù)規(guī)劃模型對(duì)畜禽養(yǎng)殖廢棄物運(yùn)輸路徑問題建模，以最短總運(yùn)輸距離為目標(biāo)函數(shù)，為便于描述，畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型中所涉及的主要符號(hào)及其說明如表1所示。

表1 主要符號(hào)及其說明Table 1 Main symbols and descriptions

1.3 數(shù)學(xué)模型的構(gòu)建

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

(1)

約束條件為

(2)

(3)

(4)

(5)

(6)

(7)

qij≥0,i∈M,j∈M

(8)

i,j=1,2,…,m

(9)

其中，式(1)為目標(biāo)函數(shù)，表示畜禽養(yǎng)殖廢棄物運(yùn)輸路徑極小化；式(2) 表示每個(gè)畜禽養(yǎng)殖廠產(chǎn)生廢棄物只能被一輛車回收且一次回收完畢；式(3)表示每輛運(yùn)輸車只能同時(shí)回收一個(gè)畜禽養(yǎng)殖廠的廢棄物；式(4)表示每輛運(yùn)輸車從畜禽廢棄物處理中心駛出，最后回到畜禽廢棄物處理中心；式(5)表示運(yùn)輸車到達(dá)該畜禽養(yǎng)殖廠，并且從該畜禽養(yǎng)殖廠離開，保證運(yùn)輸過程的連續(xù)性；式(6)表示運(yùn)輸車裝載的廢棄物不能超過該車的最大載貨量；式(7)表示每條路線中不存在子回路，|Tk|表示其模長(zhǎng)；式(8)表示每個(gè)畜禽養(yǎng)殖廠產(chǎn)生的廢棄物不能為負(fù)數(shù)，符合實(shí)際情況；式(9)表示變量的取值范圍。

2 IWOA算法設(shè)計(jì)

2.1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法(WOA)是由澳大利亞Mirialili博士于2016年提出的新型啟發(fā)式優(yōu)化算法[17]，Mirialili博士根據(jù)鯨魚在捕食過程中表現(xiàn)出的包圍、追捕和攻擊等行為，模擬出WOA中相應(yīng)的包圍獵物、攻擊和搜索獵物3個(gè)階段，在WOA算法中，每一只鯨魚的位置向量表示一種可行解，獵物的位置對(duì)應(yīng)問題的全局最優(yōu)解。假設(shè)鯨魚的數(shù)量為N，搜索空間為d維，第i只鯨魚的位置表示為

(10)

2.1.1 包圍獵物階段

鯨魚通過向獵物方向游動(dòng)實(shí)現(xiàn)對(duì)獵物的包圍，但是對(duì)優(yōu)化問題的全局最優(yōu)解沒有先驗(yàn)知識(shí)，將此刻最優(yōu)鯨魚位置作為最優(yōu)解，其他鯨魚個(gè)體向最優(yōu)位置包圍，數(shù)學(xué)模型表示為

D=|CX′(gen)-X(gen)|

(11)

X(gen+1)=X′(gen)-AD

(12)

式中：X′(gen)為此刻最優(yōu)鯨魚個(gè)體的位置向量；X(gen)為某一鯨魚個(gè)體的位置向量；gen為目前迭代次數(shù)；A和C為系數(shù)，其數(shù)學(xué)公式為

A=2αr1-α

(13)

C=2r2

(14)

(15)

式中：α為控制參數(shù)，從2線性遞減到0；r1和r2為(0,1)范圍內(nèi)的隨機(jī)數(shù)；genmax為最大迭代次數(shù)。

2.1.2 攻擊階段

根據(jù)鯨魚的狩獵行為，其在包圍獵物后，采用螺旋式運(yùn)動(dòng)游向獵物，此階段的數(shù)學(xué)模型為

Dp=|X′(gen)-X(gen)|

(16)

X(gen+1)=X′(gen)+Dpeblcos(2πl(wèi))

(17)

式中：Dp為鯨魚個(gè)體和最優(yōu)個(gè)體之間的距離，p為(0,1)范圍內(nèi)的隨機(jī)數(shù)；b為常數(shù)，用來定義螺旋的形狀；l為(-1,1)范圍內(nèi)的隨機(jī)數(shù)。

需要注意的是，鯨魚以螺旋式游向獵物的同時(shí)做縮緊環(huán)狀游動(dòng)，因此，為了能夠同時(shí)模擬這兩種行為，設(shè)置有一半概率選擇收縮包圍行為，有另一半的概率選擇螺旋游動(dòng)來更新鯨魚的位置，數(shù)學(xué)模型表示為

(18)

2.1.3 搜索獵物階段

鯨魚除了向獵物方向包圍外，還可以根據(jù)非最優(yōu)個(gè)體進(jìn)行隨機(jī)游走來搜索獵物的位置，這種策略能夠增強(qiáng)WOA算法的全局搜索能力。在算法中，設(shè)定當(dāng)|A|≥1時(shí)，迫使鯨魚偏離獵物，選擇隨機(jī)鯨魚個(gè)體更新自己的位置，以此找到全局最優(yōu)解，數(shù)學(xué)模型表示為

D=|CXr(gen)-X(gen)|

(19)

X(gen+1)=Xr(gen)-AD

(20)

式中：Xr(gen)為隨機(jī)鯨魚個(gè)體的位置向量。

2.2 改進(jìn)鯨魚優(yōu)化算法

WOA雖然在部分領(lǐng)域已經(jīng)證實(shí)其優(yōu)秀的全局搜索能力，但其運(yùn)行機(jī)制仍具有一定的缺陷，如：在求解過程中，很多參數(shù)為隨機(jī)數(shù)，導(dǎo)致算法只求得局部最優(yōu)解，A取值不穩(wěn)定，導(dǎo)致全局搜索和局部搜索不平衡等問題。為提升WOA算法的求解質(zhì)量，在種群生產(chǎn)階段采用反向?qū)W習(xí)策略，提高初始種群的多樣性，由于標(biāo)準(zhǔn)WOA算法不能求解離散問題，引入ROV機(jī)制將小數(shù)轉(zhuǎn)化為整數(shù)，并保證使路徑方案的可行性，在算法迭代后期引入PBX交叉和逆序變異因子，提高鯨魚個(gè)體的解的質(zhì)量，從而提出IWOA的求解性能。

2.2.1 基于反向?qū)W習(xí)策略的種群初始化

初始種群的質(zhì)量對(duì)算法搜索性能有重要影響，優(yōu)秀的初始種群，能夠使算法收斂更快，求解精度更高。然而在標(biāo)準(zhǔn)WOA中，初始種群是采用隨機(jī)方式生成的，其質(zhì)量不能夠得到保障，故采用反向?qū)W習(xí)(opposition-based learning, OBL)策略[18]優(yōu)化初始種群?；诜聪?qū)W習(xí)策略的種群初始化的思想是在初始種群的基礎(chǔ)上，通過規(guī)定的映射準(zhǔn)則產(chǎn)生相同數(shù)量的反向個(gè)體，將初始種群與反向個(gè)體混合，優(yōu)秀的個(gè)體參與后期算法迭代過程。采用基于反向?qū)W習(xí)策略產(chǎn)生的種群個(gè)體可以表示為

(21)

2.2.2 升序排列轉(zhuǎn)換機(jī)制

畜禽養(yǎng)殖廢棄物運(yùn)輸路徑問題屬于典型的離散問題，然而標(biāo)準(zhǔn)WOA算法的3個(gè)更新階段針對(duì)連續(xù)變量?jī)?yōu)化問題所設(shè)計(jì)，無法直接實(shí)現(xiàn)路徑優(yōu)化問題的更新。有鑒于此，采用升序排列(ROV)轉(zhuǎn)換機(jī)制[19]將小數(shù)轉(zhuǎn)化為整數(shù)，并且使得IWOA算法更新得到的方案具有可行性。

ROV轉(zhuǎn)換機(jī)制的思路為：首先根據(jù)假設(shè)2的要求，將經(jīng)過IWOA算法更新的個(gè)體位置向量第一個(gè)維度抽出，并賦值為1，然后按升序排列給剩余每個(gè)維度賦予唯一的ROV值，最后將第一維度對(duì)應(yīng)的值與ROV值依次排列，即構(gòu)造出相應(yīng)的離散個(gè)體，如圖1所示。

圖1 ROV轉(zhuǎn)換機(jī)制示例Fig.1 Example of ROV conversion mechanism

2.2.3 PBX交叉

交叉算子是算法迭代過程中，擴(kuò)大種群多樣性的有效操作，能夠探索更多未知空間，增強(qiáng)算法的全局搜索能力。采用基于位置的交叉(PBX)算子[20]，鯨魚個(gè)體進(jìn)行PBX交叉操作后，能夠保證其解的可行性。以長(zhǎng)度為8的路徑方案為例，對(duì)PBX交叉進(jìn)行詳細(xì)說明，如圖2所示，具體步驟如下。

圖2 PBX交叉示意圖Fig.2 PBX crossover diagram

步驟1選取兩個(gè)鯨魚個(gè)體作為父代，分別記為O1和O2，生成兩個(gè)相同維度的零向量，作為子代個(gè)體，分別記為S1和S2。

步驟2在O1上隨機(jī)選擇幾個(gè)位置，將這些位置上的元素平移到S1對(duì)應(yīng)的位置，將O2上相同位置的元素平移到S2對(duì)應(yīng)的位置。

步驟3識(shí)別O2中與S1中不沖突的元素，將其按照O2上的順序依次填入S1空位中，按此方式填充S2。

2.2.4 逆序變異

在IWOA算法中，PBX交叉算子保證算法能夠擴(kuò)大搜尋空間，增強(qiáng)其全局搜索能力，而逆序變異(reverse mutation)算子能夠保證算法局部尋優(yōu)能力，提高算法收斂速度。逆序變異是有序整數(shù)編碼中常用的操作算子，在進(jìn)行逆序變異后不需要進(jìn)行沖突基因檢驗(yàn)，方便且有效，以長(zhǎng)度為8的路徑方案為例，對(duì)逆序變異進(jìn)行說明，如圖3所示，具體步驟如下。

圖3 逆序變異示意圖Fig.3 Schematic diagram of reverse mutation

步驟1選取一條鯨魚個(gè)體作為父代個(gè)體，記為O1，生成一個(gè)相同維度的零向量，作為子代個(gè)體，記為S1。

步驟2隨機(jī)選擇O1中的兩個(gè)位置作為截?cái)帱c(diǎn)。

步驟3將截?cái)帱c(diǎn)之間的向量取出，進(jìn)行逆轉(zhuǎn)操作，并依次放入S1對(duì)應(yīng)位置。

步驟4將O1的剩余基因依次填入S1中。

2.2.5 IWOA算法步驟

改進(jìn)鯨魚優(yōu)化算法(improved whale optimization algorithm, IWOA)是在標(biāo)準(zhǔn)WOA算法上進(jìn)行改進(jìn)，以使其能夠更好地求解畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型。IWOA算法流程圖如圖4所示，操作步驟如下。

步驟1參數(shù)和種群初始化。

步驟2使用反向?qū)W習(xí)策略優(yōu)化初始種群，得到新的鯨魚種群。

步驟3生成隨機(jī)數(shù)r，若r<0.5，執(zhí)行攻擊階段的公式，否則執(zhí)行步驟4。

步驟4計(jì)算|A|的值，若|A|<1，執(zhí)行包圍獵物階段公式，否則執(zhí)行步驟5。

步驟5執(zhí)行搜索獵物階段的公式。

步驟6采用ROV轉(zhuǎn)換機(jī)制，將小數(shù)轉(zhuǎn)化為整數(shù)編碼。

步驟7計(jì)算更新鯨魚種群的適應(yīng)度值。

步驟8對(duì)種群適應(yīng)度值進(jìn)行聚類分析，并選擇聚類分析中適應(yīng)度值最優(yōu)一類的個(gè)體。

步驟9PBX交叉操作產(chǎn)生新個(gè)體。

步驟10逆序變異操作產(chǎn)生新個(gè)體。

步驟11將新個(gè)體與舊個(gè)體混合，進(jìn)行適應(yīng)度值計(jì)算并選擇適應(yīng)度值較優(yōu)的前Nind個(gè)鯨魚個(gè)體作為本次迭代最終種群。

步驟12判斷是否達(dá)到最大迭代次數(shù)，若是則輸出最優(yōu)解，否則采取精英保留策略并進(jìn)入步驟2繼續(xù)迭代。

圖4 IWOA算法流程圖Fig.4 Flow chart of IWOA algorithm

步驟13結(jié)束。

根據(jù)上述IWOA算法的流程描述，IWOA算法的偽代碼如表2所示。

2.2.6 IWOA算法的時(shí)間復(fù)雜度分析

IWOA算法的時(shí)間復(fù)雜度主要取決于種群初始化、聚類分析、PBX交叉及逆序變異步驟，分別記作T1、T2、T3和T4。假設(shè)種群規(guī)模為m、最大迭代次數(shù)為n、聚類分析的中心數(shù)為l，最優(yōu)類中的個(gè)體數(shù)量為k。

表2 IWOA算法偽代碼Table 2 Pseudo code of IWOA algorithm

種群初始化依次生成m個(gè)個(gè)體，隨后OBL策略對(duì)種群進(jìn)行優(yōu)化，并不存在嵌套循環(huán)，故種群初始化的時(shí)間復(fù)雜度為

T1=O(mn)

(22)

在聚類分析中采用的是K-means聚類分析，將m個(gè)個(gè)體分為l類，故聚類分析的時(shí)間復(fù)雜度為

T2=O(lmn)

(23)

PBX交叉和逆序變異是針對(duì)聚類分析后最優(yōu)秀的一類進(jìn)行操作，故PBX交叉和逆序變異的時(shí)間復(fù)雜度分別為

T3=O(kn)

(24)

T4=O(kn)

(25)

綜上，IWOA算法的時(shí)間復(fù)雜度為

TIWOA=O(mn+lmn+kn+kn)

(26)

由于時(shí)間復(fù)雜度只關(guān)注最高數(shù)量級(jí)，與系數(shù)無關(guān)，并且m和l為常量，故IWOA算法的時(shí)間復(fù)雜度最終可表示為

TIWOA=O(kn)

(27)

3 實(shí)驗(yàn)分析

為驗(yàn)證設(shè)計(jì)的IWOA算法求解畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型的有效性，設(shè)計(jì)兩組實(shí)驗(yàn)，一組為使用VRP領(lǐng)域有代表性的Solomon數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)[21]，另一組引用相關(guān)文獻(xiàn)中使用的真實(shí)公司數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)[22]。

3.1 Solomon算例仿真測(cè)試

為更能體現(xiàn)仿真實(shí)驗(yàn)的客觀性，第一組仿真實(shí)驗(yàn)在Solomon算例中選取9個(gè)不同規(guī)模的算例，其中節(jié)點(diǎn)數(shù)分別包含25、50和100三種。鑒于WOA算法屬于群體智能優(yōu)化算法，另選取較為經(jīng)典且擁有優(yōu)異求解性能的粒子群優(yōu)化算法(particle swarm optimization, PSO)和蟻群優(yōu)化算法(ant colony optimization, ACO)，以及近年提出的新型智能優(yōu)化算法——灰狼算法(gray wolf optimization, GWO)進(jìn)行對(duì)比，由于PSO算法、ACO算法及GWO算法只適用于對(duì)連續(xù)函數(shù)的求解，并且為了保證算法之間的可比性，故對(duì)3種算法進(jìn)行改進(jìn)，改進(jìn)后的算法分別為：改進(jìn)粒子群優(yōu)化算法(improved particle swarm optimization, IPSO)、改進(jìn)蟻群優(yōu)化算法(improved ant colony optimization, IACO)及改進(jìn)灰狼算法(improved gray wolf optimization, IGWO)，通過與其他同類算法對(duì)比來驗(yàn)證IWOA算法的求解性能。設(shè)置算法中參數(shù)[15,23-24]為：種群規(guī)模Nind=100，最大迭代次數(shù)genmax=100，車輛最大載重L=200，螺旋系數(shù)b=1，IPSO算法中系數(shù)C1=C2=1.496 2，ω=0.729 8，IACO算法中α=1，β=5，信息素增加強(qiáng)度系數(shù)Q=10，信息素蒸發(fā)系數(shù)ρ=0.75。4種算法對(duì)每個(gè)算例運(yùn)行20次獨(dú)立實(shí)驗(yàn)，運(yùn)行結(jié)果如表3所示。

由表3可知，設(shè)計(jì)的IWOA算法在9個(gè)算例中，在最小值best和平均值avg方面均明顯優(yōu)于其他3種算法。從best和avg方面來看，IWOA算法取得的結(jié)果最優(yōu)，其次是IACO算法，再次是IPSO算法，最后是IGWO算法，在問題規(guī)模為25個(gè)節(jié)點(diǎn)時(shí)，4個(gè)算法求解效果差距較小，隨著問題規(guī)模的增大，求解更為復(fù)雜，IGWO算法明顯表現(xiàn)出其求解能力的不足，IWOA算法和IACO算法表現(xiàn)較優(yōu)。針對(duì)var方面，IWOA算法在8個(gè)算例中均取得最小值，由于算法求解時(shí)具有很大的隨機(jī)性，即使在第一個(gè)算例中，IACO算法的方差最小，也能夠說明IWOA算法求解效果的穩(wěn)定性，隨著問題規(guī)模的增大，明顯看出4種算法的方差波動(dòng)也隨之增大，但I(xiàn)WOA算法所受影響較小。綜上可得，IWOA算法在求解精度及穩(wěn)定性方面均明顯優(yōu)于其他算法。

3.2 實(shí)例仿真測(cè)試

引用文獻(xiàn) [22]中的算例進(jìn)行仿真測(cè)試，繼續(xù)對(duì)IWOA算法、IACO算法、IPSO算法及IGWO算法的求解性能進(jìn)行對(duì)比分析。實(shí)例可以描述為：該區(qū)域內(nèi)，有1個(gè)畜禽廢棄物處理中心和31個(gè)畜禽養(yǎng)殖廠，所有位置坐標(biāo)及各養(yǎng)殖廠廢棄物產(chǎn)量已知，由載重為200 t的貨車收運(yùn)，尋找出遍歷各畜禽養(yǎng)殖廠的總短路徑最短方案，畜禽廢棄物處理中心及畜禽養(yǎng)殖廠信息如表4所示。

4種算法分別對(duì)測(cè)試實(shí)例獨(dú)立運(yùn)行20次，算法參數(shù)設(shè)置參照3.1節(jié)內(nèi)容，仿真結(jié)果數(shù)據(jù)如表5所示，各項(xiàng)指標(biāo)中最優(yōu)結(jié)果加粗表示。由表5可知，IWOA算法在各指標(biāo)中均明顯優(yōu)于其他算法，在最小值方面，IWOA算法比IPSO算法、IACO算法及IGWO算法分別提高4.9%、6.5%和43.7%。IWOA算法在20次運(yùn)行結(jié)果中最大值比其他3種算法的最小值方案還要優(yōu)秀，證明IWOA算法具有很好的尋優(yōu)能力。IWOA算法的極差僅為15.01，方差僅為11.78，足以證明IWOA算法具有較強(qiáng)的穩(wěn)定性。

表3 算法運(yùn)行結(jié)果Table 3 Algorithm running results

表4 畜禽廢棄物處理中心及畜禽養(yǎng)殖廠信息Table 4 Livestock and poultry waste treatment center and livestock and poultry breeding plant information

表5 算法仿真結(jié)果比較Table 5 Comparison of algorithm simulation results

4種算法在運(yùn)行20次中最優(yōu)結(jié)果對(duì)應(yīng)的車輛路徑圖如圖5～圖8所示。4種算法迭代軌跡圖如圖9所示。根據(jù)圖5～圖8分析可知，在此案例中需要收運(yùn)31個(gè)畜禽養(yǎng)殖廠的廢棄物，4種算法均只需2輛車即可完成，但是4種算法求解20次，所得到的最優(yōu)方案不同。圖5、圖6和圖8方案對(duì)應(yīng)的目標(biāo)函數(shù)值分別為341.74、375.03和381.38，三者的目標(biāo)函數(shù)值相差較小，因此部分路徑相同，由于畜禽養(yǎng)殖廠及畜禽廢棄物處理中心的位置隨機(jī)分布，更能體現(xiàn)出IWOA算法求解精度更高。圖7為IGWO算法求解路徑方案，明顯看出其路線錯(cuò)綜復(fù)雜，在求解畜禽養(yǎng)殖廢棄物運(yùn)輸路徑方面性能最差。由圖9也可知，IWOA算法生成的初始種群質(zhì)量更高，首次迭代比IGWO算法運(yùn)行結(jié)束后的結(jié)果更好，IPSO算法和IACO算法雖然取得稍好的結(jié)果，但是在運(yùn)行過程中容易跳出最優(yōu)解，收斂效果不好，體現(xiàn)出IWOA算法使用精英保留策略的重要性。Solomon算例和實(shí)例仿真實(shí)驗(yàn)均表明了IWOA算法求解畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型，具有更高的求解精度和穩(wěn)定性。

圖5 IWOA算法路徑優(yōu)化方案Fig.5 IWOA algorithm path optimization scheme

圖6 IPOS算法路徑優(yōu)化方案Fig.6 IPOS algorithm path optimization scheme

圖7 IGWO算法路徑優(yōu)化方案Fig.7 IGWO algorithm path optimization scheme

圖8 IACO算法路徑優(yōu)化方案Fig.8 IACO algorithm path optimization scheme

圖9 4種算法優(yōu)化過程Fig.9 Optimization process of four algorithms

4 結(jié)論

為提高畜禽養(yǎng)殖廢棄物的收運(yùn)效率，基于整數(shù)規(guī)劃方法，建立了畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型，并且改進(jìn)WOA算法以使其能夠求解本文模型。在改進(jìn)WOA算法中，采用基于反向?qū)W習(xí)策略的種群初始化方法，提升了初始種群質(zhì)量，加快了算法收斂速度；在迭代過程中引入優(yōu)秀算子，如PBX交叉算子和逆序變異算子，并使用精英保留策略將上一代優(yōu)秀個(gè)體作為下一代的部分初始種群，成功設(shè)計(jì)出一種可以求解離散問題的IWOA算法。通過Solomon算例和實(shí)例仿真實(shí)驗(yàn)，結(jié)合其他優(yōu)秀算法進(jìn)行對(duì)比分析，得出結(jié)論如下。

(1)算法方面，IWOA算法通過一系列改進(jìn)，極大地提升了其求解精度和穩(wěn)定性。在9個(gè)Solomon算例及實(shí)例仿真實(shí)驗(yàn)中，IWOA算法相較于IPSO算法、IGWO算法和IACO算法在最優(yōu)值方面分別提高10.63%～24.56%、7.87%～69.03%和4.96%～15.62%，尤其在求解大規(guī)模案例時(shí)，IWOA算法相較于其他算法求解性能大幅提高。在畜禽廢棄物運(yùn)輸實(shí)例仿真實(shí)驗(yàn)中，IWOA算法求解結(jié)果比IPSO算法、IACO算法及IGWO算法分別提高4.9%、6.5%和43.7%，因此IWOA算法能夠有效求解畜禽養(yǎng)殖廢棄物運(yùn)輸路徑優(yōu)化模型。

(2)實(shí)踐方面，之前鮮有學(xué)者使用智能優(yōu)化算法對(duì)畜禽養(yǎng)殖廢棄物運(yùn)輸路徑進(jìn)行分析，為畜禽廢棄物的收運(yùn)提出了新的、可行的且高效的方法，為此行業(yè)貢獻(xiàn)一種方案。

(3)在“碳中和”和“碳達(dá)峰”的愿景下，今后的工作可以進(jìn)一步關(guān)注綠色畜禽養(yǎng)殖，降低畜禽養(yǎng)殖行業(yè)的碳排放，如考慮運(yùn)輸車輛的碳排放問題，設(shè)計(jì)更好的算法求解雙目標(biāo)模型。