智能垃圾回收下收集中心選址-路徑二層優(yōu)化

馬艷芳，賈佳鵬，李宗敏，閆 芳

1.河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401

2.四川大學(xué) 商學(xué)院，成都 610064

3.重慶交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，重慶 400074

4.重慶市環(huán)衛(wèi)集團(tuán)，重慶 401137

《“十四五”城鎮(zhèn)生活垃圾分類和處理設(shè)施發(fā)展規(guī)劃》指出要加快建立城鎮(zhèn)生活垃圾處理系統(tǒng)，并鼓勵依托物聯(lián)網(wǎng)等新興技術(shù)提升垃圾處理能力。國內(nèi)已有不少公司利用智能垃圾箱開展垃圾回收業(yè)務(wù)，如“小黃狗”“愛家物聯(lián)”“綠島”等智能垃圾箱。物聯(lián)網(wǎng)技術(shù)能夠?qū)錉顟B(tài)進(jìn)行跟蹤監(jiān)測[1-2]，將信息傳輸?shù)皆诰€平臺[3]，當(dāng)垃圾量達(dá)到閾值時平臺發(fā)出預(yù)警信號，根據(jù)平臺信息優(yōu)化回收路徑確保容量不足的智能垃圾箱得到及時清理。而下游收集中心作為回收車輛終點，其位置決定回收系統(tǒng)的有效性，選址不當(dāng)將產(chǎn)生高額運(yùn)輸成本。因此，收集中心選址和回收路徑規(guī)劃整合研究極大影響垃圾回收的成本和效率。

智能垃圾箱是一種利用物聯(lián)網(wǎng)等技術(shù)獲取垃圾桶內(nèi)相關(guān)信息的智能環(huán)保設(shè)備，如何利用這些信息實現(xiàn)資源高效利用成為亟待解決的問題。為了克服這一問題，Ramos 等[4]提出智能垃圾收集路徑（smart waste collection routing，SWCR），依據(jù)其收集閾值先選擇需要訪問的垃圾箱再確定最佳收集順序。此外，Gutierrez 等[5]依據(jù)傳感器存儲的數(shù)據(jù)庫選擇要收集的垃圾桶，采用路徑優(yōu)化算法計算出最優(yōu)的路徑，以使行車距離最小化。Gilardino等[6]根據(jù)各收集點垃圾量和每輛車的可用工作時間優(yōu)化收集路徑。物聯(lián)網(wǎng)背景下智能垃圾箱逐漸普及，優(yōu)化回收路徑時充分利用其信息量大和可預(yù)警等特點可實現(xiàn)資源高效利用。

表1 總結(jié)了LRP 及其在垃圾回收領(lǐng)域的相關(guān)研究?？梢钥闯鲇嘘P(guān)LRP研究多采用雙層結(jié)構(gòu)，由不同層次多個參與者參與聯(lián)合決策，隨著服務(wù)多樣化和專業(yè)化的發(fā)展，大多企業(yè)選擇將物流作業(yè)外包給第三方企業(yè)，如生鮮外包配送[7]，充電基礎(chǔ)設(shè)施選址-路徑問題[8]等。但垃圾回收背景下的LRP相關(guān)研究較少，建立雙層模型來考慮不同決策主體進(jìn)行聯(lián)合優(yōu)化的研究更少。除此之外，LRP是NP難問題，多數(shù)文獻(xiàn)都采用啟發(fā)式算法進(jìn)行求解[7-15]。其中遺傳算法應(yīng)用尤為廣泛，但部分文獻(xiàn)遺傳操作較為簡單[9-10]，多采用單一初始化方式，即隨機(jī)初始化[7，10-11，15]或啟發(fā)式初始化[8，14]，采用單點變異[7，11]或單點交叉[10，15]等算子進(jìn)行交叉變異操作，并通過傳統(tǒng)概率復(fù)制來選擇新種群[10-11，14]。此外，已有文獻(xiàn)采用聚類算法分配需求[10，15-16]，但忽視了容量約束。本文提出改進(jìn)的遺傳算法：使用多種初始化方法，在保持種群多樣性的同時尋求較優(yōu)的初始解；引入最優(yōu)成本路線交叉算子和反向變異算子，減少回收車輛的使用數(shù)量，降低總回收成本的同時[17-18]，增加種群多樣性避免陷入局部最優(yōu)；并在此基礎(chǔ)上通過精英選擇策略保留優(yōu)質(zhì)種群加快迭代速度。

表1 相關(guān)文獻(xiàn)特征Table 1 Characteristics of relevant literature

綜上，目前關(guān)于LRP 的研究已取得了一定的成果，但在收集中心選址及智能垃圾箱回收路徑規(guī)劃方面仍存在不足之處：一方面，將垃圾處理點選址與回收路徑問題整合規(guī)劃的研究較少，且少有學(xué)者研究智能垃圾箱回收問題；另一方面，多數(shù)研究基于遺傳算法求解雙層LRP模型，但存在采用單一初始化方式和個別效果較差的算子等問題，因此有必要對此進(jìn)行改進(jìn)?；诖?，本文研究智能垃圾回收下帶容量約束的雙層選址-路徑整合優(yōu)化問題，考慮了上下層不同決策主體之間復(fù)雜關(guān)系，應(yīng)用智能垃圾收集路徑方式進(jìn)行路徑規(guī)劃，設(shè)計改進(jìn)的遺傳算法進(jìn)行求解，最后通過算例分析驗證了模型和算法的有效性和適用性。

