基于改進鯨魚優化算法的畜禽廢棄物運輸路徑優化問題

路雪剛， 張雪花*， 張夢桃

(1.天津工業大學經濟與管理學院， 天津 300387； 2.北京郵電大學經濟管理學院， 北京 100876)

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

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

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

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

綜上，目前關于畜禽養殖廢棄物研究主要集中在以下3個方面：一是技術層面，包括養殖污染負荷的估算評估與污染處理技術、資源環境承載力研究等；二是經濟學層面，研究畜禽養殖戶行為動機與養殖布局變遷的經濟學分析；三是政策及管理層面，主要涉及畜禽養殖污染防控、促進資源再利用的政策與管理機制等。但是，鮮有對于畜禽養殖廢棄物的運輸問題進行研究。在智能優化算法方面，本文對鯨魚優化算法進行改進，目前鯨魚優化算法用于求解路徑優化問題較少，另外標準的鯨魚優化算法只能求解連續函數，而所研究的問題屬于離散型問題。

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

1 畜禽養殖廢棄物運輸路徑優化模型 的構建

1.1 模型的描述與假設條件

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

為便于研究且保證問題的科學性，做出以下假設。

假設1所研究區域內，僅有1個畜禽廢棄物處理中心，有m個畜禽養殖廠，并且所有畜禽養殖廠的位置及廢棄物產生量提前已知。

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

假設3每個畜禽養殖廠之間都互通，并且都能直接到達畜禽廢棄物處理中心，采用歐式距離進行計算。

假設4每一輛運輸車可以經過多個畜禽養殖廠，但一個畜禽養殖廠產生的廢棄物只能由一輛運輸車收集。

假設5研究領域內的畜禽廢棄物種類相同，可存放在一輛運輸車內。

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

1.2 主要符號說明

使用整數規劃模型對畜禽養殖廢棄物運輸路徑問題建模，以最短總運輸距離為目標函數，為便于描述，畜禽養殖廢棄物運輸路徑優化模型中所涉及的主要符號及其說明如表1所示。

表1 主要符號及其說明Table 1 Main symbols and descriptions

1.3 數學模型的構建

目標函數為

(1)

約束條件為

(2)

(3)

(4)

(5)

(6)

(7)

qij≥0,i∈M,j∈M

(8)

i,j=1,2,…,m

(9)

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

2 IWOA算法設計

2.1 鯨魚優化算法

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

(10)

2.1.1 包圍獵物階段

鯨魚通過向獵物方向游動實現對獵物的包圍，但是對優化問題的全局最優解沒有先驗知識，將此刻最優鯨魚位置作為最優解，其他鯨魚個體向最優位置包圍，數學模型表示為

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

(11)

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

(12)

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

A=2αr1-α

(13)

C=2r2

(14)

(15)

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

2.1.2 攻擊階段

根據鯨魚的狩獵行為，其在包圍獵物后，采用螺旋式運動游向獵物，此階段的數學模型為

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

(16)

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

(17)

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

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

(18)

2.1.3 搜索獵物階段

鯨魚除了向獵物方向包圍外，還可以根據非最優個體進行隨機游走來搜索獵物的位置，這種策略能夠增強WOA算法的全局搜索能力。在算法中，設定當|A|≥1時，迫使鯨魚偏離獵物，選擇隨機鯨魚個體更新自己的位置，以此找到全局最優解，數學模型表示為

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

(19)

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

(20)

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

2.2 改進鯨魚優化算法

WOA雖然在部分領域已經證實其優秀的全局搜索能力，但其運行機制仍具有一定的缺陷，如：在求解過程中，很多參數為隨機數，導致算法只求得局部最優解，A取值不穩定，導致全局搜索和局部搜索不平衡等問題。為提升WOA算法的求解質量，在種群生產階段采用反向學習策略，提高初始種群的多樣性，由于標準WOA算法不能求解離散問題，引入ROV機制將小數轉化為整數，并保證使路徑方案的可行性，在算法迭代后期引入PBX交叉和逆序變異因子，提高鯨魚個體的解的質量，從而提出IWOA的求解性能。

2.2.1 基于反向學習策略的種群初始化

初始種群的質量對算法搜索性能有重要影響，優秀的初始種群，能夠使算法收斂更快，求解精度更高。然而在標準WOA中，初始種群是采用隨機方式生成的，其質量不能夠得到保障，故采用反向學習(opposition-based learning, OBL)策略[18]優化初始種群。基于反向學習策略的種群初始化的思想是在初始種群的基礎上，通過規定的映射準則產生相同數量的反向個體，將初始種群與反向個體混合，優秀的個體參與后期算法迭代過程。采用基于反向學習策略產生的種群個體可以表示為

(21)

2.2.2 升序排列轉換機制

畜禽養殖廢棄物運輸路徑問題屬于典型的離散問題，然而標準WOA算法的3個更新階段針對連續變量優化問題所設計，無法直接實現路徑優化問題的更新。有鑒于此，采用升序排列(ROV)轉換機制[19]將小數轉化為整數，并且使得IWOA算法更新得到的方案具有可行性。

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

