基于禁忌搜索算法的廢棄家具回收車輛路徑優(yōu)化

龐 燕，羅華麗，夏揚坤

(中南林業(yè)科技大學(xué) 物流與交通學(xué)院，湖南 長沙 410004)

0 引言

隨著人們生活水平的提高，消費觀念發(fā)生了很大的改變，對新奇和時尚家具的追求也越來越高，家具產(chǎn)品的更新?lián)Q代速度逐年加劇。另外，我國中小家具制造企業(yè)眾多，企業(yè)為了迎合消費者需求，搶占市場份額，大肆推陳出新，這種粗糙的生產(chǎn)模式造成家具產(chǎn)能過剩，導(dǎo)致大量家具因滯銷而廢棄于倉庫之中[1]，既浪費了社會資源又污染了環(huán)境。可見，廢棄家具的回收處理已經(jīng)成為一項亟需解決的社會難題。根據(jù)生產(chǎn)者責(zé)任延伸制度[2]，家具制造企業(yè)必須承擔(dān)回收廢棄家具的責(zé)任[3]。對廢棄家具進行回收處理再利用，不僅能夠有效緩解企業(yè)面臨的環(huán)保壓力，樹立企業(yè)的良好社會形象，還能創(chuàng)收一定的經(jīng)濟效益[4]。

廢舊家具回收屬于逆向物流的范疇，從物品特點來看，其一般體積和重量較大且形狀不一，在裝載上需要對車輛容量進行限制。從回收的特殊性來看，回收需求點客戶分散于各個小區(qū)，對路線規(guī)劃要求高，而企業(yè)可以自由選擇回收服務(wù)時間。車輛路徑問題(Vehicle Routing Problem, VRP)是廢棄家具回收逆向物流體系中的核心環(huán)節(jié)，對廢棄家具回收車輛路徑問題(Vehicle Routing Problem of Waste Furniture Recycling, VRPWFR)進行研究具有較高的實踐價值，縮短行駛距離和減少使用車輛數(shù)可以在較大程度上降低企業(yè)的總成本。在對各回收站點的廢棄家具進行配載裝車時，需要結(jié)合各站點的需求量和地理位置分布情況，根據(jù)車輛裝載能力限制劃分車輛路徑，既要遍歷所有站點，還要盡可能地縮短行駛距離并減少車輛數(shù)，從而形成一個帶容量約束的雙目標(biāo)函數(shù)家具回收VRP。

帶容量約束的車輛路徑優(yōu)化問題(Capacitated Vehicle Routing Problem, CVRP)在物流配送領(lǐng)域中應(yīng)用廣泛，對CVRP進行有效改進能夠在較大程度上降低物流成本、提升效益和客戶滿意度。因為CVRP是NP-hard問題，一般的精確算法[5]很難求解大規(guī)模配送問題，而經(jīng)典的啟發(fā)式算法又不具備全局尋優(yōu)能力，所以設(shè)計智能啟發(fā)式算法(智能優(yōu)化算法)進行求解。曹高立等[6]設(shè)計了一種混合量子進化算法求解CVRP，利用二維量子位觀測模型直接產(chǎn)生十進制編碼個體，增強了算法鄰域搜索的能力；李陽等[7]在生物共棲算法的基礎(chǔ)上，結(jié)合變鄰域搜索策略，采用混合智能啟發(fā)式搜索算法求解CVRP。

部分學(xué)者采用兩階段的方式來降低求解難度，提高了算法效率。Mohammed等[8]提出兩階段遺傳算法，在找到車輛行駛最短路徑的基礎(chǔ)上尋找?guī)萘肯拗频能囕v路徑；Lai等[9]在求解具有時間窗的VRP時，第一階段采用模擬退火算法減少路徑中的車輛數(shù)，第二階段采用禁忌搜索算法(Tabu Search Algorithm, TSA)降低總行駛成本，結(jié)果表明兩階段求解方式能夠更快地獲得優(yōu)化解；Wang等[10]在處理帶時間窗的多目標(biāo)多中心的VRP時，設(shè)計了一個兩階段多目標(biāo)進化算法，第一階段尋找極值解，第二階段以極值解為基礎(chǔ)進行擴展尋找最優(yōu)解，實驗結(jié)果表明兩階段求解方式確實有利于解的改進；李陽等[7]在求解帶模糊需求的容量限制VRP時，設(shè)計了兩階段變鄰域TSA，第一階段處理客戶的模糊需求，第二階段處理客戶的實際需求，最后通過算例測試驗證了兩階段求解方式是解決CVRP的有效途徑。

