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

文/陳歡歡 朱虹宇

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

1.引言

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

2.模型構(gòu)建

2.1 問題描述及符號(hào)說明

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

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

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

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

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

3.算法設(shè)計(jì)

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

3.1 編碼與解碼

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

圖1 編碼解碼示意圖

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

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

3.3 選擇Ⅰ

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

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

3.4 變異和交叉

改進(jìn)回溯搜索算法通過變異和交叉獲得試驗(yà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，那么對(duì)于當(dāng)前種群中的每個(gè)個(gè)體，計(jì)算要映射的元素?cái)?shù)量：將種群中每個(gè)個(gè)體的元素?cái)?shù)乘以混合率和0～1范圍內(nèi)的隨機(jī)數(shù)，從而計(jì)算出需要映射的元素?cái)?shù)。再根據(jù)需要映射的元素?cái)?shù)，分別將映射數(shù)組中的前幾個(gè)數(shù)設(shè)為0，其余則設(shè)為1。如果a≥b，則只有一個(gè)元素被映射為0，其余則設(shè)為1，被映射為0的元素的位置由每個(gè)個(gè)體的元素?cái)?shù)乘以0～1范圍內(nèi)的隨機(jī)數(shù)所得值確定。

則可表示為：

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

3.5 選擇Ⅱ

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

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

4.算例分析

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

4.1 算例背景信息

重慶市是中國面積最大的十個(gè)城市之一，其中重慶主城區(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)有生活垃圾收運(yùn)系統(tǒng)不再適應(yīng)重慶主城區(qū)的快速發(fā)展，迫切需要對(duì)現(xiàn)有垃圾收運(yùn)系統(tǒng)進(jìn)行調(diào)整。對(duì)此，本文進(jìn)行生活垃圾收運(yùn)路徑優(yōu)化研究，改善垃圾收運(yùn)系統(tǒng)中的前端收集系統(tǒng)的現(xiàn)狀，優(yōu)化生活垃圾收運(yùn)系統(tǒng)。

4.2 實(shí)例信息

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

4.3 結(jié)果分析

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

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

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

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

表2 生活垃圾收運(yùn)路徑方案

5.結(jié)論

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