混合超啟發式算法求解復雜兩級車輛路徑問題

尹 丹，胡 蓉**，錢 斌，郭 寧

(1.昆明理工大學 信息工程與自動化學院,云南 昆明 650500；2.云南省計算機技術應用重點實驗室,云南 昆明 650500)

隨著電子商務的快速發展，物流調度的重要性日趨顯著.傳統的車輛路徑問題(vehicle routing problem,VRP)即倉庫直接服務客戶的運輸方式，難以滿足日益增長的需求量；并且多數城市對大型車輛采取限行措施，由此形成兩級車輛路徑問題(two-echelon vehicle routing problem,2E-VRP)[1].2EVRP 增加了中間設施中轉站，中心倉庫通過中轉站間接服務客戶的方式可將大型車輛限制在城市中心之外，在改善城市交通的同時，提高了服務效率[2].同時，全球氣候變暖愈加嚴重，物流調度中的交通運輸已成為碳排放的主要來源之一，考慮運輸車輛的燃油消耗或碳排放量受到重視[3].此外，在實際情況中，客戶的需求往往存在不確定性.譬如，快遞公司提供攬收服務時，難以明確客戶的需求[4].在上述背景下，本文針對攬收貨物的情況，研究模糊需求下的綠色兩級車輛路徑問題(green twoechelon vehicle routing problem with fuzzy demand,G2E-VRPFD).由于G2E-VRPFD 屬于NP-hard 問題.故研究G2E-VRPFD 的建模及其求解算法具有理論價值和現實意義.

2E-VRP 在快遞服務、雜貨店和電子商務等領域內應用廣泛[5].2E-VRP 最先由Feliu 等[1]提出，并建立數學模型.隨后，針對以最小化運輸總成本為優化目標的2E-VRP 得到了廣泛的研究，Zeng 等[6]設計一種基于貪婪隨機自適應搜索算法與變鄰域下降算法的混合算法進行求解；Breunig 等[7]設計一種改進大鄰域搜索算法進行求解；Liu 等[8]設計一種混合模因算法進行求解；Yan 等[9]設計一種基于圖的模糊進化算法進行求解；Wang 等[10]基于距離對客戶分類將該問題劃分為多個VRP 子問題，并設計一種混合蟻群算法求解分解后的子問題；Wang 等[11]考慮了顧客的位置和購買行為等相似特征設計了一種結合聚類算法的增強遺傳算法進行求解.針對綠色兩級車輛路徑問題(green twoechelon vehicle routing problem,G2E-VRP)研究較為有限，Wang 等[12]以最小化駕駛員工資、燃油成本和裝卸成本之和為優化目標，設計一種混合變鄰域搜索算法進行求解；李正雯等[13]針對帶時間窗的綠色多車型兩級車輛路徑問題(green twoechelon heterogeneous-fleet vehicle routing problem with time windows,G2E-HVRP-TW)，以最小化車輛固定成本、時間窗懲罰成本和油耗成本之和為優化目標，設計一種學習型離散排超聯賽算法進行求解.

模糊需求車輛路徑問題(vehicle routing problem with fuzzy demand,VRPFD)是模糊車輛路徑問題(fuzzy vehicle routing problem,FVRP)的一種.現有文獻多采用模糊理論處理車輛調度中的不確定因素.王連鋒等[14]針對VRPFD，以最小化運輸總成本為優化目標，建立其模糊期望值模型，設計一種混合并行粒子群算法進行求解.馬艷芳等[15]針對模糊需求下的綠色同時取送貨問題(green vehicle routing problem with simultaneous pickup and delivery with fuzzy demand,GVRPSPDFD)，以最小化運輸總成本為優化目標，將三角模糊數轉化為模糊期望值，設計一種改進的遺傳禁忌搜索算法進行求解.目前對于VRPFD 已有一定研究，但對實際中廣泛存在的G2E-VRP 尚未看到模糊需求下的建模和智能算法求解方面的相關研究.

