基于超啟發式算法的選址-路徑問題研究

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

選址-路徑問題(Location-routing problem, LRP)將選址分配問題(Location allocation problem, LAP)與經典車輛路徑問題(Vehicle routing problem, VRP)進行組合研究，屬于經典的NP難問題。隨著全球氣候變暖，低碳問題得到了越來越多人的重視，而物流業是碳排放的主要來源之一，因此對于低碳物流模型的研究日趨增多。在模型上，曹劍東等[1-2]以總成本最小化為優化目標研究了考慮碳排放因素的車輛路徑問題(Vehicle routing problem，VRP)。在求解算法上，基本以遺傳算法、禁忌搜索等啟發式算法居多，但這些算法不具有良好的通用性，無法適用于新研究出來的模型。

超啟發式算法[3](Hyper-heuristic algorithms)是近年才發展起來的一種新型的啟發式算法，可以簡單闡述為“尋找啟發式算法的啟發式算法”，該算法具有良好的通用性，可用于求解排課問題[4]、流水車間調度問題[5]和裝箱問題[6]等約束較少的組合優化問題。超啟發式算法的研究主要集中在選擇策略、接收策略和底層算子三部分。文獻[7]研究了針對旅行錦標賽問題的基于蟻群的超啟發式算法，采用蟻群算法來管理和操縱LLH以獲得新的啟發式算法，每只螞蟻均構造一個新的啟發式算法。Marshall等[8]將語法演化應用在超啟發式算法中，使其產生良好的解，通過仿真實驗，對40 個著名的車輛路徑問題進行仿真，取得了不錯的結果。國內外關于超啟發式算法在低碳LRP模型中的應用研究甚少，筆者將基于蛙跳算法的選擇策略用于啟發式算法對低碳LRP問題進行求解，并提出了基于最長公共子序列的相似度計算方式。

1 問題描述

1.1 低碳LRP模型

本實驗采用的模型[9]為多個配送中心使用單一類型車輛為每個客戶點配送貨物，不考慮時間窗、車輛最大行駛距離等約束條件。此問題描述為：有n個客戶點需要配送貨物，有M個倉庫點進行發送貨物，每個倉庫都只有一種類型的車，車的載重都為Qk。每個客戶點都由某一個倉庫點進行貨物發送，每一輛車都從倉庫出發，前往每一個客戶點去送貨，直至送完所有貨物，最后返回倉庫。具體詳情見表1。

表1 符號與變量說明Table 1 Explanation of variable and symbol

目標函數為

(1)

約束條件為

(2)

(3)

(4)

(5)

(6)

式(1)是LRP模型中車輛碳排放量的計算方法，即所有車輛完成配送任務后所產生的碳排放量，也是本實驗的目標函數，是在張春苗等[9]所提計算方法的基礎上取消了配送中心開放的固定碳排放量，增加了每一輛車的固定碳排放量，以鼓勵減少車輛的使用；式(2)表示車的貨物總量總是小于車的載重；式(3)保證每個配送中心訪問的顧客總需求小于配送中心的容量；式(4)保證每個客戶均被訪問一次；式(5)保證每一輛車從配送中心出發最終又回到配送中心；式(6)保證每一個客戶點的需求都被滿足。

1.2 算子介紹

根據超啟發式算法的特點，底層啟發式算子屬于問題域，由應用領域的專家所提供。在低碳LRP模型中，根據文獻[10]，筆者采用的底層啟發式算子為

LLH1：2-opt算子。選擇一條路徑，客戶數量為N，從前N-1個客戶中隨機選舉一個客戶，將這個客戶點和其后面相鄰的客戶點進行交換。

LLH2：or-opt算子。選擇一條路徑，客戶數量為N(N>2)，隨機選取相鄰的兩個客戶點，將這兩個客戶點隨機插入到該路徑的其他位置。

LLH3：shift算子。選擇兩條路徑，從第一條路徑中，隨機選取一個客戶點，將它插入到第二條路徑合適的位置。

LLH4：Interchange。選擇兩條路徑，隨機從兩條路徑中各選取一個客戶點進行交換。

LLH5：配送中心的shift算子。選擇一條路徑，給這條路徑設置一個新的配送中心。

LLH6：配送中心的Interchange算子。選擇兩條路徑，交換它們的配送中心。

