張琦琪，陳群

改進(jìn)分散搜索算法求解包裝廢棄物回收路徑規(guī)劃問題

張琦琪，陳群*

（上海出版印刷高等?？茖W(xué)校，上海 200093）

將包裝廢棄物回收路徑規(guī)劃歸納為一個(gè)帶回路和時(shí)間窗的逆向物流車輛路徑問題（RL-VRPBTW），以最小化回收成本、發(fā)車成本和時(shí)間窗懲罰為聯(lián)合優(yōu)化目標(biāo)進(jìn)行建模。引入“車輛剩余空間回收能力”因素，改進(jìn)經(jīng)典節(jié)約里程算法，求得較好的初始解；基于分散搜索框架，設(shè)計(jì)基于初始解改進(jìn)的分散搜索算法（ISISS），根據(jù)問題模型，采用含0的編碼方式，通過多樣性產(chǎn)生、參考集更新、子集產(chǎn)生、子集合并、解改進(jìn)等5個(gè)步驟實(shí)現(xiàn)算法功能。在“部分回收點(diǎn)分布較密集”的城市型地理場景下，針對快消企業(yè)的低值固廢包裝，生成回收點(diǎn)數(shù)量分別為50、100、200的3種規(guī)模算例，并考慮大小兩種車型進(jìn)行仿真實(shí)驗(yàn)。將ISISS算法與改進(jìn)節(jié)約里程、遺傳和分散搜索3種算法比較后可知，ISISS算法在大規(guī)模包裝廢棄物回收車輛路徑問題上具有更優(yōu)的求解性能。仿真實(shí)驗(yàn)結(jié)果表明，ISISS是一種求解多目標(biāo)大規(guī)模包裝廢棄物回收路徑規(guī)劃問題的較優(yōu)算法。

逆向物流；帶時(shí)間窗和回路的車輛路徑問題；分散搜索；局部搜索

綠色包裝產(chǎn)業(yè)發(fā)展是加快推進(jìn)我國生態(tài)文明建設(shè)的重要一環(huán)。2020年11月，國家發(fā)展改革委、國家郵政局等八部門聯(lián)合發(fā)布了《關(guān)于加快推進(jìn)快遞包裝綠色轉(zhuǎn)型的意見》，明確提出“規(guī)范包裝廢棄物回收和處置”及“提升快遞包裝可回收性能”等要求。廢棄包裝品回收路徑規(guī)劃屬于逆向物流車輛路徑問題，是對傳統(tǒng)車輛路徑問題的擴(kuò)展[1-3]，具有重大的社會(huì)意義?？煜B鎖餐飲網(wǎng)點(diǎn)的食品級包裝固體廢棄物具有材料同質(zhì)、回收量小、批次多且分布不均等特點(diǎn)，企業(yè)對包裝固體廢棄物的回收循環(huán)利用從一定程度上縮減了生產(chǎn)中的物料成本，在提升經(jīng)濟(jì)效益的同時(shí)實(shí)施綠色制造，實(shí)現(xiàn)了社會(huì)效益的增長。由此可見，基于逆向物流理論，研究包裝廢棄物回收路徑規(guī)劃、科學(xué)安排運(yùn)輸回收路線具有較大的現(xiàn)實(shí)意義。

帶回路和時(shí)間窗的逆向物流車輛路徑問題（RL-VRPBTW，Reverse Logistics Vehicle Routing Problem with Backhauls and Time Windows）屬于大規(guī)模組合優(yōu)化問題。Anily等[4]證明逆向物流VRP問題屬于NP難題，精確算法難以在有效時(shí)間內(nèi)求解該類問題，而經(jīng)典啟發(fā)式算法也只能在數(shù)據(jù)規(guī)模較小時(shí)求得一個(gè)近優(yōu)解。隨著遺傳算法、蟻群算法等進(jìn)化計(jì)算方法的出現(xiàn)，逆向物流車輛路徑問題的求解有了新方向。文獻(xiàn)[5]基于貪婪算法，設(shè)計(jì)了初始解改進(jìn)遺傳算法，以求解包裝廢棄物回收車輛路徑問題。文獻(xiàn)[6]設(shè)計(jì)了改進(jìn)蟻群算法，以求解逆向物流車輛路徑問題。文獻(xiàn)[7]考慮了CO2排放量因素，構(gòu)建了逆向物流車輛短路徑優(yōu)化模型，并結(jié)合局部搜索和果蠅算法求解。文獻(xiàn)[8]構(gòu)建了考慮貨架壽命的配送車輛路徑優(yōu)化模型，通過改進(jìn)遺傳算法進(jìn)行求解。以上研究將進(jìn)化計(jì)算與逆向物流問題結(jié)合，從最小化運(yùn)輸成本角度出發(fā)建模求解，有效驗(yàn)證了進(jìn)化算法在解決逆向物流VRP問題上的計(jì)算能力。以上研究未在回收路徑的規(guī)劃過程中考慮車載容量是否有利于回收旅程的問題，因此還需進(jìn)一步研究。

