考慮路徑可靠性的垃圾回收選址路徑問題研究

史志學(xué) 李銳

摘要：? 在路徑中斷情況下，為了降低垃圾回收成本和提高收集路徑的安全性，本文主要對基于路徑可靠性的垃圾回收選址路徑問題進(jìn)行研究。建立了帶有車輛路徑可靠性約束的選址路徑問題優(yōu)化模型，在路徑可靠性水平滿足要求的條件下，最小化回收物流總成本。根據(jù)問題模型的特點(diǎn)設(shè)計粒子群優(yōu)化（particle swarm optimization， PSO）算法求解，為了驗證模型的合理性和算法的有效性，采用Matlab軟件編程，對不同的數(shù)值算例進(jìn)行仿真測試，并且分析路徑可靠性水平對成本的影響。實驗結(jié)果表明，該模型能夠?qū)栴}進(jìn)行合理描述，粒子群優(yōu)化算法能夠?qū)Σ煌?guī)模的問題進(jìn)行有效求解，并且隨著可靠性水平的增大，總成本增加，開設(shè)成本無明顯變化，車輛運(yùn)營成本增加，運(yùn)輸和處理成本增加。該研究對提高垃圾回收系統(tǒng)的可靠性具有重要意義。

關(guān)鍵詞：? 垃圾回收; 選址路徑問題; 路徑可靠性; 粒子群優(yōu)化算法

中圖分類號： TP29? 文獻(xiàn)標(biāo)識碼： A

收稿日期： 20210331; 修回日期： 20210617

基金項目： 遼寧省自然科學(xué)基金指導(dǎo)計劃項目（20180550300）; 遼寧省教育廳青年科技人才“育苗”項目（JQL202015407）

作者簡介：? 史志學(xué)（1996），男，江蘇徐州人，碩士研究生，主要研究方向為物流網(wǎng)絡(luò)設(shè)計和智能優(yōu)化。

通信作者：? 李銳（1985），男，遼寧海城人，博士，副教授，碩士生導(dǎo)師，主要研究方向為智能計算和物流優(yōu)化。 Email： 279496574@88.com

垃圾是環(huán)境污染的重要來源之一，為有效緩解環(huán)境污染，長期以來，垃圾回收一直是各個國家亟待解決的問題。對于壓縮車直運(yùn)模式下的垃圾回收，垃圾綜合處理中心的合理選址及車輛路徑的優(yōu)化有利于節(jié)約回收成本。隨著安全意識的增強(qiáng)，人們不僅關(guān)注垃圾回收的物流成本，還需要關(guān)注垃圾回收過程中路徑中斷對回收系統(tǒng)造成的影響。因此，考慮路徑可靠性的垃圾回收網(wǎng)絡(luò)對于垃圾回收的可持續(xù)性具有重要意義。近年來，國內(nèi)外學(xué)者對各種選址路徑問題（locationrouting problem，LRP）進(jìn)行了研究。C.Prodhon等人[1]對LRP的最新進(jìn)展進(jìn)行了綜述，包括經(jīng)典LRP的求解以及各種LRP的擴(kuò)展;M.Schneider等人[2]對標(biāo)準(zhǔn)LRP的不同求解方法進(jìn)行了詳細(xì)的綜述;胡大偉等[3]主要對LRP的擴(kuò)展問題相關(guān)研究進(jìn)行了介紹。目前，逆向物流LRP更加引起關(guān)注。Hong L等人[4]對多目標(biāo)逆向物流LRP進(jìn)行了研究;V.R.Ghezavati等[5]研究了帶有時間窗的逆向物流LRP;Hong L等人[6]對帶有灰色回收需求的逆向物流LRP進(jìn)行了研究;Zhao J等人[7]對爆炸性廢棄物回收LRP進(jìn)行了研究;J.S.Kim等人[8]研究回收物流網(wǎng)絡(luò)設(shè)計問題集成LRP模型;喬佩利等人[9]對第三方逆向物流LRP問題進(jìn)行了研究;李昌兵等人[10]研究集成庫存的逆向LRP;Li H等人[11]研究城市固體廢棄物回收LRP;M. Rabbani等人[12]研究工業(yè)危險廢棄物回收LRP。雖然當(dāng)前國內(nèi)外學(xué)者對LRP進(jìn)行了大量的研究，但對于考慮可靠性的LRP研究較少。Zhang Y等人[13]利用基于情景的規(guī)劃方法對考慮隨機(jī)中斷的LRP進(jìn)行研究;Xie W等人[14]研究設(shè)施以概率中斷的可靠性LRP;A.Ahmadijavid等人[15]研究考慮隨機(jī)的生產(chǎn)配送中心和車輛的中斷風(fēng)險下的LRP;F.Rayat等人[16]研究考慮配送中心的供應(yīng)中斷和集成庫存的可靠性LRP。以上研究均未考慮中斷的逆向物流LRP?；诖耍疚难芯靠紤]路徑可靠性的垃圾回收物流選址路徑優(yōu)化問題，建立垃圾回收選址路徑優(yōu)化模型，在路徑可靠性水平滿足要求的條件下，最小化回收物流總成本，根據(jù)問題模型特點(diǎn)設(shè)計粒子群優(yōu)化算法求解，通過實驗來驗證模型的合理性及算法的有效性。本研究對垃圾回收具有一定的實際應(yīng)用價值。

