改進分散搜索算法求解包裝廢棄物回收路徑規劃問題

張琦琪，陳群

改進分散搜索算法求解包裝廢棄物回收路徑規劃問題

張琦琪，陳群*

（上海出版印刷高等專科學校，上海 200093）

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

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

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

1.2 符號說明

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

定義決策變量：x表示0-1變量，車輛從節點行駛到節點時為1，否則為0；z表示0-1變量，節點由車輛服務為1，否則為0；t表示車輛到達節點的時間。

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

1.3 數學模型

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

s. t.

(11)

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

2 算法設計

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

2.1 多樣化初始解

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

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

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

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

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

2.2 參考解更新

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

1）根據目標函數，計算整個種群所有解的目標值，并從小到大排序，取前|1|個解，加入參考集中。

2）計算種群中剩余解(?1)與子集1中解的距離。遍歷種群的所有剩余解，對于任意一個剩余解，計算解中所有有向邊的數量，記作s。計算高質量子集1中任意一個解所有有向邊的數量，記作s，并計算解與解中相同的邊數量，記作s。根據式（14）計算剩余解對于高質量解集合1的距離。取剩余解中距離最大的|2|個解加入參考集中。

2.3 子集產生與子集合并

1）首先去掉每個子集2個解中的所有0，在回收節點長度范圍內隨機產生一個交換基因位。

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

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

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

圖1 子集合并過程

2.4 解改進方法

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

2.4.1 局部搜索策略1

遍歷整個種群，針對種群中的任意解進行如下步驟。

1）隨機選擇一條回收路徑上的2個不同的點，如果2個回收點之間含0，或者回收點本身為0，則繼續隨機選擇。

2）將行駛路徑上這2個回收點之間所有回收點的車輛行駛方向逆轉，得到一個新解。

3）計算新解的目標值，如果目標值優于原解，則保留新解；否則不保留此新解。

局部搜索策略1只在解的一條路徑內部進行，因此不需要考慮車輛的最大負載上限和車輛最大行駛時間上限等約束，相當于在原解的鄰域進行搜索，在解改進時不考慮會產生非可行解的情況。

2.4.2 局部搜索策略2

遍歷整個種群，針對種群中的任意解進行如下步驟。

1）隨機選擇2條回收路徑上的2個非0回收點，交換回收點在解中的基因位置。

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

3）計算新解的目標值，如果目標值優于原解，則保留新解；否則不保留此新解。

局部搜索策略2在一個解的多條路徑之間隨機選擇交換點，擴大了搜索空間中這個解的鄰域范圍。由于交換路徑間的回收點可能導致車載上限或車輛最大行駛時間上限等約束不滿足的情況出現，所以需要重新判斷解的可行性，對非可行情況進行修復。

3 仿真實驗

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

3.1 算例生成方法

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

關于時間窗的生成，參照Solomon提出的VRPTW基準數據生成方法，時間窗的中間值在區間(00,i,0-t,0)中隨機生成，且時間窗寬度為標準正態分布隨機數，其中[0,0]為回收中心進行回收服務的時間窗，0, i和t,0分別表示車輛從回收中心到回收點的行駛時間和該回收點回到回收中心的行駛時間。在模型中假設回收中心時間窗[0,0]為[0, 24]，所有車輛的發車成本C為50，所有車輛的行駛速度v為60，提前到達或延期到達回收點的懲罰系數、均為1。

3.2 算法比較

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

圖2 3種規模下目標值的比較

由圖2可知，相對于改進C-W算法生成的較好解，其他3種進化算法的求解優勢明顯。當回收點數量為50時，GA求得的目標值僅略優于C-W算法，而SS和ISISS算法求得的目標值明顯優于C-W，說明在相同的數據規模和計算復雜度下，ISISS算法能夠充分發揮參考集更新和解改進等策略的優勢，但ISISS相對于隨機初始解SS的改進效果并不顯著。當回收點數量擴大為100時，選擇較大的車型（3）時，ISISS相對于GA的改進幅度達到了65.8%，相對于SS的改進率也很明顯；選擇較小車型（8）時，ISISS相對于SS的改進效果仍不夠顯著。隨著數據規模的進一步擴大，當回收點為200時，ISISS算法在2種車型選擇下的改進效果才顯示出來。由于ISISS在初始解生成時就采用C-W啟發式算法生成了較好的初始解，并在此基礎上進行了多樣化處理，因此ISISS具有更優的多樣性解和較好解，從而增強了算法的尋優能力，更加適合于求解大規模回收車輛路徑問題。

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

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

表1 發車數量比較

Tab.1 Comparison of the number of departures

表2 基于算例C50-3、C100-3、C200-3的3種算法目標值分項比較

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

3.3 路線明細

在回收點為100、最小車輛數量為3時，算例C100-3的一次路徑規劃明細如表3所示，對應的回收路徑規劃如圖3所示。

表3 算例C100-3路徑排序

Tab.3 Route sorting of C100-3

圖3 ISISS求得算例C100-3的一個較好解

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

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

表4 算例C100-8路徑排序

Tab.4 Route sorting of C100-8

4 結語

從廢棄包裝品回收的實際問題出發，研究了逆向物流車輛路徑規劃問題，將軟時間窗約束轉化為逆向物流車輛路徑問題的優化目標，以最小化運輸成本、發車成本和時間窗懲罰成本為目標，建立了帶回路的車輛路徑問題聯合優化數學模型。采用含0的整數編碼，同時考慮車輛旅行時間節約值和車輛剩余回收空間收益兩方面因素，確定節約值，利用改進的節約里程算法得到一個初始解，并設計初始解多樣化策略，生成初始解集合。基于改進的優質多樣性初始解，利用分散搜索進化算法求解。針對“部分回收點分布較密集”的類似市區型地理場景生成多組算例，在不同的數據規模下驗證算法的性能。下一步將對ISISS算法在同時送取貨的回收場景及考慮回收服務時間的路徑規劃問題進行研究。

[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]. 包裝工程, 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]. 制造業自動化, 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] 趙嬈, 陳志華. 基于局部搜索的逆向物流車輛最短路徑優化[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] 楊瑋, 趙晶, 張堃, 等. 基于貨架壽命的乳制品配送車輛路徑優化研究[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] 毛麗麗, 張則強, 朱立夏. 混合模擬退火及分散搜索優化過道布置問題[J]. 計算機工程與應用, 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]. 中國機械工程, 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] 張濤, 余綽婭, 劉嵐, 等. 同時送取貨的隨機旅行時間車輛路徑問題方法[J]. 系統工程理論與實踐, 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] 張鵬威, 李英, 成琪. 有限充電設施下的多配送中心電動車輛路徑問題研究[J]. 工業工程與管理, 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）；國家新聞出版署“智能與綠色柔版印刷”重點實驗室項目（KLIGFP-01)；上海市東方學者特聘教授基金（TP2022126）