考慮容量約束的村鎮垃圾收運路線優化方法研究

李洋潔，毛 霖，周秋菊，鄒可瑩，高 華，林思聰

（南通大學，江蘇南通 226019）

0 引言

近年來，我國村鎮垃圾年產量已超一億噸，并呈逐年上升趨勢，在鄉村振興戰略的背景下，人們對生活環境質量的要求越來越高，使得如何實現對垃圾處理系統的統籌管理已成為當下研究的一個熱點。而垃圾收運是垃圾處理系統的重要組成部分，垃圾收運通常包括收集、運輸和中轉三個部分。其中，垃圾收集和運輸的費用占整個處理系統費用的70%～80%[1]。因此，優化垃圾收運路線對降低垃圾運輸成本、降低燃料消耗、減少垃圾對生活環境的污染具有重要的現實意義。

村鎮垃圾收運路線優化問題可以看作經典的VRP（車輛路徑規劃問題），國內針對VRP 問題開展了大量的研究。陳玉光等[2]以廣東乳液公司的產品配送為例，建立了基于準時送貨與最小化耗油量的配送車輛路徑模型，通過改進的粒子群算法，進行路徑優化。朱明華等[1]以浦東南碼頭街道部分區域為例，以總的垃圾收運距離最短為優化目標并建立數學模型，通過掃描算法和分枝限界法相結合的求解方法進行求解，得到垃圾量分配運輸的最優方案。除了城區生活垃圾收運路線優化研究外，還有少量研究集中在村鎮垃圾方面，如陳海濱等[3]以蒙城縣岳坊鎮為例，綜合考慮垃圾收運過程的運輸距離、路況、環境污染等因素，利用層次分析法確定了不同級別道路的綜合權重，修正后得到綜合運輸距離。以節約綜合運輸距離為目標，使用節約法對收運路線進行優化。

針對垃圾配送方面的VRP 問題，國外的一些學者也進行了相關研究。Masoud Rabbani 等[4]考慮時間窗口之外的懲罰成本，將早于指定時間到達客戶點的懲罰成本定義為運營成本，并嘗試使用TransCAD 軟件來計算問題的最優解，從而減少垃圾收集時間和車隊規模。Assaf 等[5]以巴勒斯坦納布盧斯南部為例，通過遺傳算法實現VRP 問題，以求解出垃圾運輸車總行駛距離以及成本最小化的最佳路線。Puspita F M 等[6]針對帕倫邦卡利多尼街道的垃圾運輸車路線安排建立了帶時間窗和截止期的魯棒對口開放容量車輛路徑問題模型，使用LINGO13.0 實現模型，以使運輸距離和時間最小化。

通過上述相關研究的描述，可以發現，大多數是針對城市生活垃圾收運路線問題，很少有相關村鎮垃圾收運路線方面的研究。本文針對村鎮垃圾收運路線優化問題提出相關求解方法。首先，將村鎮垃圾收運線路優化問題轉化為容量約束車輛路徑問題，并考慮到天氣因素，構建混合整數規劃模型，再通過禁忌搜索算法和模擬退火算法進行求解，從而彌補傳統清運系統的不足，實現低成本高效率的運營模式。

1 村鎮垃圾收運路線優化模型

1.1 基本假設

為了簡化問題的復雜性，便于根據垃圾收運的實際情況建立模型。做出以下假設：（1）區域內只有一個中轉站；（2）垃圾收集點的數量、位置及垃圾量是已知確定的；（3）垃圾收運系統只有一種車型，載重有限，且每輛車都從中轉站出發，最后返回中轉站；（4）每一個收集點只能訪問一次，即一次進入與一次離開。

1.2 符號定義

（1）垃圾收集點集合C={1,2,…,n}；（2）頂點集合N=C∪{0,n+1}；（3）車輛集合K={1,2,…,m}；（4）車輛總容量Q；（5）路徑成本（各個垃圾收集點之間的距離）cij；（6）yik表示是否將垃圾收集點i 指派給車輛k，為0～1 變量，若是則為1，反之為0；（7）表示車輛k 從垃圾收集點i 到垃圾收集點j 的弧是否被選擇，為0～1 變量，若是則為1，反之為0；（8）T表示天氣狀況，為0～1 變量，若是晴天則為1，若是雨天則為0；（9）qj為垃圾收集點符合滿載標準時的容量（滿載標準如下：設一個垃圾桶的實際總容量為240L，一個垃圾收集點共放置十個垃圾桶。①當T=1 時，qj=2 000，即垃圾收集點的垃圾達到2 000L 為滿載；②當T=0 時，qj=1 500，即垃圾收集點的垃圾達到1 500L 即為滿載）；