1 問題描述

本文研究一個具有雙決策主體的容量有限的選址-路徑多主體優(yōu)化問題（capacitated location-routing problem，CLRP），建立了雙層規(guī)劃模型來描述該問題。在該模型中，上層決策者依據(jù)給定的收集中心備選點進(jìn)行選址決策；下層決策者首先確定需要收集的智能垃圾箱，當(dāng)垃圾箱內(nèi)垃圾量大于閾值說明垃圾箱容量不足亟待收集，反之則不需收集，其次依照上層決策來規(guī)劃收集路線以確保整體優(yōu)化。

在實際生活中，由于智能回收企業(yè)的業(yè)務(wù)布局范圍較廣，如“小黃狗”和“愛家物聯(lián)”分別進(jìn)駐48、36個城市等，故多是負(fù)責(zé)智能垃圾箱運(yùn)營和維護(hù)等工作，而清理收運(yùn)則多是雇傭當(dāng)?shù)氐奈锪鬟\(yùn)輸公司來負(fù)責(zé)。智能回收企業(yè)在建立回收系統(tǒng)過程中要均衡各方面成本以實現(xiàn)總成本最低，而外包物流公司只關(guān)心其運(yùn)輸相關(guān)成本，故而在進(jìn)行收集中心選址和回收路徑規(guī)劃決策的過程中，存在兩個決策主體，分別是智能回收企業(yè)（上層決策者）和外包物流公司（下層決策者），但二者間存在復(fù)雜的沖突合作關(guān)系，如圖1所示。

首先，智能回收企業(yè)決定收集中心的位置，將直接影響外包物流公司的回收路線計劃。智能回收企業(yè)做出選址決定后，外包物流公司才能根據(jù)閾值確定容量不足的智能垃圾箱，從而規(guī)劃最優(yōu)的收集路線以確保運(yùn)輸相關(guān)成本最小化。其次，外包物流公司的路徑規(guī)劃又將反作用于智能回收企業(yè)的選址決策。外包物流公司規(guī)劃好回收路徑，將會產(chǎn)生運(yùn)輸成本和車輛啟動成本等，這又將會影響企業(yè)總經(jīng)濟(jì)目標(biāo)的實現(xiàn)，從而影響選址決策。顯然，雙層CLRP模型中兩個主體決策行為相互影響。雖然智能回收企業(yè)和外包物流公司都尋求獨立地最小化其目標(biāo)，但又都受到彼此行為的影響，這些決策的相互影響既體現(xiàn)在目標(biāo)函數(shù)中，也體現(xiàn)在約束條件中。

依據(jù)Baldacci 等[19]提出的雙商品流公式，建立多倉庫的選址-車輛路徑模型。其中車輛每條路線都涉及兩種流：一種是車輛從收集中心出發(fā)，最終到達(dá)其副本時的負(fù)載，另一種是同一車輛上對應(yīng)的空載。將該公式引入VRP 模型，可提高精確算法或啟發(fā)式算法求解的收斂速度[20-21]，也可用于建立LRP模型，如爆炸性廢物回收系統(tǒng)的選址-路徑問題[22]。

雙商品流動公式中所提出的基本流動規(guī)律如圖2所示，其中車輛容量Q=1 000，9 個待收集的智能垃圾箱、兩輛車和一個收集中心。雙商品流公式使用兩個流變量yij和yji來模擬車輛穿過邊(i,j)時所攜帶的廢棄物的流，即每條路線由兩條路徑定義：一條由表示車輛載荷的yij流變量表示從節(jié)點0到節(jié)點n+1 的路徑P1；從節(jié)點n+1 到節(jié)點0的第二條路徑P2由表示車輛空白區(qū)域的流變量yji表述。因此，兩種流的總和等于車輛容量，例如y36+y63=1 000。具體來說，以節(jié)點1、3、6和8 之間的流動為例，可以注意到：（1）節(jié)點3 的總流出量減去總流入量等于該節(jié)點產(chǎn)生的廢棄物量的兩倍，即(y31+y36)-(y13+y63)=2m3；（2）收集中心副本n+1 的總流出等于剩余車輛容量，即y(n+1)8=Q-y8(n+1)；（3）收集中心副本n+1 的總流入量等于裝載的廢物總量，即y8(n+1)=m1+m3+m6+m8；（4）yij和yji變量取可行值，其中y13+y31=Q×x131×g1。

圖2 雙商品流示意圖Fig.2 Two-commodity flow formulation representation

2 模型建立

針對以上描述，介紹了建立模型所需的假設(shè)條件和參數(shù)符號，并給出數(shù)學(xué)模型。

