基于智能垃圾箱回收閾值的回收車輛路徑問(wèn)題

文/孟亞雷

本文針對(duì)智能回收車輛路徑問(wèn)題，考慮了智能垃圾箱回收閾值對(duì)回收公司運(yùn)營(yíng)成本的影響，構(gòu)建了回收公司運(yùn)營(yíng)成本最小化的優(yōu)化模型，并運(yùn)用PSO粒子群算法進(jìn)行車輛路徑優(yōu)化，并結(jié)合實(shí)例對(duì)模型和算法的有效性進(jìn)行了驗(yàn)證。結(jié)果表明，回收公司通過(guò)確定合理的垃圾箱回收閾值進(jìn)行車輛優(yōu)化調(diào)度，可以有效降低回收運(yùn)營(yíng)成本，進(jìn)而為智慧城市回收物流網(wǎng)絡(luò)建設(shè)提供了理論借鑒。

1.問(wèn)題描述

隨著城鎮(zhèn)化進(jìn)程的加快與居民消費(fèi)水平的提高，居民生活垃圾與日俱增，“垃圾圍城”現(xiàn)象普遍存在，并成為新一輪城鎮(zhèn)化發(fā)展的制約因素[1]。近年來(lái)，國(guó)家大力推動(dòng)城市環(huán)衛(wèi)系統(tǒng)與再生資源系統(tǒng)的兩網(wǎng)融合，以減少資源消耗，降低環(huán)境污染。一種基于物聯(lián)網(wǎng)技術(shù)的智能垃圾箱應(yīng)運(yùn)而生[2]。智能垃圾箱可以實(shí)施監(jiān)測(cè)箱體內(nèi)廢棄物的填充狀態(tài)，當(dāng)達(dá)到一定的閾值后，回收公司派遣車輛進(jìn)行清理。而不同的回收閾值將導(dǎo)致待清理的智能垃圾箱數(shù)量與廢棄物回收量有所差異，對(duì)車輛調(diào)度與路徑優(yōu)化提出了更高的要求[3]。在車輛數(shù)量一定的情況下，為了提高回收效率并節(jié)約回收運(yùn)輸成本，需要綜合考慮垃圾箱回收閾值對(duì)車輛調(diào)度的影響，進(jìn)行合理的回收車輛路徑優(yōu)化問(wèn)題研究。圖1展示了基于智能垃圾箱回收閾值的回收車輛路徑優(yōu)化前后對(duì)比。

圖1 基于智能垃圾箱回收閾值的回收車輛路徑優(yōu)化前后對(duì)比

由圖1可知，圖1（a）表示傳統(tǒng)回收路徑下，回收公司統(tǒng)一清理服務(wù)范圍內(nèi)的智能垃圾箱，由于部分垃圾箱內(nèi)廢棄物數(shù)量較少，回收公司派遣車輛進(jìn)行清理，使得回收效率低下，且回收網(wǎng)絡(luò)中存在長(zhǎng)距離運(yùn)輸與交叉運(yùn)輸?shù)痊F(xiàn)象，增加了回收運(yùn)輸成本。圖1（b）表示基于智能垃圾箱回收閾值的回收路徑，回收公司預(yù)先設(shè)定合理的回收閾值，當(dāng)智能垃圾箱內(nèi)廢棄物填充狀態(tài)達(dá)到回收閾值后，回收公司派遣車輛進(jìn)行回收，并結(jié)合智能垃圾箱的分布情況與達(dá)到回收閾值的時(shí)間進(jìn)行合理的路徑優(yōu)化，節(jié)約了廢棄物運(yùn)輸成本，并提高了回收效率。

2.模型建立

基于智能垃圾箱回收閾值的回收車輛路徑問(wèn)題可表示為G=（N0，A）的無(wú)向圖，N0為圖中所有回收節(jié)點(diǎn)的集合，包括垃圾箱N與回收公司0，A為圖中任意節(jié)點(diǎn)間弧的集合，xijv為0-1變量，當(dāng)車輛v由節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j時(shí)，xijv=1，否則，xijv=0。Uv為車輛v服務(wù)的智能垃圾箱的集合，V為所有車輛的集合，Dij為回收節(jié)點(diǎn)i與回收節(jié)點(diǎn)j之間的距離，fv為單位距離油價(jià)，o為回