分散搜索[9]（Scatter Search, SS）是一類新型優(yōu)化算法框架，它基于種群的全局搜索策略，利用一系列子方法構(gòu)建新解，既可以提高搜索的集中性，又可以保持種群的多樣性。近年來，將SS與其他搜索策略相結(jié)合，被廣泛應(yīng)用于求解復(fù)雜的生產(chǎn)計(jì)劃調(diào)度問題[10-12]。在VRP問題的研究中，文獻(xiàn)[13]利用分散搜索算法，求解同時(shí)送取貨的隨機(jī)旅行時(shí)間車輛路徑問題。文獻(xiàn)[14]設(shè)計(jì)了分散搜索算法，以求解多配送中心車輛路徑問題。文獻(xiàn)[15]提出一種基于分散搜索的自適應(yīng)記憶編程技術(shù)，以求解多商品多變體的取貨車輛路徑問題。文中針對連鎖餐飲快消企業(yè)對低值固體廢棄包裝品的回收需求，以最小化車輛運(yùn)輸成本、回收中心發(fā)車成本及時(shí)間窗提前或拖期懲罰為聯(lián)合優(yōu)化目標(biāo)，建立整數(shù)規(guī)劃模型，基于運(yùn)輸與回收協(xié)同的理念，引入“車輛剩余空間回收能力”改進(jìn)節(jié)約里程算法（Clarke-Wright, C-W）[16]求得初始解，然后利用局部搜索策略對初始解進(jìn)行多樣化處理，最后根據(jù)分散搜索框架設(shè)計(jì)基于初始解改進(jìn)的分散搜索算法進(jìn)行求解。

1 問題描述與模型建立

1.1 問題描述

可以將連鎖餐飲企業(yè)低值廢棄包裝回收問題抽象為一個(gè)考慮時(shí)間窗約束的帶回路的逆向物流車輛路徑問題（RL-VRPBTW）。具體描述如下：完全連接網(wǎng)絡(luò)=(0,)，其中節(jié)點(diǎn)集合為0，節(jié)點(diǎn)0表示回收中心，集合=0{0}表示回收節(jié)點(diǎn)集合，中各節(jié)點(diǎn)均有回收需求P，且每個(gè)節(jié)點(diǎn)的需求服務(wù)受到時(shí)間窗[E,L]的約束；有向邊集合是0的二元子集，∈，(v,v)。假設(shè)車輛載重在回收過程中不變，車輛在有向邊(v,v)上勻速行駛，且所有車輛的載重上限相同，每輛車的行駛總時(shí)間不超過事先確定的最大值；車輛從回收中心空車出發(fā)，從回收點(diǎn)取貨，每個(gè)回收點(diǎn)有且僅有1輛車服務(wù)1次；不考慮車輛在回收點(diǎn)的服務(wù)時(shí)間，車輛如提前于時(shí)間窗到達(dá)回收點(diǎn)，需等待；當(dāng)超過車載上限或最大行駛時(shí)間限制時(shí)返回回收中心，直到服務(wù)完所有回收點(diǎn)。廢棄包裝回收路徑規(guī)劃需要解決的問題是在滿足所有節(jié)點(diǎn)回收需求、時(shí)間窗約束、車輛載重限制及車輛行駛時(shí)間限制等前提下，如何安排車輛的行駛路徑，使得回收中心的回收成本最小。

1.2 符號說明

符號說明：表示所有回收點(diǎn)集合；0表示區(qū)域內(nèi)所有節(jié)點(diǎn)集合，節(jié)點(diǎn)包括回收中心和回收點(diǎn)，0∪{0}；表示所有車輛集合；D表示2個(gè)節(jié)點(diǎn)與之間的歐幾里得距離，其中∈0；v表示車輛在節(jié)點(diǎn)與之間的行駛速度；t表示車輛在節(jié)點(diǎn)與之間的行駛時(shí)間，t=D/v；C表示車輛在節(jié)點(diǎn)與之間的行駛成本，假設(shè)車輛的單位行駛成本為1，則有C=t；C表示車輛的發(fā)車成本；P表示回收點(diǎn)的回收量；[E,L]表示節(jié)點(diǎn)的時(shí)間窗，其中[0,0]為回收中心節(jié)點(diǎn)0開啟服務(wù)的時(shí)間窗；q表示車輛訪問完節(jié)點(diǎn)后在訪問節(jié)點(diǎn)之前的載重量；Q表示車輛的載重上限；B表示車輛行駛的總時(shí)間上限；表示回收中心允許選擇的最小車輛數(shù)量；表示提前到達(dá)的懲罰系數(shù)；表示延期到達(dá)的懲罰系數(shù)。

