考慮時(shí)空距離的低值可回收物收運(yùn)路線優(yōu)化

□ 張 慧

(上海理工大學(xué) 管理學(xué)院,上海 200093)

1 引言

2021年5月6日，國(guó)家發(fā)展改革委、住房城鄉(xiāng)建設(shè)部下發(fā)《“十四五”城鎮(zhèn)生活垃圾分類和處理設(shè)施發(fā)展規(guī)劃》強(qiáng)調(diào)，推動(dòng)低值可回收物的回收和再生利用。隨著消費(fèi)水平不斷提升，垃圾數(shù)量正以平均每年10%-15%的速度增長(zhǎng)[1]，“垃圾圍城”成為亟需解決的環(huán)境問(wèn)題。產(chǎn)生該問(wèn)題的主要原因是生活垃圾中摻雜大量低值可回收物。據(jù)中國(guó)環(huán)保在線統(tǒng)計(jì)，我國(guó)年產(chǎn)生活垃圾中有27%為可回收部分，剩下73%的垃圾中有40%是低值回收物[2]。由于收運(yùn)成本過(guò)高，低值可回收物無(wú)人問(wèn)津。較低回收率不僅會(huì)造成資源流失，還會(huì)污染環(huán)境。因此，有必要優(yōu)化收運(yùn)路線。

生活垃圾收運(yùn)路線優(yōu)化一直是國(guó)內(nèi)外研究的熱點(diǎn)，部分學(xué)者進(jìn)行了相關(guān)的研究。Jo?o Teixeira等[3]運(yùn)用啟發(fā)式算法求解車輛服務(wù)的地理范圍，每天的收集廢物類型、收運(yùn)路線。結(jié)果表明，安排收集計(jì)劃可大幅度節(jié)約成本。Afroditi Anagnostopoulou等[4]優(yōu)化收集服務(wù)的路線，節(jié)約總收運(yùn)時(shí)間和能源消耗。張爽等[5]考慮垃圾量不確定因素，構(gòu)建居民滿意度的生活垃圾上門收運(yùn)路線優(yōu)化模型，采用人工魚群算法求解出最短路徑。王晨頔等[6]在調(diào)度模型中加入車輛中轉(zhuǎn)站排隊(duì)等待的時(shí)間，考慮工作量、清運(yùn)時(shí)間兩方面，建立以成本最低為目標(biāo)的模型。符俊波等[7]為解決垃圾清運(yùn)量變化引起的干擾問(wèn)題，分析收運(yùn)車輛的擾動(dòng)辨識(shí)，建立調(diào)整后的方案與原方案誤差最小的數(shù)學(xué)模型。目前，關(guān)于低值可回收物的研究聚焦于政府經(jīng)濟(jì)激勵(lì)層面。杜歡政等[8]從收集、運(yùn)輸、分揀三個(gè)環(huán)節(jié)確定各品類低值廢物的成本和收益后，核算不同利潤(rùn)率下政府的補(bǔ)貼金額。杜歡政等[9]采用政府節(jié)約綜合選擇法計(jì)算回收低值可回收物的政府補(bǔ)貼，與“一刀切”式相比，該方法能降低支出。蔣南青[10]對(duì)低值可回收物的源頭收集，提出不同的獎(jiǎng)勵(lì)方式。

綜上，生活垃圾收運(yùn)路線優(yōu)化的研究十分豐富，對(duì)低值可回收物的研究需要進(jìn)一步探索。因此，本文以收運(yùn)成本最低為目標(biāo)，構(gòu)建考慮時(shí)空距離的兩級(jí)車輛路徑優(yōu)化模型。

2 問(wèn)題描述與符號(hào)說(shuō)明

2.1 問(wèn)題描述

兩級(jí)收運(yùn)路徑問(wèn)題描述如下：二級(jí)收集車輛從中轉(zhuǎn)站出發(fā)，通過(guò)既定的路線為居民服務(wù)，待完成全部收運(yùn)任務(wù)后，返回中轉(zhuǎn)站。在中轉(zhuǎn)站，低值可回收物被轉(zhuǎn)移到一級(jí)運(yùn)輸車輛，完成后返回集散中心。在收集過(guò)程中，因路況或服務(wù)時(shí)間窗更改等原因，居民可接受車輛提前或延遲到達(dá)收集點(diǎn)。需解決的問(wèn)題是合理規(guī)劃路線，最大程度降低成本。

圖1 兩級(jí)收運(yùn)路線結(jié)構(gòu)圖

2.2 模型假設(shè)

①收集、運(yùn)輸車輛的單位運(yùn)輸成本已知；

②中轉(zhuǎn)站和居民的數(shù)量、地理位置已知；

③收集車輛、運(yùn)輸車輛的裝載容量已知。

2.3 符號(hào)說(shuō)明

集合：

D：集散中心，D ={0}

S：中轉(zhuǎn)站集合，S ={1,2,…,s}

C：收集點(diǎn)集合，C ={1,2,…,n}

B：一級(jí)運(yùn)輸車輛集合，B ={1,2,…,b0}