G2E-VRPFD 綜合考慮了2E-VRP 和GVRPFD的特點，更符合現實攬收要求.對2E-VRP 的求解，智能算法已有一定研究.在大多數研究中，都將兩級問題視為一個整體，對其進行編碼和求解[6-9]，由于該類問題的兩級問題相互耦合且決策變量復雜，造成解空間規模龐大且編碼較為繁瑣，僅憑智能算法本身的搜索機制難以在短時間內將算法搜索引導至解空間的較優區域，易造成算法的搜索效率低下.針對兩級問題的特性，已有學者成功采用聚類分解將問題分解為多個相同的子問題，再設計智能算法依次對每個子問題進行求解，然后對各個子問題的解合并，獲得原問題的解[10-11,13]；該類結合分解的方法能將智能算法搜索空間限制在較優區域內，提升智能算法對問題解空間的搜索效率.因此，本文采用結合聚類分解的智能算法對G2E-VRPFD進行求解.

超啟發式算法(hyper-heuristic algorithm,HHA)是解決復雜優化問題的一種新型算法.通常被描述為“搜索啟發式算法的啟發式算法”，該算法通過一種高層策略(high-level strategy,HLS)動態操控多個底層啟發式算子(low-level heuristic,LLH)實現對問題解空間的搜索.由于HHA 較于傳統的啟發式算法擁有良好的通用性，并且無需進行復雜的參數設置即可獲得穩定且高質量解[16]，因此被用于求解各類車輛路徑問題[17-19].基于文獻[17-19]調研可知，高效的啟發式算法作為HLS 與結合問題特點構造的LLH 是設計HHA 的關鍵.分布估計算法(estimation of distribution algorithm,EDA)是基于概率模型的算法，能有效避免傳統智能算法中存在對較優解模式破壞的問題[20]；然而，大部分學者均使用二維概率模型的EDA 求解VRP 相關問題[21-22].由于二維概率模型只能學習操作塊信息而無法學習操作塊所在的位置信息，使算法在采樣生成新個體時可能會因操作塊放置不合理而導致算法搜索效率降低，這在引導算法搜索時具有較大的局限性.而三維概率模型通過學習優質解中操作塊的位置信息[23]，在一定程度上減小對優良解的破壞，提升算法的搜索效率.因此，本文HHA 的高層策略采用基于三維概率模型的EDA 來優化高層個體.此外，HHA 已被成功用于求解多類VRP 上，但尚未發現用于求解2E-VRP 及其相關問題.

綜上所述，本文建立最小化車輛運營成本和油耗成本之和為優化目標的G2E-VRPFD 模型.根據G2E-VRPFD 這類問題的解空間復雜且兩級問題互耦合的特點，提出一種混合超啟發式算法(hybrid hyper-heuristics algorithm,HHHA)進行求解.首先，設計一種聚類分解算法將G2E-VRPFD 分解成多個子問題，用以合理縮小問題的求解規模，實現對兩級問題的解耦.其次，利用增強超啟發式分布估計算法(enhanced hyper-heuristic estimation of distribution algorithm,EHHEDA)對各個子問題進行求解；然后將各子問題的解合并，得到原問題的解.在EHHEDA 的高層策略域設計一種基于三維概率模型的分布估計算法，該概率模型用于描述優質個體的序結構信息，并通過采樣該模型來動態確定由底層操作域中各搜索算子所組成的排列，更好的保護較優解模式不被破壞.在EHHEDA 的底層操作域設計10 種有效鄰域搜索算子，對問題解執行深入的搜索，并在每個算子中加入重升溫操作的模擬退火機制作為問題解的接受準則，在算法陷入局部最優解時能在一定概率下跳出.最后，通過在不同規模測試集下的仿真實驗和算法對比，驗證了所提算法在求解G2E-VRPFD 的有效性.