定義決策變量：x表示0-1變量，車輛從節(jié)點(diǎn)行駛到節(jié)點(diǎn)時(shí)為1，否則為0；z表示0-1變量，節(jié)點(diǎn)由車輛服務(wù)為1，否則為0；t表示車輛到達(dá)節(jié)點(diǎn)的時(shí)間。

以上描述中，∈0，∈,且=|0|，=||。

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

考慮上述問題，建立模型，見式（1）～（12）。

s. t.

(11)

其中，式（1）為目標(biāo)函數(shù)，由3個(gè)部分構(gòu)成，第1部分為回收中心的發(fā)車成本；第2部分為車輛的回收成本；第3部分為軟時(shí)間窗懲罰，對不能按要求到達(dá)回收點(diǎn)（提前或拖期）的情況給予懲罰。式（2）確保每個(gè)回收節(jié)點(diǎn)都會(huì)被服務(wù)1次且僅有1次。式（3）確保到達(dá)每個(gè)節(jié)點(diǎn)并離開的是同一輛車。式（4）確保車輛從回收中心出發(fā)，最終返回回收中心。式（5）表示車輛上的回收總數(shù)量不超過載重限額的約束。式（6）確保車輛的總行駛時(shí)間（包括提前到達(dá)的等待時(shí)間）不超過行駛時(shí)間上限。式（7）表示奇異子回路排除約束。式（8）確保車輛的最終回收載重量等于它訪問的所有回收點(diǎn)回收數(shù)量之和。式（9）表示車輛在訪問節(jié)點(diǎn)前后的載重量約束。式（10）確保每個(gè)節(jié)點(diǎn)的回收量不大于車載上限。式（11）～（12）表示決策變量取值范圍約束。

2 算法設(shè)計(jì)

在分散搜索框架下，基于初始解改進(jìn)的分散搜索算法（Initial Solution Improvement Scatter Search algorithm, ISISS）由5個(gè)計(jì)算步驟組成，分別是多樣性產(chǎn)生、參考集更新、子集產(chǎn)生、子集合并和解改進(jìn)等。SS只是一個(gè)柔性框架，其中每個(gè)步驟都可以根據(jù)實(shí)際問題利用多種方法實(shí)現(xiàn)，這就使SS在擁有進(jìn)化算法交叉和變異等功能的同時(shí)，還可以通過控制分散和收斂聚集，提升算法的收斂性和全局覆蓋能力。

2.1 多樣化初始解

采用含0的整數(shù)編碼方式，0表示回收中心，自然數(shù)為路徑上回收點(diǎn)的編號。比如編碼0102030405060708090，表示解中有9條路徑，每條路徑上只有1個(gè)回收點(diǎn)。

首先利用改進(jìn)的節(jié)約里程算法生成模型的一個(gè)初始解，記作CW解。節(jié)約里程算法的基本思想：首先，使每個(gè)回收點(diǎn)與回收中心單獨(dú)連接，構(gòu)造出(?1)條路徑；然后，基于三角不等式關(guān)系，對初始解進(jìn)行縮小總距離處理，基于路徑間合并可以節(jié)約距離，計(jì)算任意2個(gè)回收點(diǎn)組合對應(yīng)的節(jié)約值Save()，將所有節(jié)約值從大到小排序，依序構(gòu)造路線，對滿足條件的回收點(diǎn)進(jìn)行連接，直到滿足約束條件為止，得到問題的一個(gè)CW解。

文中主要研究廢棄包裝回收問題，將節(jié)約值統(tǒng)一在時(shí)間尺度上進(jìn)行考量，同時(shí)將車輛行駛過程中的“剩余空間回收能力”引入節(jié)約值的計(jì)算，即越有利于接下來回收裝載的回收點(diǎn)，應(yīng)該盡早插入當(dāng)前回收路徑中，根據(jù)行車運(yùn)輸時(shí)間和回收點(diǎn)的回收量計(jì)算回收點(diǎn)兩兩之間的節(jié)約值，見式（13）。

式中：Save()為路線上插入回收點(diǎn)后的節(jié)約值；()為2個(gè)回收點(diǎn)間的行駛時(shí)間；λP表示從回收中心出發(fā)，僅訪問回收點(diǎn)的車載空間損失（或收益）；為懲罰因子。