收公司預(yù)先設(shè)定的回收閾值，mj表示智能垃圾箱的容量，qv表示車輛容量，L為車輛行駛最大距離，Q為回收公司處理能力，|Uv|為車輛v服務(wù)的智能垃圾箱的數(shù)量，[ej，lj]為智能垃圾箱回收時(shí)間窗，ajv為車輛到達(dá)節(jié)點(diǎn)j的時(shí)間，div為車輛離開(kāi)節(jié)點(diǎn)i的時(shí)間，tijv為車輛由節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j的運(yùn)輸時(shí)間，λe為車輛早于垃圾箱時(shí)間窗到達(dá)回收點(diǎn)的單位時(shí)間懲罰成本，λd為車輛晚于垃圾箱時(shí)間窗到達(dá)回收點(diǎn)的單位時(shí)間懲罰成本，kv為車輛租賃成本，δv為車輛維修成本，ρ 為回收品固定處理成本，σ 為回收品變動(dòng)處理成本，wjv為車輛在節(jié)點(diǎn)j的等待時(shí)間，W 為無(wú)窮大常數(shù)。本文以回收公司運(yùn)營(yíng)成本最小化為目標(biāo)，建立基于智能垃圾箱回收閾值的回收路徑優(yōu)化模型，如式（1）所示。

式（4）表示任一智能垃圾箱只能由一輛車進(jìn)行服務(wù)，式（5）為流量守恒約束，式（6）為車輛容量約束，式（7）為車輛行駛距離約束，式（8）為回收公司處理能力約束，式（9）表示消除了車輛行駛子回路，式（10）-式（12）為車輛到達(dá)垃圾箱所處回收點(diǎn)的時(shí)間約束，式（13）為變量約束。

3.PSO粒子群算法

車輛路徑問(wèn)題是由Dantzig和Ramser于1959年首次提出，屬于典型的NP-hard問(wèn)題，學(xué)者們傾向于采用啟發(fā)式算法進(jìn)行求解。PSO粒子群算法是模擬鳥(niǎo)類捕食行為的一種智能優(yōu)化算法，經(jīng)常被用于求解路徑優(yōu)化問(wèn)題[4]。粒子群算法搜索過(guò)程中，每一個(gè)粒子都表示一個(gè)優(yōu)化解，擁有速度和位置兩個(gè)屬性。其中，離子飛行速度根據(jù)粒子搜索過(guò)程中的最優(yōu)解（局部最優(yōu)）和種群搜索過(guò)程中的最優(yōu)解（全局最優(yōu)）進(jìn)行動(dòng)態(tài)調(diào)整。粒子速度與位置更新公式如下所示。

式（14）為粒子速度更新公式，式（15）為粒子位置更新公式。式（14）與式（15）中n=1，2，3，...，N；N表示種群中粒子的個(gè)數(shù)；表示表示粒子的慣性權(quán)重，是0-1之間的隨機(jī)數(shù)；vn，i表示在第i代搜索過(guò)程中粒子n的速度；c1與c2表示學(xué)習(xí)因子，一般c1=c2=2，r1與r2表示0-1之間的隨機(jī)數(shù)；pbest表示粒子搜索過(guò)程中的最優(yōu)解（局部最優(yōu)），gbest表示種群搜索過(guò)程中的最優(yōu)解（全局最優(yōu)）；xn，i表示粒子在第i代搜索過(guò)程中的位置。粒子群算法具體實(shí)施步驟如表1所示。

表1 粒子群算法步驟

4.實(shí)例分析

以智能回收公司A與其服務(wù)范圍內(nèi)100個(gè)智能垃圾箱為例，研究基于智能垃圾箱回收閾值的回收路徑優(yōu)化問(wèn)題。為了提高回收效率，提高智能回收服務(wù)水平，回收公司A需要預(yù)先設(shè)置合理的回收閾值o，并運(yùn)用PSO粒子群算法進(jìn)行合理的車輛調(diào)度。根據(jù)已有文獻(xiàn)[5，6]與多次實(shí)驗(yàn)計(jì)算基礎(chǔ)上，本文的算法參數(shù)設(shè)置為：種群規(guī)模popsize=100，算法最大迭代次數(shù)i_max=200，回收閾值o=80%，智能垃圾箱容量mj=50kg，回收車輛容量qv=500kg，單位距離油價(jià)fv=0.8元，回收公司處理能力Q=10000kg，單位時(shí)間懲罰成本λe=15，λd=20，車輛租賃成本kv=100元，車輛維修成本元δv=50，回收品固定處理成本ρ=1000元，回收品變動(dòng)處理成本σ=0.15元。以回收公司運(yùn)營(yíng)成本最小化為目標(biāo)，結(jié)合智能垃圾箱回收閾值對(duì)車輛路徑進(jìn)行優(yōu)化，基于智能垃圾箱回收閾值的回收路徑優(yōu)化前后各項(xiàng)指標(biāo)對(duì)比如表2所示。

表2 基于智能垃圾箱回收閾值的回收路徑優(yōu)化對(duì)比