1 G2E-VRPFD 的問題描述及數學模型

1.1 G2E-VRPFD 問題描述及相關假設G2EVRPFD 包括兩級物流網絡，如圖1 所示，第一級網絡中含有一個中心倉庫、多個中轉站和多臺可用的大型車輛；第二級網絡中含有多個中轉站、若干個客戶點和多臺可用的小型車輛.在攬收過程中，二級車輛先從中轉站出發向若干個客戶攬收貨物，并存放在中轉站內；一級車輛再從中心倉庫出發為多個中轉站攬收貨物，其中客戶的需求具有一定模糊性.該模型要求在給定目標(運輸總成本最小)和約束條件下對客戶進行服務，合理安排車輛及服務路線以實現運輸總成本最小化.該模型假設：①中心倉庫、中轉站和客戶的信息已知；②在物流網絡中，同級網絡攬收車輛相同；③中轉站僅負責貨物中轉，不儲存貨物，同一中轉站或客戶的貨物不得拆分攬收，中心倉庫不能直接服務客戶；④車輛從中轉站或者中心倉庫空載出發；每輛車所服務的客戶總需求不能超過該車輛的最大載重量；⑤中轉站容量(或中心倉庫容量)、可用車輛數、攬收能力滿足客戶點(或中轉站)服務要求；⑥車輛空載出發，可同時派出多輛車(不超過可用車輛總數)進行攬收服務.

圖1 G2E-VRPFD 示意圖Fig.1 Schematic diagram of G2E-VRPFD

1.2 期望模糊需求在現實攬收貨物場景中，由于各種不確定因素，客戶很難給出一個精確的需求量，通常會根據經驗給出一個大致的范圍，并在范圍中取一個可能的需求值.因此，針對這種需求不確定的情況，本文參考文獻[15]引用模糊變量，將客戶需求設置為三角模糊數，使用三角模糊數的期望值對客戶的模糊需求進行定量處理.

設一客戶的模糊需求A=(q1,q2,q3)，其中0

設A邊 為fA和gA的三角模糊數A=(q1,q2,q3)，可得：

定義1區間隨機集S～R(A)的期望值稱為模糊數A 的期望區間[24]，E(A)可表示為：

定義2模糊數A的期望區間的中心稱為該數的期望值，用ε(A)表示[24]，即：

1.3 問題建模

1.3.1 目標函數 G2E-VRPFD 的優化目標為運輸總成本最小化，其中運輸總成本(F)包含4 個部分，分別為一級車輛的運營成本(F1)、一級車輛的油耗成本(E1)、二級車輛的運營成本(F2)和二級車輛的油耗成本(E2).F1和F2的計算如下：

碳排放主要來源為車輛使用燃油量，文獻[25]表明，燃油消耗量與碳排放量成正比，因此本文采用文獻[12]中考慮速度、載重、距離、發動機排量等因素的綜合油耗模型計算油耗量，并通過油耗量折算為成本加入運輸總成本中.其符號定義如表1所示.根據該模型，一級車輛燃油消耗量成本(E1)和二級車輛燃油消耗量成本(E2)的計算如下：

表1 油耗模型符號定義表Tab.1 Fuel consumption model symbol definition table

式中：c1=KξNV/kψ，c2=ξβ/1 000kψεω，c3=ξ(g(sinθ+Crcosθ))/1 000kψεω.

1.3.2 混合整數線性規劃模型 本節所涉及的數學符號及說明如表2 所示.

表2 GVRPFD 模型符號定義表Tab.2 GVRPFD model symbol definition table

問題優化目標為：

