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

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

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

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

1 垃圾運輸問題提出及其數(shù)學模型

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

目標函數(shù)如下式所示：

約束條件如下式所示：

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

實際案例中垃圾回收點和垃圾中轉(zhuǎn)站散點圖如圖1所示，網(wǎng)格單位為米。

圖1 垃圾回收點和垃圾中轉(zhuǎn)站散點圖

2 遺傳算法求解

2.1 編碼

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

2.2 種群初始化

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

2.3 適應(yīng)度函數(shù)

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

即遍歷n個回收點再返回0點路程的倒數(shù)，適應(yīng)度函數(shù)的值越大染色體表現(xiàn)越好，反之則越差。

2.4 遺傳算子

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

2.5 交叉運算

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

2.6 變異運算

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

遺傳算法初始相關(guān)參數(shù)如表1。

表1 遺傳算法初始參數(shù)

2.7 優(yōu)化結(jié)果

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

表2 遺傳算法路徑表

圖2 中轉(zhuǎn)站數(shù)=1時清運路徑優(yōu)化圖及總成本變化趨勢圖

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

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

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

3 選址問題的提出及其數(shù)學模型

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

目標函數(shù)如式（10）所示：

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

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

4 免疫算法求解

4.1 初始化記憶庫

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

4.2 多樣性評價參數(shù)

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

4.3 免疫操作

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

免疫算法初始相關(guān)參數(shù)如表4。

表4 遺傳算法初始參數(shù)

4.4 優(yōu)化結(jié)果

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

圖4 垃圾中轉(zhuǎn)站數(shù)量分別為2、3、4、5時選址位置圖及收斂曲線圖

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

圖5 中轉(zhuǎn)站數(shù)=3時清運路徑圖及總成本變化趨勢圖

5 結(jié)論

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

園區(qū)內(nèi)當前僅有一個垃圾中轉(zhuǎn)站，本研究增加了邊緣垃圾中轉(zhuǎn)站的訪問路徑，根據(jù)免疫算法將園區(qū)內(nèi)中轉(zhuǎn)站設(shè)定為3個，可以在現(xiàn)有垃圾回收點不變的情況下，進一步優(yōu)化清運路徑及降低費用。