面向路網(wǎng)結(jié)構(gòu)的垃圾分類車輛調(diào)度研究

楊春霞,趙 霞,王 皓,王曉軍

(太原科技大學(xué) 交通與物流學(xué)院,太原 030024)

據(jù)統(tǒng)計,2020年全國已有237個城市啟動垃圾分類,將垃圾分為濕垃圾、可回收垃圾、干垃圾和有害垃圾四類。其中不少地方的中間垃圾收運環(huán)節(jié)仍混裝收運,該環(huán)節(jié)費用占垃圾處理系統(tǒng)總費用60%～80%[1],因此,對垃圾分類車輛調(diào)度進行研究,能解決城市垃圾分類實施中的短板,具有現(xiàn)實意義。

目前,根據(jù)約束條件和優(yōu)化目標(biāo)的不同,國內(nèi)外現(xiàn)有研究可以分為以下幾大類:(1)帶容量約束[2]的收運調(diào)度問題,如丁偉[3]以伊斯坦布爾城市為例,建立了有車輛容量約束的車輛路徑問題模型,并設(shè)計了相應(yīng)的遺傳算法;李佳書[4]通過研究滿載與非滿載結(jié)合的車輛調(diào)度問題,構(gòu)建了一種較為完善的廢棄物回收網(wǎng)絡(luò)。(2)多目標(biāo)優(yōu)化的收運調(diào)度問題,如趙今越等[5]以最小化運輸成本和車輛固定成本為目標(biāo)建立了數(shù)學(xué)模型; Shan-Huen Huang等[6]將廢物收集問題看作為一個集合到達和車輛路徑問題,提出了一種雙層優(yōu)化模型。(3)帶時間窗約束[7]的收運調(diào)度問題,如Benjamin等[8]考慮處置設(shè)施時間窗,對公共廢物收集問題進行了回收路徑的優(yōu)化;李珍萍等[9]對同一顧客多種需求的服務(wù)時間具有固定先后順序的車輛路徑問題進行優(yōu)化。

垃圾分類背景下,傳統(tǒng)車輛調(diào)度問題的解決辦法已不太適用。垃圾車不僅存在多種車型,調(diào)度模式也發(fā)生了變化。于偉[10]研究了中轉(zhuǎn)站優(yōu)化方法及其生活垃圾收運模式;王晨頔[11]在分類基礎(chǔ)上,對生活垃圾清運車輛進行了優(yōu)化研究。上述研究在建模時均將垃圾收集點、中轉(zhuǎn)站和處理廠等當(dāng)成節(jié)點,但節(jié)點與節(jié)點間能直接連接且路徑唯一,沒有考慮到實際路網(wǎng)結(jié)構(gòu)及節(jié)點間可能存在多路徑的情況。為此,本文首先基于路網(wǎng)結(jié)構(gòu),引入虛擬的網(wǎng)絡(luò)節(jié)點,將垃圾清運過程中與垃圾投放點相關(guān)的路口作為節(jié)點一起進行車輛的路線規(guī)劃,更準(zhǔn)確地進行車輛調(diào)度,給出垃圾分類調(diào)度優(yōu)化模型;其次,在算法方面遺傳算法[12]對于復(fù)雜多目標(biāo)優(yōu)化問題有較好的求解適應(yīng)性;粒子群算法在大規(guī)模連續(xù)優(yōu)化問題上有較好的適應(yīng)性[13]。分別采用兩種算法對模型進行求解,以提供優(yōu)化性更好的調(diào)度路徑。

1 問題描述

本文中路網(wǎng)被抽象為由垃圾收集點、處理中心、停車場以及實際路段共同組成的無向圖,垃圾收集點之間若有直線相連則表明可以直接到達,直線段的長度為兩收集點之間的實際距離;若無直線相連接,則表明兩收集點要通過路網(wǎng)節(jié)點才能相連接,此時不能將兩點之間的直線距離作為車輛調(diào)度的實際距離。

將處理中心、垃圾投放節(jié)點以及虛擬的網(wǎng)絡(luò)節(jié)點簡化為節(jié)點,引入路網(wǎng)節(jié)點之后實際路網(wǎng)的抽象結(jié)構(gòu)圖如圖1所示。

圖1 實際路網(wǎng)抽象結(jié)構(gòu)圖Fig.1 Abstract structure diagram of actual road network