必須指出，以上節(jié)約里程算法只能生成一個(gè)較好解，且不能作為進(jìn)化算法的初始解集合，需設(shè)計(jì)多樣化策略，形成初始解集合。這里通過隨機(jī)交換CW解中任意2個(gè)回收點(diǎn)的方法，產(chǎn)生個(gè)初始解。由于采用含0的編碼方式，在CW解中任意交換回收節(jié)點(diǎn)可能導(dǎo)致生成的新解不滿足模型的約束條件，必須重新根據(jù)車載上限約束式（5）和行駛時(shí)間最大上限約束式（6）等，對產(chǎn)生的新解進(jìn)行修復(fù)。由于回收點(diǎn)的位置選擇具有隨機(jī)性，所以在保證初始解是較好解的同時(shí)，隨著回收點(diǎn)規(guī)模的增大，還可以保證初始解的多樣性。

2.2 參考解更新

參考集由高質(zhì)量的解子集1和多樣性解子集2兩部分構(gòu)成。1由整個(gè)種群的解目標(biāo)值從小到大排序決定。2根據(jù)種群中所有解與高質(zhì)量解子集的距離決定，距離越大則多樣性越好。參考集更新步驟如下。

1）根據(jù)目標(biāo)函數(shù)，計(jì)算整個(gè)種群所有解的目標(biāo)值，并從小到大排序，取前|1|個(gè)解，加入?yún)⒖技小?/p>

2）計(jì)算種群中剩余解(?1)與子集1中解的距離。遍歷種群的所有剩余解，對于任意一個(gè)剩余解，計(jì)算解中所有有向邊的數(shù)量，記作s。計(jì)算高質(zhì)量子集1中任意一個(gè)解所有有向邊的數(shù)量，記作s，并計(jì)算解與解中相同的邊數(shù)量，記作s。根據(jù)式（14）計(jì)算剩余解對于高質(zhì)量解集合1的距離。取剩余解中距離最大的|2|個(gè)解加入?yún)⒖技小?/p>

2.3 子集產(chǎn)生與子集合并

1）首先去掉每個(gè)子集2個(gè)解中的所有0，在回收節(jié)點(diǎn)長度范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)交換基因位。

2）保留其中一個(gè)解的前段，并在另一解中去除已保留的回收節(jié)點(diǎn)，將剩余的回收節(jié)點(diǎn)按原順序排于保留路徑之后。具體合并過程如圖1所示。

3）根據(jù)車載上限，車輛最大行駛時(shí)間上限等約束在新解中重新插入0。

4）比較原解1、原解2、新解1、新解2的目標(biāo)值，保留目標(biāo)值最小的那個(gè)解到下一代種群。

圖1 子集合并過程

2.4 解改進(jìn)方法

由于文中采用含0的編碼設(shè)置，因此在解的改進(jìn)時(shí)可以考慮“路徑內(nèi)部”的隨機(jī)交換回收點(diǎn)（局部搜索策略1），以及“路徑之間”的隨機(jī)交換回收點(diǎn)（局部搜索策略2）這2種局部搜索改進(jìn)策略。

2.4.1 局部搜索策略1

遍歷整個(gè)種群，針對種群中的任意解進(jìn)行如下步驟。

1）隨機(jī)選擇一條回收路徑上的2個(gè)不同的點(diǎn)，如果2個(gè)回收點(diǎn)之間含0，或者回收點(diǎn)本身為0，則繼續(xù)隨機(jī)選擇。

2）將行駛路徑上這2個(gè)回收點(diǎn)之間所有回收點(diǎn)的車輛行駛方向逆轉(zhuǎn)，得到一個(gè)新解。

3）計(jì)算新解的目標(biāo)值，如果目標(biāo)值優(yōu)于原解，則保留新解；否則不保留此新解。

局部搜索策略1只在解的一條路徑內(nèi)部進(jìn)行，因此不需要考慮車輛的最大負(fù)載上限和車輛最大行駛時(shí)間上限等約束，相當(dāng)于在原解的鄰域進(jìn)行搜索，在解改進(jìn)時(shí)不考慮會(huì)產(chǎn)生非可行解的情況。

2.4.2 局部搜索策略2

遍歷整個(gè)種群，針對種群中的任意解進(jìn)行如下步驟。

1）隨機(jī)選擇2條回收路徑上的2個(gè)非0回收點(diǎn)，交換回收點(diǎn)在解中的基因位置。

