生活垃圾收集階段車輛路徑問題研究

文/張燕紅

1.引言

隨著城市規模的不斷擴大和經濟水平的逐步提高，我國生活垃圾清運量增長迅速[1]。在國內外學者的研究中，有諸多算法[2-5]可用于解決垃圾收集階段的車輛路徑優化問題。本文通過比較掃描算法和遺傳算法的計算效果，從兩者中選擇較優的一方，作為將來在研究垃圾收集階段車輛路徑問題的求解算法。其中，本文的優化區域共計10個轉運站，它們負責服務多個收集點。求解時，采用兩階段算法，先使用整數規劃將收集點指派給轉運站，再分別使用掃描算法和遺傳算法計算其車輛的運輸總路程。

2.掃描算法

將掃描算法應用于本文的城市生活垃圾收運問題，根據調研得知，運輸車輛通常從一次轉運站出發訪問各收集點，則對應的起始點為各一次轉運站，約束條件是垃圾收集車車輛的限重，滿足約束條件的收集點則加入當前組中，直到垃圾收集車輛載重達到限定值后，建立一個新組，只有當所有的收集點都歸入相應組時算法停止。這樣，每一個組便形成了一條大致路徑，即垃圾收集車輛可以從一次轉運站出發，按順序經過每組中的各收集點，最后返回一次轉運站。

3.遺傳算法

將遺傳算法運用到本文所研究的垃圾收集階段的收運路徑問題中，以200個收集點，10個轉運站為例，進行算法構造的處理細節如下：（1）編碼方式的設計。本文采用實數編碼方法，垃圾收集點用序號1~200表示，垃圾一次轉運站用序號201~210表示，且序號具有唯一性。（2）初始群體的確定。完成上述編碼及其他相關數據設置后，接著根據一次轉運站和垃圾收集點的數量、地理位置以及垃圾收運能力或垃圾產生量等因素，使用整數規劃理論求解出各個轉運站服務的收集點。而后，將各轉運站服務的收集點序號隨機排列生成個體，且每個個體不出現相同的自然數。本文的群體規模確定為20。（3）適應度評估。個體的適應度是用來評估其方案優劣程度的，此處的目標函數值是運輸路程長度，當目標函數值越小時，它的適應度反而越大。因此，本文的適應度函數F（x）與目標函數f（x）的關系為：maxF（x）=min（-f（w））。（4）選擇操作。將種群中的多個個體根據其從大到小的適應度進行排名，選出排名靠前的20名留下作為下一次迭代的父代，同時，將較劣的路徑方案舍去。其中排名第一的個體在性能上是最佳的。（5）交叉操作。對于之前已通過選擇操作才生成的新種群，此處采用0.8的交叉概率，使用類似OX法的一種交叉方法，隨機在父代個體中選擇交配區域[37]。（6）變異操作。自然界中，變異是后代基因根據小概率改動的變化。在遺傳算法中，為模擬自然界的變異故將種群突變的情況設置為小概率事件，可能會使群體中小部分個體發生改變。本文中取0.1的突變概率，即對于每一個父代（染色體），生成1個0~1之間的隨機數，若該數小于突變概率，則父代執行變異操作，且每次改變其位值的基因數只有兩個，變異時基因換位次數取1。（7）終止判斷。本文選取的終止準則為迭代次數限制，當迭代次數未達到設定代數時，運算繼續循環；反之，則運算停止。

4.結果分析

根據上述提到的掃描算法和遺傳算法運用到垃圾收運問題的具體步驟，使用專業求解軟件編程分別計算重慶市主城區10個一次轉運站各自的垃圾收運總路程，得到的結果見表1所示。

表1 掃描算法和遺傳算法計算結果比較

從表1可以看出，在掃描算法的計算結果中，最小的是13.71km，最大的是795.37km；在遺傳算法的計算結果中，最小的是11.1km，最大的是656.3km。其中第一個轉運站服務的收集點較少，因而使用兩種算法計算得出的運行總路程均較小；而第七個轉運站服務的收集點較多且部分收集點位于面積較廣的風景區，因此其運行總路程對于其他幾個轉運站而言最大。同時，可以發現對于一次轉運站至收集點的垃圾收運工作路徑安排，采用遺傳算法計算得出的運輸總路程相較于掃描算法計算得出的運輸總路程而言更少，且大多數轉運站的優化比例超過10%，其中有兩個轉運站的優化比例在20%左右，優化效果較好。

5.結論

綜上所述，采用遺傳算法能夠有效解決垃圾收運路徑問題，減少垃圾收運車輛運輸總路程，從而降低在途運輸時間，從而為緩解道路交通壓力、助力“生態文明城市”建設貢獻力量。

引用出處

[1]中華人民共和國國家統計局.中國統計年鑒[M].北京:中國統計出版社,2015-2021.

[2]趙紅霞,劉高森,李愈.基于隨機游走的分類垃圾回收最優路徑規劃[J].交通運輸工程與信息學報,2018,16(3):103-108.

[3]Nowakowski P,Szwarc K,Boryczka U.Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms[J].Transportation Research Part D:Transport and Environment,2018,63:1-22.

[4]張玉州,張子為.基于合作協同進化的多回收站點垃圾收運問題求解[J].中國科學技術大學學報,2020,50(5):695-704.

[5]朱明華,范秀敏,劉炳凱,等.上海浦東新區城市生活垃圾收運路線優化研究[J].資源科學,2009,31(9):1612-1618.