求解物流配送同時取送貨低碳選址—路徑問題的量子超啟發(fā)式算法

冷龍龍，趙燕偉+，蔣海青，張春苗,2，王 舜

(1.浙江工業(yè)大學 機械工程學院，浙江 杭州 310014；2.嘉興職業(yè)技術學院 機電與汽車分院，浙江 嘉興 314036)

0 引言

選址—路徑問題(Location-Routing Problem, LRP)是供應鏈管理和物流系統(tǒng)規(guī)劃中一個重要的組合優(yōu)化問題，該問題處理的好壞直接影響物流配送成本、效率和客戶滿意度。低碳物流是考慮碳排放因素的行車路線規(guī)劃和倉庫選址的集合。近些年來，路徑規(guī)劃和選址分配問題的優(yōu)化對經(jīng)濟、社會和環(huán)境起著重大作用。因此，本文對考慮環(huán)境因素的LRP構建數(shù)學模型，旨在減少燃料消耗以及二氧化碳等溫室氣體的排放量。

倉庫選址分配問題(Location-Allocation Problem, LAP)和車輛路徑問題(Vehicle-Routing Problem, VRP)是構成LRP的兩個關鍵問題，兩者在物流配送系統(tǒng)中相互影響、相互依賴和相互制約。LRP由Watson-Gandy等于1973年首次提出，目前已成為運籌管理與物流優(yōu)化領域的研究熱點，例如：物品回收，食品派送以及危險有毒物品配送等[1-4]。根據(jù)應用的領域，LRP衍生出許多變體，比如基本的容量約束的LRP(Capacitated LRP, CLRP)[5-6]，時間窗LRP(LRP with Time Windows, LRPTW)[7]，取送貨LRP(LRP with Simultaneous Pickup and Delivery, LRPSPD)[8-9]等。然而，已有大部分LRP變型屬于經(jīng)典LRP范疇，即大多衍生體都以物流配送成本、客戶滿意度等作為優(yōu)先優(yōu)化的目標，并不考慮道路貨物運輸過程中造成的環(huán)境問題，即污染問題。鑒于此，許多研究人員致力于降低道路運輸過程中的副產(chǎn)品——碳排放，以達到節(jié)能減排的目的，由此便形成了污染環(huán)境問題(Pollution-Routing Problem, PRP)[10]。在以往對PRP的研究中，分析燃油消耗在碳排放的重要性，往往采用將車輛燃油消耗線性轉化為碳排放量，通過優(yōu)化燃油消耗達到降低碳排放的目的，與此同時提出了幾種模型來探討車輛燃油消耗及其最小化，即及時燃油消耗模型(Instantaneous Fuel Consumption Model, IFCM)[11]、運行模式燃油消耗(Four-mode elemental Fuel Consumption Model, FFCM)[12]、運行速度燃油消耗模型(Running Speed fuel Consumption Model, RSCM)[11]、綜合模態(tài)排放模型(Comprehensive Modal Emission Model, CMEM)[13]、排放與能量消耗模型(Methodology for calculating Transportation Emissions and Energy consumption, MEET)[14]以及道路運輸燃油消耗模型(Computer Program to calculate Emissions from Road Transportation model, COPERT)[15]。以上模型分析了影響車輛燃油消耗的因素，包括汽車參數(shù)，道路狀況，自然因素以及駕駛員水平與習慣等，然而能夠實時準確獲取以上因素是十分困難且沒有必要的[16]。Xiao等[17]提出一種理想狀態(tài)下的燃油消耗速率模型(Fuel Consumption Rate, FCR)，即僅考慮了距離和負載對燃油消耗的影響，大大簡化了模型的復雜度并提供了一種燃油消耗的參照。然而，以上7種模型僅適用于PRP問題或低碳VRP問題，并未討論倉庫對碳排放的影響。Cagri等[18]提出了適用于LRP問題的CMEM(CMEM-LRP)模型,研究了選址問題和車型構成對碳排放的影響，并用自適應大鄰域搜索算法求解。作者將燃油消耗成本轉化為CLRP中的路徑成本，通過優(yōu)化物流配送成本從而達到降低碳排放的目的。張春苗等[16]將FCR模型應用于低碳選址—路徑問題(Low-Carbon Location-Routing Problem, LCLRP)，驗證了FCR模型在節(jié)能減排上的有效性。本文設計了混合量子進化算法(Quantum Evolutionary Algorithm, QEA)，探討配送中心碳排放對車輛碳排放和配送成本的影響。然而，據(jù)筆者所知，目前LCLRPSPD未獲得任何研究人員的關注。