式(13)和式(14)表示各級網絡中，使用的車輛總數不超過該級擁有的車輛總數.式(15)表示中轉站的模糊需求為該中轉站所服務的客戶模糊需求之和.式(16)表示一個客戶有且僅由一個中轉站為其服務.式(17)表示中轉站的容量約束.式(18)表示中心倉庫不能直接服務客戶.式(19)表示在第二級物流網絡中，每條路徑的起點與終點均為同一個中轉站，且每個客戶有且僅由一輛二級車輛對其進行服務.式(20)和式(21)表示相同節點無路徑連接.式(22)表示在第二級物流網絡中，開始和結束都應為中心倉庫.且每個中轉站有且僅由一輛一級車輛為其服務.式(23)和式(24)表示攬收過程中不能超過對應車輛的最大負載.式(25)～(27)表示決策變量.

1.4 問題特點分析及求解思路由圖1 可知，G2EVRPFD 第一級問題為GVRPFD，第二級問題為模糊需求下的綠色多車場車輛路徑問題(green multidepot vehicle routing problem with fuzzy demand,GMDVRPFD).

該問題的兩級問題相互耦合，改變第二級問題的解會影響第一級問題的解.若直接使用智能算法對問題進行整體編碼和求解，解空間為第一級問題和第二級問題解空間乘積，并且隨著客戶數量的增加，造成解空間規模十分龐大；若設計合理的聚類算法將第二級問題分解為ns個相對簡單的子問題，則共有ns+1 個GVRPFD 子問題，再對分解后的各個子問題進行求解，此時問題解空間為各子問題解空間之和，該方法可極大程度縮小問題解空間，并能將算法限制在較小且較優的區域進行搜索，縮短算法搜索時間，提升智能算法的搜索能力.因此，根據G2E-VRPFD 的特點分析，本文先采用聚類分解策略分解為ns+1 個GVRPFD 子問題，再設計智能算法對其求解.

2 混合超啟發式算法(HHHA)

本文采用K-medoids 聚類算法將問題分解為多個GVRPFD 子問題，然后設計EHHEDA 依次求解每個子問題，再合并各子問題之解，得到整個問題的解.

2.1 聚類分解策略由于K-medoids 算法聚類結果相當緊湊，且對孤立點和噪聲數據的敏感性小[26].因此，本文將K-medoids 的聚類算法應用到求解G2-VRPFD 中，將第二級問題分解為ns個GVRPFD.具體步驟為：

步驟1將中轉站坐標設為該算法的初始聚類重心.

步驟2計算各個客戶點到聚類重心的歐式距離.將客戶點分配為最近的聚類重心.

步驟3將每類中每個客戶點均作為聚類重心，計算每個客戶點到該類中其余客戶點的歐式距離，然后選擇歐式距離和最小的點作為新的聚類重心.Ci是聚類重心，Pi是非聚類重心.計算公式如下：

步驟4重復步驟2 和步驟3，直至聚類重心不再改變.

2.2 增強超啟發式分布估計算法求解子問題對于將G2E-VRPFD 聚類分解后的每個GVRPFD 子問題，均采用EHHEDA 求解.EHHEDA 由高層策略域和底層操作域組成，在EHHEDA 的高層策略域采用基于三維概率模型的EDA，用于合理學習高層個體的優良模式，其高層個體是由底層操作域中各搜索算子所組成的排列.在底層操作域設計10 種有效鄰域搜索算子，并加入重升溫操作的模擬退火機制作為問題解（即底層個體）的接受準則，對問題解執行深入的搜索.

2.2.1 編碼與解碼 在高層策略域種群中，每個高層個體采用十進制的編碼方式，一個序號代表相應的底層啟發式算子；且每個個體都由10 個底層啟發式算子 LLHc構成，可允許每個算子重復出現，一個高層個體編解碼示意圖如圖2 所示.解碼時，按高層個體中底層啟發式算子的排序，依次對問題解空間執行搜索.高層個體的評價值等于對相應的低層個體執行底層啟發式算子搜索后的目標函數值.在底層操作域種群中，每個底層個體為原問題的解.本文將G2E-VRPFD 分解后的ns+1個子問題分別用相同的方式進行編碼，編碼方式采用基于客戶以及中轉站排序的十進制編碼.譬如，在第G代中轉站i服務8 個客戶，可記為=[1,2,3,4,8,7,5,6]，解碼過程中，在滿足車輛容量約束的條件下，將中的客戶從左到右分配給各車輛，解碼后可得到該中轉站所有車輛的服務路徑=[(1,2,3),(4,8),(7,5,6)].

