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

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

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

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

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

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

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

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

1 G2E-VRPFD 的問題描述及數(shù)學模型

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

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

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

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

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

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

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

1.3 問題建模

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

碳排放主要來源為車輛使用燃油量，文獻[25]表明，燃油消耗量與碳排放量成正比，因此本文采用文獻[12]中考慮速度、載重、距離、發(fā)動機排量等因素的綜合油耗模型計算油耗量，并通過油耗量折算為成本加入運輸總成本中.其符號定義如表1所示.根據(jù)該模型，一級車輛燃油消耗量成本(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 混合整數(shù)線性規(guī)劃模型 本節(jié)所涉及的數(shù)學符號及說明如表2 所示.

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

問題優(yōu)化目標為：

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

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

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

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

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

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

步驟1將中轉(zhuǎn)站坐標設(shè)為該算法的初始聚類重心.

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

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

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

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

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

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

圖3 統(tǒng)計矩陣模型生成Fig.3 Generation of statistical matrix model

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

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

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

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

(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ā)式操作.

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

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

式中：Δt為最優(yōu)解持續(xù)未改變的迭代次數(shù)，u和b為常數(shù).

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

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

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

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

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

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

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

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

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

步驟5選擇高層種群中的Nmax×ρ個優(yōu)質(zhì)個體，更新統(tǒng)計矩陣.

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

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

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

步驟9判斷是否到達終止條件.若算法達到終止條件，則輸出最優(yōu)解；否則調(diào)整至步驟3.

3 實驗設(shè)計與分析

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

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

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

表3 HHHA 各參數(shù)水平表Tab.3 Level table of main parameters

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

表4 正交表和 R 統(tǒng)計值Tab.4 Orthogonal table and R statistics

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

表5 HHHA 各參數(shù)響應(yīng)值Tab.5 Response value of HHHA parameters

圖4 HHHA 各參數(shù)在不同水平下的響應(yīng)趨勢圖Fig.4 Response trend of HHHA parameters at different levels

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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