LLH7：Location-based Radial Ruin。選擇一條路徑，隨機選舉其中一個客戶點，將此客戶點作為基準客戶，根據每個客戶和基準客戶的歐氏距離來重新生成解。

LLH8：Interchange*。與之前的Interchange算子一樣，只不過此算子只接受改進解。

LLH9：shift*。與之前的shift算子一樣，只不過此算子只接受改進解。

LLH10：2-opt*。與之前的2-opt算子一樣，只不過此算子只接受改進解。

2 基于蛙跳算法的選擇策略

選擇式超啟發算法根據反饋機制來源不同，可以分為不學習、離線學習和在線學習3 種，而在線學習機制又可分為基于元啟發、基于強化學習和基于函數選擇3 種選擇方法，筆者使用了蛙跳算法(SFLA)來選擇底層啟發式算法，是在線學習機制中基于元啟發選擇方法的一種。SFLA模擬青蛙尋找食物的過程，是一種新型群智能進化算法，它是由Eusuff和Lansey[11]于2003年首次提出，并應用在求解水資源網絡的管徑選擇和管網擴張問題中。筆者提出一種基于SFLA的上層選擇策略，將蛙跳算法應用在選擇式超啟發，其框架如圖1所示，在原有的基本框架上，加入了SFLA算法用于低層啟發式算法的選擇，同時根據應用算子后的結果反饋于SFLA算法。

圖1 基于蛙跳算法的選擇策略框架Fig.1 Framework of hyper-heuristic algorithm in leapfrog algorithm

2.1 算法流程

算法的具體流程為

步驟1初始化參數。確定蛙群的數量、種群以及每個種群的青蛙數。

步驟2隨機產生初始蛙群，計算各個蛙的適應值。

步驟3劃分種群。

步驟3.1隨機找尋一個解，計算其他解與它的相似度，按相似度劃分種群。

步驟3.2重復步驟3.1，直到種群劃分結束。

步驟4根據SFLA算法公式，在每個族群中進行元進化。

步驟4.1對全局最優和局部最優進行隨機擾動。

步驟4.2對操作后的解計算適應度，如果有更優解出現，則進行更新。

步驟4.3重復步驟4.1和步驟4.2，直至達到預設循環次數。

步驟5將各個族群進行混合。在每個族群都進行過一輪元進化之后，將各個族群中的蛙重新進行排序和族群劃分并記錄全局最好解Px。

步驟5.1利用更新策略對局部最差解進行替換。

步驟5.2如果達到迭代次數則停止，轉步驟6；如果沒有，則轉步驟3。

步驟6輸出全局最優解。

算法流程圖如圖2所示。

圖2 蛙跳算法流程圖Fig.2 Flow chart of leapfrog algorithm

2.2 編碼解碼和算法參數

由于筆者所提及的蛙跳算法是作為選取算子的高層策略，所以搜索到的空間不是車輛路徑的解空間，而是算子的組合空間。如圖3所示，這是一個青蛙個體，是由一串數字組成，每一個數字對應著各自的底層算法，例如數字1就代表著2-opt算子，即對解執行2-opt算子。一個解從最原始的狀態進過一個青蛙個體之后，就會產生一個新的解，新的解的目標函數就是該青蛙個體的適應值。與其他優化算法一樣，SFLA也具有一些必要的計算參數：F為蛙群的數量；m為族群的數量；n為族群中青蛙的數量；Smax為最大允許跳動步長；Px為全局最好解；Pb為局部最好解；Pw為局部最差解；q為子族群中蛙的數量；LS為局部元進化次數；SF為全局思想交流次數等。

3536114…6891

圖3 青蛙個體示意圖

Fig.3 Diagram of frog individual

2.3 更新策略

筆者更新策略采用文獻[12]提出的方法，具體為對比每個種群內局部最優和局部次優解，如果相同位置上有相同的算子編號，則對該位置進行記錄。推測該位置上的算子編號很可能是有利于增加適應度的，即有利于調度的，所以將種群內最差解位置上的算子編號替換為記錄的算子編號。該操作如圖4所示，一共為4 串數字，也就是4 個個體，第一行為全局最優解Px，第二行為子群最優解Pb，第三行是子群最差解Pw，第四行是更新后的Pw。

圖4 更新策略示意圖Fig.4 Diagram strategy of update strategy