在圖1中,W表示垃圾處理中心,a-p表示垃圾投放節(jié)點,1-13表示路網(wǎng)節(jié)點,節(jié)點之間的線段表示道路實際路網(wǎng)結(jié)構(gòu)。

2 垃圾分類收運調(diào)度優(yōu)化模型

2.1 模型假設(shè)

以垃圾分類收運模式為基礎(chǔ),將垃圾車調(diào)度問題轉(zhuǎn)化為多處理中心、多車輛、多車型、多路徑、有容量約束且?guī)в袝r間窗的車輛調(diào)度問題。

主要假設(shè)條件如下:(1)將收集區(qū)域內(nèi)的每一個社區(qū)視為一個垃圾投放節(jié)點,每日垃圾產(chǎn)生量已知,且濕垃圾、可回收垃圾和干垃圾按一定比例投放;(2)以實際路網(wǎng)為基礎(chǔ)設(shè)置垃圾投放點、處理廠、停車場等節(jié)點位置。引入虛擬網(wǎng)絡(luò)節(jié)點,其對應(yīng)垃圾產(chǎn)生量為0;(3)設(shè)有6噸箱式車、6噸壓縮車、9噸壓縮車三種車型,每種車型數(shù)量充足,其中箱式車裝可回收物和干垃圾,壓縮車裝濕垃圾;(4)清運車輛的工作時間與垃圾投放點的開放時間相一致,在時間窗范圍內(nèi),車輛可以多次往返于垃圾投放點進行清運工作;(5)清運車輛在到達處理場進行卸料作業(yè)時,實行先到先服務(wù)的原則;(6)單個清運車輛可服務(wù)于多個垃圾投放節(jié)點,即單個垃圾投放點的產(chǎn)生量不大于服務(wù)于該點的車輛載重限制;(7)所有車輛從停車場出發(fā)在進行多次清運工作后最終必須返回停車場。

2.2 基本參數(shù)

收運網(wǎng)絡(luò)用有向圖G={VE}表示收運網(wǎng)絡(luò),其中V表示模型所涉及到的投放點集合,收運節(jié)點i,j∈V;W為投放點集合,qi表示垃圾投放點i的生活垃圾清運需求量;[ai,bi]為投放點i的時間窗;P表示停車場集合,p為停車場節(jié)點;F為處理廠集合;C表示車輛集合,對車輛編號c∈C,φc為其固定成本,Lc為行駛距離;K表示車次集合,車次編號k∈K;mk為車次k的最大載重限制;yik為車次k在收運節(jié)點i收集的垃圾量;dij表示垃圾投放節(jié)點i,j之間的距離;vij表示垃圾投放節(jié)點i到節(jié)點j的行駛時間;α表示垃圾投放節(jié)點之間的單位運輸成本;tjk表示車次k在處理廠j內(nèi)的排隊等待時間;h表示車輛在處理場卸料作業(yè)的時間;σ為擁堵系數(shù);ε表示在時間窗允許的范圍外所需要的懲罰成本;θ表示清運車輛作業(yè)時的單位等待時間成本;τi表示在垃圾投放點i進行收集作業(yè)的時間;τj表示在處理場j進行卸料作業(yè)的時間;wpk為車次k到達停車場p的時間;wik車次k到達垃圾投放節(jié)點i的時間;S1、E1分別表示垃圾清運車輛工作的開始和結(jié)束時間。

定義以下決策變量:Xik表示車次k是否前往垃圾投放點i進行收運作業(yè),是則為1,否則為0;Yik表示車次k是否在清運時間窗范圍內(nèi)到達垃圾投放點i,是則取1,否則為0;xijk表示車次k是否經(jīng)過路徑(i,j),是則取值1,否則為0;Zijk表示車次k經(jīng)過路徑(i,j)時是否擁擠,是則取值1,否則為0;Uck表示車次k對應(yīng)的車輛標(biāo)號是否為c,是則取值1,否則為0.

2.3 多目標(biāo)優(yōu)化模型

建立同時考慮成本和時間的多目標(biāo)優(yōu)化模型,如式(1)所示。F1表示清運車輛在處理場內(nèi)的排隊等待總時間最小,見式(2).F2表示垃圾清運總成本最小,包括車輛固定成本、運輸成本以及時間窗范圍外作業(yè)的懲罰成本三部分,其中運輸成本包括停車場到垃圾收集點的運輸成本、車輛在垃圾收集點之間的運輸成本、垃圾投放點到處理廠之間的運輸成本以及處理廠到停車場的運輸成本之和,詳見式(3).