TSA是對局部搜索算法的擴展，是一種模仿人類智能思維的全局逐步尋優(yōu)智能啟發(fā)式算法，很多學(xué)者對TSA表現(xiàn)出了濃厚的興趣。Wang等[11]基于解決方案的禁忌策略，采用協(xié)調(diào)的哈希函數(shù)加速禁忌狀態(tài)，產(chǎn)生了更好的優(yōu)化方案；Ben等[11]針對背包問題設(shè)計了一個多鄰域概率搜索TSA；Tao等[12]研究了三維裝箱約束VRP，利用迭代禁忌搜索尋找可行路徑；Liu等[13-15]對TSA進行了重點研究，指出TSA具有簡單性、適應(yīng)性和易操作性等優(yōu)點。由以上文獻(xiàn)可以看出，在TSA中，鄰域結(jié)構(gòu)可以增強算法的搜索能力，禁忌表可以通過避免算法較早陷入局部最優(yōu)來增強尋優(yōu)能力，對CVRP求解起到了很好的優(yōu)化作用。隨著優(yōu)化模型的不斷拓展，其求解變得越來越復(fù)雜，本文設(shè)計的改進兩階段禁忌搜索算法(Improved Two-stage Tabu Search Algorithm, ITTSA)也將圍繞鄰域結(jié)構(gòu)和禁忌表兩個方面進行改進。

1 問題描述與數(shù)學(xué)模型的構(gòu)建

1.1 問題描述

本文所研究的VRPWFR是在滿足回收站點需求量di和車輛裝載能力限制Q的基礎(chǔ)上，對廢棄家具回收車輛路徑進行規(guī)劃，從而合理地安排車輛k在各回收站點i之間的行駛順序，并最小化總行駛距離和車輛數(shù)。

在每次回收中需要滿足的條件為：①路徑中僅有一個廢棄家具處理中心，但擁有多個家具回收站點(客戶點)；②各回收站點的地理位置和回收量已知；③處理中心的地理位置已知；④處理中心擁有足夠數(shù)目的同車型車輛；⑤每個回收站點只能被車輛拜訪一次；⑥全部車輛從處理中心出發(fā)，回收廢棄家具后需返回原處理中心；⑦車輛在各點之間的行駛距離符合三角不等式約束。

1.2 相關(guān)符號定義

為了方便問題描述，定義相關(guān)符號如表1所示。

表1 相關(guān)符號的含義說明

1.3 數(shù)學(xué)模型構(gòu)建

(1)

minK。

(2)

s.t.

(3)

(4)

(5)

(6)

(7)

(8)

K≥Kmin=；

(9)

xijk∈{0,1}?i,j∈V′,?k∈M。

(10)

其中：目標(biāo)函數(shù)式(1)表示最小化路徑的總距離值；目標(biāo)函數(shù)式(2)表示最小化使用車輛數(shù)；式(3)表示回收車輛的容量約束，保證每輛車不會超過其載重；式(4)保證到達(dá)回收站點i的車輛數(shù)與離開該站點的車輛數(shù)一致；式(5)保證到達(dá)每個回收站點的車輛有且僅有一輛車；式(6)可消除子回路；式(7)和式(8)保證全部車輛從回收處理中心出發(fā)并最終返回原出發(fā)點；式(9)用于估算所需的最少車輛數(shù)；式(10)表示車輛k是否從回收點i到點j(i≠j)，是則為1，否則為0。

2 禁忌搜索算法設(shè)計

TSA是一種具有指導(dǎo)性搜索能力的智能優(yōu)化算法，其可以利用短期禁忌表來記憶相應(yīng)的禁忌信息，避免搜索重復(fù)解。以往的TSA將同一鄰域交換點對作為禁忌對象，存在禁忌重復(fù)的弊端，本文設(shè)計一個新的線性禁忌表，將鄰域算子和鄰域交換點對同時作為禁忌對象，并設(shè)計多鄰域結(jié)構(gòu)來模擬相應(yīng)局部極值的分布情況。具體算法設(shè)計見后續(xù)說明。

