考慮排隊時間的城市生活垃圾收運路徑優(yōu)化研究

文/朱虹宇 陳歡歡

隨著城市現(xiàn)代化水平的提高，城市生活垃圾的數(shù)量呈現(xiàn)逐年增長的趨勢，同時對于垃圾收運的效率也提出了巨大的要求。在垃圾收運過程中，車輛在中轉站的排隊等待時間占比較多，會影響到垃圾收運的整體效率，因此考慮排隊時間的生活垃圾收運問題顯得十分重要。基于當前的研究現(xiàn)狀，本文考慮車輛在中轉站的排隊等待時間，以垃圾收運成本和車輛等待時間最小為目標函數(shù)，建立數(shù)學模型，并用模擬退火算法對該問題進行求解，驗證本文模型的可行性。

1.引言

城市生活垃圾數(shù)量的增加給垃圾處理帶來了極大挑戰(zhàn)，研究垃圾收運路徑優(yōu)化問題，制定經濟高效的城市生活垃圾收運方案顯得尤為重要[1]。車輛在中轉站的排隊等待時間會影響到整個垃圾收運系統(tǒng)的運行效率，進而影響垃圾收運成本，因此考慮排隊等待時間的城市生活垃圾收運問題十分重要。

2.問題描述

垃圾收運路徑問題可以描述為：中轉站有足夠多的車輛完成垃圾收運，車輛從中轉站出發(fā)，到各個垃圾收集點進行垃圾收運，車輛容量有限制，當達到車輛最大裝載能力后返回中轉站排隊卸載垃圾，然后車輛繼續(xù)返回之前沒有被服務到的垃圾收集點進行服務，直到所有的垃圾收集點都被服務。然后車輛繼續(xù)返回未被服務的垃圾收集點，繼續(xù)上述工作，直到對所有的垃圾收集點都完成收運，車輛返回中轉。建立模型以收運成本和等待時間最小為目標，合理安排收運路線。

3.模型建立

本文模型的參數(shù)說明如下：N為所有點的集合，Nc為垃圾收集點集合，N0表示中轉站，xiju為0-1變量，當車輛u由節(jié)點i行駛至節(jié)j點時，xiju=1，否則，xiju=0。yiu為0-1變量，當車輛u訪問節(jié)點i時，yiu=1，否則yiu=0。U為車輛集合，qu為車輛u的最大載重量，Vu為車輛u的行駛速度，gi為收集點i的垃圾量，C1、C2為車輛的固定成本和單位距離行駛成本，dij為兩個設施點間的距離，tij表示車輛從節(jié)i點到節(jié)點j的行駛時間，tiu為u車對垃圾收集點i的服務時間，Tu為u車在中轉站的等待時間，hu為u車在中轉站的平均作業(yè)時間，wiu為u車到達垃圾收集點i的時間，wou為u車到達垃圾中轉站的時間，β 為所有設施點不滿足時間窗約束的懲罰成本。[Ai，Bi]為收集點i的期望時間窗。本文以垃圾收運成本和等待時間最小為目標建立模型。

obj1：運輸距離產生的成本、固定成本、時間窗懲罰成本

模型中，（4）表示每個垃圾收集點只有一輛車進行服務；（5）表示每個垃圾收集點均需被服務，且只被服務一次；（6）表示車輛容量約束；（7）表示流量平衡；（8）表示每輛車從中轉站出發(fā)，完成垃圾收集后又回到中轉站。對雙目標函數(shù)進行歸一化處理[2]：

4.模擬退火算法

1953年Metropolis最早提出模擬退火算法的思想，Kirkptrick在1983年將模擬退火算法應用在解決組合優(yōu)化的問題中[3]。模擬退火算法是一種依據(jù)固體退火原理，模擬加熱熔化金屬退火過程的智能算法，其以一定的概率選擇劣質解，全局搜索能力強，并且不容易陷入局部最優(yōu)，算法步驟如下：Step1：設置模型參數(shù)；Step2：隨機生成初始解S；Step3：對解進行解碼；Step4：計算目標函數(shù)；Step5：對當前解進行領域搜索，產生新解Snew；Step6：計算Δf=f（Snew）-f（S）；Step7：按Metropolis準則接受新解；若Δf＜0，接受新解，若Δf≥0，則以的概率接受新解；Step8：若滿足終止條件，則輸出最優(yōu)解，否則退火T=T0*q，并返回步驟5。

5.算例分析

現(xiàn)以重慶市南岸區(qū)的垃圾收運路線優(yōu)化為例進行分析，選取49個垃圾收集點和1個垃圾中轉站，收運車輛的最大載重量為6噸，速度為35km/h，運輸成本為3元/km，啟動成本為400元/天。結合現(xiàn)有的相關文獻[4，5]對本文進行參數(shù)設置：初始溫度設置為T0=1000，降溫速率設置為0.95，迭代次數(shù)為maxgen=1000，每個溫度下的迭代次數(shù)設置為Lk=200。

從表2可以看出，本文模型的排隊時間最低為0.0436小時，與不考慮排隊時間的模型運行結果相比，排隊時間減少了8.656小時，其最大改進幅度為99.5%。本文模型的車輛排隊時間占比最小為0.27%，不考慮排隊時間的模型計算出來的車輛排隊時間占比為60.7%，排隊時間占比明顯減少，說明車輛的利用率有所提高。綜合上述分析，本文模型能夠有效減少排隊時間和車輛工作時間，降低排隊時間在整個垃圾收運過程所占比例，提高車輛工作效率，進而提高中轉站整體的運行效率。

表2 結果對比分析

6.結論

本文對生活垃圾收運路徑問題進行研究，重點考慮了車輛在中轉站的排隊時間，以最小化垃圾收運成本和排隊時間為目標建立了數(shù)學模型，數(shù)值算例結果表明，本文所設計的考慮排隊時間模型能更好的降低車輛排隊時間。由于垃圾收運車在中轉站的等待時間減少，進而使車輛資源和人力資源發(fā)揮最大效益，進一步提高垃圾清運效率，為解決垃圾收運的實際問題提供了更多的理論和決策支持，因此考慮排隊時間的垃圾收運模型更具有現(xiàn)實意義和實用價值。