1 問題描述及模型建立

壓縮車直運(yùn)模式下的回收系統(tǒng)包括垃圾收集點(diǎn)、綜合處理中心、垃圾壓縮車和收集線路4部分。垃圾壓縮車從綜合處理中心出發(fā)依次通過不同的垃圾收集點(diǎn)進(jìn)行垃圾收集，然后返回原綜合處理中心，進(jìn)行填埋、堆肥或焚燒等廢棄處理?？紤]路徑可靠性的垃圾回收LRP，建立帶有車輛路徑可靠性約束的LRP優(yōu)化模型，通過選擇開設(shè)綜合處理中心及確定不同車輛的行駛路徑，在滿足可靠性要求水平的條件下，最小化系統(tǒng)總成本。優(yōu)化模型的假設(shè)條件如下：

1） 垃圾收集點(diǎn)的位置和數(shù)量已知。

2） 候選的綜合處理中心的位置和數(shù)量已知。

3） 任意一個垃圾收集點(diǎn)必須有且只有一輛壓縮車服務(wù)。

4） 每輛壓縮車只能從一個綜合處理中心出發(fā)，并返回該綜合處理中心。

5） 每個綜合處理中心允許多個車輛駛出和駛?cè)搿?/p>

1.1 符號及變量

為了問題模型的建立，引入以下符號。N=J∪L表示節(jié)點(diǎn)集合，其中L表示收集點(diǎn)集合，J表示綜合處理中心集合;V表示收集車輛集合;Dl表示收集點(diǎn)l∈L的收集量;Gj表示綜合處理中心j∈J的開設(shè)成本;Uj表示綜合處理中心j∈J的處理能力;Pj表示綜合處理中心j∈J的單位處理成本;Rj表示綜合處理中心j∈J的可靠性;Fv表示車輛v∈V的固定運(yùn)營成本;Qv表示車輛v∈V的運(yùn)輸能力;Cab表示從點(diǎn)a∈N到點(diǎn)b∈N的固定運(yùn)輸成本;rab表示從點(diǎn)a∈N到點(diǎn)b∈N的可靠性。