2.4 改進的種群相似度計算方法

算法開始時隨機初始化總數量的青蛙，即隨機生成總數量的具有固定長度的一組數字，每個數字都代表一種底層啟發式算子。在常見的SFLA算法中[13-16]，青蛙按適應度進行排序，以特定的劃分原則進行種群劃分。文獻[12]提出了一種新的個體相似度定義，其算法是對比兩個個體每一位上的數字，如果相同，則相似度加1。如圖5所示，圖5中兩個解的相似度為3。

圖5 相似度計算示意圖Fig.5 Diagram of similarity computation

相比于傳統的個體相似度計算方式，筆者提出了基于最長公共子序列的相似度算法，將該相似度算法應用在超啟發式算法的上層策略中是本研究的主要創新點。所謂的最長公共子序列(LCS：longest-common-subsequence problem)是一個在一個序列集合中(通常為兩個序列)用來查找所有序列中最長子序列的問題。一個數列，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則稱為已知序列的最長公共子序列。例如以下兩串編碼“123456”和“234567”，根據文獻[12]的相似度計算，它們的相似度為0，然而事實上它們其實十分相似，只是前者比后者一開始先調用了1次“1”算子，后者比前者最后多調用了1次“7”算子。根據最長公共子序列的相似度計算，前者有子串“23456”和后者的子串“23456”是完全一樣的，所以它們的相似度為5，可以明顯地看到采用公共最長子序列進行相似度計算能更好地還原兩只青蛙的相似性。

因LCS問題的具有最優子結構性質[17]，最長公共子序列計算公式為

根據上述的遞歸公式和初值，有如下偽代碼和實現：

輸入兩個青蛙個體

輸出兩個個體的相似度

步驟1function LCS(x,y,i,j)

步驟2if (x[i]=y[j])

步驟3thenc[i,j]=LCS(x,y,i-1,j-1)+1

步驟4elsec[i,j]=max{LCS(x,y,i,j-1)，LCS(x,y,i-1,j)}

步驟5returnc[i,j]

因此采用最長公共子序列的算法對圖5的兩個數組進行相似度計算，結果如圖6所示。最長公共子序列為“4232314”，所以兩只青蛙的相似度為7。

圖6 最長公共子序列相似度計算示意圖Fig.6 Diagram of similarity computation base on longest common subsequence

根據新的個體相似度計算方法，進行種群劃分：

步驟1隨機找到一個解，計算該解與其他解的相似度，按相似度從高到低選取n個解，劃分成一個種群，其中n=青蛙總數(F)/種群個數(m)。

步驟2在剩余解中隨機找尋一個解，利用步驟1的方法進行種群劃分，直至種群劃分結束。

3 數值仿真與分析

3.1 實驗設計和參數分析

為了驗證算法的實用性，對基準樣例進行仿真實驗，包括了5 個配送中心，20 個客戶點，其中每個配送中心的坐標、庫存量已知，每個客戶點的坐標、需求量已知，配送中心的車輛載重已知，樣例詳細信息見網址[18]。基于蛙跳算法上層選擇策略的超啟發式算法，采用Cplusplus編程，運行在CPU為Intel Core i7，4.0 GHz，RAM為8 G內存的計算機平臺上，考慮到蛙跳算法很多參數可能會對性能造成影響，根據文獻[12]的結論，采用如下具體參數：青蛙總數Population=200，種群數量Group=20，個體長度Individual=20，迭代次數Maxloop=20。因采用新的更新策略，所以蛙跳算法中的最大允許跳動步長(Smax)等參數將不存在。

筆者提出的核心創新點就是SFLA算法中的相似度計算的改進，由原來的個體每一位相比較改為基于最長公共子序列的相似度計算。為了驗證筆者提出的相似度計算方法的有效性，設計了兩個對比算法。

1) SFLA：最基本的蛙跳算法，相似度即個體的適應度。劃分總群即按相似度從高到低依次分配到每個子群。

2) SFBE(SFLA base each dimension)：由2.4節所描述的根據每個個體每一位上是否相等來計算相似度。

3) SFBL(SFLA base longest common subsequence)：筆者提出的基于最長公共子序列的相似度計算。

3.2 結果分析