2.1 模型假設(shè)

建立雙層選址-路徑問題的數(shù)學(xué)模型所需假設(shè)條件如下所示：

（1）候選收集中心的數(shù)量、地理位置、固定成本已知。

（2）各收集中心容量已知，分配給各收集中心的總需求量不能超過設(shè)施的容量限制。

（3）配送車輛均為同質(zhì)車輛，固定成本和容量已知，各運(yùn)輸路徑上車輛載重不能超過容量限制。

（5）每處收集點（需要收集的智能垃圾柜）的地理位置和所產(chǎn)垃圾量已知。

（6）各節(jié)點間距離按照歐氏距離計算，運(yùn)輸車輛單位距離運(yùn)輸成本已知。

（7）每個站點每次只能被一輛車收集一次，收集車輛從收集中心出發(fā)并最終返回收集中心。

2.2 參數(shù)符號

集合

I：智能垃圾箱集合I={1,2,…,n}；

C：收集中心備選位置集合C={1,2,…,c}；

：收集中心的復(fù)制點{1,2,…}；

G：智能垃圾箱和收集中心的集合G=I?C?

V：同質(zhì)車輛的集合；

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

i/j/m：智能垃圾箱站點和收集中心的索引i,j,m∈G；

k：車輛的索引k∈V；

n：智能垃圾箱總數(shù)，即垃圾產(chǎn)生站點總數(shù)；

c：備選收集中心總數(shù)；

l：同質(zhì)運(yùn)輸車輛總數(shù)；

mi：智能垃圾箱i處所產(chǎn)生垃圾的質(zhì)量i∈I；

Q0：收集中心的額定容量；

Q：車輛的額定載重質(zhì)量；

FCi：收集中心i的固定開放成本i∈C；

VCi：收集中心i的每單位垃圾的處理成本i∈C；

FVk：啟用車輛k的固定成本；

c0：所用車輛的單位運(yùn)輸費(fèi)率；

dij：節(jié)點i和節(jié)點j之間的距離；

φi：智能垃圾箱回收閾值。

決策變量

hi：0-1變量，如果候選收集中心i∈C開放，則為1，否則為0；

gk：0-1變量，如果車輛啟用k∈V，則為1，否則為0；

zik：0-1變量，如果車輛k∈V訪問點i∈I，則為1，否則為0；

yij：表示點i到點j的流量，為非負(fù)數(shù)；

xijk：0-1變量，如果車輛k訪問邊(i,j)，則為1，否則為0。

2.3 數(shù)學(xué)模型

2.3.1 上層規(guī)劃

上層規(guī)劃由智能回收企業(yè)確定收集中心選址，確保由收集中心的開設(shè)成本、運(yùn)營成本、車輛運(yùn)輸成本和車輛固定成本組成的總成本最小化。上層公式如下：

目標(biāo)函數(shù)（1）是總經(jīng)濟(jì)成本最小化，包括收集中心開放成本、操作運(yùn)營成本、車輛運(yùn)輸成本和車輛固定成本。由于每個行程都被定義為包含兩條路徑的車輛路線，因此車輛運(yùn)輸成本需要除以2以獲得真實的運(yùn)輸成本。約束（2）保證收集中心的總數(shù)至少為一個，且滿足約束（3）確保解滿足收集中心容量限制。

2.3.2 下層規(guī)劃

經(jīng)過分析，下層模型是一個車輛路徑規(guī)劃問題。因此，車輛運(yùn)輸相關(guān)成本最小化是外包物流公司的目標(biāo)，包括車輛運(yùn)輸成本和車輛固定成本。其數(shù)學(xué)公式描述如下：

目標(biāo)函數(shù)式（5）表示外包物流公司的總運(yùn)輸成本最低；約束（6）確保每個點的流出量減去流入量等于每個點中廢棄物量的兩倍；約束（7）確保復(fù)制點n+1 的總流入等于所收集的智能垃圾箱中總廢物量；約束（8）確保復(fù)制點總流出量等于車隊的剩余容量；約束（9）保證實際路徑的裝載總量小于或等于車隊的運(yùn)力；約束（10）和（11）根據(jù)回收閾值篩選容量不足的智能垃圾箱，并確保這些需要收集的智能垃圾箱僅由一輛車提供服務(wù)，本文根據(jù)智能垃圾箱i前10 天垃圾投放平均值來估計其每日預(yù)期投放量αi，并定義回收閾值φi=(1-αi/q0)×q0，其中q0為智能垃圾箱額定容量，當(dāng)智能垃圾箱現(xiàn)存垃圾量mi大于φi時，其容量不足難以容納次日投放量，故該智能垃圾箱需要進(jìn)行收集；反之則不需收集該垃圾箱；約束（12）表示每個點都有兩條路徑；約束（13）確保車輛離開收集中心時是空載；約束（14）表示車輛必須完全清空它訪問的所有垃圾箱；約束（15）確保啟用的車輛數(shù)量不超過車隊總數(shù)；約束（16）連接了變量yij和xijk，表示保證如果有車輛訪問邊(i,j)，其流量之和必須等于車輛的通行能力；約束（17）～（20）避免產(chǎn)生非可行解；約束（4）和（21）～（24）給出變量的定義域。