LCLRPSPD為NP-hard問題，目前尚未有任何啟發(fā)式算法(包括超啟發(fā)式算法)和精確算法求解LCLRPSPD。本文采用量子超啟發(fā)式算法求解LCLRPSPD，將基于滑動窗口的量子旋轉門機制(Quantum Strategies Based Sliding Windows, QSSW)作為高層學習策略用于搜索LLH構成的空間，并監(jiān)測LLHs最近歷史性能而非全局歷史性能，SW采取先進先出(First-In-First-Out, FIFO)機制排除不相關的算子早期性能并記錄近期的LLHs的性能信息。從仿真實驗結果驗證了基于QSSW策略求解LCLRPSPD比QS(Quantum Strategies)性能和效率更優(yōu)。

本文的主要貢獻與創(chuàng)新如下：①構造了能夠保證解的可行性的編碼方式與LLHs，避免了使用解的修復技術；②提出一種快速簡單易行的適應度評價方法，避免了適應度的額外計算；③首次將滑動窗口結合量子旋轉門更新策略，以實時準確的監(jiān)控底層算子的近期性能；④建立了一種集成式的三維指數(shù)LCLRPSPD模型；⑤首次將超啟發(fā)式算法用于求解LCLRPSPD。

1 LCLRPSPD 模型

LCLRPSPD可以定義為在一個有M個候選倉庫、N位客戶和K輛可用配送車輛的完全定向網(wǎng)絡中，每個客戶均有配貨和集貨需求，車輛從倉庫出發(fā)，依次服務一系列客戶，同時滿足客戶的配集貨需求后返回起始倉庫。求解的問題為在配送過程產(chǎn)生的碳排放量最小的情形下，確定最佳的倉庫位置和數(shù)量及行車路線。在此，問題的目標包括倉庫的固定碳排放和車輛行駛過程造成的碳排放量。

本文參考文獻[8，10]，借鑒CLRPSPD和LCLRP的數(shù)學模型，給出LCLRPSPD需滿足的約束條件：①每個客戶節(jié)點只能被一個倉庫與車輛服務一次；②車輛必須返回起始倉庫；③每兩節(jié)點間弧段上的車輛的負載不能超過額定容量；④倉庫的負載不能超過其額定容量；⑤不考慮陸續(xù)不定發(fā)車情況等等。模型中出現(xiàn)的符號變量含義如表1所示。

表1 參數(shù)符號含義

LCLRPSPD數(shù)學模型如下：

(1)

(2)

(3)

(4)

xijk=0,?k∈K,i,j∈J；

(5)

(6)

(7)

(8)

(9)

zij≤yj,?j∈J,i∈I；

(10)

(11)

(12)

(13)

(14)

(15)

(16)

0≤Qijk≤CV,?i,j∈V,k∈K。

(17)

其中：式(1)為目標函數(shù)或適應度，表示倉庫的固定碳排放與車輛運輸過程中產(chǎn)生的碳排放的總和；式(2)為FCR模型；式(3)表示客戶只能被車輛服務一次；式(4)保證一條路線只能由一輛車服務；式(5)保證倉庫之間不能存在任何線路；式(6)表示車輛進出平衡約束；式(7)避免路線中的支路，S為車輛k服務路線的客戶集合；式(8)保證每個客戶必須由某個倉庫服務且只能被其服務一次；式(9)～式(12)表示啟用的倉庫必須服務客戶；式(13)為倉庫負載約束；式(14)表示車輛從倉庫出發(fā)時的負載量，式(15)表示車輛返程時的負載量；式(16)保證車輛在任意弧段上的負載進出平衡等式；式(17)為車輛負載約束。

2 超啟發(fā)式算法設計

