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

（南通大學(xué)，江蘇南通 226019）

0 引言

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

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

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

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

1 村鎮(zhèn)垃圾收運路線優(yōu)化模型

1.1 基本假設(shè)

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

1.2 符號定義

（1）垃圾收集點集合C={1,2,…,n}；（2）頂點集合N=C∪{0,n+1}；（3）車輛集合K={1,2,…,m}；（4）車輛總?cè)萘縌；（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為垃圾收集點符合滿載標準時的容量（滿載標準如下：設(shè)一個垃圾桶的實際總?cè)萘繛?40L，一個垃圾收集點共放置十個垃圾桶。①當T=1 時，qj=2 000，即垃圾收集點的垃圾達到2 000L 為滿載；②當T=0 時，qj=1 500，即垃圾收集點的垃圾達到1 500L 即為滿載）；

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

（1）目標函數(shù)

（2）約束條件

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

2 實例研究

2.1 研究區(qū)域概況

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

圖1 江蘇省新沂市合溝鎮(zhèn)地圖

圖2 鎮(zhèn)區(qū)環(huán)衛(wèi)工程規(guī)劃圖

2.2 信息采集

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

表1 垃圾中轉(zhuǎn)站與垃圾收集點信息

經(jīng)數(shù)據(jù)調(diào)查，將垃圾運輸車的滿載容量設(shè)置為10 000L，即Q=10 000L。根據(jù)檢測器檢測到垃圾收集點已滿的狀態(tài)后將信號發(fā)送給后臺，后臺經(jīng)過算法計算出最優(yōu)路徑，垃圾運輸車按照最優(yōu)路線及時予以清理，保證高效清運。

2.3 算法求解

通過Matlab 實現(xiàn)禁忌搜索算法和模擬退火算法，并對兩種結(jié)果進行分析比較。首先假設(shè)20 個垃圾收集點都是已滿的狀態(tài)，利用Matlab 實現(xiàn)禁忌搜索算法。在晴天的情況下，對20 個垃圾收集點和1 個垃圾中轉(zhuǎn)站點求解出5 條最優(yōu)路徑，如圖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 條最優(yōu)路徑，如圖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 晴天狀態(tài)下禁忌搜索算法的計算結(jié)果

圖4 雨天狀態(tài)下禁忌搜索算法的計算結(jié)果

同理，假設(shè)20 個垃圾收集點都是已滿的狀態(tài)，利用Matlab 實現(xiàn)模擬退火算法。在晴天的情況下，對20 個垃圾收集點和1個垃圾中轉(zhuǎn)站點求解出5 條最優(yōu)路徑，如圖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 條最優(yōu)路徑，如圖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 晴天狀態(tài)下模擬退火算法的計算結(jié)果

圖6 雨天狀態(tài)下模擬退火算法的計算結(jié)果

兩種不同方法對兩種不同天氣狀態(tài)進行計算，計算結(jié)果的比較如表2 所示?？梢园l(fā)現(xiàn)模擬退火算法的計算結(jié)果明顯優(yōu)于禁忌搜索算法，從計算時長來看，模擬退火算法的計算時長在0.5 秒左右，而禁忌搜索算法的計算時長均超出2 秒。

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