2）去掉解中所有的0，采用窮盡車載上限及最大車輛行駛時(shí)間的方式，即能夠納入前一輛車的回收點(diǎn)盡量納入前一條行駛路線，重新插入0，得到一個(gè)新解。

3）計(jì)算新解的目標(biāo)值，如果目標(biāo)值優(yōu)于原解，則保留新解；否則不保留此新解。

局部搜索策略2在一個(gè)解的多條路徑之間隨機(jī)選擇交換點(diǎn)，擴(kuò)大了搜索空間中這個(gè)解的鄰域范圍。由于交換路徑間的回收點(diǎn)可能導(dǎo)致車載上限或車輛最大行駛時(shí)間上限等約束不滿足的情況出現(xiàn)，所以需要重新判斷解的可行性，對非可行情況進(jìn)行修復(fù)。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證文中提出的ISISS算法在包裝廢棄物回收路徑規(guī)劃問題中的有效性，以“部分回收點(diǎn)分布較密集”的類似市區(qū)分布為地理場景，針對連鎖餐飲快消企業(yè)對低值固廢包裝品的回收需求量級，利用Dethloff[17]和Solomon[18]提出的測試數(shù)據(jù)和時(shí)間窗生成方法，隨機(jī)生成分別包含50、100、200個(gè)回收點(diǎn)的3種規(guī)模，且最小車輛數(shù)為3或8的各10組樣本數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)。

3.1 算例生成方法

以100個(gè)回收點(diǎn)測試規(guī)模為例，在“部分回收點(diǎn)分布較密集”的地理場景下，利用Dethloff隨機(jī)測試算例生成方法，首先在區(qū)間[0, 100]的二維正方形區(qū)域內(nèi)，以均勻分布方式隨機(jī)生成50個(gè)回收點(diǎn)的坐標(biāo)；50個(gè)回收點(diǎn)坐標(biāo)在[100/3, 200/3]的二維正方形區(qū)域內(nèi)，以均勻分布方式隨機(jī)生成，從而在1/9的區(qū)域內(nèi)生成密集的市區(qū)配置地理場景。由于這里只考慮了回收問題，每個(gè)回收點(diǎn)的廢棄包裝回收量P=（0.5+r）R，其中R為均勻分布在[0, 100]之間的整數(shù)，r為[0, 1]之間的隨機(jī)數(shù)。由此，確定每個(gè)算例的車載限額=∑P/。其中，∑P表示所有回收點(diǎn)的回收總量，為允許選擇的最小車輛數(shù)量，這里選擇為3或8生成算例。本算例的數(shù)據(jù)無實(shí)際物理意義，是在[0, 100]區(qū)間生成的，因此相應(yīng)的目標(biāo)值也無量綱。

關(guān)于時(shí)間窗的生成，參照Solomon提出的VRPTW基準(zhǔn)數(shù)據(jù)生成方法，時(shí)間窗的中間值在區(qū)間(00,i,0-t,0)中隨機(jī)生成，且時(shí)間窗寬度為標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)，其中[0,0]為回收中心進(jìn)行回收服務(wù)的時(shí)間窗，0, i和t,0分別表示車輛從回收中心到回收點(diǎn)的行駛時(shí)間和該回收點(diǎn)回到回收中心的行駛時(shí)間。在模型中假設(shè)回收中心時(shí)間窗[0,0]為[0, 24]，所有車輛的發(fā)車成本C為50，所有車輛的行駛速度v為60，提前到達(dá)或延期到達(dá)回收點(diǎn)的懲罰系數(shù)、均為1。

3.2 算法比較

為了驗(yàn)證ISISS算法的求解性能，與改進(jìn)的節(jié)約里程（C-W）、分散搜索（SS）和遺傳（Genetic Algorithm, GA）等3種算法進(jìn)行對比。其中，SS和GA的初始解均采用隨機(jī)初始解，GA的交叉率c為0.6，變異率m為0.1，種群規(guī)模為100，運(yùn)行代數(shù)為20 000；SS和ISISS算法的參考集|=20，其中較好解集|1=10，多樣解集|2=10，種群規(guī)模為100，運(yùn)行代數(shù)為100。由于GA與SS算法在迭代方式上存在不同，2種算法無法基于相同的迭代次數(shù)進(jìn)行比較，因此將2種算法在種群規(guī)模相同且運(yùn)算時(shí)間大致相同的前提下對不同規(guī)模的算例進(jìn)行比較。對比了3種規(guī)模下，最小車輛數(shù)量分別為3或8的各10組數(shù)據(jù)目標(biāo)值平均計(jì)算結(jié)果，如圖2所示。

圖2 3種規(guī)模下目標(biāo)值的比較