超啟發(fā)式算法(Hyper-Heuristics, HH)是由Cowling等[19]于2000年提出的一種新型方法論，將其定義為“啟發(fā)式選擇啟發(fā)式”算法。后來，Burke[20]等拓展了超啟發(fā)式算法：啟發(fā)式選擇和啟發(fā)式生成。超啟發(fā)式算法采用領域屏障隔離高層控制策略(High-level Heuristic, HLH)和底層問題領域層(Low-level Heuristic, LLH)。底層問題領域包含實際問題的數(shù)據(jù)信息、用于直接搜索問題空間的底層算子以及問題領域的種群信息(染色體和適應度等)。在高層控制域中，存在兩種不同目標的策略：算子的選擇策略和解的接收機制。選擇策略用于搜索LLH構成的空間并監(jiān)測LLH的歷史性能信息以選擇優(yōu)質合適的算子(隔離與任何實際問題相關的任何信息)，而接收準則根據(jù)子代解的質量來判斷是否取代父代解，控制著算法的搜索方向和收斂速度。此外，在高層控制策略和底層問題領域之間存在信息傳遞器，用于交換和傳遞與問題領域無關的信息，包括選擇信息、接收策略的判斷信息以及底層提供的改進率、算子運行時間與次數(shù)、當前解連續(xù)無法改進的次數(shù)等。

下面將從以下4個方面研究LCLRPSPD和超啟發(fā)算法：①解的編碼與初始解的構造；②超啟發(fā)算法高層策略的設計，包括2種選擇策略和4種接收準則等；③算子庫的設計，包括6種局部搜索算子和7種變異算子；④超啟發(fā)式算法的復雜度分析等。

2.1 解的編碼與初始解的產(chǎn)生

在問題鄰域中，一個完整的解可表示為所有路線的集合，即R={r1,r2,…,rK}。每條車輛行駛路線ri的首末兩端為所選用的倉庫，中間部分為客戶節(jié)點的編號(表示訪問順序)，且每條路線儲存在對應的元胞數(shù)組中。染色體長度是僅與車輛數(shù)K和客戶規(guī)模N相關的非定長自然數(shù)列，取值為2K+N，元胞數(shù)組的長度為K(車輛數(shù)是可變的)。此外，為便于快速計算適應度，每條車輛行駛路線的屬性也包括在R中(儲存在第二行的元胞數(shù)組中)，定義為路線屬性行，例如：車輛的起始負載、行駛路線的碳排放量以及選用的倉庫等等，計算適應度值時只需調用屬性行中的路線造成的碳排放與倉庫的固定碳排放，避免了重復計算。此外，該編碼能夠保證路線的可行性且避免了可行性修復技術，減少了計算負擔。圖1為一個簡單實例，即客戶集I∈{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}，倉庫集J∈{16,17,18,19}，CV=70。類似于分層樹形編碼方法[8]，樹根部分為行車路線，包含4條路線；枝干為車輛數(shù)，包含4輛服務車輛即元胞數(shù)組的長度；樹葉為每條路線的屬性，包括起止車輛負載量、碳排放量以及倉庫等。

本文的超啟發(fā)式算法采用單點搜索框架(Single-Point Search Framework, SPSF)，即非種群機制。為了避免SPSF易陷入局部解的特性，每次獨立運行的個體從種群中隨機選擇。本文采用隨機生成式方法構建初始種群，即首先隨機生成客戶序列，利用貪婪法則分配客戶并派送車輛(每兩節(jié)點之間車輛負載必須滿足該車輛的容量約束要求)，然后根據(jù)形成的車輛路線隨機選擇倉庫(必須滿足倉庫的容量約束)，并計算每條路線的屬性，最后構造完整的車輛路線集。

2.2高層策略構造

2.2.1 QSSW選擇策略

在量子計算中，量子位為最小的信息儲存單元，可通過量子旋轉門實現(xiàn)轉變其所處轉態(tài)(0或1)。鑒于此，超啟發(fā)底層算子的選擇概率更新過程類似于量子位狀態(tài)的更新機制。在本文的QSSW選擇策略中，一個量子位表征為一個LLH，一個長度為|ξ|的量子染色體表示為：

(18)

其中[αi,βi]T為第i個量子位或底層算子的概率幅。|α|2為量子位處于“0”態(tài)的概率(算子棄用概率)，|β|2為量子位處于“1”態(tài)的概率(算子選擇概率)，兩者滿足|α|2+|β|2=1。在啟發(fā)式搜索空間的初始化過程中，每個算子的αi與βi的初始值相等，表示所有的LLHs有相等的概率被選擇或棄用。

基于量子旋轉門的學習策略用于更新與轉移量子位或LLH的狀態(tài)，經(jīng)由量子門引導個體進化：

(19)

式中：μ為旋轉方向，保證算法的收斂，即當?shù)讓铀阕觝i在第一、三象限，取值為-1，否則為1；θi為每個量子位的旋轉角，控制量子位的選擇概率，其值查表獲得。為了將底層算子的性能參數(shù)反應到旋轉角上，采用以下方式計算旋轉角的大?。?/p>

