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

文/朱虹宇 陳歡歡

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

1.引言

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

2.問(wèn)題描述

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

3.模型建立

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

obj1：運(yùn)輸距離產(chǎn)生的成本、固定成本、時(shí)間窗懲罰成本

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

4.模擬退火算法

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

5.算例分析

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

從表2可以看出，本文模型的排隊(duì)時(shí)間最低為0.0436小時(shí)，與不考慮排隊(duì)時(shí)間的模型運(yùn)行結(jié)果相比，排隊(duì)時(shí)間減少了8.656小時(shí)，其最大改進(jìn)幅度為99.5%。本文模型的車輛排隊(duì)時(shí)間占比最小為0.27%，不考慮排隊(duì)時(shí)間的模型計(jì)算出來(lái)的車輛排隊(duì)時(shí)間占比為60.7%，排隊(duì)時(shí)間占比明顯減少，說(shuō)明車輛的利用率有所提高。綜合上述分析，本文模型能夠有效減少排隊(duì)時(shí)間和車輛工作時(shí)間，降低排隊(duì)時(shí)間在整個(gè)垃圾收運(yùn)過(guò)程所占比例，提高車輛工作效率，進(jìn)而提高中轉(zhuǎn)站整體的運(yùn)行效率。

表2 結(jié)果對(duì)比分析

6.結(jié)論

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