圖2 高層個體編解碼示意圖Fig.2 Schematic diagram of coding and decoding of highlevel individuals

圖3 統計矩陣模型生成Fig.3 Generation of statistical matrix model

2.2.2 種群初始化 為避免種群中的解分布過于集中，導致無法對問題解空間進行充分搜索，本文在初始化時，設置每個高層個體和底層個體均隨機生成，且每個高層個體中的底層啟發式算子不重復出現.

2.2.3 底層啟發式算子 LLH 中每個底層啟發式算子是直接對問題解空間進行搜索，因此LLH設計的好壞決定了搜索能力與解的質量.本文根據問題特性，在算法底層操作域中設計了10 種有效的鄰域搜索操作算子，LLH1至 LLH6為車輛內路徑鄰域操作算子，LLH7至 LLH10為車輛間路徑鄰域操作算子.具體為：

(1) LLH1: Swap(πi,j,m,n),m≠n.πi,j表示中轉站i中的車輛j服務路線.在 πi,j中，隨機選擇兩個不相鄰客戶m和n，將m和n交換，生成新的路徑

(2) LLH2: 2-Opt(πi,j,m,n)，m≠n. 在 πi,j中，隨機選擇兩個客戶m和n，將m和n之間的客戶服務順序逆序，生成新的路徑

(3) LLH3: S hift(πi,j,m,n),m≠n. 在 πi,j中，隨機選擇兩個客戶m和n，將客戶m插入在客戶n之前，生成新的路徑

(4) LLH4: S wap_two(πi,j,m,n),m≠n. 在 πi,j中，隨機選擇兩個相鄰的客戶m和n，將客戶m與客戶n交換，生成新的路徑

(5) LLH5: S hift_two(πi,j,s,m,n),s≠m≠n. 在πi,j中，隨機選擇兩個相鄰的客戶m和n插入到隨機選取 πi,j中的客戶點s之前，生成新的路徑

(6) LLH6: Swap_n(πi,j,s,w,m,n),s≠w≠m≠n.在 πi,j中，隨機選擇兩對相鄰的客戶s、w與m、n交換，生成新的路徑

(7) LLH7: Swap*(πi,j,m,πi,l,n),j≠l. 在 πi,j中 隨機選取一客戶點m；另外，在 πi,l中隨機選取一客戶點n，將m和n交換，生成新的路徑

(8) L LH8: S hift*(πi,j,m,πi,l,n),j≠l. 在 πi,j中隨機選取一客戶點m；在 πi,l中隨機選取一客戶點n，將m插入到n之前，生成新的路徑

(9) LLH9: Swap_two*(πi,j,m,n,s,w),j≠l,m≠n,s≠w. 在 πi,j中隨機選取兩個相鄰的客戶點m和n；在 πi,l隨機選取兩個相鄰客戶點s和w，將m、n和s、w交換，生成新的路徑

(10) LLH10:Swap_one*(πi,j,m,n,πi,l,s),j≠l,m≠n. 在 πi,j，隨機選取兩個相鄰的客戶點m和n；在 πi,l隨機選取一個客戶點s，將m、n和s交換，生成新的路徑

溫度通過式(30)影響底層啟發式操作.

式中：Δf為每執行一次底層啟發式算子得到的新解與舊解適應度值的差值.迭代時，每個高層個體中的底層啟發式操作對相應的解均內部執行5 次，若 Δf＜0，則替換舊解；否則生成一個隨機數r∈[0,1]，若r小于概率P，則接受這個較差解，否則不接受.