由圖2可知，相對于改進(jìn)C-W算法生成的較好解，其他3種進(jìn)化算法的求解優(yōu)勢明顯。當(dāng)回收點(diǎn)數(shù)量為50時(shí)，GA求得的目標(biāo)值僅略優(yōu)于C-W算法，而SS和ISISS算法求得的目標(biāo)值明顯優(yōu)于C-W，說明在相同的數(shù)據(jù)規(guī)模和計(jì)算復(fù)雜度下，ISISS算法能夠充分發(fā)揮參考集更新和解改進(jìn)等策略的優(yōu)勢，但I(xiàn)SISS相對于隨機(jī)初始解SS的改進(jìn)效果并不顯著。當(dāng)回收點(diǎn)數(shù)量擴(kuò)大為100時(shí)，選擇較大的車型（3）時(shí)，ISISS相對于GA的改進(jìn)幅度達(dá)到了65.8%，相對于SS的改進(jìn)率也很明顯；選擇較小車型（8）時(shí)，ISISS相對于SS的改進(jìn)效果仍不夠顯著。隨著數(shù)據(jù)規(guī)模的進(jìn)一步擴(kuò)大，當(dāng)回收點(diǎn)為200時(shí)，ISISS算法在2種車型選擇下的改進(jìn)效果才顯示出來。由于ISISS在初始解生成時(shí)就采用C-W啟發(fā)式算法生成了較好的初始解，并在此基礎(chǔ)上進(jìn)行了多樣化處理，因此ISISS具有更優(yōu)的多樣性解和較好解，從而增強(qiáng)了算法的尋優(yōu)能力，更加適合于求解大規(guī)?；厥哲囕v路徑問題。

另一方面，從4種算法得出的發(fā)車數(shù)量（表1）比較結(jié)果可以看出，在不同規(guī)模下，C-W算法都可以得到較少的發(fā)車數(shù)量，但這是以高額的時(shí)間窗懲罰和回收成本為代價(jià)，ISISS算法可以在同時(shí)考慮回收成本和時(shí)間窗懲罰的基礎(chǔ)上，將回收中心總發(fā)車數(shù)量控制在一個(gè)較小的數(shù)量上。當(dāng)回收點(diǎn)為50、100時(shí)，ISISS得到的發(fā)車數(shù)量（4、9）僅比對應(yīng)的最小車輛數(shù)（3、8）多1輛車，而隨機(jī)初始解的GA和SS都無法達(dá)到這個(gè)發(fā)車數(shù)量，說明對于同一個(gè)回收路徑規(guī)劃問題，ISISS可以更好地發(fā)揮已派出車輛的裝載率，從而降低總用車數(shù)量。

文中將時(shí)間窗懲罰引入優(yōu)化目標(biāo)，而非單純采用運(yùn)輸成本。表2列出了GA、SS、ISISS等3種算法在不同數(shù)據(jù)規(guī)模下3個(gè)具體算例C50-3、C100-3、C200-3的目標(biāo)值分項(xiàng)。數(shù)據(jù)表明，相對于隨機(jī)初始解的GA、SS算法，ISISS算法能夠得到更優(yōu)的可行解，找到了滿足約束且在不同的目標(biāo)上表現(xiàn)更好的解。當(dāng)回收點(diǎn)數(shù)量較小時(shí)，ISISS在運(yùn)輸成本和提前拖期懲罰2項(xiàng)目標(biāo)值上比隨機(jī)初始解SS略有改進(jìn)，但并不明顯；當(dāng)回收點(diǎn)數(shù)量增至200時(shí)，ISISS除了能達(dá)到更好的運(yùn)輸成本，同時(shí)還能盡可能地滿足不同回收點(diǎn)服務(wù)時(shí)間窗的要求，大幅降低了時(shí)間窗提前拖期懲罰目標(biāo)，并減少了發(fā)車數(shù)量，降低了發(fā)車成本。

表1 發(fā)車數(shù)量比較

Tab.1 Comparison of the number of departures

表2 基于算例C50-3、C100-3、C200-3的3種算法目標(biāo)值分項(xiàng)比較

Tab.2 Itemized comparison of the objective values based on C50-3, C100-3 and C200-3

3.3 路線明細(xì)

在回收點(diǎn)為100、最小車輛數(shù)量為3時(shí)，算例C100-3的一次路徑規(guī)劃明細(xì)如表3所示，對應(yīng)的回收路徑規(guī)劃如圖3所示。

表3 算例C100-3路徑排序

Tab.3 Route sorting of C100-3

圖3 ISISS求得算例C100-3的一個(gè)較好解