決策變量定義如下：xabv∈0，1表示如果車輛v∈V從點(diǎn)a∈N到點(diǎn)b∈N，取值為1，如果車輛v∈V沒有從點(diǎn)a∈N到點(diǎn)b∈N，取值為0;yjv∈0，1表示如果車輛v∈V服務(wù)于綜合處理中心j∈J取值為1，如果車輛v∈V不服務(wù)于綜合處理中心j∈J取值為0;zj∈0，1表示如果開設(shè)綜合處理中心j∈J取值為1，如果沒有開設(shè)綜合處理中心j∈J則取值為0。決策變量xabv、yjv和zj對應(yīng)的向量分別定義如下：X=xabv|a，b∈M，v∈V，Y={yjv|j∈J，v∈V}，Z={zj|j∈J}。

1.2 優(yōu)化模型

基于以上符號和變量說明，考慮路徑可靠性的垃圾回收選址路徑優(yōu)化模型為

minf（X，Y，Z）=∑j∈JGjzj+∑v∈V∑j∈JFvyjv+∑j∈JPj∑v∈V∑l∈L∑b∈NDlxlbvyjv+∑a∈N∑b∈N∑v∈VCabxabv（1）

s.t.

∏j∈JRjyjv∏a∈N∏b∈Nrabxabv≥β?? v∈V（2）

∑l∈Lxjlv-yjv=0?? j∈J，v∈V（3）

∑v∈V∑l∈Lxjlv-zj≥0?? j∈J（4）

∑l∈Lxjlv-zj≤0?? j∈J，v∈V（5）

∑b∈Nxabv-∑b∈Nxbav=0?? a∈N，v∈V（6）

∑a∈W∑b∈Wxabv≤W-1?? WL，W≥2，v∈V（7）

∑j∈J∑l∈Lxjlv≤1?? v∈V（8）

∑v∈V∑b∈Nxlbv=1?? l∈L（9）

∑v∈Vxabv=0?? a，b∈J（10）

∑l∈L∑b∈NDlxlbv≤Qv?? v∈V（11）

∑v∈V∑l∈L∑b∈NDlxlbvyjv≤zjUj?? j∈J（12）

xabv∈0，1?? a，b∈N，v∈V（13）

yjv∈0，1?? j∈J，v∈V（14）

zj∈0，1?? j∈J（15）

目標(biāo)函數(shù)表達(dá)式（1）為最小化物流總成本，包括綜合處理中心的固定開設(shè)成本、車輛的固定運(yùn)營成本、處理成本和運(yùn)輸成本;式（2）為車輛路徑的可靠性約束，β為要求的可靠性水平;約束（3）表示車輛v服務(wù)于綜合處理中心j;約束（4）表示如果綜合處理中心開設(shè)，那么必須有車輛駛出;約束（5）表示沒有開設(shè)的綜合處理中心，則沒有車輛駛出;約束（6）表示車輛從某收集點(diǎn)或綜合處理中心駛?cè)?，也要從該點(diǎn)駛出;約束（7）表示收集點(diǎn)之間不能形成子環(huán)路;約束（8）要求每輛車最多服務(wù)一個綜合處理中心;約束（9）要求每個收集點(diǎn)必須有且只有一個車輛服務(wù);約束（10）保證在任意兩個綜合處理中心之間沒有車輛;式（11）為車輛的運(yùn)輸能力約束;式（12）為綜合處理中心的能力約束;式（13）～（15）為二值變量約束。

2 算法設(shè)計

考慮路徑可靠性的垃圾回收選址路徑問題是經(jīng)典LRP的擴(kuò)展，所以也是NPhard問題。當(dāng)規(guī)模較大時，問題求解困難，所以設(shè)計智能優(yōu)化算法對該問題進(jìn)行求解。粒子群優(yōu)化算法是一種經(jīng)典的群智能優(yōu)化算法[17]。目前，PSO算法已經(jīng)得到廣泛應(yīng)用，如作業(yè)車間調(diào)度問題[18]、目標(biāo)特征選擇[19]、云計算資源調(diào)度問題[20]等。本文根據(jù)問題特點(diǎn)設(shè)計粒子群優(yōu)化算法進(jìn)行求解，采用實數(shù)編碼方式進(jìn)行編碼。

2.1 算法的主要步驟

