基于遺傳算法和免疫算法的垃圾清運路徑規劃
——以安陽工學院為例

李 航，劉 然，張 潔，李亞茹

（安陽工學院，河南 安陽 455000）

隨著垃圾分類的力度日益加大，高校為了滿足垃圾收集，在校園內投放了大量的垃圾桶，但是垃圾回收車的路徑常為隨機運動，這使得運輸產生了較多的往復，增加了運輸時間和成本，一些研究運用蟻群算法進行路徑優化[1-8]，一些則采用遺傳算法將之轉變為TSP問題求解[9-15]。實際垃圾收運問題涉及回收中心、車輛裝載、往復運輸等約束條件，因此垃圾收運可以化歸為CVRP問題，垃圾中轉站設置可以化歸為FLP問題，為了更加有效的設置中轉站并調動垃圾車清運，采用GA算法和IA算法進行優化設計。

1 垃圾運輸問題提出及其數學模型

安陽工學院校園內現有垃圾回收點77處，垃圾中轉站1處，垃圾回收車7輛，每輛垃圾回收車最大載量為400 L，每次全園區清運總費用約1 150元，在無時間窗限制的情況下，垃圾回收車均以空車狀態從垃圾中轉站出發，遍歷77處垃圾回收點，當回收達到最大載量后需要回到中轉站卸載而后再投入工作，直至所有垃圾清運完成，其數學模型可以描述為：園區內有1處垃圾中轉站，中轉站有m輛垃圾回收車，記為V={k},k=1,2,……m,每輛垃圾回收車載重為L,站點集合記為P={i}，i=1,2,……n，各站點垃圾數量為Qi，從站點i到j的路程記為Dij，Cij為收運成本，規劃收運路線最短，分配垃圾回收車數量m最少。

目標函數如下式所示：

約束條件如下式所示：

其中，式（1）表示垃圾回收車行程最短；式（2）表示垃圾回收車數量使用數最少；式（3）表示最小清運成本；式（4）表示垃圾回收車不能超載；式（5）、式（6）、式（7）表示垃圾回收車從垃圾中轉站0出發，如果某處垃圾站點已經被回收則其他垃圾車不再處理，回收完成后所有垃圾回收車最終返回中轉站。

實際案例中垃圾回收點和垃圾中轉站散點圖如圖1所示，網格單位為米。

圖1 垃圾回收點和垃圾中轉站散點圖

2 遺傳算法求解

2.1 編碼

對于n個目標點的CVRP問題使用自然數編碼，即坐標系內各點用自然數（n≥1）標記，本例中中轉站數量為1，編號標記為0，各垃圾回收點從1開始標記，受載重的約束，垃圾回收車ki從0開始收運并累積每個回收點的垃圾數量，超過最大載量時返回0點，并繼續遍歷，直到園區內垃圾均回收。

2.2 種群初始化

根據目標點規模數量初始化一個種群作為初始解，本例采用隨機生成法，取值50。

2.3 適應度函數

將P1|P2|P3|……|Pn|作為一個采用自然數編碼的染色體，為回收點Pi到Pj的距離，個體適應度Fitness可表述為

即遍歷n個回收點再返回0點路程的倒數，適應度函數的值越大染色體表現越好，反之則越差。

2.4 遺傳算子

個體被選中的概率與其適應度函數成正比，數量為n群體中，個體i被選中遺傳到下一代的概率Si的可表述為式（9），在遺傳算子的基礎上，采用輪盤賭算法確定個體是否被遺傳到下一代。

2.5 交叉運算

采用部分映射多點雜交，產生個數為Nu的隨機數，則父代個體基因串被分成Nu個基因段，A（i）表示父代個體A的第i個基因段，Ai=1……Nu，交叉概率取0.9。

2.6 變異運算

采用基本位變異，變異概率設定為0.05，即種群內所有基因的5%進行變異，迭代數為100。

遺傳算法初始相關參數如表1。

表1 遺傳算法初始參數

2.7 優化結果

本例中僅存在一個垃圾中轉站，5輛垃圾回收車即可完成整個園區的清運工作，較當前設置可以節省2輛垃圾回收車，5輛垃圾回收車總路程為5 986.84 m，路徑圖及清運總成本變化趨勢如圖2所示，清運路徑如表2所示，回收成本降到600元左右，降比約48%。

表2 遺傳算法路徑表

圖2 中轉站數=1時清運路徑優化圖及總成本變化趨勢圖

分析優化結果可知，路線5僅經過了5個回收點，且與多條路徑之間產生交叉點，導致清運線程增加。在該模式下，處于園區邊緣的回收點垃圾存放量較少，垃圾回收車僅需訪問1次即可完成該點清運，因此Pc=0.9時，模型趨向純粹隨機搜索，遺傳算法結果的收斂性較差，重新設置Pc=0.5，Pm=0.01,并增加迭代次數為200，優化清運路線及總成本變化趨勢如圖3所示，5輛垃圾回收車路徑如表3，總路程5 853.33 m，回收成本為595元。

