生活垃圾收運路徑優(yōu)化研究

文/陳歡歡 朱虹宇

基于生活垃圾量劇增、城市建成區(qū)范圍不斷擴(kuò)展、生活垃圾終端處理設(shè)施不斷外移、收運系統(tǒng)模式重新調(diào)整等問題，構(gòu)建以最小化運輸成本和碳排放成本為目標(biāo)的生活垃圾收運路徑優(yōu)化模型，并通過重構(gòu)解空間設(shè)計了一種改進(jìn)回溯搜索算法對模型展開求解。最后，通過與遺傳算法和模擬退火算法相比，改進(jìn)回溯搜索算法能獲得更高質(zhì)量的解，收運路徑方案的收運距離最短，在生活垃圾收運路徑優(yōu)化中能得到一個較好的應(yīng)用。

1.引言

近年來，隨著中國經(jīng)濟(jì)社會的發(fā)展和城鎮(zhèn)人口的增多，使城市生活垃圾的產(chǎn)生量也隨之增加，2021年我國城市生活垃圾產(chǎn)生量約2.49億噸，清運壓力仍不容小覷。國家統(tǒng)計局?jǐn)?shù)據(jù)顯示，生活垃圾的收集和運輸?shù)奈镔Y消耗占整個垃圾處理系統(tǒng)的70%～80%[1]。同時，為順應(yīng)公益、垃圾分類回收以及低碳環(huán)保等政策要求，合理的生活垃圾收運方案能有效地縮短收運距離為企業(yè)降本增效、降低碳排放量減少環(huán)境污染，故對生活垃圾收運路徑進(jìn)行優(yōu)化，具有重要的現(xiàn)實意義。生活垃圾收運路徑優(yōu)化問題屬于一般車輛路徑問題，國內(nèi)外學(xué)者對該問題已展開了深入研究。張玉州等[2]以最小車輛運輸費用為目標(biāo)構(gòu)建了多回收站垃圾收運問題模型，引入合作協(xié)同算法，并結(jié)合改進(jìn)聚類算法和混合遺傳算法對模型展開求解，證明了所提算法在降低復(fù)雜垃圾收運問題時，具有良好的性能；趙今越等[3]針對帶硬時間窗的垃圾收運路徑問題，以最小化運輸成本和車輛固定成本為目標(biāo)建立了數(shù)學(xué)模型，并提出一種以改進(jìn)蟻群算法為外部框架，混沌電磁場優(yōu)化算法為內(nèi)部模塊的新型混合蟻群算法對城市生活垃圾分類收運問題進(jìn)行求解；Alshraideh等[4]通過遺傳算法和約定居民服務(wù)水平的概率約束方法研究了隨機(jī)需求下帶時間窗的周期性醫(yī)療廢棄物收運路徑問題；Lu等[5]提出了一個基于信息通信技術(shù)的智能將垃圾分類收集系統(tǒng)抽象為一個雙目標(biāo)數(shù)學(xué)模型優(yōu)化垃圾收集問題的編程模型，證實了所提出的多目標(biāo)混合算法遺傳算法具有較好的優(yōu)化效果，能有效地解決多個廢物處理中心、廢物轉(zhuǎn)運站和廢物桶的廢物管理問題；Akhtar等[6]提出了一種改進(jìn)的有容量車輛路徑問題回溯搜索算法，該算法基于容量車輛路徑問題模型與智能箱的概念，提供了最佳的垃圾收集路徑，能有效降低收運經(jīng)濟(jì)成本和收運過程中的環(huán)境負(fù)效應(yīng)。目前國內(nèi)外針對生活垃圾收運路徑優(yōu)化的研究已有一定的基礎(chǔ)。從現(xiàn)有研究來看，雖然部分學(xué)者考慮了碳排放等環(huán)境指標(biāo)，但較少研究實際清運過程中車輛實時載重對碳排放量的影響，且在相關(guān)求解算法的選取上，目前大多數(shù)學(xué)者多用元啟發(fā)式算法中較為常見的算法對問題展開求解，對于回溯搜索算法的研究應(yīng)用較少。綜上所述，本文以最小化運輸成本和碳排放成本為目標(biāo)構(gòu)建生活垃圾收運路徑優(yōu)化模型，運用回溯搜索算法對該問題展開求解，并通過重構(gòu)解空間優(yōu)化回溯搜索算法，從而保證算法與問題的適配性，最終獲取最優(yōu)的生活垃圾收運路徑方案，為相關(guān)企業(yè)降本增效。

2.模型構(gòu)建

2.1 問題描述及符號說明