2.1 兩階段求解方式的設(shè)計

作為旅行商問題(Traveling Salesman Problem, TSP)的一種拓展，VRPWFR已被證明是NP-Hard問題，其在求解較大規(guī)模精確解上具有極高的難度。結(jié)合以往VRP研究[8]經(jīng)驗可知，兩階段求解方式有助于降低求解難度，提升求解效率。本文將兩階段求解思想融入TSA，第一階段，根據(jù)所有客戶回收站點的位置編號生成TSP路徑；第二階段，根據(jù)TSP路徑排列中站點的需求量和車輛裝載能力限制劃分VRP路徑，盡可能地使車輛滿載(此舉對應(yīng)了第二目標(biāo)最小化使用車輛數(shù)K)。

2.2 解的評價設(shè)計

在每次迭代生成候選解集后，都先挑選出當(dāng)前的全局最好解Sbest和當(dāng)前解Snow。其中，Sbest用于存儲迭代中出現(xiàn)的最好結(jié)果，Snow用于在下一次迭代的鄰域變換過程中生成候選解集。本文采用總行駛距離值Z來評價解的優(yōu)劣。在候選解無禁忌的情況下，認(rèn)為Z值越小其解越優(yōu)。在每次迭代生成候選解集后，如果最佳候選解Sbestca比全局最好解Sbest更優(yōu)，則不考慮禁忌情況，直接將Sbestca設(shè)定為全局最好解Sbest和當(dāng)前解Snow；若Sbestca比Sbest更差，則將非禁忌的最佳候選解*Sbestca設(shè)定為當(dāng)前解Snow。

2.3 解的表示與初始解的生成

問題的一個解可以用回收處理中心點0和各個站點的編號排列來表示，每一個解都有其對應(yīng)的TSP路徑和VRP路徑。在其TSP路徑中，起始點和終止點為點0，中間節(jié)點為各站點的自然數(shù)編號。在其VRP路徑中，數(shù)字0是不同VRP路徑劃分的分界點。例如，在VRP路徑S=(0-2-4-1-0-8-6-5-0-9-7-12-0-…-0)中，前3條車輛路徑分別為(0-2-4-1-0)，(0-8-6-5-0)，(0-9-7-12-0)。本文采用隨機方式生成可行初始解。初始解的具體生成過程如下：①隨機生成一個關(guān)于站點編號的自然數(shù)TSP排列，并構(gòu)建TSP路徑；②根據(jù)該TSP路徑、站點回收量和車輛裝載能力限制劃分相應(yīng)的閉合式VRP路徑(盡可能地使車輛滿載)。

2.4 鄰域結(jié)構(gòu)設(shè)計

(3)分序點插入 分兩種情形：

2.5 線性禁忌表設(shè)計

在算法中引入短期線性禁忌表，記錄已經(jīng)搜索過的當(dāng)前解所對應(yīng)的禁忌對象，在后續(xù)一定搜索次數(shù)中，不再對該禁忌對象進行重復(fù)搜索，以提升算法跳出局部最優(yōu)的能力。禁忌表用來儲存禁忌對象，本文設(shè)計一個大小為16×3的線性禁忌表，將鄰域算子和鄰域交換點對都作為禁忌對象，采用先進先出機制，當(dāng)禁忌信息溢出時，釋放排在最前面的禁忌信息。

TSA禁忌的目的是為了避免重復(fù)搜索相同解，若為直接禁忌解，則匹配計算量會很大，在以往的TSA[16-17]中，一般用禁忌鄰域交換點對對象模擬相應(yīng)候選解的禁忌情況。然而，同一鄰域交換點對可能對應(yīng)多個不同的候選解，容易造成對優(yōu)良候選解的過度禁忌。因此，本文對禁忌表進行改進，將鄰域算子編號也加入禁忌表，使得禁忌對象改變?yōu)椤班徲蛩阕泳幪栢徲蚪粨Q點1鄰域交換點2”，在迭代搜索中，只有當(dāng)鄰域算子編號和鄰域交換點在禁忌表中同時存在時，才認(rèn)為其對應(yīng)的候選解是禁忌的，從而擴大了搜索范圍，避免陷入早熟。另外，對候選解的禁忌情況進行標(biāo)記，可以更準(zhǔn)確地模擬相應(yīng)候選解的禁忌，降低搜索的重復(fù)程度，縮短搜索時間，提升算法鄰域搜索的效率，有利于優(yōu)化候選解的質(zhì)量。