PSO的主要步驟如下：

Step 1：種群初始化。隨機(jī)生成初始的位置X1，X2，…，XN和速度V1，V2，…，VN。

Step 2：計算每個粒子的適應(yīng)值。

Step 3：更新粒子i的歷史最好位置Pti和全局最好位置Ptg。

Step 4：按照下式更新粒子的速度和位置，即

Vt+1ij=wVtij+c1·r1Ptij-Xtij+c2·r2Ptgj-Xtij（16）

Xt+1ij=Xtij+Vt+1ij（17）

其中，Vtij為粒子i第j維第t代的運(yùn)動速度;Ptij為粒子i歷史最好位置的第j維;Ptgj為全局最好位置的第j維;r1和r2為0，1之間的隨機(jī)數(shù);c1和c2為加速度常數(shù);w為慣性系數(shù)。

Step 5：如果達(dá)到最大迭代次數(shù)，則終止循環(huán)，并輸出最優(yōu)解;否則，轉(zhuǎn)到Step 2。

2.2 解的編碼與解碼

實數(shù)向量對應(yīng)問題的解。向量包括3個部分，第1部分表示垃圾收集點(diǎn)的排序，每一位對應(yīng)一個垃圾收集點(diǎn)，取值為0，1之間的實數(shù)，根據(jù)取值可以得到垃圾收集點(diǎn)的排序;第2部分表示各個垃圾收集點(diǎn)的車輛分配，每一位取值范圍為1，NV，對應(yīng)的整數(shù)表示選擇的車輛號，NV為車輛數(shù);第3部分表示車輛所分配的綜合處理中心，每一位對應(yīng)一個車輛，取值為1，NK之間實數(shù)，對應(yīng)的整數(shù)表示車輛選擇的處理中心，NC為垃圾收集點(diǎn)數(shù)量，NK為綜合處理中心數(shù)量。

2.3 適應(yīng)值函數(shù)

給定粒子位置Xi，通過解碼得到解X，Y，Z，并計算粒子適應(yīng)值為

C=f（X，Y，Z）+α1β-∏j∈JRjyjv∏a∈N∏b∈Nrabxabv++α2∑v∈V∑l∈L∑b∈NDlxlbv-Qv++α3∑j∈J∑v∈V∑l∈L∑b∈NDlxlbvyjv-zjUj+（18）

式中，f（X，Y，Z）為目標(biāo)函數(shù)（1），可靠性約束（2）和能力約束（11）和（12）作為懲罰項加入評價函數(shù)中;α1，α2和α3為懲罰系數(shù)，取值為很大的正數(shù);·+表示如果括號內(nèi)值為正則取該值，否則取0。

3 實驗及結(jié)果分析

為了驗證模型的合理性和算法的有效性，對不同的數(shù)值算例進(jìn)行測試。算法通過Matlab編程實現(xiàn)，并且所有測試的實驗環(huán)境為Intel Core i5 CPU 2.70 GHz，內(nèi)存8 GB計算機(jī)，操作系統(tǒng)Windows 7。

不同算例規(guī)模如表1所示。算例的參數(shù)按照均勻分布產(chǎn)生：收集點(diǎn)的收集量Dl～U[150，200];綜合處理中心的開設(shè)成本Gj～U[40 000，60 000];綜合處理中心的處理能力Uj～U[4 000，5 000];綜合處理中心的單位處理成本Pj～U[1，10];綜合處理中心的可靠性Rj～U[0.9，1];車輛的固定運(yùn)營成本Fv～U[5 000，8 000];車輛的運(yùn)輸能力Qv～U[1 500，2 000];從點(diǎn)a到點(diǎn)b的固定運(yùn)輸成本Cab～U[800，1 800];從點(diǎn)a到點(diǎn)b的可靠性rab～U[0.9，1]。