隨著回收點(diǎn)數(shù)量的增多，ISISS算法仍然可以將規(guī)劃車輛數(shù)控制在4輛車，前3輛車的車輛負(fù)載都盡可能充分利用，基本接近車載上限，且從路徑規(guī)劃（圖3）可以看出，在“部分回收點(diǎn)分布較密集”的地理場景下，ISISS算法能夠在一輛車的路徑規(guī)劃上兼顧市區(qū)密集部分點(diǎn)和郊區(qū)零散分布點(diǎn)，各條路徑彼此重疊覆蓋的區(qū)域較少，且各條路線上的交叉回路較少。在相同的回收點(diǎn)分布下，選擇較小的車型（8）時(shí)，算例C100-8的路徑規(guī)劃如圖4所示，對應(yīng)的路徑排序如表4所示。

圖4 ISISS求得算例C100-8的一個(gè)較好解

表4 算例C100-8路徑排序

Tab.4 Route sorting of C100-8

4 結(jié)語

從廢棄包裝品回收的實(shí)際問題出發(fā)，研究了逆向物流車輛路徑規(guī)劃問題，將軟時(shí)間窗約束轉(zhuǎn)化為逆向物流車輛路徑問題的優(yōu)化目標(biāo)，以最小化運(yùn)輸成本、發(fā)車成本和時(shí)間窗懲罰成本為目標(biāo)，建立了帶回路的車輛路徑問題聯(lián)合優(yōu)化數(shù)學(xué)模型。采用含0的整數(shù)編碼，同時(shí)考慮車輛旅行時(shí)間節(jié)約值和車輛剩余回收空間收益兩方面因素，確定節(jié)約值，利用改進(jìn)的節(jié)約里程算法得到一個(gè)初始解，并設(shè)計(jì)初始解多樣化策略，生成初始解集合?；诟倪M(jìn)的優(yōu)質(zhì)多樣性初始解，利用分散搜索進(jìn)化算法求解。針對“部分回收點(diǎn)分布較密集”的類似市區(qū)型地理場景生成多組算例，在不同的數(shù)據(jù)規(guī)模下驗(yàn)證算法的性能。下一步將對ISISS算法在同時(shí)送取貨的回收場景及考慮回收服務(wù)時(shí)間的路徑規(guī)劃問題進(jìn)行研究。

[1] GAO Z H, YE C Y. Reverse Logistics Vehicle Routing Optimization Problem Based on Multivehicle Recycling[J]. Mathematical Problems in Engineering, 2021, 2021: 5559684.

[2] ALIZADEH FOROUTAN R, REZAEIAN J, MAHDAVI I. Green Vehicle Routing and Scheduling Problem with Heterogeneous Fleet Including Reverse Logistics in the Form of Collecting Returned Goods[J]. Applied Soft Computing, 2020, 94: 106462.

[3] HAN Y. Evolutionary Algorithms for the Heterogeneous Fleet Green Vehicle Routing Problem with Reverse Logistics Characteristics[J]. Journal of the Korean Society of Supply Chain Management, 2017, 17(2): 133-143.

[4] ANILY S, MOSHEIOV G. The Traveling Salesman Problem with Delivery and Backhauls[J]. Operations Research Letters, 1994, 16(1): 11-18.

[5] 張異. 包裝廢棄物回收車輛路徑問題的改進(jìn)遺傳算法[J]. 包裝工程, 2018, 39(17): 147-152. ZHANG Y. Improved Genetic Algorithm for Vehicle Routing Problem in Packaging Waste Recycling[J]. Packaging Engineering, 2018, 39(17): 147-152.

[6] 陳秀娟, 高更君, 馮媛媛. 基于改進(jìn)蟻群算法的逆向物流車輛路徑優(yōu)化[J]. 制造業(yè)自動(dòng)化, 2019, 41(5): 46-49. CHEN X J, GAO G J, FENG Y Y. Optimization of Reverse Logistics Vehicle Path Based on Improved Ant Colony Algorithm[J]. Manufacturing Automation, 2019, 41(5): 46-49.

[7] 趙嬈, 陳志華. 基于局部搜索的逆向物流車輛最短路徑優(yōu)化[J]. 計(jì)算機(jī)仿真, 2022, 39(11): 215-219. ZHAO R, CHEN Z H. Shortest Path Optimization of Reverse Logistics Vehicle Based on Local Search[J]. Computer Simulation, 2022, 39(11): 215-219.

[8] 楊瑋, 趙晶, 張堃, 等. 基于貨架壽命的乳制品配送車輛路徑優(yōu)化研究[J]. 包裝工程, 2019, 40(11): 72-79. YANG W, ZHAO J, ZHANG K, et al. Path Optimization of Dairy Distribution Vehicle Based on Shelf Life[J]. Packaging Engineering, 2019, 40(11): 72-79.