F=min{F1,F2}

(1)

F1=∑k∈K∑j∈Ftjk

(2)

∑k∈K∑i∈W∑j∈Fdijxijk+

∑k∈K∑j∈F∑i∈Wdjixjik+

(3)

主要約束條件如下:

∑k∈K∑j∈G∪Fxijk≥1,?i∈G∪F

(4)

∑i∈G∪F∪Pxigk-∑j∈G∪Fxgik=0

v1=G∪F∪P,?i∈G

(5)

∑i∈Gxilk-∑j∈G∪Pxljk=0,

?l∈W;k∈K

(6)

∑i∈Gyik=mk,?k∈K

(7)

∑i∈Gxpik=∑j∈Fxjpk≥1,?k∈K

(8)

∑k∈Kyik=qi,?i∈G

(9)

∑k∈Kqi≤∑k∈Kmk

(10)

yik≤uik≤mk,k∈K

(11)

0≤yik≤∑j∈G∪F∪Pqixjik,?i∈G,k∈K

(12)

xijk≤TE-TS,?c∈C

(13)

公式(4)表示一個垃圾投放點可以由多個車次進行收運服務(wù);公式(5)表示收運車輛在垃圾投放點完成收運工作以后需要立即離開;公式(6)表示收運車輛在處理廠完成卸料作業(yè)離開后,要去往干垃圾投放點進行收運作業(yè)或者去往停車場;公式(7)表示某類垃圾收運車輛k在垃圾投放點可以進行多次收集作業(yè),直到達到該類車輛最大載重時前往處理場卸料;公式(8)表示收運車輛k從停車場出發(fā)去往垃圾收集點的次數(shù)和車輛k從處理場回到停車場的次數(shù)相同,且過程不止一次;公式(9)表示垃圾收運車輛去往投放點i進行多次收運作業(yè)后所收集的垃圾總量等于該投放點的生活垃圾清運需求量;公式(10)表示清運車輛k的最大載重量要滿足垃圾投放點i的生活垃圾清運需求量;公式(11)表示在清運車輛k在垃圾投放點i進行收運作業(yè)時垃圾收運量不能少于該點的垃圾產(chǎn)生量,同時去往處理廠時垃圾的收運量不能超過清運車輛的最大載重限制;公式(12)表示清運車輛k在垃圾投放點i的垃圾收運量非負(fù),且當(dāng)車輛經(jīng)過該點時才能發(fā)生收運行為;公式(13)表示清運車輛k的總工作時間要在時間窗范圍內(nèi)。

3 實例分析

3.1 收運路網(wǎng)結(jié)構(gòu)圖

3.1.1 節(jié)點坐標(biāo)

以某市H區(qū)為例,建立收運路網(wǎng)結(jié)構(gòu)圖。該區(qū)的垃圾收運網(wǎng)絡(luò)中共包含67個節(jié)點,其中包括一個停車場(編號1)、一個垃圾處理中心(編號2)、一個可回收資源分揀中心(編號3)、23個垃圾投放節(jié)點(編號4-26).通過Google Earth軟件確定各節(jié)點經(jīng)緯度坐標(biāo),如圖2所示。

圖2 去除街道影像后H區(qū)垃圾投放點位置Fig.2 Location of garbage dropping point in H district after removing street image

以坐標(biāo)為(112.531235,37.954798)的點為坐標(biāo)原點,得到垃圾投放節(jié)點在地圖上的位置及其相對位置坐標(biāo)。

3.1.2 路網(wǎng)節(jié)點坐標(biāo)

將各節(jié)點及路徑的相對坐標(biāo)提取出來,建立路網(wǎng)結(jié)構(gòu)圖,如圖3所示。根據(jù)路徑連接情況,引入41個虛擬節(jié)點(編號27-67),虛擬節(jié)點的垃圾產(chǎn)生量為0,時間窗為24小時。以圖3為基礎(chǔ),將個節(jié)點連接起來,形成可行的路徑網(wǎng)絡(luò),如圖4所示。

圖3 垃圾收運網(wǎng)絡(luò)節(jié)點路網(wǎng)結(jié)構(gòu)圖Fig.3 Road network structure diagram of garbage collection and transportation network nodes

圖4 垃圾收運網(wǎng)絡(luò)節(jié)點連接示意圖Fig.4 Schematic diagram of node connection of garbage collection and transportation network