K：二級(jí)收集車輛集合，K ={1,2,…,k0}

指標(biāo)和參數(shù)：

i/j：居民點(diǎn)、中轉(zhuǎn)站節(jié)點(diǎn)索引

QB：運(yùn)輸車輛的容量

QK：收集車輛的容量

FB：運(yùn)輸車輛固定成本

FK：收集車輛固定成本

a1：運(yùn)輸車輛單位運(yùn)輸費(fèi)用

a2：收集車輛單位運(yùn)輸費(fèi)用

dij：節(jié)點(diǎn)i，j間的距離

qi：收集點(diǎn)i的收集量

Lbij：車輛b在弧 (i,j) 之間裝載量，b ∈ B

Lkij：車輛k在弧 (i,j) 之間運(yùn)輸量， k ∈ K

tki/tkj：車輛k到達(dá)i或j的時(shí)間，k ∈ K

tkij：車輛k從節(jié)點(diǎn) i 駛向節(jié)點(diǎn) j 的時(shí)間

tkdi：車輛k在居民點(diǎn)i的等待時(shí)間，k ∈ K，i ∈ C

tksi：車輛k在居民點(diǎn)i的服務(wù)時(shí)間，k ∈ K，i ∈ C

[ETi，LTi] ：收集點(diǎn)i ∈ C的期望時(shí)間窗

c：收集點(diǎn)單位時(shí)間窗偏離量費(fèi)用

決策變量：

xijb：0-1 變量，若車輛b通過(guò)弧(i,j)，則為1，否則為0；

yijk：0-1 變量，若車輛k通過(guò)弧(i,j)，則為1，否則為0；

zik：0-1 變量，若i點(diǎn)由車輛 k 收集，則為1，否則為0。

3 模型構(gòu)建

3.1 目標(biāo)函數(shù)

目標(biāo)函數(shù)包括車輛固定成本(Z1)、運(yùn)輸成本(Z2)、車輛未在期望時(shí)間窗內(nèi)到達(dá)的懲罰成本(Z3)，三者之和成本最少。

Min=Z1+Z2+Z3

(1)

(2)

(3)

(4)

3.2 約束條件

(5)

一級(jí)運(yùn)輸車輛的容量約束；

(6)

確保每個(gè)中轉(zhuǎn)站最多只能被服務(wù)一次；

(7)

保證一級(jí)收運(yùn)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的進(jìn)出車輛相同；

(8)

二級(jí)收集車輛的容量約束；

(9)

保證每個(gè)收集點(diǎn)被一輛收集車輛服務(wù)一次；

(10)

保證二每個(gè)節(jié)點(diǎn)進(jìn)出車輛相同；

(11)

車輛載重量守恒約束；

(12)

確保所有車輛空車返回其原始集散中心或中轉(zhuǎn)站；

(13)

計(jì)算收集車輛的等待時(shí)間；

tkdi=max[(ETi-tki)zik,0],?i∈C,k∈K

(14)

計(jì)算車輛到達(dá)節(jié)點(diǎn)j∈C的時(shí)間

(15)

3.3 求解收運(yùn)路線算法介紹

由于居民點(diǎn)較多，第二級(jí)收集路線采用考慮時(shí)空距離的改進(jìn)模擬退火算法，第一級(jí)節(jié)點(diǎn)數(shù)量較少，采用精確方法。

①考慮時(shí)空距離的初始路徑規(guī)劃。

一般車輛路徑問(wèn)題用空間距離衡量遠(yuǎn)近[11]。實(shí)際中，服務(wù)時(shí)間窗接近，位置相隔較遠(yuǎn)，不適宜規(guī)劃在同一路徑上。因此，本文采用時(shí)空距離度量收集點(diǎn)間時(shí)間加空間的遠(yuǎn)近關(guān)系。

(16)

歐式距離描述i(xi,yi)和j(xj,yj)之間的空間距離。

(17)

假設(shè)[a,b]和[c,d]是居民點(diǎn)i,j預(yù)約的時(shí)間窗。不妨令a≤c，若收集車到達(dá)點(diǎn)i的時(shí)間為t∈ [a,b],si是服務(wù)時(shí)間，tij是指點(diǎn)i到點(diǎn)j花費(fèi)的路由時(shí)間，則到達(dá)j的時(shí)間為t′∈ [a′,b′],其中：a′=ei+si+tij，b′=li+si+tij

提前或超過(guò)規(guī)定時(shí)間窗的，增加相應(yīng)懲罰系數(shù)。根據(jù)提前、準(zhǔn)時(shí)、延后到達(dá)居民點(diǎn)三種情況，i點(diǎn)與j點(diǎn)之間時(shí)間距離為：

(18)

②初始解優(yōu)化。

改進(jìn)模擬退火算法是在傳統(tǒng)基礎(chǔ)上，加入變鄰域搜索算法、交換算子，兩種變換：變換1 某條路線中的一個(gè)收集任務(wù)插入到另一條路線中；變換2 某兩條路線中兩個(gè)居民點(diǎn)的收集任務(wù)互換。