2.6 終止條件

終止條件包括鄰域搜索的終止條件和迭代的終止條件。鄰域搜索的終止條件有一個，即每次迭代中候選解的數(shù)目達(dá)到預(yù)設(shè)的上限值N0；迭代的終止條件有兩個，達(dá)到其中任意一個便可終止迭代：①總的迭代次數(shù)達(dá)到預(yù)設(shè)的上限值N1；②全局最好解連續(xù)保持不變的迭代次數(shù)達(dá)到預(yù)設(shè)的上限值N2。為了使算法能夠適用于求解不同規(guī)模問題，將N0，N1，N2均設(shè)置為與回收站點有關(guān)的線性函數(shù)，取N0=50+N，N1=6 000+150N，N2=5 000+30N。

2.7 算法流程圖

本文ITTSA的基本流程如圖1所示。

3 算法測試與分析

Aleman等[18]在求解帶裝載能力限制的VRP時，設(shè)計了構(gòu)造啟發(fā)式算法(Constructive heuristic Approach, CA)、迭代構(gòu)造算法(Iterative Constructive Approach, ICA)和迭代構(gòu)造變鄰域下降法(Iterative Constructive Approach plus Variable Neighborhood Descent, ICA+VND)(ICA+VND采用兩階段求解方式，以ICA的結(jié)果作為VND的初始解)，并對站點規(guī)模分別為50/75/100的C1/C2/C33個算例進行了測試分析，具體請參考文獻(xiàn)[18]。為了方便對比分析，本文也選用C1，C2，C33個算例進行測試分析。本文采用MATLAB2014a進行編程，在榮耀Magic Book、CPU為i5-8250U、主頻為1.60 GHz、內(nèi)存為8 GB的電腦上完成計算，對每個算例獨立測試20次。

3.1 鄰域結(jié)構(gòu)測試

不同鄰域結(jié)構(gòu)[19]對應(yīng)不同的算法搜索空間，當(dāng)鄰域過多時，算法運行成本過大，因此對鄰域組合進行測試來確定最優(yōu)鄰域結(jié)構(gòu)，以減少不必要的搜索，從而提高算法尋優(yōu)能力和運行速度。本文設(shè)計了5種鄰域算子，為了比較各鄰域算子的尋優(yōu)性能，探討鄰域結(jié)構(gòu)的優(yōu)化能力，以C1算例分別對5種鄰域算子的不同組合情況進行測試，每一種情況測試20次，并對求解結(jié)果進行統(tǒng)計分析。

(1)采用1種鄰域算子

表2所示為各鄰域算子的總距離Z值的最好值Zbest、平均值Zavg、最差值Zworst、極差值Zdev(最差值與最好值的差值)、極差百分比Zdev/%(極差值相對于最好值的百分比)、標(biāo)準(zhǔn)差Zsd及求得的平均車輛數(shù)Kavg，其中Zbest，Zavg，Zworst，Kavg體現(xiàn)了算法的尋優(yōu)能力，Zdev，Zdev/%，Zsd體現(xiàn)了算法求解的穩(wěn)定性。表2中NO-1/NO-2/NO-3/NO-4/NO-5分別表示所采用的鄰域算子1/2/3/4/5，加粗?jǐn)?shù)據(jù)表示比較數(shù)據(jù)中的最好值。從表2可見，對于同一算例的數(shù)據(jù)，NO-5的各項參數(shù)值均為最小，相對于NO-5而言，NO-1，NO-2，NO-3，NO-4求得的最短距離值較高，偏差百分比較大，標(biāo)準(zhǔn)差較大，穩(wěn)定性較差。由此可見，NO-5的優(yōu)化效果和穩(wěn)定性最好。選取Zbest，Zavg，Zworst的數(shù)據(jù)繪制優(yōu)化結(jié)果，如圖2所示。

表2 采取1種算子測試的總距離值Z的比較

(2)采用2種鄰域算子