表3 Pc=0.5、MAXGEN=200路徑表

圖3 Pc=0.5、MAXGEN=200路徑優化路線圖及總成本變化趨勢圖

3 選址問題的提出及其數學模型

由上述遺傳算法結果可知，1處垃圾中轉站無法保證垃圾回收車就近卸載，實際上延長了清運路線，適當增加中轉站數量并求解其位置可以進一步減少清運路線和清運成本。此處選擇使用免疫算法對多基址選取進行模擬優化[16-22]，在遺傳算法得出5輛垃圾回收車的前提下，其數學模型可以描述為：園區內有大于1處的垃圾中轉站，記為Hi，所有中轉站共有5輛垃圾回收車，記為V={k},k=1,2,……5,每輛垃圾回收車載重為L,垃圾站點集合記為P={i}，i=1,2,……n，各站點垃圾數量為Qi，從垃圾回收站點i到垃圾中轉站j的路程記為dij，垃圾中轉站距離由其服務的垃圾回收車的距離上限記為S，到回收點i的清運距離小于S的備選中轉站集合記為Mi，垃圾回收站點與垃圾中轉站的分配關系記為Jij，該值為0-1變量，Jij=1表示回收站點與垃圾中轉站j匹配，否則Jij=0，點j是否選為垃圾中轉站由0-1變量表示，記為hi，hj=1表示選為中轉站，否則hj=0，綜上在滿足距離上限的前提下，從所有回收點找出中轉站并回收垃圾，目標函數是各中轉站到回收站點的清運量和清運距離的乘積之和最小。

目標函數如式（10）所示：

約束條件如式（11）-式（15）所示：

式中，式（10）表示垃圾回收站點到垃圾中轉站距離乘積之和最小；式（11）表示5輛垃圾回收車只能由一個垃圾中轉站發出；式（12）表示沒有中轉站則不會接受垃圾回收車返程卸載；式（13）表示垃圾中轉站總數量；式（14）表示Jij和hj兩個變量；式（15）表示垃圾回收站點與垃圾中轉站距離未超過上限值。

4 免疫算法求解

4.1 初始化記憶庫

設置非空記憶庫，保證初始抗體群從記憶庫中產生，每個選址方案形成一個長度為t的抗體（t表示垃圾中轉站數量），每個抗體表示被選為中轉站的序列，本例中t=3，記憶庫容量=20。

4.2 多樣性評價參數

多樣性評價由抗體與抗原間的親和力、抗體與抗體間的親和力、抗體濃度以及繁殖概率得出，本例中采用精英保留策略，每次更新記憶庫均先將與抗原親和度最高的個體存入記憶庫，針對垃圾中轉站選址模型，設定多樣性評價參數Ps=0.9。

4.3 免疫操作

采用輪盤賭算法選擇單點交叉機制以及隨機變異，得交叉概率Pc=0.8，變異概率Pm=0.01，迭代次數為200，垃圾中轉站數為2。

免疫算法初始相關參數如表4。

表4 遺傳算法初始參數

4.4 優化結果

將垃圾中轉站數量分別設定為2個、3個、4個、5個，選址位置及收斂曲線如圖4所示。本例中，當垃圾中轉站數量超過3個后，垃圾回收車及中轉站利用率迅速降低，因此，綜合評價園區內可設置垃圾中轉站數量為3，其坐標分別為A[191,261]，B[381,323]，C[527,65],對應垃圾回收點數量分別為16，48，13。

圖4 垃圾中轉站數量分別為2、3、4、5時選址位置圖及收斂曲線圖

以3個垃圾中轉站再次進行遺傳算法路徑優化，路徑圖和總成本圖如圖5所示，5個垃圾回收車的清運總路徑為5 326.94 m，清運成本約為502元，較“2.7”環節計算結果總路徑進一步減少550 m，清運成本降低約90元，分析變化趨勢圖可以發現曲線有較大波動但是收斂效果較佳。

圖5 中轉站數=3時清運路徑圖及總成本變化趨勢圖

5 結論

以安陽工學院為例研究了垃圾中轉站設置和垃圾清運路線，得出校園內站點分布相對集中、中轉站數量相對較少，不同分區內垃圾數量的差異較大，處于邊緣的垃圾回收站點通常僅需一次訪問，在沒有時間窗限制的條件下，垃圾回收車路徑優化主要由交叉概率Pc、變異概率Pm兩個參數控制，當Pc=0.5和Pm=0.01時收斂平穩的結論。

園區內當前僅有一個垃圾中轉站，本研究增加了邊緣垃圾中轉站的訪問路徑，根據免疫算法將園區內中轉站設定為3個，可以在現有垃圾回收點不變的情況下，進一步優化清運路徑及降低費用。