首先，通過求解不同規(guī)模算例I1～I(xiàn)3，對PSO的性能進(jìn)行測試，對于每個算例，算法分別運(yùn)行10次。PSO算法的種群規(guī)模為50，最大迭代次數(shù)為100，慣性系數(shù)w取值為0.8，加速度常數(shù)c1和c2取值為1.2。不同規(guī)模算法求解結(jié)果如表2所示示，不同規(guī)模算例詳細(xì)結(jié)果如表3所示，不同算例詳細(xì)車輛路徑如表4所示。

由表2可以看出，對于不同規(guī)模的算例，PSO算法的標(biāo)準(zhǔn)方差在1.2%～4.9%之間變化，并且隨著問題規(guī)模的增加，PSO算法性能穩(wěn)定，因此PSO算法能夠?qū)栴}進(jìn)行有效求解。表3給出了算例I1～I(xiàn)3各種成本。表4給出了算例I1～I(xiàn)3的車輛路徑。

為研究路徑可靠性水平對成本的影響，以算例I1為例進(jìn)行實驗。在不同可靠性水平下，算例I1各種成本變化情況如圖1所示。由圖1可以看出，隨著可靠性水平增大，總成本增加，開設(shè)成本無明顯變化，車輛運(yùn)營成本增加，運(yùn)輸和處理成本增加。

4 結(jié)束語

鑒于目前對于逆向物流LRP的研究均未考慮路徑可靠性，本文對壓縮車直運(yùn)模式下考慮路徑可靠性的垃圾回收LRP進(jìn)行研究。建立帶有路徑可靠性約束的垃圾回收LRP優(yōu)化模型，設(shè)計PSO算法求解，并通過不同規(guī)模的數(shù)值算例進(jìn)行仿真實驗。實驗結(jié)果表明，對于不同規(guī)模的問題，PSO算法能夠有效求解，并保持性能穩(wěn)定。根據(jù)可靠性水平的影響分析發(fā)現(xiàn)，隨著可靠性水平的增加，總成本增加，其中車輛運(yùn)營成本及運(yùn)輸和處理成本是導(dǎo)致總成本增加的重要因素。因此，要得到路徑可靠性較高的回收網(wǎng)絡(luò)需要增加成本投入。本文的研究為壓縮車直運(yùn)模式下考慮路徑可靠性的垃圾回收系統(tǒng)選址路徑優(yōu)化提供了有效的參考模型和求解算法。對于垃圾回收系統(tǒng)的有效運(yùn)作和安全性的提高具有重要意義。

參考文獻(xiàn)：

[1] Prodhon C， Prins C. A survey of recent research on locationrouting problems[J]. European Journal of Operational Research， 2014， 238（1）： 117.

[2] Schneider M， Drexl M. A survey of the standard locationrouting problem[J]. Annals of Operations Research， 2017， 259（1）： 389414.

[3] 胡大偉， 陳希瓊， 高揚(yáng). 定位-路徑問題綜述[J]. 交通運(yùn)輸工程學(xué)報， 2018， 18（1）： 111129.

[4] Hong L， Wang W， Zhang Q. Multiobjective locationrouting problem of reverse logistics based on GRA with entropy weight[J]. Grey Systems Theory & Application， 2012， 2（2）： 249258.

[5] Ghezavati V R， Beigi M. Solving a biobjective mathematical model for locationrouting problem with time windows in multiechelon reverse logistics using metaheuristic procedure[J]. Journal of Industrial Engineering International， 2016， 12（4）： 469483.

[6] Hong L， Zhang Q， Wang W. Research on locationrouting problem of reverse logistics with grey recycling demands based on PSO[J]. Grey Systems Theory and Application， 2011， 1（1）： 97104.

[7] Zhao J， Ke G Y. Incorporating inventory risks in locationrouting models for explosive waste management[J]. International Journal of Production Economics， 2017， 193： 123136.

[8] Kim J S， Lee D H. An integrated approach for collection network design， capacity planning and vehicle routing in reverse logistics[J]. Journal of the Operational Research Society， 2015， 66： 7685.

