生活垃圾收運路徑優化研究

文/陳歡歡 朱虹宇

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

1.引言

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

2.模型構建

2.1 問題描述及符號說明

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

2.2 數學模型

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

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

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

3.算法設計

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

3.1 編碼與解碼

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

圖1 編碼解碼示意圖

3.2 構建初始種群

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

3.3 選擇Ⅰ

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

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

3.4 變異和交叉

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

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

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

則可表示為：

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

3.5 選擇Ⅱ

通過下式對種群進行更新：

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

4.算例分析

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

4.1 算例背景信息

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

4.2 實例信息

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

4.3 結果分析

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

表1 算法有效性分析結果對比

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

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

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

5.結論

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