考慮時空距離的低值可回收物收運路線優化

□ 張 慧

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

1 引言

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

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

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

2 問題描述與符號說明

2.1 問題描述

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

圖1 兩級收運路線結構圖

2.2 模型假設

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

②中轉站和居民的數量、地理位置已知；

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

2.3 符號說明

集合：

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

S：中轉站集合，S ={1,2,…,s}

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

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

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

指標和參數：

i/j：居民點、中轉站節點索引

QB：運輸車輛的容量

QK：收集車輛的容量

FB：運輸車輛固定成本

FK：收集車輛固定成本

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

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

dij：節點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從節點 i 駛向節點 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 模型構建

3.1 目標函數

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

Min=Z1+Z2+Z3

(1)

(2)

(3)

(4)

3.2 約束條件

(5)

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

(6)

確保每個中轉站最多只能被服務一次；

(7)

保證一級收運網絡中每個節點的進出車輛相同；

(8)

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

(9)

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

(10)

保證二每個節點進出車輛相同；

(11)

車輛載重量守恒約束；

(12)

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

(13)

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

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

(14)

計算車輛到達節點j∈C的時間

(15)

3.3 求解收運路線算法介紹

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

①考慮時空距離的初始路徑規劃。

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

(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

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

(18)

②初始解優化。

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

4 算例研究

4.1 算例數據

擬選取80個低值可回收物產生點，表1中xi為收集點橫坐標，yi為收集點縱坐標，Qi為收集量(單位：t)，[ETi，LTi] 收集點i的期望時間窗。專家篩出中轉站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 收集點、中轉站、集散場位置

4.2 算例結果

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

表2 四種算法求解結果對比表

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

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

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

4.3 兩級收運路線優化結果

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

表3 兩級車輛路徑相關成本

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

第二級收集路線：

1：中轉站4→29→2→73→65→9→13→4→63→68→中轉站4

2：中轉站4→45→50→6→42→17→14→23→27→71→中轉站4

3：中轉站4→78→25→75→20→10→57→3→中轉站4

4：中轉站4→15→8→21→56→22→34→28→54→中轉站4

5：中轉站2→36→77→48→中轉站2

6：中轉站2→67→60→19→69→76→39→38→中轉站2

7：中轉站2→66→41→30→72→16→47→5→62→中轉站2

8：中轉站4→35→53→31→80→18→24→55→中轉站4

9：中轉站1→26→79→11→33→59→46→51→中轉站1

10：中轉站2→7→61→32→74→43→中轉站2

11：中轉站1→44→64→52→1→37→49→40→中轉站1

12：中轉站4→12→70→58→中轉站4

第一級運輸路線：

1：集散中心2→中轉站2→集散中心2

2：集散中心3→中轉站1→中轉站4→集散中心3

5 結語

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

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