(20)

(21)

式中，C為常數(shù)；pf和cf分別為父代和子代適應度；FRR為FIR標準化后的數(shù)值；FIR表示累計適應度改進率(Fitness Improvement Rate, FIR)，當FIR取值為算子全局歷史性能時，將采用這種策略的超啟發(fā)式算法命為HH-QS。然而，現(xiàn)階段的底層算子的性能可能與算子的早期性能參數(shù)不相關，采用全局歷史性能作為底層算子的性能表征可能會導致選擇不恰當?shù)腖LH，因此本文借鑒FRR-MAB[21]中的滑動窗口機制記錄算子近期性能，以便改進HH-QS。滑動窗口由W×2維矩陣，第一列為算子使用順序，第二列為算子的FIR，采用FIFO機制排除滑動窗口中的算子的早期性能參數(shù)。最后將滑動窗口中的FIR標準化獲得信用分配值，即FRR，命為HH-QSSW。

最后，采用輪盤賭的方式分配算子選擇概率hp，可定義為式(22)：

(22)

采用該方法可避免算法后期選擇的單一性，增強選擇的多樣性。

2.2.2 接收準則設計

接收準則(Acceptance)用于判斷子代解cf是否替換父代解pf，其處理的好壞直接影響超啟發(fā)算法收斂速度與優(yōu)化精度。

當cf優(yōu)于pf，cf直接取代父本進入下一次迭代，否則利用概率公式(24)計算cf取代pf的概率并做出抉擇，查閱文獻，幾乎所有的接收準則都是一種計算概率p的策略，本文采用4種接受準則：

(1)全接收(AM) 所有的cf都接收并代替pf，即p=1；

(2)蒙特卡洛(MC) 非改進解以概率p=e-δ大小被接收，其中δ=m×Δf/Q，m為常數(shù)(本文取10)，Δf=cf-pf，Q為當前解未被改進的計數(shù)器，如果最小碳排放被更新，重置Q為ε(無窮小值)；

(3)大洪水(GD) 如果非改進解cf的值小于等于pf+ΔF×(1-t/tmax)時才會被接收，此時p=1，t為當前迭代次數(shù)，tmax為最大迭代次數(shù)，ΔF=bf1-bft為最大門檻高度，其中bf1，bft分別為第一次迭代最優(yōu)解和當前迭代最優(yōu)解；

(4)模擬退火(SA) 非改進解以概率p=e-δ大小被接收，其中δ=(cf-pf)/(ΔF×(1-t/tmax))。

2.3 底層算子設計

底層算子庫(Pool of LLH, PLLH)可直接搜索問題領域解空間，由問題領域專家提供。PLLH可視為無法操作的黑箱，根據(jù)優(yōu)化性質分為變異算子和局部優(yōu)化算子兩類。變異算子往往對當前解微小擾動，以便在搜索過程中提供足夠的隨機性并防止陷入局部最優(yōu)解，但無法保證獲得高質量解。然而，局部優(yōu)化算子的目的在于改進當前解，促使算法快速收斂并提高收斂精度。這兩類算子在組合優(yōu)化中是必不可少的，本文共構造6種局部優(yōu)化算子和7種變異算子。

局部優(yōu)化算子有：線路內部2-Opt(Inside-2opt)、線路間2-Opt(Inter-2opt)、線路內交換客戶(Inside-swap)、線路間交換客戶(Inter-swap)、線路內移動客戶(Inside-shift)和線路間移動客戶(Inter-shift)。局部優(yōu)化算子每次執(zhí)行的約束條件包括：①改進率FIR≥0；②任意弧段的車輛負載必須小于額定容量；③倉庫的負載不能超過額定容量。對于線路內部局部優(yōu)化時，采用的策略為完全優(yōu)化策略[22]，而線路間的局部優(yōu)化則采用K-1優(yōu)化機制，即隨機選定一條路線，與其他路線的客戶逐一局部優(yōu)化，算子復雜度從K(K-1)/2降低為K-1。