由表可知，經(jīng)過(guò)回收路徑優(yōu)化后，回收公司運(yùn)營(yíng)成本有效降低了33.80%，車輛使用數(shù)降低了3輛。其中，違反時(shí)間窗懲罰成本降低了78.39%，車輛租賃成本與維修成本均降低了37.50%，運(yùn)輸成本降低了36.94%。此外，為了進(jìn)一步確定合理的回收閾值，本文探討了不同回收閾值下滿足回收條件的垃圾箱數(shù)量、回收品數(shù)量、車輛使用數(shù)與回收公司運(yùn)營(yíng)成本的變化情況，如表3所示。

表3 不同回收閾值下指標(biāo)對(duì)比

由表可知，隨著回收閾值由100%降低到70%，需要服務(wù)的智能垃圾箱數(shù)量逐漸增多，有32個(gè)增加值70個(gè)，收集到的回收品數(shù)量由1600kg增加值2569kg，回收車輛使用數(shù)由4輛增加值6輛。此外，本文通過(guò)對(duì)比不同回收閾值下回收車輛的平均裝載率來(lái)確定最優(yōu)的回收閾值。不同回收閾值下回收車輛的平均裝載率、車輛使用數(shù)與回收公司運(yùn)營(yíng)成本的對(duì)比圖如圖2所示。

圖2 不同回收閾值下指標(biāo)對(duì)比

由表3和圖2可知，當(dāng)回收閾值為80%時(shí)，車輛平均裝載率達(dá)到最大值，為90.60%，回收公司運(yùn)營(yíng)成本達(dá)到了最小值，為3491元；相比于回收閾值分別為100%、95%、90%和70%的場(chǎng)景，運(yùn)營(yíng)成本分別降低了23.76%、13.14%、11.87%和9.87%。綜上所述，回收公司預(yù)先確定回收閾值為80%時(shí)，可以獲得最低的運(yùn)營(yíng)成本。

5.結(jié)論

本文研究了基于智能垃圾箱回收閾值的回收車輛路徑問(wèn)題，考慮了當(dāng)回收公司預(yù)先確定合理的回收閾值進(jìn)行回收服務(wù)時(shí)運(yùn)營(yíng)成本的變化情況，建立了回收公司運(yùn)營(yíng)成本最小化的成本模型，并運(yùn)用PSO粒子群算法進(jìn)行求解。以智能回收公司A為例，對(duì)其服務(wù)范圍內(nèi)智能垃圾箱的回收路徑進(jìn)行優(yōu)化，并對(duì)模型與算法的有效性進(jìn)行了驗(yàn)證。研究結(jié)果表明，經(jīng)過(guò)回收路徑優(yōu)化后，回收公司運(yùn)營(yíng)成本有效降低了33.80%，車輛使用數(shù)降低了3輛。不同回收閾值下優(yōu)化目標(biāo)的對(duì)比結(jié)果表明，相比與回收閾值為100%、95%、90%和70%的場(chǎng)景，回收公司預(yù)先確定80%為回收閾值時(shí)，車輛平均裝載率最高，為90.60%，回收公司運(yùn)營(yíng)成本最低，為3491元。本文豐富了智能回收優(yōu)化調(diào)度理論，為研究逆向物流車輛路徑問(wèn)題提供了新的研究思路，進(jìn)而為智慧城市回收網(wǎng)絡(luò)優(yōu)化建設(shè)提供了方法借鑒。

引用出處

[1]林晶晶,毛雅婧,林宗平.“互聯(lián)網(wǎng)+再生資源回收”模式推進(jìn)機(jī)制的三方演化博弈研究[J].生態(tài)經(jīng)濟(jì),2022,38(03):202-209.

[2]丁夢(mèng)思,王琰,潘可可,陳學(xué)進(jìn),李桂榮.智能識(shí)別分類垃圾箱的認(rèn)識(shí)與設(shè)計(jì)[J].科技創(chuàng)新與應(yīng)用,2022,12(14):78-81.

[3]Hannan,M.A.,Akhtar,M.,Begum,R.A.,et al.Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm[J].Waste Management,2018,71:31-41.

[4]楊景明,穆曉偉,車海軍,呼子宇,侯宇浩.多策略改進(jìn)的多目標(biāo)粒子群優(yōu)化算法[J].控制與決策,2017,32(03):435-442.

[5]卿東升,鄧巧玲,李建軍,劉帥,劉鑫,曾素平.基于粒子群算法的滿載需求可拆分車輛路徑規(guī)劃[J].控制與決策,2021,36(06):1397-1406.

[6]郭森,秦貴和,張晉東,于赫,盧政宇,于佳欣.多目標(biāo)車輛路徑問(wèn)題的粒子群優(yōu)化算法研究[J].西安交通大學(xué)學(xué)報(bào),2016,50(09):97-104.