2.3.3 全局模型

垃圾收集的選址路徑問題可以分為兩個層次：智能回收企業(yè)為上層決策者，外包物流公司為下層決策者。在BP 問題中，底層模型也是全局模型的約束。根據(jù)2.3.1和2.3.2小節(jié)，可以得到全局模型如下：

在全局模型中，智能回收企業(yè)決定開設(shè)哪個收集中心（決策變量hm），以實現(xiàn)總成本的全局最小化。外包物流公司先根據(jù)閾值確定亟待收集的智能垃圾箱，進(jìn)而在智能回收企業(yè)決策的基礎(chǔ)上進(jìn)行路徑規(guī)劃。然而，路徑規(guī)劃對智能回收企業(yè)的成本最小化目標(biāo)有著重要的影響。全局模型描述了垃圾回收選址-路徑模型中存在沖突和協(xié)調(diào)的智能回收企業(yè)與外包物流公司之間的相互影響。

2.4 公式有效性

由于雙商品流公式僅用于下層路徑模型，故而本節(jié)證明將該公式引入CVRP模型的有效性。

首先，證明CVRP 的解可滿足雙商品流公式。當(dāng)CVRP 求解得到回收路線時，其變量xijk和yij滿足如下約束：

不妨將不屬于上述CVRP解的邊都設(shè)置成xijk=0，yij=yji=0，此時上述所定義的兩個變量顯見是雙商品流公式的可行解。

3 求解算法

選址路徑多主體優(yōu)化問題求解難度非常大，屬于強(qiáng)NP難問題。目前大多采用啟發(fā)式算法[7-15]求解，如遺傳算法，粒子群算法等，本文提出了一種改進(jìn)的遺傳算法來求解雙層規(guī)劃問題。首先，結(jié)合多種初始化方式以獲得初始解，上層聚類獲得初始選址方案，下層采用隨機(jī)和節(jié)約里程算法獲得初始路徑，確保種群多樣性同時尋求更優(yōu)良的初始解；其次，將最優(yōu)成本路線交叉、反向變異和精英選擇相結(jié)合，改善算法局部搜索能力的同時檢查可行性約束。

3.1 編碼與解碼

上述問題包含垃圾收集中心選址和回收路徑兩個子問題，用三個向量來表示一個完整的解，第一個向量為車輛向量，第二個是順序向量，第三個表示車輛所屬收集中心向量。假設(shè)有8 個備選配送中心，編號為1，2，…，8；可支配車輛4 輛，編號為1、2、3、4；待收集的智能垃圾箱16個，編號為1，2，…，16，回收方案如下：

首先，收集中心向量表示上層選址方案，即選擇2和6，且車輛1、3 從收集中心2 出發(fā)，車輛2、4 從收集中心6 出發(fā)。其次，確定需要收集的智能垃圾箱，不難看出編號為7和13的智能垃圾箱未達(dá)回收閾值，不需要回收。最后，在上層決策的基礎(chǔ)上進(jìn)行回收路徑規(guī)劃，智能垃圾箱編號對應(yīng)位置的車輛向量值表示收集該垃圾箱的車輛，如客戶1、6 和16 由車輛4 收集；車輛向量對應(yīng)的順序向量值表示車輛收集的先后順序，如車輛4先收集垃圾箱1，其次是垃圾箱6，最后是垃圾箱16。因此，上層解碼后得到選址方案為收集中心2和6；下層解碼后得到回收路線，整合上下層解碼得到最終問題的解如下：

3.2 初始化與適應(yīng)度函數(shù)

上層采用聚類算法確定初始選址方案，下層則采用隨機(jī)和節(jié)約里程算法生成初始車輛路徑，其中80%的初始種群是隨機(jī)的，另外20%用節(jié)約里程算法生成[23]。Jammeli 等[16]采用“聚類優(yōu)先，路徑其次”的分層方法來求解回收過程中的分配和路徑方案，Mendoza等[24]使用節(jié)約里程算法生成初始路徑方案來加速算法收斂。在前人研究的基礎(chǔ)上，采用多種初始化方法以期得到一個良好的初始化種群，盡量避免計算資源的浪費(fèi)，也希望種群具有良好的多樣性，降低算法復(fù)雜度且不易陷入局部最優(yōu)。

上層采用聚類算法確定初始選址方案，將多收集中心路徑問題轉(zhuǎn)化為單收集中心路徑問題，從而大幅降低問題的復(fù)雜度。比較常用的方法是根據(jù)智能垃圾箱與收集中心間的距離進(jìn)行分類，但這種方法沒有考慮收集中心容量約束，導(dǎo)致結(jié)果質(zhì)量偏低。為解決這一問題，本文聚類算法考量收集中心容量約束，具體步驟如下：

（1）計算所需最少收集中心個數(shù)knum，在C中隨機(jī)選取knum作為收集中心，其中。