一輛或多輛垃圾收運車從車場出發(fā)，對區(qū)域內(nèi)的所有垃圾收集點展開清運，當(dāng)垃圾收運車滿載或完成路徑內(nèi)最后一個垃圾收集點的清運工作后，垃圾收運車返回至車場卸載垃圾，重復(fù)上述過程，直至完成所有垃圾收集點的清運。根據(jù)問題描述，對本文的模型假設(shè)如下：1）垃圾收集點和車場的位置已知；2）各垃圾收集點的垃圾量已知且固定；3）垃圾收運車單一且車輛載重固定。模型所涉及的相關(guān)參數(shù)及定義如下：W，表示生活垃圾收集點的集合；Z，表示垃圾收運車的集合；Q，垃圾收運車的最大載重量；dij，表示節(jié)點i，j間的距離；P，表示單位油價；pe，表示單位碳排放成本；qi，表示生活垃圾收集點的垃圾量；Qc，表示收運車單位燃料消耗產(chǎn)生的碳排放量；fij，表示節(jié)點i，j間垃圾收運車的單位距離油耗；xijk，表示當(dāng)垃圾收集點i到垃圾收集點j由車輛清運，xijk=1，否則；xijk=0，yik表示當(dāng)垃圾收集點i由車輛k清運，yik=1，否則yik=0。

2.2 數(shù)學(xué)模型

本文以運輸成本和碳排放成本最小為目標(biāo)，其中燃油消耗通過“負(fù)載估計法”計算得出[7]，即

其中，ρe為車輛空載時的單位距離油耗，ρf為車輛滿載時的單位距離油耗。

式（5）表示每個垃圾收集點被清運一次且只能由一輛車進(jìn)行清運；式（6）表示進(jìn)出平衡約束；式（7）表示每條收運路徑上的餐廚垃圾總量不得大于垃圾收運車的最大載重；式（8）表示消除子回路，其中J為車輛k的收運垃圾點集合；式（9）表示決策變量間的邏輯關(guān)系；式（10）保證每輛車都從車場出發(fā)；式（11）和式（12）表示變量的取值約束。

3.算法設(shè)計

回溯搜索算法是一種新穎而強(qiáng)大的進(jìn)化算法，該算法只有一個控制參數(shù)。相較于其他元啟發(fā)式算法而言，該算法結(jié)構(gòu)簡單，有效、快速，能夠輕松適應(yīng)不同的優(yōu)化問題，全局優(yōu)化能力強(qiáng)。因此，本文選取回溯搜索算法對問題展開求解。由于回溯搜索算法主要用于求解連續(xù)空間的優(yōu)化問題，而本文生活垃圾收運路徑優(yōu)化問題屬于非連續(xù)空間的組合優(yōu)化問題，故，需要對回溯搜索算法加以改進(jìn)，重構(gòu)解空間。具體的改進(jìn)回溯搜索算法流程如下：

3.1 編碼與解碼

根據(jù)回溯搜索算法求解問題的適配性，重構(gòu)解空間。采用非負(fù)整數(shù)編碼的方式表示解空間，生活垃圾收集節(jié)點為1，2，3，…，n，車場編碼為0，假設(shè)現(xiàn)有8個生活垃圾收集點，其編碼為1～8，車場為0，種群中每個個體表示收運車對生活垃圾收集節(jié)點的清運順序，再根據(jù)目標(biāo)函數(shù)和約束條件對個體進(jìn)行解碼，獲取車輛的實際清運路徑，如圖1所示。第一輛車從車場出發(fā)，對生活垃圾收集節(jié)點2、5、1清運完成后，返回車場。第二輛車從車場出發(fā)，對生活垃圾收集節(jié)點6、4、5、8、7、3清運完成后，返回車場。重復(fù)以上操作，直至完成所有生活垃圾收集節(jié)點的清運工作。

圖1 編碼解碼示意圖

3.2 構(gòu)建初始種群

改進(jìn)回溯搜索算法的種群由當(dāng)前種群P和歷史種群HisP構(gòu)成，首先對P和HisP初始化。初始種群采用隨機(jī)選擇法和最鄰近法相結(jié)合的方法構(gòu)建。首先以車場為起點，隨機(jī)選擇一個生活垃圾收集點連接車場，再依據(jù)當(dāng)前收運車剩余裝載容量、當(dāng)前垃圾收集點與剩余未被清運的生活垃圾收集點間的距離從剩余未被清運的收集點中選擇一節(jié)點加入當(dāng)前路徑中，直至當(dāng)前路徑不存在可行插入節(jié)點時，新增一條初始路徑。選擇新的路徑，重復(fù)上述步驟，直至所有節(jié)點均在路徑中，產(chǎn)生初始配送方案，組成初始種群。

3.3 選擇Ⅰ

首先隨機(jī)生成兩個數(shù)a和b，其中a～U（0，1），b～U（0，1），并基于式（13）進(jìn)行歷史種群的選擇，然后通過隨機(jī)排列準(zhǔn)則打亂歷史種群中個體的順序，生成最終歷史種群。

其中，:=表示前者隨后者更新。

3.4 變異和交叉

改進(jìn)回溯搜索算法通過變異和交叉獲得試驗種群T，T 的初始形態(tài)由變異產(chǎn)生，為了獲得T，首先通過式（14）進(jìn)行變異：mutant=P+F·（HisP-P）（14）