隨著迭代次數的增加，溫度越來越低，根據概率P值接受差解的可能性隨之降低，模擬退火機制的停滯導致一直在貪婪搜索，陷入局部極小解時停滯不前，降低算法的搜索性能.因此，本文在模擬退火機制中加入重升溫操作，算法最優解持續未改變時，適當提升溫度，從而激活較差解的接受概率，對當前解進行一定概率的擾動.升溫公式如下：

式中：Δt為最優解持續未改變的迭代次數，u和b為常數.

2.2.4 分布估計算法 三維概率模型基于二維概率模型，能夠進一步準確記錄操作塊在優質解中的具體位置信息，保護較優解操作序列不被破壞，從而合理地引導種群進化方向.因此，本文設計一種基于三維概率模型的分布估計算法作為高層策略，對高層策略域種群進行優化.

在高層個體中，將整個底層啟發式操作序列中的兩個相鄰操作視為操作塊.高層個體π1=[2,4,6,9,1,3,1,7,6,8]為 例，其中 [2,4]、[4,6]、[6,9]等為操作塊，共有9 個操作塊.

為研究高層策略域中優質個體啟發式操作序列中的操作塊分布特征，設計了一種統計矩陣模型構建三維概率模型.用于統計優質高層個體中操作塊[y,z]在位置x上的分布特征，層次結構如式(32)所示，統計方式如式(33)所示.

歌唱是通過聲音來表現的。在藝術性歌唱中，歌唱的音色就好象繪畫中的色彩，音色的好壞可直接影響歌唱的效果，是音樂中極為動人，最直接觸動觀眾，也是表達真情實感不可缺少的條件。不同的音樂表現不同的音樂形象。歌唱者要學會巧妙地運用自己的聲音色彩。根據作品內容，選用恰當的音色，貼切地表現作品。

2.2.6 算法流程 求解子問題的EHHEDA 具體步驟如下：

步驟1算法參數初始化，三維概率矩陣初始化；

步驟2隨機初始化高層策略域種群和底層操作域種群.

步驟3將高層個體中的每個底層啟發式操作算子對相應的底層個體執行搜索，每執行一次搜索采用模擬退火機制判斷是否要接受該解，直至種群中所有高層個體都執行完畢.

步驟4評價底層種群，并將種群中底層個體和對應的高層個體按照目標函數值升序排序.

步驟5選擇高層種群中的Nmax×ρ個優質個體，更新統計矩陣.

步驟6更新三維概率矩陣.

步驟7輪盤賭采樣更新高層策略域種群.

步驟8若最優解持續超過b代未改變，模擬退火機制采用公式(31)重升溫；否則，采用公式(29)降溫.

步驟9判斷是否到達終止條件.若算法達到終止條件，則輸出最優解；否則調整至步驟3.

3 實驗設計與分析

目前暫無G2E-VRPFD 的標準測試數據，故本文采用文獻[6]中的部分算例組成的測試集，客戶的需求量基于三角模糊數隨機生成，改編后的數據地址：https://pan.baidu.com/s/12JFy_nJ-1XOB145Oz n4-eQ?pwd=a123(提取碼：a123).本文利用Python 3.8對本文中所有算法進行編程測試，操作系統為Windows 10,CPU 主頻為2.40 GHz，8 GiB 內存.對所選取的不同規模測試集，每種算法均在相同時間20×nc×nsms 下，運行20 次.

3.1 關鍵參數設置G2E-VRPFD 模型中的油耗模型中的系數設定參考文獻[13]，燃油費用系數設參考文獻[27]；運營成本系數設定參考文獻[28].第2.2.3 節加入重升溫操作的模擬退火機制中，初始溫度T=100，b=3，系數u=10.

在HHHA 中，主要參數有種群規模Nmax、學習率 γ、精英個體所占比例 ρ和冷卻系數 λ.為考察各參數設置對算法效果的影響，本節采用文獻[29]實驗設計方法DOE 確定HHHA 的參數取值.上述4 個參數均取4 個水平值，如表3 所示.