（2）計算各智能垃圾箱i∈I到knum個收集中心的距離，并將其分配給最近的收集中心記為Cknum。

（3）計算每個集合Cknum中的智能垃圾箱數(shù)量，并按降序排序。選擇排名最高且未被選中的收集中心開放。

（4）根據(jù)收集中心容量回收智能垃圾箱。依次累計計算智能垃圾箱i∈Cknum的垃圾量直到超過收集中心容量；Cknum中未被分配的客戶將被分配到下一個開放的收集中心。

節(jié)約里程數(shù)的計算公式為ΔCij=C0i+C0j-Cij。公式的意思是i到j(luò)的節(jié)約里程數(shù)為收集中心到i的距離加上收集中心到j(luò)的距離減去i到j(luò)的距離。節(jié)約里程法計算步驟如下：

（1）作運(yùn)輸里程表，列出收集中心到用戶及用戶間的最短距離。

（2）按節(jié)約里程計算公式求得相應(yīng)的節(jié)約里程數(shù)ΔCij。

（3）把節(jié)約的行程值從大到小排序，放到list中。

（4）檢查各連接點可行性，按照list的順序連接各客戶結(jié)點，最終確定配送線路。

適應(yīng)度函數(shù)要結(jié)合求解問題本身而定，每個染色體的適應(yīng)度值反映目標(biāo)值，據(jù)此判斷個體的優(yōu)劣，從而來進(jìn)行選擇操作。上層決策目標(biāo)為建造、服務(wù)和運(yùn)輸總成本最小，每個備選點的建設(shè)成本已知，下層目標(biāo)為運(yùn)輸相關(guān)成本最小，根據(jù)雙層規(guī)劃理論，上層決策者在決策中占主導(dǎo)地位，上層目標(biāo)是雙層規(guī)劃中的主導(dǎo)目標(biāo)。當(dāng)滿足各約束時，目標(biāo)函數(shù)如公式（1）。

考慮到車輛和收集中心容量約束，對超出容量約束的染色體添加一個足夠大的懲罰值，避免生成非可行解。此外，由于模型為最小化組合優(yōu)化問題，目標(biāo)函數(shù)值越小，對應(yīng)的染色體適應(yīng)度越高，解越優(yōu)良。因此，以上層目標(biāo)函數(shù)值與懲罰函數(shù)值之和的倒數(shù)作為適應(yīng)度函數(shù)。適應(yīng)度函數(shù)如下：

其中，fi表示第i條染色體的適應(yīng)度值，F(xiàn)1i表示對應(yīng)的目標(biāo)函數(shù)值，P1和P2分別表示車輛超載或收集中心容量不足時產(chǎn)生的足夠大的懲罰值，當(dāng)滿足約束時，P1=0,P2=0。

3.3 算法流程

改進(jìn)的GA算法在標(biāo)準(zhǔn)遺傳算法基礎(chǔ)上進(jìn)行改進(jìn)，引入最優(yōu)成本路線交叉算子和反向變異算子確保種群多樣性的同時增加算法的搜索能力，結(jié)合精英策略避免優(yōu)秀個體丟失。改進(jìn)GA算法流程如圖3所示。

圖3 GA-pro算法流程圖Fig.3 Flowchart of GA-pro

算法步驟概括如下：

步驟1輸入計算數(shù)據(jù)，設(shè)置交叉率、變異率等參數(shù)，并初始化種群。其中，初始化種群分為兩部分。上層依據(jù)備選智能垃圾箱信息應(yīng)用聚類算法獲得初始收集中心選址方案；下層依據(jù)回收閾值選定亟待收集的智能垃圾箱，再通過隨機(jī)和節(jié)約里程算法獲得初始回收路徑。

步驟2計算各個個體的適應(yīng)度值，進(jìn)行選擇、交叉和變異操作，并應(yīng)用精英策略形成新種群防止最優(yōu)解退化。其中，對交叉和變異操作進(jìn)行改進(jìn)，采用最優(yōu)成本路線交叉算子和反向變異算子來增加算法的局部搜索能力。

最優(yōu)成本路線交叉：由于交叉操作過程中父代隨機(jī)刪除一條路徑，并在滿足容量約束的前提下將刪除的基因重新插入到局部最優(yōu)位置，最后將所得基因按順序替換父代染色體基因確保編碼為0 的位置不變從而得到子代，因此，該算子可在最小化車輛數(shù)量和成本的同時檢查容量約束[17-18]。用規(guī)模為11 的任意問題實例來解釋該交叉過程，如圖4 所示。首先，根據(jù)所給父代P1 和P2確定各個車輛路徑，如步驟（a）所示P1有三條車輛路線，即3→4→2、6→8→1、5→7，從父代中隨機(jī)各選擇一條路徑。在本例中，選擇P1包含垃圾箱5和7的第三條路徑，以及P2 中包含垃圾箱2 和4 的第二條路徑。其次，從P1 中移除P2 所選路徑包含的垃圾箱。如圖4 步驟（b）所示，從P1 中移除2 和4，從P2 中移除5 和7。隨后，將被刪除的垃圾箱在不違背容量約束的情況下，一個接一個地重新插入到局部最優(yōu)位置如步驟（c），以使整個行程的總成本最小化，其間，插入的順序是隨機(jī)進(jìn)行的。最后，確保0 位置不變的情況下，將得到的染色體按順序替換父代染色體基因獲得子代染色體。

