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

(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

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

1 問題描述

1.1 低碳LRP模型

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

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

目標(biāo)函數(shù)為

(1)

約束條件為

(2)

(3)

(4)

(5)

(6)

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

1.2 算子介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 算法流程

算法的具體流程為

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

步驟2隨機產(chǎn)生初始蛙群，計算各個蛙的適應(yīng)值。

步驟3劃分種群。

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

步驟3.2重復(fù)步驟3.1，直到種群劃分結(jié)束。

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

步驟4.1對全局最優(yōu)和局部最優(yōu)進行隨機擾動。

步驟4.2對操作后的解計算適應(yīng)度，如果有更優(yōu)解出現(xiàn)，則進行更新。

步驟4.3重復(fù)步驟4.1和步驟4.2，直至達到預(yù)設(shè)循環(huán)次數(shù)。

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

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

步驟5.2如果達到迭代次數(shù)則停止，轉(zhuǎn)步驟6；如果沒有，則轉(zhuǎn)步驟3。

步驟6輸出全局最優(yōu)解。

算法流程圖如圖2所示。

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

2.2 編碼解碼和算法參數(shù)

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

3536114…6891

圖3 青蛙個體示意圖

Fig.3 Diagram of frog individual

2.3 更新策略

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

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

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

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

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

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

因LCS問題的具有最優(yōu)子結(jié)構(gòu)性質(zhì)[17]，最長公共子序列計算公式為

根據(jù)上述的遞歸公式和初值，有如下偽代碼和實現(xiàn)：

輸入兩個青蛙個體

輸出兩個個體的相似度

步驟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的兩個數(shù)組進行相似度計算，結(jié)果如圖6所示。最長公共子序列為“4232314”，所以兩只青蛙的相似度為7。

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

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

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

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

3 數(shù)值仿真與分析

3.1 實驗設(shè)計和參數(shù)分析

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

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

1) SFLA：最基本的蛙跳算法，相似度即個體的適應(yīng)度。劃分總?cè)杭窗聪嗨贫葟母叩降鸵来畏峙涞矫總€子群。

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

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

3.2 結(jié)果分析

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

3.2.1 收斂代數(shù)分析

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

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

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

3.2.2 目標(biāo)函數(shù)分析

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

圖7 目標(biāo)函數(shù)收斂情況比較Fig.7 Comparison of objective function convergence

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

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

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

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

表3 最優(yōu)路線Table 3 Optimal routes

3 個方案，12 個樣例的結(jié)果如表4所示，加粗表示為該樣例在3 個方案中最好的結(jié)果。從運行時間方面來講，因為是毫秒級，3 個算法的復(fù)雜度一樣，所以運行時間差距不大，總體而言SFBL方案運行時間最少。從目標(biāo)函數(shù)而言，SFBL方案所獲得的解質(zhì)量最高，其次是SFBE，最后是SFLA?？傮w而言，問題規(guī)模越大，SFBL算法能獲得最優(yōu)解的概率就越高。

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

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

4 結(jié) 論

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