變異算子分為兩類：一類為針對行車路線擾動的變異算子，包括Inside-2opt-M、Inside-oropt、Inter-shift-M、inter-swap-M和Shaw[23]，這類算子的擾動機制為隨機選取1/4～1/2的路線并隨機擾動線路內或線路間的客戶，并不保證獲得優(yōu)質解；另一類變異算子對倉庫進行擾動，包括Add和Relocation。Add算子隨機選取1/3～2/3的路線并分配給一個新的倉庫或關閉一個倉庫，并將該倉庫的所有路線安排到另一倉庫，以防止過少的倉庫導致過快收斂。Relocation將每條行駛路線坍塌為一個“Super-client”，然后將倉庫插入到每條路線中獲得最小插入成本并作為該倉庫與該路線之間的距離，類似于Barreto[24]。變異算子的約束條件為倉庫和車輛的負載不能超過額定容量。底層算子庫中的所有算子必須滿足所有約束條件后才操作，保證路線的可行性和避免使用修復技術。

2.4 算法復雜度分析

算法的時間復雜度是運行時間的相對量度，用于衡量一個算法的運行時間性能。對于種群規(guī)模為|P|，迭代次數(shù)為Tmax，客戶數(shù)為N，車輛數(shù)為K與底層算子數(shù)為NL的問題，迭代一次的算法復雜度如下：高層選擇策略中，計算FIR的復雜度為O(|P|)，更新滑動窗口計算復雜度為O(2×W)，計算FRR、旋轉門更新以及輪盤賭的復雜度為O(3×NL)，接收策略的復雜度為O(|P|)，精英保留策略的復雜度為O(|P|)。由于無法確定每次迭代的底層算子，計算復雜度設定為耗時最長的算子的計算復雜度即O(|P|×N2)，此外，主循環(huán)外部存在種群初始化的計算復雜度為O(|P|×N2)以及適應度計算的計算復雜度O(|P|),算法在迭代一次的計算復雜度約為O(3×|P|)+O(2×W)+O(3×NL2)+O(|P|×N2)，算法的總體計算復雜度O(HH-QSSW)為：

O(HH-QSSW)=Tmax×(O(3×|P|)+

O(2×W)+O(3×NL)+O(|P|×N2))+

O(|P|×N2)+O(|P|)=O((3×Tmax+1)×

|P|)+O(2×WTmax)+O(3×Tmax×NL)+

O((Tmax+1)×|P|×N2)。

(23)

由上述分析可知，算法的整體計算復雜度約為Tmax|P|O(N2)，即高層策略的計算復雜度可忽略不計，HH-QSSW的總體計算復雜度約為底層算子的計算復雜度的總和。

3 仿真實驗與比較

實驗主要分為3部分，實驗1通過與目前求解LCLRP的算法進行對比分析來驗證本文高層策略和底層算子的有效性，然后通過實驗2確定性能最好的4種策略組合，最后將實驗2中的4種組合策略用于求解LCLRPSPD，進一步驗證所提的QSSW的高效性與魯棒性。超啟發(fā)式算法采用MATLAB 2015b并行編程，計算機環(huán)境為intel(R)Core(TM)CPU i7-6700K @4.00 GHz,8 GB RAM, Windows 10。為了保證對比公平性，每個策略組合的算法的終止條件為最大Tmax且采用同一初始種群。此外，每種策略(CF和FRR-MAB)的參數(shù)盡量采用文獻中參數(shù)或隨機數(shù)的方式，具體參數(shù)設置如表2所示。

表2 算法參數(shù)設置

3.1 測試算例

目前尚無對低碳LRPSPD的標準算例，為了測試HH-QSSW的性能以及確定最佳策略組合，實驗1采用文獻[16]改進的Prins算例[27]求解LCLRP，以檢驗算法的效率和模型的正確性；實驗2采用的實例為Barreto標準算例(文獻[9])，以確定4種最佳組合策略；實驗3改進3類算例以適用于LCLRPSPD，包括Barreto、Prins和Tuzun[28]標準算例。Tuzun標準算例為首次用于求解LRPSPD/LCLRPSPD的算例，所采用的分割方法為Karaoglan方法[29]，且令β=0.8。所有LCLRPSPD原型算例(即LRP標準算例)可從網(wǎng)址http://sweet.ua.pt/sbarreto/private/SergioBarretoHomePage.htm和http://prodhonc.free.fr/homepage上下載。

3.2 仿真實驗

3.2.1 分析算法有效性