圖4 最優(yōu)成本路線交叉Fig.4 Best cost route crossover operator

反向變異：隨機(jī)選擇兩個位于親本染色體上的變異位置，然后將兩個位點之間的所有基因進(jìn)行反轉(zhuǎn)，得到一個新的后代染色體，以維持種群的多樣性，改善遺傳算法的局部搜索能力[25]。

步驟3判斷是否滿足終止條件，滿足則輸出最優(yōu)解，否則返回步驟2。

4 基準(zhǔn)案例測試

首先，選用兩組LRP 經(jīng)典基準(zhǔn)案例集Prins 等[26]和Barreto等[27]進(jìn)行測試來驗證改進(jìn)的GA算法（GA-pro）性能，兩個案例集均可在http：//prodhonc.free.fr/Instances/instances下載；其次，結(jié)合模擬實際案例，證明雙層模型的合理性。本文構(gòu)建的數(shù)學(xué)模型與算法用MATLAB R2014b 編碼，在Lenovo 小新-14API 2019 計算機(jī)運(yùn)行，具體配置為2.10 GHz Ryzen 5-3500U 處理器，操作系統(tǒng)為Windows 10 64位。

GA算法涉及的參數(shù)主要有迭代次數(shù)、種群規(guī)模、交叉概率、變異概率等參數(shù)。通過一定的實驗測試和文獻(xiàn)參考[7]，設(shè)置迭代次數(shù)為500 代，種群規(guī)模為50，變異概率為0.2，交叉概率為0.75。

選取Prins 等提出的算例中客戶數(shù)為20、50、100 三種規(guī)模大小的總計24 個案例和Barreto 所提出的12 個算例進(jìn)行測試，并與求解結(jié)果較好的GAPSO[7]和BSA算法[28]進(jìn)行對比分析，且調(diào)整算法目標(biāo)成本與各案例中目標(biāo)成本相匹配以更具備可比性，求解結(jié)果如表2和表3所示。BKS為基準(zhǔn)案例已知最優(yōu)解，GA-pro所得結(jié)果為將各案例運(yùn)行10次的最優(yōu)結(jié)果，Gap為各算法最優(yōu)解與BKS的差距百分比。

表2 Prins案例求解結(jié)果Table 2 Solution results of instance Prins

表3 Barreto案例求解結(jié)果Table 3 Solution results of instance Barreto

表2 為Prins 的24 個LRP 基準(zhǔn)案例求解結(jié)果，其中GA-pro在12個案例中求得了最優(yōu)解，另12個案例絕大多數(shù)也可獲得近似最優(yōu)解。當(dāng)顧客規(guī)模小于100 時，GAPSO均能求得最優(yōu)解，而GA-pro稍遜。而在顧客規(guī)模等于100 的12 個案例中，BSA 有4 個案例求得最優(yōu)解，3個案例結(jié)果較另兩個算法更優(yōu)；GAPSO和GA-pro僅求得一個最優(yōu)解，且各有2、3個案例求解結(jié)果優(yōu)于另兩種算法。GA-pro在大中小規(guī)模案例中的表現(xiàn)均介于兩種對比算法之間，且與最優(yōu)解BKS 的差距均值僅為0.419%，由此可見，GA-pro可以在一定程度上較好地解決CLRP問題。

由表3 可以看出，BSA 算法整體表現(xiàn)良好，在大規(guī)模算例中求得結(jié)果更為接近BKS。相比之下，GA-pro求解大規(guī)模算例的能力相對較弱，當(dāng)顧客規(guī)模小于50時都能找到最優(yōu)解，在中大規(guī)模算例中雖不能全部找到最優(yōu)解，但是與其他算法差距不大。從整體來看，GA-pro 在中小規(guī)模案例中表現(xiàn)優(yōu)于BSA，在大規(guī)模案例中表現(xiàn)優(yōu)于GAPSO，具備一定的競爭力。

5 模擬案例

5.1 案例描述

為驗證本文模型的合理性和適用性，擬選用4個備選收集中心，以滿足50 處智能垃圾箱的回收需求。備選收集中心的位置、容量和建設(shè)成本如表4所示。智能垃圾箱位置、需求量和回收閾值如表5 所示，僅列出前15個智能垃圾箱相關(guān)信息為例。根據(jù)實際情況和社會經(jīng)驗，使用的其他參數(shù)設(shè)置如下：車輛容量為1 000 kg，每輛固定成本為400 元，每千米運(yùn)輸費(fèi)用為0.75 元，其他參數(shù)設(shè)置同第4章。

表4 備選收集中心信息表Table 4 Information sheet for alternative collection center

表5 智能垃圾箱部分信息表Table 5 Information sheet for some smart bins

5.2 主從二層結(jié)果分析

5.2.1 智能垃圾收集模式

