□ 張 慧

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

1 引言

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

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

2 問題描述與符號說明

2.1 問題描述

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

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

2.2 模型假設(shè)

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

②中轉(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}

指標(biāo)和參數(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到達(dá)i或j的時間，k ∈ K

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

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

tksi：車輛k在居民點i的服務(wù)時間，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 目標(biāo)函數(shù)

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

Min=Z1+Z2+Z3

(1)

(2)

(3)

(4)

3.2 約束條件

(5)

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

(6)

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

(7)

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

(8)

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

(9)

保證每個收集點被一輛收集車輛服務(wù)一次；

(10)

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

(11)

車輛載重量守恒約束；

(12)

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

(13)

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

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

(14)

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

(15)

3.3 求解收運路線算法介紹

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

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

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

(16)

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

(17)

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

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

(18)

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

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

4 算例研究

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

擬選取80個低值可回收物產(chǎn)生點，表1中xi為收集點橫坐標(biāo)，yi為收集點縱坐標(biāo)，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)站。運用改進(jìn)模擬退火算法-時空距離、模擬退火算法、變鄰域搜索算法、改進(jìn)模擬退火算法求解收運路線，最優(yōu)值結(jié)果如表2。

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

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

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

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

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

考慮時空距離的改進(jìn)模擬退火算法求解兩級收運路徑的收運成本和懲罰成本，結(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)化問題展開了研究，建立了多中心、軟時間窗模型，在此基礎(chǔ)上設(shè)計了一種考慮時空距離的改進(jìn)模擬退火算法。算例結(jié)果表明：①考慮時空距離的改進(jìn)模擬退火算法能夠大幅度提高求解質(zhì)量及速度,②兩級收運成本為13865.63元，降低了225.06元。

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