其中，F(xiàn)是控制參數(shù)，控制搜索方向矩陣（HisP-P）的幅度，F(xiàn)=d·rndn，rndn～N（0，1），d為問題維數(shù)。

其次，在交叉策略中引入映射矩陣，具體如下：隨機(jī)生成均勻分布的隨機(jī)數(shù)a和b，取值范圍為0～1，如果a＜b，那么對于當(dāng)前種群中的每個個體，計算要映射的元素數(shù)量：將種群中每個個體的元素數(shù)乘以混合率和0～1范圍內(nèi)的隨機(jī)數(shù)，從而計算出需要映射的元素數(shù)。再根據(jù)需要映射的元素數(shù)，分別將映射數(shù)組中的前幾個數(shù)設(shè)為0，其余則設(shè)為1。如果a≥b，則只有一個元素被映射為0，其余則設(shè)為1，被映射為0的元素的位置由每個個體的元素數(shù)乘以0～1范圍內(nèi)的隨機(jī)數(shù)所得值確定。

則可表示為：

此時，T中可能存在非可行解，若存在非可行解，則試驗種群中的個體隨機(jī)選取可行域范圍內(nèi)的一個值替代。

3.5 選擇Ⅱ

通過下式對種群進(jìn)行更新：

其中，DistTn，d和DistPn，d分別表示T和P中個體的適應(yīng)度值。如果當(dāng)P中的個體最優(yōu)解優(yōu)于當(dāng)前改進(jìn)回溯搜索算法獲得的全局最優(yōu)解，則改進(jìn)回溯搜索算法獲得的全局最優(yōu)解隨當(dāng)代種群中的個體最優(yōu)解更新。

4.算例分析

改進(jìn)回溯搜索算法程序在MatlabR2017a下完成，種群數(shù)目為30，個體長度等于生活垃圾收集點數(shù)與垃圾收運車輛數(shù)之和減1，混合率mixrate為0.8，最大迭代次數(shù)為100。

4.1 算例背景信息

重慶市是中國面積最大的十個城市之一，其中重慶主城區(qū)是全市的政治、經(jīng)濟(jì)、文化、交通、金融中心。2021年末，主城區(qū)城鎮(zhèn)人口高達(dá)967.58萬人，常住人口高達(dá)1038.99萬人，GDP為10927.63億元，占全市GDP總量的39.17%。人口和經(jīng)濟(jì)水平的增長使重慶主城區(qū)生活垃圾量也隨之增加，致使現(xiàn)有生活垃圾收運系統(tǒng)不再適應(yīng)重慶主城區(qū)的快速發(fā)展，迫切需要對現(xiàn)有垃圾收運系統(tǒng)進(jìn)行調(diào)整。對此，本文進(jìn)行生活垃圾收運路徑優(yōu)化研究，改善垃圾收運系統(tǒng)中的前端收集系統(tǒng)的現(xiàn)狀，優(yōu)化生活垃圾收運系統(tǒng)。

4.2 實例信息

通過調(diào)研，本文隨機(jī)選取主城區(qū)的20個垃圾收集點、1個垃圾處理廠為研究對象展開生活垃圾收運路徑優(yōu)化研究。模型中涉及的相關(guān)參數(shù)設(shè)定為：垃圾收運車的最大載重為2000kg、單位油價為7元/kg、單位碳排放成本為0.025元/kg、單位燃料消耗產(chǎn)生的碳排放量為2.67kg/L、空載時的單位距離油耗為0.165L/km、滿載時的單位距離油耗為0.377L/km。

4.3 結(jié)果分析

為了驗證本文所提算法的有效性，在獲取最終收運方案前，本文分別運用改進(jìn)回溯搜索算法、遺傳算法以及模擬退火算法獨立運行10次實例算例，并選取最優(yōu)解的收運距離為對比指標(biāo)進(jìn)行結(jié)果對比，結(jié)果如表1所示：

表1 算法有效性分析結(jié)果對比

從表1可以看出，本文所提算法求解到的最優(yōu)收運方案總收運距離為177.8223km，分別比遺傳算法和模擬退火算法所獲得的最優(yōu)解降低了21.44%、8.71%，證明本文所提算法具有良好的性能，可較好地解決生活垃圾收運路徑優(yōu)化問題。

運用改進(jìn)回溯搜索算法對上述實例進(jìn)行計算，得到餐廚垃圾收運最優(yōu)路徑如表2所示：

表2 生活垃圾收運路徑方案

5.結(jié)論

本文針對生活垃圾收運路徑優(yōu)化問題，構(gòu)建了一個以最小化運輸成本和碳排放成本為目標(biāo)的生活垃圾收運路徑優(yōu)化模型，并通過重構(gòu)解空間設(shè)計了一個改進(jìn)回溯搜索算法對模型展開求解。相較于遺傳算法和模擬退火算法，本文所提算法分別使收運距離降低了21.44%和8.71%，說明本文所提算法具有良好的計算表現(xiàn)性，能較好地求解生活垃圾收運路徑優(yōu)化問題。