圖1 ROV轉換機制示例Fig.1 Example of ROV conversion mechanism

2.2.3 PBX交叉

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

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

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

步驟2在O1上隨機選擇幾個位置，將這些位置上的元素平移到S1對應的位置，將O2上相同位置的元素平移到S2對應的位置。

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

2.2.4 逆序變異

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

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

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

步驟2隨機選擇O1中的兩個位置作為截斷點。

步驟3將截斷點之間的向量取出，進行逆轉操作，并依次放入S1對應位置。

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

2.2.5 IWOA算法步驟

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

步驟1參數和種群初始化。

步驟2使用反向學習策略優化初始種群，得到新的鯨魚種群。

步驟3生成隨機數r，若r<0.5，執行攻擊階段的公式，否則執行步驟4。

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

步驟5執行搜索獵物階段的公式。

步驟6采用ROV轉換機制，將小數轉化為整數編碼。

步驟7計算更新鯨魚種群的適應度值。

步驟8對種群適應度值進行聚類分析，并選擇聚類分析中適應度值最優一類的個體。

步驟9PBX交叉操作產生新個體。

步驟10逆序變異操作產生新個體。

步驟11將新個體與舊個體混合，進行適應度值計算并選擇適應度值較優的前Nind個鯨魚個體作為本次迭代最終種群。

步驟12判斷是否達到最大迭代次數，若是則輸出最優解，否則采取精英保留策略并進入步驟2繼續迭代。

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

步驟13結束。

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

2.2.6 IWOA算法的時間復雜度分析

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

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

種群初始化依次生成m個個體，隨后OBL策略對種群進行優化，并不存在嵌套循環，故種群初始化的時間復雜度為

T1=O(mn)

(22)

在聚類分析中采用的是K-means聚類分析，將m個個體分為l類，故聚類分析的時間復雜度為

T2=O(lmn)

(23)

PBX交叉和逆序變異是針對聚類分析后最優秀的一類進行操作，故PBX交叉和逆序變異的時間復雜度分別為

T3=O(kn)

(24)

T4=O(kn)

(25)

綜上，IWOA算法的時間復雜度為

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

(26)

由于時間復雜度只關注最高數量級，與系數無關，并且m和l為常量，故IWOA算法的時間復雜度最終可表示為

TIWOA=O(kn)

(27)

3 實驗分析

為驗證設計的IWOA算法求解畜禽養殖廢棄物運輸路徑優化模型的有效性，設計兩組實驗，一組為使用VRP領域有代表性的Solomon數據進行仿真實驗[21]，另一組引用相關文獻中使用的真實公司數據進行仿真實驗[22]。

3.1 Solomon算例仿真測試

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

由表3可知，設計的IWOA算法在9個算例中，在最小值best和平均值avg方面均明顯優于其他3種算法。從best和avg方面來看，IWOA算法取得的結果最優，其次是IACO算法，再次是IPSO算法，最后是IGWO算法，在問題規模為25個節點時，4個算法求解效果差距較小，隨著問題規模的增大，求解更為復雜，IGWO算法明顯表現出其求解能力的不足，IWOA算法和IACO算法表現較優。針對var方面，IWOA算法在8個算例中均取得最小值，由于算法求解時具有很大的隨機性，即使在第一個算例中，IACO算法的方差最小，也能夠說明IWOA算法求解效果的穩定性，隨著問題規模的增大，明顯看出4種算法的方差波動也隨之增大，但IWOA算法所受影響較小。綜上可得，IWOA算法在求解精度及穩定性方面均明顯優于其他算法。

3.2 實例仿真測試

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

4種算法分別對測試實例獨立運行20次，算法參數設置參照3.1節內容，仿真結果數據如表5所示，各項指標中最優結果加粗表示。由表5可知，IWOA算法在各指標中均明顯優于其他算法，在最小值方面，IWOA算法比IPSO算法、IACO算法及IGWO算法分別提高4.9%、6.5%和43.7%。IWOA算法在20次運行結果中最大值比其他3種算法的最小值方案還要優秀，證明IWOA算法具有很好的尋優能力。IWOA算法的極差僅為15.01，方差僅為11.78，足以證明IWOA算法具有較強的穩定性。

表3 算法運行結果Table 3 Algorithm running results

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

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

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

圖5 IWOA算法路徑優化方案Fig.5 IWOA algorithm path optimization scheme

圖6 IPOS算法路徑優化方案Fig.6 IPOS algorithm path optimization scheme

圖7 IGWO算法路徑優化方案Fig.7 IGWO algorithm path optimization scheme

圖8 IACO算法路徑優化方案Fig.8 IACO algorithm path optimization scheme

圖9 4種算法優化過程Fig.9 Optimization process of four algorithms

4 結論

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

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

(2)實踐方面，之前鮮有學者使用智能優化算法對畜禽養殖廢棄物運輸路徑進行分析，為畜禽廢棄物的收運提出了新的、可行的且高效的方法，為此行業貢獻一種方案。

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