表3 HHHA 各參數水平表Tab.3 Level table of main parameters

基于表3，采用正交表L16(44)，使用中等算例75×5_1在16 組不同水平參數組合下進行實驗.每組參數在相同時間內獨立運行20 次，20 次結果的平均值作為平均響應值AVG，AVG 越小則代表在相應的參數設置下算法性能越好.正交表和AVG統計值如表4 所示.

表4 正交表和 R 統計值Tab.4 Orthogonal table and R statistics

根據表4 中的AVG 統計值，得到表5 中各個參數在不同水平下的平均響應值和等級，其中等級一欄表示參數對算法性能的影響力等級排名，以及各參數的響應趨勢圖（圖4），每組水平的最低點表示算法性能占優.

表5 HHHA 各參數響應值Tab.5 Response value of HHHA parameters

圖4 HHHA 各參數在不同水平下的響應趨勢圖Fig.4 Response trend of HHHA parameters at different levels

由表4、表5 和圖4 可知，當HHHA 的參數設置為：Nmax=40，γ=0.6，ρ=0.5，λ=0.9時，其性能在不同參數組合下的各算法中占優.因此，后續測試中按此設置HHHA 的參數.

3.2 仿真結果比較與分析本文通過所設計的接受準則、高層策略域算法以及整體算法這3 個部分，驗證所提算法的有效性.其中，用R1、R2和R3分別表示一個算例獨立運行20 次輸出本文目標函數值最小化運輸總成本的平均值、最優值和最差值.

基于所有算例獨立運行20 次結果的橫向均值，得到6 個不同智能算法與HHHA 比較的95%置信區間圖如圖5 所示，縱坐標表示橫向平均目標函數值.算法區間圖所處的位置越低，表示該算法性能越好；區間越小，算法越穩定.

圖5 HHHA 和6 種不同算法比較的95%置信區間圖Fig.5 95% confidence interval diagram of HHHA and 6 different algorithms

3.2.1 驗證接受準則有效性 為驗證HHHA 中底層啟發式算子嵌入的重升溫操作的模擬退火機制作為接受準則的有效性，在文本問題上，將其與接受準則為只接受好解的HHHA(HHHA_V1)和接受準則為模擬退火機制但是無重升溫操作的HHHA(HHHA_V2)進行比較.實驗結果見表6，HHHA 與HHHA_V1、HHHA_V2 的95%橫向均值區間置信圖見圖5(a).

表6 接受準則性能驗證Tab.6 Performance verification of acceptance criteria

由表6 和圖5(a)可知，HHHA 優于HHHA_V1和HHHA_V2.原因在于，將只接受好解作為接受準則的HHHA_V1，迭代過程中一直在貪婪搜索，算法容易較早的陷入局部最優狀態，無法跳出，在后期浪費不必要的搜索時間，降低搜索能力.而將每個底層啟發式算子中嵌入模擬退火機制，未加入重升溫操作作為接受準則的HHHA_V2，雖然在算法迭代前期，模擬退火機制以一定概率接受差解，避免算法較早陷入局部最小，但在后期隨著溫度的不斷降低，導致模擬退火機制停滯，而HHHA 中的重升溫操作在達到一定條件下可激活模擬退火機制，提升算法全局的搜索能力.因此在將底層啟發式算子嵌入重升溫操作的模擬退火機制作為接受準則有一定有效性.

3.2.2 驗證高層策略有效性 為驗證HHHA 中的EHHEDA 高層策略有效性，在不同規模測試集上，分別將其與傳統GA 作為高層策略的超啟發式算法(HHGA)和傳統EDA 作為高層策略的超啟發式算法(HHEDA)進行實驗對比，算法其余部分保持一致.實驗結果見表7，HHHA 與HHGA、HHEDA的95%橫向均值區間置信圖見圖5(b).