[9] 喬佩利， 王娜. 考慮逆向物流第三方配送的選址路徑問題研究[J]. 計算機(jī)工程與應(yīng)用， 2017， 53（10）： 5560.

[10] 李昌兵， 張斐敏. 集成選址—路徑—庫存問題的逆向物流網(wǎng)絡(luò)優(yōu)化[J]. 計算機(jī)集成制造系統(tǒng)， 2014， 20（7）： 17931798.

[11] Li H， Ma Z， Wang C. The stochastic locationroutinginventory problem in reverse logistics systems for municipal solid waste[C]∥Eighth International Conference of Chinese Logistics & Transportation Professionals， Chengdu， China： ASCE， 2008.

[12] Rabbani M， Heidari R， Yazdanparast R. A stochastic multiperiod industrial hazardous waste locationrouting problem： integrating nsgaii and monte carlo simulation[J]. European Journal of Operational Research， 2019， 272（3）： 945961.

[13] Zhang Y， Qi M， Lin W， et al. A metaheuristic approach to the reliable location routing problem under disruptions[J]. Transportation Research Part Elogistics and Transportation Review， 2015， 83（11）： 90110.

[14] Xie W， Ouyang Y， Wong S C， et al. Reliable locationrouting design under probabilistic facility disruptions[J]. Transportation Science， 2016， 50（3）： 11281138.

[15] Ahmadijavid A， Seddighi A H. A locationrouting problem with disruption risk[J]. Transportation Research Part Elogistics and Transportation Review， 2013， 53（1）： 6382.

[16] Rayat F， Musavi M M， Bozorgiamiri A， et al. Biobjective reliable locationinventoryrouting problem with partial backordering under disruption risks： a modified AMOSA approach[J]. Applied Soft Computing， 2017， 59（6）： 622643.

[17] Shi Y H， Eberhart R C. A modified particle swarm optimizer[C]∥Evolutionary Computation Proceedings， Piscataway， USA： IEEE， 1998.

[18] 劉洪銘， 曾鴻雁， 周偉， 等. 基于改進(jìn)粒子群算法作業(yè)車間調(diào)度問題的優(yōu)化[J]. 山東大學(xué)學(xué)報： 工學(xué)版， 2019， 49（1）： 5762.

[19] 王金杰， 李煒. 混合互信息和粒子群算法的多目標(biāo)特征選擇方法[J]. 計算機(jī)科學(xué)與探索， 2020， 14， 136（1）： 88100.

[20] 趙宏偉， 李圣普. 基于粒子群算法和RBF神經(jīng)網(wǎng)絡(luò)的云計算資源調(diào)度方法研究[J]. 計算機(jī)科學(xué)， 2016， 43（3）： 113117.

LocationRouting Problem of Waste Recycling with Routing Reliability Considered

SHI Zhixue， LI Rui

（School of Electronics and Information Engineering， Liaoning University of Technology， Jinzhou 121001， China）

Abstract：? In order to reduce the cost of waste recycling and improve the security of collection route under the condition of route disruption， this paper mainly studies the locationrouting problem of waste recycling based on route reliability. An optimization model of locationrouting problem with vehicle routing reliability constraints is established， which minimizes the total cost of recycling logistics under the condition that the routing reliability level meets the requirements. According to the characteristics of the problem model， particle swarm optimization （PSO） algorithm is designed to solve the problem. In order to verify the rationality of the model and the effectiveness of the algorithm， Matlab software is used to program and simulate different numerical examples， and the influence of routing reliability level on the cost is analyzed. The experimental results show that the model can reasonably describe the problem， and the particle swarm optimization algorithm can effectively solve the problems of different sizes. With the increase of reliability level， the total cost increases， the setup cost has no obvious change， the vehicle operation cost increases， and the transportation and processing costs increase. This research is of great significance to improve the reliability of waste recycling system.

Key words： waste recycling; locationrouting; route reliability; particle swarm optimization