采用HH-QSSW-SA和HH-SR-SA求解LCLRP，采用的算例為文獻[16]改進的Prins算例，結果如表3所示。其中：BKS為已知最小油耗量(單位：L)，由文獻[16]獲得，BF、MF、SD以及MT分別為最小碳排放、平均碳排放量、標準差以及平均運行時間(s)，Gap表示BF與BKS百分比差距，表格的末尾為所有數(shù)據(jù)的平均值和中位數(shù)。由表3可知，兩種策略組合的BF均優(yōu)于文獻[16]中提供的最小碳排放，其中兩種策略組合比BKS最多可減少30%碳排放量，最少能降低2%的碳排放量，表明本文算法在降低碳排放量上的有效性和性能優(yōu)于文獻[16]的QEA。此外，在相同的接收準則(SA)下，QSSW的綜合性能優(yōu)于SR，主要表現(xiàn)在BF、MF、SD和Gap的平均值與中位數(shù)上，然而QSSW的時間性能劣于SR大約32%，SR算法花費的最大運行時間為236 s，而QSSW策略耗費的運行時間最大為477 s，這符合于No-free-lunch定理[30]。采用Friedman檢驗(見2.2.4節(jié))對表3的BF統(tǒng)計分析，統(tǒng)計結果見表4，根據(jù)統(tǒng)計量p值可推斷3種算法之間存在顯著差異。表5為Post-hoc Wilcoxon Rank-Sum檢驗，結論表明HH-QSSW-SA與HH-SR-SA在性能上都優(yōu)越于QEA。

綜上所述，本文提出的超啟發(fā)式算法能夠在合理的計算時間內求解LCLRP并能夠獲得優(yōu)質解，表明EHH的高層選擇策略和接收準則以及底層算子的有效性。

3.2.2 最佳策略組合選擇