表7 高層策略性能驗證Tab.7 Performance verification of high-level strategy

由表7 和圖5(b)可知，HHHA 優于HHGA 和HHEDA，且HHHA 更穩定.一方面，HHHA 作為一種學習型的智能算法，可避免HHGA 這類經典進化算法在每次迭代時，通過交叉變異操作對種群中較優高層個體的破壞，導致過多無效的操作，降低算法的搜索效率；另一方面，HHHA 通過學習高層個體中操作塊位置信息來更新高層種群，可在一定程度上避免HHEDA 對優質操作塊的破壞，更為合理地學習高層個體的優良解模式.

3.2.3 驗證本文整體算法有效性 因目前無G2EVRPFD 的相關研究，為驗證HHHA 的整體有效性，在本文問題上，將HHHA 與國際期刊上求解相似問題的VNS[12]和IGA[30]進行對比.其中VNS 和IGA 均是對整個問題進行編解碼，無聚類分解階段.各算法比較結果如表8 所示，HHHA 與VNS、IGA 的95%橫向均值區間置信圖見圖5(c).

由表8 和圖5(c)可知，隨著客戶數量的增加，HHHA 顯著優于VNS 和IGA 算法，且HHHA 算法穩定型更強.表明對兩級問題整體編碼并求解，難以在短時間內獲得滿意的解.以算例21×2_1（客戶、中轉站和中心倉庫的數量分別為21、2 和1）為例，若對該算例整體編碼與求解，解空間為S1=21!×2!.如果采用k-medoids 算法將該算例的第二級問題分解為兩個GVRPFD 子問題：客戶數分別為12 和9，則第一級問題中的2 個中轉站容量便可以根據這兩個客戶數固定下來，實現了兩級問題間的解耦，而此時的解空間為S2=12!+9!+2!.顯然，S2遠遠小于S1.因此，采用有效的分解策略可明顯縮減搜索區域，將算法引導至較優區域進行搜索，有利于提高算法的搜索效率.此外，VNS 和IGA 這類常規的智能算法，在迭代循環時，均采用固定順序的幾個局部搜索操作對問題解空間進行搜索，未考慮到操作順序對搜索能力的影響，使算法在對解空間搜索時有一定局限性.而HHHA 中的EHHEDA 通過采用高層策略學習優質個體中啟發式操作順序，動態混合多種底層啟發式算子更新種群，實現對問題解空間的搜索，可較易發現解空間不同區域的優質解，提高算法的搜索能力.因此，HHHA 在測試算例中表現優異.

4 結論

本文針對模糊需求下的綠色兩級車輛路徑問題（G2E-VRPFD），考慮距離、載重、速度等多個因素，使用綜合油耗模型計算方法，建立以最小化車輛運營成本和油耗成本之和為優化目標的數學模型，進而結合問題特性提出一種混合超啟發式算法（HHHA）進行求解.所提算法具有如下優點：

（1）考慮G2E-VRPFD 的解空間龐大且兩級問題相互耦合，采用K-Medoids 算法對G2E-VRPFD進行分解，可明顯縮減搜索區域，從而能一定程度上避免無效搜索；

（2）EHHEDA 的高層策略域采用基于三維概率模型的分布估計算法，能合理學習和積累優質高層個體的操作塊信息，從而可有效引導和控制算法搜索行為，有助于提升算法搜索效率；

（3）EHHEDA 的底層操作域設計10 種高效底層啟發式算子（即鄰域搜索算子）來共同執行對問題解空間的搜索，并加入重升溫操作的模擬退火機制，以幫助算法跳出局部極小，可加大算法搜索的深度，從而能進一步增強算法性能.

通過在不同規模測試集下的仿真實驗和算法對比，驗證了所提算法可有效求解G2E-VRPFD.后續工作將進一步研究考慮路況的綠色兩級車輛路徑問題的建模與求解.