1.3 數學模型

（1）目標函數

（2）約束條件

公式（1）求解總的出行距離最小；公式（2）保證每個垃圾收集點必須被一輛車服務；公式（3）保證每個垃圾收集點進入一次并離開一次，且被同一輛車服務；公式（4）為容量約束，即每輛車的執行路徑上容量不能超過限制；公式（5）保證每輛車的執行路徑上不能形成子回路。

2 實例研究

2.1 研究區域概況

本文的對象實例合溝鎮位于江蘇省新沂市，全鎮下轄20 個行政村，人口約6 萬人。如圖1、圖2 所示，鎮區有垃圾中轉站1 座，各村均設有1 個垃圾收集點，各村之間通有村道和鄉道。各村收集點的垃圾每天需要收運至垃圾中轉站中轉，鎮區共有6 輛垃圾運輸車、132 名工人（包括司機）。每年鎮區的環衛工程大約共花費320 萬元。

圖1 江蘇省新沂市合溝鎮地圖

圖2 鎮區環衛工程規劃圖

2.2 信息采集

基于研究區概況，利用AutoCAD 軟件，對江蘇省新沂市合溝鎮的1 個垃圾中轉站以及20 個垃圾收集點進行標注彼此的相對位置，以垃圾中轉站（合溝鎮）為原點，進行繪制垃圾中轉站以及各垃圾收集點的坐標，各點坐標的信息如表1 所示。

表1 垃圾中轉站與垃圾收集點信息

經數據調查，將垃圾運輸車的滿載容量設置為10 000L，即Q=10 000L。根據檢測器檢測到垃圾收集點已滿的狀態后將信號發送給后臺，后臺經過算法計算出最優路徑，垃圾運輸車按照最優路線及時予以清理，保證高效清運。

2.3 算法求解

通過Matlab 實現禁忌搜索算法和模擬退火算法，并對兩種結果進行分析比較。首先假設20 個垃圾收集點都是已滿的狀態，利用Matlab 實現禁忌搜索算法。在晴天的情況下，對20 個垃圾收集點和1 個垃圾中轉站點求解出5 條最優路徑，如圖3 所示，分別為1→9→21→20→19→1，1→15→16→17→18→1，1→6→3→2→8→1，1→11→12→10→14→1，1→7→4→5→13→1。在雨天的情況下，求解出4 條最優路徑，如圖4 所示，分別為1→4→8→2→3→6→1，1→20→13→5→7→19→1，1→18→17→15→9→21→1，1→16→14→10→12→11→1。

圖3 晴天狀態下禁忌搜索算法的計算結果

圖4 雨天狀態下禁忌搜索算法的計算結果

同理，假設20 個垃圾收集點都是已滿的狀態，利用Matlab 實現模擬退火算法。在晴天的情況下，對20 個垃圾收集點和1個垃圾中轉站點求解出5 條最優路徑，如圖5 所示，分別為1→4→3→2→8→1，1→5→13→9→21→1，1→20→19→6→7→1，1→11→12→10→14→1，1→15→18→17→16→1。在雨天的情況下，求解出4 條最優路徑，如圖6 所示，分別為1→4→3→2→8→5→1，1→15→18→17→16→21→1，1→11→12→10→14→9→1，1→13→7→6→19→20→1。

圖5 晴天狀態下模擬退火算法的計算結果

圖6 雨天狀態下模擬退火算法的計算結果

兩種不同方法對兩種不同天氣狀態進行計算，計算結果的比較如表2 所示。可以發現模擬退火算法的計算結果明顯優于禁忌搜索算法，從計算時長來看，模擬退火算法的計算時長在0.5 秒左右，而禁忌搜索算法的計算時長均超出2 秒。

表2 實例的禁忌搜索算法和模擬退火算法計算結果的比較