3.2.1節(jié)分析了超啟發(fā)式算法在求解LCLRP方面的有效性，本節(jié)研究20種組合策略的綜合性能以確定4種最佳策略組合用于求解LCLRPSPD問題，其中選擇策略有SR、FRR-MAB、CF、QS以及QSSW，接收機制為MC、DG、SA和AM。此外，采用CHESC-Cross-domain heuristic search challenge評分系統(tǒng)(http://www.asap.cs.nott.ac. uk/external/chesc2011/)對20種策略組合進行評分排名，即將適應度從小到大依次排列并賦值前8位組合策略得分(10,8,6,5,4,3,2,1)，其他策略為0分。在Barreto標準數(shù)據(jù)中，選用了16組實例(客戶數(shù)N∈[21,150])，即每個策略組合所得最大分為160分，實驗結果如表6所示。不考慮接收準則的影響，本文提出的QSSW得分排名第一，SR、QS和FRR-MAB分別列為第二、三、四名，CF表現(xiàn)最差；僅對接收準則分析，GD性能最好排名第一，MC獲得344分排名第二，SA與AM性能最差；根據(jù)對20種組合策略的綜合評分，所選取的4種性能最好的策略為SR-GD、QSSW-MC、FRR-MAB-GD與QS-GD。本文提出的兩種算法表現(xiàn)較好，分別以95和83分排第二、四名，SR-GD以112位列第一，F(xiàn)RR-MAB-GD以84分排名第三。從獲得滿分10分的次數(shù)來看，F(xiàn)RR-MAB與SR獲得10次，QSSW獲得8次，QS獲得6次和CF僅獲得4次。

表3 LCLRP算例對比

續(xù)表3

表4 Friedman統(tǒng)計分析結果

表5 Post-hoc Wilcoxon Rank-Sum統(tǒng)計分析(源自表3數(shù)據(jù))

表6 20種組合策略得分

綜上所述，本文提出的QSSW以及QS在求解LCLRPSPD表現(xiàn)出較好的性能，SR與FRR-MAB的性能更優(yōu)。根據(jù)評分排名，選用SR-GD、QSSW-MC、FRR-MAB-GD與QS-GD等4種策略組合來執(zhí)行實驗3。

3.2.3 三種算例的求解和模型有效性

本節(jié)將實驗2的4種精英組合策略用于求解LCLRPSPD的標準實例(Cm≠0)，實驗結果如表7～表9所示。類似于表3，僅提供了每個實例的BF和MT(頁面空間問題)，此外，由于本文為首次求解LCLRPSPD，無法獲得BKS。表格最后一行添加了NB，表示在所獲得最小碳排放的個數(shù)(粗體表示結果為最小碳排放)。表格的最后兩列為所求解的CLRPSPD最小成本模型下的路徑規(guī)劃的碳排放量，其中dif(%)為求解CLRSPD的BF與前4種組合策略所求解的最小BF之間的百分比差距。

表7 Barreto標準實例計算結果

續(xù)表7

由表7中4種策略對Barreto的16個算例的運行結果可知，QSSW-MC在16個算例中10次獲得最優(yōu)，F(xiàn)RR-MAB-GD獲得9次最優(yōu)排名第二，SR-GD與QS-GD分別獲得6次和4次；就最優(yōu)值的平均耗油量而言，QSSW-MC以平均值為15552.9位列第一，QS-GD與SR-GD排名第二、三名，F(xiàn)RR-MAB-GD表現(xiàn)最差；SR-GD和FRR-MAB-GD在運行時間上分別為52秒和65秒位列第一、二名，本文的兩種策略組合排名最后。此外，QS-GD在求解小規(guī)模問題表現(xiàn)出優(yōu)越的性能，而在大中規(guī)模的性能略低于FRR-MAB-GD，與SR-GD持平，但優(yōu)越于QS-GD。

表8是本文算法求解Prins標準數(shù)據(jù)的數(shù)據(jù)結果。在求得最小碳排放個數(shù)上，QSSW-MC獲得了17次最優(yōu)，SR-GD和QS-GD分別獲得11次和12次，F(xiàn)RR-MAB-GD表現(xiàn)最差只獲得了6次最優(yōu)值，QSSW-MC在大部分規(guī)模算例中都能夠獲得最小碳排放；在最小碳排放的平均值上，QSSW-MC以均值4552.7kg排名第一，SR-GD排名第二，QS-GD和FRR-MAB-GD為末兩位。在平均運行時間上，SR-GD和FRR-MAB-GD以63.9 s和76.3 s摘得一、二名，本文的兩種策略排名末兩位，分別為89.1 s和96.9 s。QSSW-GD在求解不同規(guī)模測試問題的性能表現(xiàn)為出現(xiàn)顯著差異，且均優(yōu)越于其他3類。

用4種組合策略求解Tuzun標準算例，求解結果如表9所示。Tuzun標準算例有36個實例，客戶數(shù)N∈{100、150、200}，倉庫為M∈{10、20}，車輛容量為150。QSSW-MC在最小碳排放的平均值和數(shù)量排名第一，分別為5212.2kg和16個，SR在最小碳排放平均值和數(shù)量上優(yōu)于FRR-MAB和QS，排名第二，而QS在最小碳排放的數(shù)量上優(yōu)于FRR-MAB但最小碳排放平均值劣于FRR-MAB。此外，對于時間性能，SR-GD和FRR-MAB-GD位列一、二名，本文兩種策略排名末位，符合沒有免費的午餐定理(no-free-lunch)。

由表7～表9中所求解CLRPSPD的BF和dif.值可知，本文模型在分別求解3類標準實例時可平均降低12.87%、7.05%和9.18%碳排放量，在求解所有算例可平均減少9.14%碳排放量，足以表明本文模型的有效性，可為相關政府部門節(jié)能減排政策的制定提供有價值的參考和借鑒。此外，QSSW-MC可獲得43個最優(yōu)解(占所有測試實例52.44%)，相比于QS-GD的占比(約28.05%)提高了24個百分點，即可推斷融入滑動時間窗的量子選擇策略可大大提供底層算子的選擇正確率。相比于SR和FRR-MAB，QSSW能獲得最優(yōu)解的個數(shù)提高了21.95%和28.05%，表明QSSW算法的性能有效性和優(yōu)越性均高于SR和FRR-MAB。

表8 Prins標準實例計算結果

表9 Tuzun標準實例計算結果

續(xù)表9

3.2.4 統(tǒng)計分析

本文對表7～表9的數(shù)據(jù)結果采用Friedman按秩二因素ANOVA(k樣本)統(tǒng)計分析，多重比較的置信水平為95%(即α=0.05)，以檢驗4種策略組合之間是否存在顯著差異，其原假設H0為：多個配對樣本來自的多個總體分布無顯著差異，即如果Freidman檢驗統(tǒng)計量χ2大于關鍵值(查卡方表)，則接收H0,否則拒絕H0，或者如果統(tǒng)計值p值滿足p≥α，則接收H0,否則拒絕H0。如果H0被拒絕，事后檢驗(Post-hoc)采用單邊Wilcoxon Rank-Sum檢驗兩兩之間是否存在顯著差異，其原假設為兩個樣本中位數(shù)相同。為了控制Friedman檢驗的多重比較謬誤(Type I-Family Wise Error Rate, FWER)，采用Bonfeeroni-Holm修正方法修正α值，即首先將p值按升序排列(p1

(25)

按照p值從小到大的順序依次與式(25)的α值比較，直到pi>αi結束，并保持原假設。統(tǒng)計實驗采用IBM SPSS Statistics 19進行，實驗結果如表10～表12所示。

將表7中4種策略組合計算結果采用Friedman檢驗(如表10)，表明4種策略之間存在顯著差異。由表11的post-hoc檢驗結果表明HH-QSSW-MC與HH-QS-GD之間中位數(shù)存在顯著差異，表明結合滑動窗口的QSSW性能要顯著優(yōu)于QS，然而無法斷定顯著優(yōu)于其他兩種策略。

對表8中的數(shù)據(jù)結果采用Friedman檢驗，結果如表10所示，表明4種策略在獲得最小碳排放時存在顯著的差異。事后檢驗結果如表12所示，結果顯示QSSW-MC和QS-GD(或SR-GD)之間中位值統(tǒng)計相同，QSSW-MC在性能上顯著優(yōu)于FRR-MAB-GD，此外，無法確定QS-GD與其他策略彼此的優(yōu)越性。

對Tuzun標準數(shù)據(jù)的數(shù)據(jù)結果采用Freidman檢驗，結果如表10所示。統(tǒng)計量p值為0.272，大于α，表明4種組合策略在求解Tuzun標準實例時不存在顯著差異，無法確定彼此的顯著優(yōu)越性。但從最小碳排放的平均值和數(shù)量上，可直觀地顯示QSSW相對其他3個組合的優(yōu)越性和有效性。

綜上所述，QSSW能在合理的計算時間內獲得大部分實例的最小碳排放量，可推斷出所提算法在求解該算例時的有效性與魯棒性。此外，對比其他3種組合策略，QSSW在降低碳排放方面表現(xiàn)出巨大的優(yōu)越性。因此可認為QSSW可實時準確地捕捉底層算子的性能表現(xiàn)并選擇合適的算子，以此提高了超啟發(fā)式算法的框架性能。

表10 Friedman統(tǒng)計分析結果

表11 Post-hoc Wilcoxon Rank-Sum統(tǒng)計分析(源自表7數(shù)據(jù))

表12 Post-hoc Wilcoxon Rank-Sum統(tǒng)計分析(源自表8數(shù)據(jù))

4 結束語

本文提出一種超啟發(fā)式算法用于求解LCLRPSPD，優(yōu)化目標為最小碳排放，包括倉庫的固定碳排放與車輛行駛造成的碳排放。首先在問題領域中，建立了符合同時取送貨的LCLRP簡單明了的三維指數(shù)MIP模型；設計了一種滿足可行性要求的解編碼方式和快速簡單的適應度評價方法，以此降低計算負擔。其次在超啟發(fā)式算法設計中，將量子進化算法中的旋轉門更新策略作為一種高層學習策略，用于搜索底層算子構成的空間并更新底層算子選擇概率以選擇算子；然后，將滑動窗口與量子進化策略的高層選擇策略相結合，利用算子近期性能信息表征算子的選擇概率，真正實現(xiàn)選擇的實時性與準確性。

實驗部分分為3類。實驗1通過對比QEA驗證了本文算法在求解LCLRP的有效性與魯棒性與模型的正確性；實驗2采用配對方法對Barreto算例求解并確定了選擇策略QSSW-MC、SR-GD、QS-GD和FRR-MAB-GD相比其他組合策略性能最好，接收準則GD和MC相比于AM和SA對算法性能的提高更為明顯；實驗3通過對3種不同實例(Barreto、Prins與Tuzun標準實例)的仿真、對比和統(tǒng)計分析，表明了實驗2的最佳4種組合策略都能有效地求解LCLRPSPD，并且本文提出的QSSW在求解大部分實例的性能表現(xiàn)最好。

未來研究將重點考慮LCLRPSPD與其他實際約束結合，例如：時間窗、多車型等。與此同時，本文的模型僅考慮了距離和載貨量對碳排放的影響，其他因素(速度、道路狀況、車輛參數(shù)等)對碳排放的影響也將會成為未來重點工作之一。此外，盡管QSSW在求解LCLRPSPD時的綜合性能較佳，但依舊存在較大的改進空間，下一步將會把QSSW與其他高效的策略結合，例如禁忌搜索、優(yōu)劣表等[31]。