基于上述數(shù)據(jù)，應(yīng)用智能垃圾收集模式，即先根據(jù)閾值確定需要收集的垃圾箱再對其進(jìn)行路徑規(guī)劃的方式，并運(yùn)用前文提出的改進(jìn)遺傳算法求解本案例，運(yùn)行算法30次，選擇其中最佳優(yōu)化結(jié)果。結(jié)果顯示，開放編號為3 和4 的收集中心，當(dāng)日待收集垃圾箱共24 個，收集中心3 發(fā)出兩輛車，收集中心4 則發(fā)出一輛車進(jìn)行收集，總計成本約為79 437 元，解碼后，上下層路徑優(yōu)化方案如下：

5.2.2 傳統(tǒng)收集模式

本文還求解相同條件下傳統(tǒng)收集方式的選址路徑方案（即每日收集全部垃圾箱）。傳統(tǒng)收集方式選擇開放編號為1和4的收集中心，且各發(fā)出兩輛車，總計成本約為88 700元，解碼后，上下層的路徑優(yōu)化方案如下：

5.2.3 兩種模式對比分析

觀察以上結(jié)果可以看出兩種收集模式下所開放收集中心不同，盡管收集中心1的建造成本及單位運(yùn)營成本在所有備選中心中最低，但在智能垃圾收集模式下顯然不是最佳選擇，無法使總成本達(dá)到最小。這是由于所設(shè)閾值是依據(jù)各處垃圾箱往日投放量來計算，而每處垃圾箱容量相同，使得一部分垃圾箱收集次數(shù)較為頻繁，而收集中心3相比于收集中心1處于此類垃圾箱較為密集的位置，更大可能降低運(yùn)輸成本。

兩種收集模式各成本對比如表6 所示，經(jīng)比較可知，智能垃圾收集模式相比于傳統(tǒng)收集模式節(jié)約成本約9 263元。智能垃圾收集模式下僅開放成本比傳統(tǒng)收集模式高，但其余三項成本皆低于傳統(tǒng)收集模式，其中運(yùn)輸成本尤為顯著，這是由于每日需要收集的垃圾箱減少，使得處理量和運(yùn)輸距離獲得不同程度的減少，從而降低總成本。

表6 兩種收集模式下成本對比Table 6 Cost comparison under two collection modes單位：元

這也表明決策過程中兩個決策主體之間產(chǎn)生了一定沖突，但由于智能回收企業(yè)不僅需要考慮建設(shè)成本和運(yùn)營成本，還需要權(quán)衡運(yùn)輸成本來保證總成本最優(yōu)，因此是下層企業(yè)的決策牽制了上層的決策行為。綜上所述，本文模型應(yīng)用智能垃圾收集路徑方式，依據(jù)閾值篩選需要收集的智能垃圾箱，再求解回收路徑最優(yōu)方案，能夠很大程度降低總成本，減少資源浪費(fèi)。

5.3 算法性能分析

為驗證提出的改進(jìn)GA 算法對于求解帶容量約束的雙層選址路徑模型的性能，將GA-pro 求得的最優(yōu)結(jié)果與標(biāo)準(zhǔn)遺傳算法（GA）、粒子群算法（PSO）和GAPSO混合算法求解結(jié)果進(jìn)行對比分析，每種算法的種群大小為50，最大迭代次數(shù)為800，運(yùn)行算法30次，選擇其中最佳優(yōu)化結(jié)果如表7 所示，算法迭代效果對比如圖5 所示?；谶@些圖表，從收斂速度、求解精度以及運(yùn)算復(fù)雜度三個方面對算法性能進(jìn)行對比分析。

圖5 算法迭代對比圖Fig.5 Comparison for convergence curves

表7 四種算法最優(yōu)結(jié)果對比Table 7 Optimal results for four algorithms

（1）觀察圖5可以看出，GA-pro收斂速度最快，PSO次之，標(biāo)準(zhǔn)GA收斂速度最慢。GA-pro算法于100代左右已收斂到最優(yōu)值附近，在390代左右逐漸收斂于最優(yōu)值；而PSO于120代左右開始收斂于最優(yōu)值附近，在400代左右才逐漸收斂于最優(yōu)值；GAPSO 雖然較早收斂于最優(yōu)值，但其收斂速度較慢。

相比于標(biāo)準(zhǔn)GA 算法，GA-pro 迭代速度更快，最優(yōu)解更佳，這是由于最優(yōu)成本路線交叉算子能夠在確保容量約束的前提下將基因插入到局部最優(yōu)位置，盡量避免非可行解產(chǎn)生的同時獲得更優(yōu)的子代，反向變異算子反轉(zhuǎn)兩個隨機(jī)點位間所有基因可增加種群多樣性，有效提升算法的搜索性能，且精英選擇策略確保優(yōu)良個體能傳遞至下一代，故GA-pro收斂性能遠(yuǎn)優(yōu)于標(biāo)準(zhǔn)遺傳算法。