因為采取1種鄰域算子進行測算得到的結(jié)果中NO-5更優(yōu)，所以在兩種鄰域算子進行測算時將NO-5與其他算子進行組合，共4種情況，用同一算例進行測算，分析結(jié)果如表3所示。從最好值、平均值、最差值和標(biāo)準(zhǔn)差等結(jié)果來看，NO-51和NO-52的結(jié)果一樣，由此可見，NO-1(前點前向插入算子)或NO-2(前點后向插入算子)的移動方式相似，產(chǎn)生的效果也一樣；NO-54的優(yōu)化結(jié)果最好，穩(wěn)定性最強，車輛數(shù)也達(dá)到了最小車輛數(shù)的要求。繪制優(yōu)化結(jié)果，如圖3所示，其中NO-51表示在算例測試中采取鄰域算子5和鄰域算子1的組合。

表3 采取2種算子測試的總距離值Z的比較

(3)采用3種鄰域算子

根據(jù)采取兩種鄰域算子的數(shù)據(jù)結(jié)果，在采取3種鄰域算子計算時，將NO-5，NO-4與其他算子進行組合，共有3種情況，用同一算例進行測試，分析結(jié)果如表4所示。從平均值來看，NO-541比其他兩種組合情況稍優(yōu)，但是在找到最好值時，NO-542的值更接近最優(yōu)；從標(biāo)準(zhǔn)差來看，NO-542算出的值最低，說明波動較小，穩(wěn)定性最好；3種鄰域算子組合的車輛數(shù)都已降至最低。因為算法的第一優(yōu)化目標(biāo)是求得最短距離，所以綜合來看，NO-542的組合情況最優(yōu)。將各組合算子的優(yōu)化結(jié)果繪制成曲線圖，如圖4所示。

表4 采取3種算子測試的總距離值Z的比較

(4)采用4種鄰域算子

根據(jù)采取3種鄰域算子的數(shù)據(jù)分析結(jié)果，在進行4種鄰域算子計算時，將NO-5，NO-4，NO-2與其他兩種算子進行組合，共有兩種情況，以同一算例進行測算，數(shù)據(jù)分析結(jié)果如表5所示。從各項數(shù)據(jù)來看，NO-5421明顯優(yōu)于NO-5423，如圖5所示。

表5 采取4種算子測試的總距離值Z的比較

(5)采用5種鄰域算子

對5種鄰域算子進行測試，在NO-5421的基礎(chǔ)上以同一算例對5種算子組合進行測試，數(shù)據(jù)分析結(jié)果如表6所示。

表6 采取5種算子測試的總距離值Z的比較

綜合以上5種測試結(jié)果，將每種算子測試時的最好結(jié)果統(tǒng)一起來進行比較，如表7和圖6所示。當(dāng)分別使用1/2/3/4/5個鄰域算子進行測算時，取得最好優(yōu)化能力的是NO-5,NO-54,NO-542,NO-5421，NO-54213。在這5種最佳組合中，其優(yōu)化能力大小排序是NO-54>NO-542>NO-54213>NO-5>NO-5421。

表7 各最優(yōu)算子測試的Z值比較

分析原因，在對單個算子進行測算時，NO-5相比其他4個算子體現(xiàn)了很好的優(yōu)化效果，說明點逆序算子的尋優(yōu)能力和穩(wěn)定性是5個算子中最好的，其在NO-54組合中也發(fā)揮了較好的作用。然而，NO-54的Zavg比NO-542稍弱，相差0.25，這是因為NO-4(點交換算子)的操作是將隨機挑選的兩個點進行交換，解空間變換較小，搜索范圍較小，所以搜索的候選解集較差。相比之下，NO-2(前點后向插入算子)在進行鄰域變換時，其解空間有所擴大，算法搜索空間增大，從而提高了候選解的質(zhì)量，但是因為NO542鄰域結(jié)構(gòu)的算子更多，運算過程更長，所以穩(wěn)定性不如NO-54。

綜合來看，NO-54的優(yōu)化效果具有較大優(yōu)勢，其能求得最短行駛距離，且車輛數(shù)最小，穩(wěn)定性較好，在求解質(zhì)量和效率上優(yōu)于其他鄰域結(jié)構(gòu)。因此，使用2種鄰域算子的結(jié)果明顯更優(yōu)，即點逆序算子和點交換算子組成鄰域結(jié)構(gòu)使算法的優(yōu)化效果更好。

