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

文/朱虹宇 陳歡歡

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

1.引言

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

2.問題描述

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

3.模型建立

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

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

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

4.模擬退火算法

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

5.算例分析

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

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

表2 結果對比分析

6.結論

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