首先對SFLA算法、SFBE算法和SFBL算法在解決低碳LRP模型的性能進行比較，通過收斂代數和目標函數收斂情況這兩個方面進行分析。

3.2.1 收斂代數分析

3 種算法對LRP模型求解的收斂代數見表2，取運行10 次的平均收斂代數，這里迭代次數不設置為20，而是采用連續5 次迭代不出現更優秀個體作為終止迭代條件。

表2 SFLA，SFBE和SFBL的收斂代數Table 2 Convergence times of SFLA，SFBE and SFBL

由表2可以看出：SFLA算法平均迭代次數最多，為96.8；其次是SFBE算法，平均迭代次數為75.1；最后是SFBL算法，平均迭代次數最少為64.4。說明SFBL算法收斂速度最快，效率更高，在求解更大規模的樣例和模型時具有更大優勢；同時，從迭代次數的方差來看，SFBL的方差最小為24.7，說明SFBL算法相比于另外兩個算法更穩定。

3.2.2 目標函數分析

為了更清楚地比較3 個算法在求解LRP模型上的最終效果，把3 個算法目標函數的碳排放隨著迭代次數的曲線圖放在一起比較，見圖7。由圖7可知：SFBL算法的末端值最低，碳排放為165.353 kg，因此SFBL算法最終的解質量最優，說明SFBL算法更有效，能夠避免早熟現象；從3 個算法的曲線來看，前期SFBL算法下降趨勢最明顯，其次是SFBE算法，最后是SFLA算法，說明了SFBL收斂速度最快。

圖7 目標函數收斂情況比較Fig.7 Comparison of objective function convergence

為了解給予蛙跳算法中底層啟發式算子對解質量的影響情況，運行10 次，統計10 個底層啟發式算子的平均改進率，即該算子對解的質量是否起到提升效果，如圖8所示。

圖8 算子的平均接受率Fig.8 Average acceptance rate of LLH

由圖8可以看出：10個底層啟發式算子的平均改進率都超過了0.5，其中局部搜索算子LLH8，LLH9，LLH10的改進率為1，這是由算子本身的性質所決定的，因為算子本身只接受改進解，其余算子從高到低分別為LLH2，LLH3，LLH7，LLH1，LLH4，LLH5，LLH6，相對而言，由于LLH5和LLH6是跟配送中心有關的算子，因此改進率比較低。總體而言，10 個底層啟發式算子都有大概率能改進解的質量，證明了算子構建的有效性。然后，對于低碳LRP問題，3 種算法給出的最優解分別為：SFLA算法195.331 kg，SFBE算法188.476 kg，SFBL算法165.353 kg。這3 個解對應的路線如表3所示。

最后，為了驗證3 個算法的通用性，將3 個算法分別用在3種不同規模的12 個測試樣例上進行實驗，分別為20 個客戶點，50 個客戶點和100 個客戶點，配送中心均為5 個，每個規模4 個測試用例，目標函數改為所有車輛行駛距離的總和。

表3 最優路線Table 3 Optimal routes

3 個方案，12 個樣例的結果如表4所示，加粗表示為該樣例在3 個方案中最好的結果。從運行時間方面來講，因為是毫秒級，3 個算法的復雜度一樣，所以運行時間差距不大，總體而言SFBL方案運行時間最少。從目標函數而言，SFBL方案所獲得的解質量最高，其次是SFBE，最后是SFLA。總體而言，問題規模越大，SFBL算法能獲得最優解的概率就越高。

表4 SFLA,SFBE和SFBL對比Table 4 Comparison of SFLA, SFBE and SFBL

由此可見：無論是從算法的收斂代數、收斂速度、穩定性和通用性，還是從最優解來看，基于最長公共子序列的相似度計算方式(SFBL算法)都比其他兩個算法要好。

4 結 論

針對低碳LRP模型，構建了和問題相關的底層啟發式算子，使用蛙跳算法作為選取底層啟發算子的高層策略，并提出了基于最長公共子序列的青蛙個體相似度計算方式，最后，將筆者提出的相似度算法與之前的相似度算法還有最原始的蛙跳算法比較，進行仿真實驗。實驗結果證明了算子構建的有效性，也表明基于最長公共子序列的相似度計算方法(SFBL算法)在求解低碳LRP能夠在獲得更好解的同時，具有更快的收斂性和穩定性，對跨問題領域求解效果也比較好。