3.2 文獻(xiàn)對比分析

結(jié)合3.1節(jié)中的鄰域算子組合測試結(jié)果可知，采用NO-54的優(yōu)化效果最好。因此，本文ITTSA在求解C1，C2，C33個算例時，直接采用NO-54構(gòu)建成的多鄰域結(jié)構(gòu)體進行測試和對比分析。

表8所示為Z的最好值Zbest、平均值Zavg、最差值Zworst、極差值Zdev、極差百分比Zdev/%和標(biāo)準(zhǔn)差Zsd?？梢娙克憷腪值偏差百分比控制在5%以下，均值偏差為3.87%，平均標(biāo)準(zhǔn)差為8.91。根據(jù)以往大規(guī)模配送VRP的研究可知，本文ITTSA的穩(wěn)定性較好。

表8 ITTSA的Z值

表9所示為NO-54組合鄰域算子下，在C1/C2/C3算例中車輛數(shù)的計算結(jié)果，其中給出了K的最好值Kbest、平均值Kavg、最差值Kworst、極差值Kdev和標(biāo)準(zhǔn)差Ksd。從表中可見，3個算例的最好結(jié)果都下降至最少車輛數(shù)，表現(xiàn)較穩(wěn)定的是C1算例和C3算例，其車輛數(shù)保持不變；C2算例中，車輛數(shù)為10或11，標(biāo)準(zhǔn)差僅為0.44，波動性較小。說明ITTSA對車輛數(shù)的求解效果較好。

表9 車輛數(shù)K的計算結(jié)果

因為各對比算法的車輛數(shù)均已下降至最小值Kmin，所以表10主要給出各對比算法距離值的對比結(jié)果?？梢?，ITTSA在降低距離值方面優(yōu)于對比文獻(xiàn)所使用的算法，除C3算例優(yōu)化的幅度較小外，C1和C2算例的優(yōu)化效果均較好。相比算法CA，ICA，ICA+VND，本文ITTSA的平均優(yōu)化程度比對比文獻(xiàn)分別高出5.48%，4.11%，2.06%，可見本文ITTSA的優(yōu)化能力強于3種對比算法，從而驗證了ITTSA的有效性。

表10 各算法的Z值比較

注：Z表示算例的最優(yōu)距離值；IMP表示ITTSA的Z值高于對比文獻(xiàn)的百分比，加粗?jǐn)?shù)據(jù)表示最好值。

3.3 回收路徑舉例分析

本文以C1算例中的計算結(jié)果為例，具體回收路徑方案如表11所示。針對C1中的50個站點，算法將其分為5條線路進行回收(已達(dá)最少車輛數(shù))，線路1包括11個站點，線路2包括11個站點，線路3包括9個站點，線路4包括9個站點，線路5包括10個站點，需要的車輛數(shù)為5，總的距離值為524.61。

表11 C1算例的回收路徑方案

4 結(jié)束語

本文對VRPWFR進行研究，設(shè)計了ITTSA并進行求解。經(jīng)算法測試與文獻(xiàn)對比分析，得出如下結(jié)論：①在改進的兩階段禁忌搜索算法中，第一階段的TSP路徑優(yōu)化為第二階段的VRP路徑劃分提供了基礎(chǔ)；②設(shè)計了一個新的線性禁忌表，將鄰域算子和鄰域交換點對同時作為禁忌對象，能夠更好地模擬對候選解的禁忌情況，有效避免重復(fù)搜索無效解，提高禁忌效率，并避免過早收斂問題；③對5種鄰域算子的組合情況進行測試，結(jié)果表明點逆序和點交換這兩種算子的組合效果最好；④算法測試與文獻(xiàn)對比表明ITTSA具有較好的優(yōu)化性能。

研究VRPWFR對于促進家具行業(yè)的綠色低碳化發(fā)展具有重要意義，考慮到供應(yīng)鏈中大規(guī)模的家具逆向物流問題更加復(fù)雜，求解難度也更大，后續(xù)將進一步對多級網(wǎng)絡(luò)同時取送貨的家具物流VRP進行研究，構(gòu)建相應(yīng)的多目標(biāo)數(shù)學(xué)模型，并進一步提升TSA的尋優(yōu)性能。