3.2 各類垃圾主要參數(shù)取值

垃圾投放點中,時間窗及清運數(shù)量見表1.

表1 垃圾收運網(wǎng)絡(luò)各節(jié)點相關(guān)信息表Tab.1 Relevant information table of each node of garbage collection and transportation network

根據(jù)調(diào)研確定:箱式車、兩種不同載重的壓縮車的固定成本分別是460.00元/車/天、451.13元/車/天和546.03元/車/天;燃油費用分別為15.63元/千米、12.80元/千米和37.85元/千米。垃圾收運車輛在投放點的裝卸時間為5 min,在處理場卸料時間為10 min,車輛在卸料完成后進行車輛維護的時間為15 min,可回收垃圾在可回收資源中心的卸料時間為10 min.車輛在進行清運時車輛行駛速度假設(shè)為30 km/h,當(dāng)在擁堵時間段早高峰[7,9]和晚高峰[17,19]時,車輛速度降為正常行駛速度的一半,為15 km/h.

3.3 模型算法驗證

3.3.1 算法參數(shù)

(1)PSO基本參數(shù)確立

設(shè)置粒子種群大小為100,由于隨著迭代的進行,慣性因子應(yīng)該逐漸減小,因此將慣性權(quán)重參數(shù)取為ω,在進行迭代計算時來提高粒子群尋找最優(yōu)解的能力;學(xué)習(xí)因子設(shè)置為c1=c2=1.494 5,粒子的最大速度設(shè)置為vmax,控制在[-0.1,0.1]范圍內(nèi);自變量取值范圍設(shè)置為[0,1],迭代次數(shù)為400次。

(2)GA基本參數(shù)確立

設(shè)置初始種群大小為100,將染色體編碼方式確定為自然數(shù)編碼,每一個數(shù)字代表一個網(wǎng)絡(luò)節(jié)點,每一串?dāng)?shù)字代表網(wǎng)絡(luò)節(jié)點被服務(wù)的先后順序,即車輛調(diào)度路徑。在選擇遺傳算子時采用錦標(biāo)賽法,從種群的n個個體中隨機抽取k個個體,并按照錦標(biāo)賽的方法選擇出適應(yīng)度更高的個體;設(shè)置算法交叉概率P1=0.65,變異后概率P2=0.05.

3.3.2 算法效率分析

本文將垃圾清運時間分為早晚清運時間兩種情況進行車輛調(diào)度,在不同時間窗內(nèi)得出三種不同類型垃圾的收運路線。利用MATLAB 軟件進行算法迭代,對早晚班清運迭代400次的結(jié)果進行分析,如圖5、圖6所示。由此可知PSO算法適應(yīng)度值更小,其效果更好。

圖5 迭代400次下的早班垃圾清運效果曲線圖Fig.5 Effectcurve of early shift garbage removal after 400 iterations

圖6 迭代400次下的晚班垃圾清運效果曲線圖Fig.6 Effect Curve of night shift garbage removal after 400 iterations

3.3.3 車輛收運路線方案

根據(jù)模型進行求解,可以得出不同類型垃圾分類單獨收運時早晚班清運的模型對比分析如表2所示。

表2 早晚班分類單獨收運模型結(jié)果分析Tab.2 Result analysis of separate collection and transportation model for morning and evening shift classification

通過表2可知,粒子群算法下模型的收運結(jié)果優(yōu)于遺傳算法,故選取粒子群算法的模型結(jié)果作為垃圾分類收運車輛調(diào)度的依據(jù)。

4 結(jié)論

首先,通過實驗分析結(jié)果可以看出:(1)以實際路網(wǎng)結(jié)構(gòu)為基礎(chǔ),確定垃圾投放點、處理廠及停車場的實際位置;同時將行駛道路及節(jié)點納入模型,獲得了可行的路徑方案。(2)通過對垃圾分類收運問題的系統(tǒng)分析,確定該問題的研究范疇,是對現(xiàn)有垃圾收運的有效拓展。(3)經(jīng)計算,與遺傳算法相比,粒子群算法獲得較優(yōu)的方案,且效率也得到提升。此外,本文假設(shè)垃圾產(chǎn)生量每天都是固定的,而現(xiàn)實中垃圾產(chǎn)生量是存在波動的。確定垃圾產(chǎn)生量的置信區(qū)間,再對收運進行優(yōu)化,這也是未來可以研究的方向。