4 算例研究

4.1 算例數(shù)據(jù)

擬選取80個(gè)低值可回收物產(chǎn)生點(diǎn)，表1中xi為收集點(diǎn)橫坐標(biāo)，yi為收集點(diǎn)縱坐標(biāo)，Qi為收集量(單位：t)，[ETi，LTi] 收集點(diǎn)i的期望時(shí)間窗。專家篩出中轉(zhuǎn)站1、2、4和集散中心2、3，。單位運(yùn)輸成本(元/t.km)分別為2.5,4.3,6.3；車容量(t)QB為4000、QK為300；車輛固定成本(元)FB為500、FK為100；單位運(yùn)輸費(fèi)用(元)a1為18.5、a2為2.5；收集點(diǎn)單位時(shí)間窗偏離量費(fèi)用(元)c為0.1；

表1 收集點(diǎn)、中轉(zhuǎn)站、集散場(chǎng)位置

4.2 算例結(jié)果

共有80個(gè)收集點(diǎn)，3個(gè)中轉(zhuǎn)站。運(yùn)用改進(jìn)模擬退火算法-時(shí)空距離、模擬退火算法、變鄰域搜索算法、改進(jìn)模擬退火算法求解收運(yùn)路線，最優(yōu)值結(jié)果如表2。

表2 四種算法求解結(jié)果對(duì)比表

由表2可看出，考慮時(shí)空距離的改進(jìn)模擬退火算法計(jì)算目標(biāo)函數(shù)值最低，成本降低了225.06。收斂過(guò)程如圖2所示。

圖2 四種算法收斂過(guò)程對(duì)比

由圖2可知，初始階段，改進(jìn)模擬退火—時(shí)空距離算法由于接受較差解的概率較大，第12次迭代時(shí)開始迅速下降，速度超過(guò)其他三個(gè)算法，最終收斂得到的總收運(yùn)成本最好。四個(gè)算法中收斂速度最慢的是模擬退火算法，最終結(jié)果最差。

4.3 兩級(jí)收運(yùn)路線優(yōu)化結(jié)果

考慮時(shí)空距離的改進(jìn)模擬退火算法求解兩級(jí)收運(yùn)路徑的收運(yùn)成本和懲罰成本，結(jié)果如表3。

表3 兩級(jí)車輛路徑相關(guān)成本

由表3計(jì)算可得，第一級(jí)收運(yùn)路線成本為3066.05元，第二級(jí)收運(yùn)成本為8733.53元，所需一級(jí)車輛數(shù)2輛，二級(jí)車輛數(shù)12輛。兩級(jí)收運(yùn)路線如下：

第二級(jí)收集路線：

1：中轉(zhuǎn)站4→29→2→73→65→9→13→4→63→68→中轉(zhuǎn)站4

2：中轉(zhuǎn)站4→45→50→6→42→17→14→23→27→71→中轉(zhuǎn)站4

3：中轉(zhuǎn)站4→78→25→75→20→10→57→3→中轉(zhuǎn)站4

4：中轉(zhuǎn)站4→15→8→21→56→22→34→28→54→中轉(zhuǎn)站4

5：中轉(zhuǎn)站2→36→77→48→中轉(zhuǎn)站2

6：中轉(zhuǎn)站2→67→60→19→69→76→39→38→中轉(zhuǎn)站2

7：中轉(zhuǎn)站2→66→41→30→72→16→47→5→62→中轉(zhuǎn)站2

8：中轉(zhuǎn)站4→35→53→31→80→18→24→55→中轉(zhuǎn)站4

9：中轉(zhuǎn)站1→26→79→11→33→59→46→51→中轉(zhuǎn)站1

10：中轉(zhuǎn)站2→7→61→32→74→43→中轉(zhuǎn)站2

11：中轉(zhuǎn)站1→44→64→52→1→37→49→40→中轉(zhuǎn)站1

12：中轉(zhuǎn)站4→12→70→58→中轉(zhuǎn)站4

第一級(jí)運(yùn)輸路線：

1：集散中心2→中轉(zhuǎn)站2→集散中心2

2：集散中心3→中轉(zhuǎn)站1→中轉(zhuǎn)站4→集散中心3

5 結(jié)語(yǔ)

本文對(duì)低值可回收物回收路徑優(yōu)化問(wèn)題展開了研究，建立了多中心、軟時(shí)間窗模型，在此基礎(chǔ)上設(shè)計(jì)了一種考慮時(shí)空距離的改進(jìn)模擬退火算法。算例結(jié)果表明：①考慮時(shí)空距離的改進(jìn)模擬退火算法能夠大幅度提高求解質(zhì)量及速度,②兩級(jí)收運(yùn)成本為13865.63元，降低了225.06元。

當(dāng)前研究還存在一些有待改進(jìn)的地方,例如:未考慮低值可回收物收運(yùn)過(guò)程中出現(xiàn)的服務(wù)時(shí)間窗變動(dòng)、回收量變化、新增訂單等干擾事件，后續(xù)可針對(duì)該方面展開一定的研究。