（2）由表7 可知，四種算法都可以得到各自最優(yōu)結(jié)果。GA-pro 算法求解結(jié)果比標(biāo)準(zhǔn)GA 算法優(yōu)化了3.58%，比PSO 算法優(yōu)化了0.08%，與GAPSO 最優(yōu)解差距僅為0.05%?？梢奊A-pro 算法求解精度明顯高于標(biāo)準(zhǔn)遺傳算法，且相比于結(jié)果最優(yōu)的GAPSO 混合算法差距不大。

（3）在算法復(fù)雜度方面，由于遺傳算法的復(fù)雜度可由適應(yīng)度函數(shù)被調(diào)用的次數(shù)得出，而適應(yīng)度函數(shù)的調(diào)用次數(shù)與種群數(shù)量、種群迭代次數(shù)、交叉率以及變異率相關(guān)[29]。以上變量均為外生給定，且GA-pro 僅在標(biāo)準(zhǔn)遺傳算法基礎(chǔ)上進(jìn)行改進(jìn)，沒有增加額外的復(fù)雜操作，故而在算法復(fù)雜度并沒有改變。

由上述對比分析可知，GA-pro 采用多種初始化方法，引入最優(yōu)成本路線交叉算子、反向變異算子和精英選擇策略沒有增加算法復(fù)雜度的同時提高了搜索性能。綜上，GA-pro 對于求解智能垃圾回收下帶容量約束的雙層選址路徑問題是可行且有效的。

5.4 模型分析

為進(jìn)一步驗證雙商品流選址-路徑模型的有效性，將結(jié)果與傳統(tǒng)選址-路徑模型的求解結(jié)果進(jìn)行對比，如表8所示。采用相同數(shù)據(jù)的情況下，雙商品流選址-路徑模型在最優(yōu)目標(biāo)函數(shù)值和計算時間方面都較傳統(tǒng)模型有所提升。相比于使用GA-pro求解傳統(tǒng)模型，表7中標(biāo)準(zhǔn)GA 求解雙商品流選址-路徑模型的結(jié)果優(yōu)化了1.66%，計算時間也減少了17.71%，這表明僅使用標(biāo)準(zhǔn)GA 求解引入雙商品流公式的選址-路徑模型也能求得良好的結(jié)果。

表8 模型結(jié)果對比Table 8 Comparison of model results

6 結(jié)論

本文研究智能垃圾回收下容量有限的雙層選址-路徑整合優(yōu)化問題。上層智能回收企業(yè)以總成本最小為目標(biāo)做收集中心選址決策；下層外包物流公司以運(yùn)輸相關(guān)成本最小為目標(biāo)，依據(jù)回收閾值選定容量不足的智能垃圾箱進(jìn)行路徑規(guī)劃。設(shè)計改進(jìn)的遺傳算法進(jìn)行求解，GA 算法改進(jìn)如下：（1）運(yùn)用多種方法生成初始種群，上層采用聚類算法處理選址初始化，下層采用隨機(jī)和節(jié)約里程算法生成初始車輛路徑；（2）結(jié)合精英選擇策略，保留優(yōu)秀個體；（3）采用最優(yōu)成本路線交叉算子和反向變異算子維持種群多樣性。

選取Prins 和Barreto 提出的經(jīng)典LRP 基準(zhǔn)案例，驗證GA-pro求解CLRP的能力。將GA-pro結(jié)果與GAPSO和BSA 兩種算法求解結(jié)果進(jìn)行對比分析，結(jié)果表明，GA-pro 在求解小規(guī)模問題時都能找到最優(yōu)解，對于中大規(guī)模問題能求得近似最優(yōu)解，整體求得結(jié)果與最優(yōu)解的差距Gap均值分別為0.42%和1.63%，表現(xiàn)介于兩種對比算法之間，且Prins 算例的大規(guī)模算例中有三個案例的求解結(jié)果優(yōu)于另兩個算法。此外，為探究本文模型與算法的適用性，基于模擬數(shù)據(jù)進(jìn)一步測試。最終結(jié)果表明：（1）智能垃圾收集路徑方式，即先依據(jù)閾值確定亟待收集的垃圾箱再對其規(guī)劃回收路徑可有效降低成本，減少資源浪費(fèi)；（2）GA-pro與其他三種算法的收斂性對比顯示，GA-pro 具有更優(yōu)良的初始解，降低運(yùn)行時間，具備良好的收斂性能；（3）引入雙商品流公式的選址-路徑模型在求解性能方面明顯優(yōu)于傳統(tǒng)的選址-路徑模型。

綜上，本文可為智能垃圾回收下有容量限制的垃圾收集中心選址和路徑規(guī)劃問題提供決策支持?？紤]不同決策主體間的復(fù)雜關(guān)系，引入雙商品流公式建立雙層選址-路徑模型，改進(jìn)遺傳算法進(jìn)行求解，并驗證智能垃圾收集路徑方式能夠有效降低回收成本，對規(guī)劃智能垃圾回收選址-路徑方案具有一定的參考意義。但是也存在一定的局限性，沒有考慮環(huán)境影響和多車型混合回收問題，這些將是下一步的研究方向。