[9] GLOVER F. A Template for Scatter Search and Path Relinking[M]// Lecture Notes in Computer Science. Berlin: Springer Berlin Heidelberg, 1998: 1-51.

[10] KALRA M, TYAGI S, KUMAR V, et al. A Comprehensive Review on Scatter Search: Techniques, Applications, and Challenges[J]. Mathematical Problems in Engineering, 2021, 2021: 5588486.

[11] 毛麗麗, 張則強(qiáng), 朱立夏. 混合模擬退火及分散搜索優(yōu)化過道布置問題[J]. 計(jì)算機(jī)工程與應(yīng)用, 2018, 54(3): 243-249. MAO L L, ZHANG Z Q, ZHU L X. Hybrid Scatter Search Algorithm with Simulated Annealing for Corridor Allocation Problem[J]. Computer Engineering and Applications, 2018, 54(3): 243-249.

[12] 范佳靜, 曹玉華, 曹敏. 基于改進(jìn)分散搜索算法的多資源跨單元調(diào)度問題研究[J]. 中國機(jī)械工程, 2017, 28(22): 2722-2731. FAN J J, CAO Y H, CAO M. Study on Multi-Resource Intercellular Scheduling Problem Based on ASS Algorithm[J]. China Mechanical Engineering, 2017, 28(22): 2722-2731.

[13] 張濤, 余綽婭, 劉嵐, 等. 同時(shí)送取貨的隨機(jī)旅行時(shí)間車輛路徑問題方法[J]. 系統(tǒng)工程理論與實(shí)踐, 2011, 31(10): 1912-1920.ZHANG T, YU C Y, LIU L, et al. Method for the Stochastic Traveling Time VRPSPD Problem[J]. Systems Engineering-Theory & Practice, 2011, 31(10): 1912-1920.

[14] 張鵬威, 李英, 成琪. 有限充電設(shè)施下的多配送中心電動(dòng)車輛路徑問題研究[J]. 工業(yè)工程與管理, 2019, 24(5): 97-105. ZHANG P W, LI Y, CHENG Q. Multi-Depot Electric Vehicle Routing Problem under Limited Recharging Infrastructures[J]. Industrial Engineering and Management, 2019, 24(5): 97-105.

[15] EUCHI J. Hybrid Adaptive Memory Programming to Optimize the Multi-Commodity many to many Vehicle Routing Problem[J]. International Journal of Mathematics in Operational Research, 2020, 1(1): 1.

[16] CLARKE G, WRIGHT J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research, 1964, 12(4): 568-581.

[17] DETHLOFF J. Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up[J]. OR-Spektrum, 2001, 23(1): 79-96.

[18] SOLOMON M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research, 1987, 35(2): 254-265.

Improved Scatter Search Algorithm to Solve Packaging Waste Recovery Vehicle Routing Problem

ZHANG Qiqi,CHEN Qun*

(Shanghai Publishing and Printing College, Shanghai 200093, China)

The work aims to summarize the packaging waste recovery routing as a reverse logistics vehicle routing problem with back path and time window (RL-VRPBTW), so as to construct a model with the minimum recovery cost, departure cost and time window penalty as the joint optimization objective. A better initial solution was obtained by introducing the factor of "vehicle remaining space recovery ability" to improve the classical heuristic C-W algorithm. Based on the Scatter Search framework, a Scatter Search algorithm (ISISS) based on initial solution improvement was designed. According to the problem model, the algorithm functions were realized through five steps of diversity generation method, reference set update method, subset generation, merging method and solution improvement method. In the city-type geographical scenario of "dense distribution of some recovery points", three scale examples with 50, 100 and 200 recovery nodes were randomly generated, and two vehicle types were considered for simulation experiments. The ISISS algorithm was compared with C-W, GA and SS algorithms to verify that the algorithm proposed had better performance in solving the routing problem of large-scale packaging waste recovery vehicles. The simulation results indicate that ISISS is a better algorithm to solve the multi-objective large-scale packaging waste recovery routing problem.

reverse logistics; vehicle routing problem with time windows and back path; scatter search; local search

TP301；TB498

A

1001-3563(2024)09-0193-08

10.19554/j.cnki.1001-3563.2024.09.025

2023-06-28

國家社科基金（18BT058）；國家新聞出版署“智能與綠色柔版印刷”重點(diǎn)實(shí)驗(yàn)室項(xiàng)目（KLIGFP-01)；上海市東方學(xué)者特聘教授基金（TP2022126）