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

□ 張 慧

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

1 引言

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

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

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

2 問題描述與符號說明

2.1 問題描述

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

圖1 兩級收運路線結(jié)構(gòu)圖

2.2 模型假設

①收集、運輸車輛的單位運輸成本已知；

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

③收集車輛、運輸車輛的裝載容量已知。

2.3 符號說明

集合：

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

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

C：收集點集合，C ={1,2,…,n}

B：一級運輸車輛集合，B ={1,2,…,b0}

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

指標和參數(shù)：

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

QB：運輸車輛的容量

QK：收集車輛的容量

FB：運輸車輛固定成本

FK：收集車輛固定成本

a1：運輸車輛單位運輸費用

a2：收集車輛單位運輸費用

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

qi：收集點i的收集量

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

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

tki/tkj：車輛k到達i或j的時間，k ∈ K

tkij：車輛k從節(jié)點 i 駛向節(jié)點 j 的時間

tkdi：車輛k在居民點i的等待時間，k ∈ K，i ∈ C

tksi：車輛k在居民點i的服務時間，k ∈ K，i ∈ C

[ETi，LTi] ：收集點i ∈ C的期望時間窗

c：收集點單位時間窗偏離量費用

決策變量：

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

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

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

3 模型構(gòu)建

3.1 目標函數(shù)

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

Min=Z1+Z2+Z3

(1)

(2)

(3)

(4)

3.2 約束條件

(5)

一級運輸車輛的容量約束；

(6)

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

(7)

保證一級收運網(wǎng)絡中每個節(jié)點的進出車輛相同；

(8)

二級收集車輛的容量約束；

(9)

保證每個收集點被一輛收集車輛服務一次；

(10)

保證二每個節(jié)點進出車輛相同；

(11)

車輛載重量守恒約束；

(12)

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

(13)

計算收集車輛的等待時間；

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

(14)

計算車輛到達節(jié)點j∈C的時間

(15)

3.3 求解收運路線算法介紹

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

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

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

(16)

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

(17)

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

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

(18)

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

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

4 算例研究

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

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

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

4.2 算例結(jié)果

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

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

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

圖2 四種算法收斂過程對比

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

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

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

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

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

第二級收集路線：

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

第一級運輸路線：

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

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

5 結(jié)語

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

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