分布估計灰狼算法求解低碳選址路徑問題

張 坤,張惠珍,馬 良,張 博

(上海理工大學 管理學院,上海 200093)

選址路徑問題(Location-Routing Problem,LRP)是一類經典的組合優化問題,需要同時確定候選設施建立的位置以及車輛行駛的路徑。隨著Cooper[1]首次提出LRP,將設施選址問題(Facility Location Problem,FLP)與車輛路徑問題(Vehicle Routing Problem,VRP)結合起來后,學界與業內逐漸發現選址與路徑決策的耦合性很高,因此,LRP也成為了供應鏈、物流以及運籌優化領域的熱點問題。截至目前,將標準LRP與實際應用相結合,多種擴展LRP 已被提出,如有容量限制的LRP(Capacitated LRP,CLRP)[2]、帶時間窗的CLRP(CLRP with Time Windows,CLRPTW)[3]和多車型 CLRP (CLRP with Heterogeneous Fleet,CLRPHF)[4]等。

近年來,隨著生態環保意識的普遍提升,低碳物流已成為運籌優化和物流領域的另一個研究熱點,通過在物流優化問題(LRP,VRP等)中加入低碳物流要素,旨在提高物流環節效率,減少碳排放量。為此,國內外學者深入研究了車輛行駛過程中的碳排放計算方法。Score等[5]和Barth等[6]基于具體車型的詳細參數對車輛的瞬時油耗進行估計。Charis等[7]提出了一種數據驅動模型,通過對發動機類型以及車輛屬性等一系列歷史數據估算車輛在行駛中的碳排放。在提高估算精度的同時,許多學者亦對估算方法做了適當的簡化以適應優化計算。Zhang等[8]設計了一種考慮行駛距離、車輛平均速度和車輛負載等參數的平均消耗模型以解決低碳背景下的VRP。Xiao等[9]在VRP 中考慮了車輛負載對油耗、碳排放的影響,其統計結果顯示油耗量與車輛負載線性相關。張春苗等[10]和王舜等[11]在LRP中加入碳排放計算方法,提出了LCLRP(Low-Carbon LRP),并討論了物流網絡中運輸成本與碳排放的關系。

此外,宏觀層面的政策研究也帶來了一定啟示。已有研究表明,合理的碳交易定價機制和碳足跡測算方法是實現節能減排的關鍵之一[12-13]。碳定價機制是當前國際上用于減少碳排放的主要政策工具,其以市場化手段解決了碳排放負外部性的內生化問題[14],有望成為中國溫室氣體減排的主要政策[15]。因此,基于碳定價背景下的物流優化,可以準確計算運輸過程中的碳排放,同時在決策層面統一碳排放量與物流成本的量綱,降低企業的決策難度。為此,本文在CLRP模型的基礎上加入油耗計算公式[9],并在碳定價背景下構建了計算總成本的方法,建立了碳定價背景下的LCLRP 模型,該模型更貼近現實情況,能為決策者提供較好的決策依據和支持。

基本LRP 及其擴展問題均屬于NP-Hard 問題。對于大規模LRP,精確算法往往無法在可以接受的時間內對其求解。因此,在有限時間內可以求得滿意解的啟發式算法成為了求解該問題的主要方法。Wang等[16]和胡大偉等[17]在求解LCLRP時加入了變鄰域搜索算法(Variable Neighborhood Search,VNS)。冷龍龍[18]提出了一種新的超啟發式方案求解異構車隊的同時送取貨選址路徑(LRP with Simultaneously Pickup and Delivery。LRPSPD)。Cao等[19]利用文化基因算法求解了低碳背景下的電動車路徑問題。這些方法在實際求解中均取得了不錯的效果。

由無免費午餐定理可知,沒有任何一種算法對所有同類問題均能表現出良好的性能,因此將不同優化算法的搜索機制及策略相融合,構建求解性能更高的混合算法已成為目前智能優化領域的一大研究方向。灰狼算法(Grey Wolf Optimizer,GWO)是一種模擬狼群狩獵與圍攻行為來搜索最優解的新興智能算法[20],其能夠較好地跳出局部最優,具有較強的全局搜索能力且所需調整的參數少。分布估計算法(Estimation of Distribution Algorithms,EDA)是一類基于種群迭代產生的新興啟發式算法,通過學習優良解的概率分布以實現種群進化,其全局搜索能力強且易于實現,并在生產調度領域表現出了良好的效果[21-23]。為了擴展GWO 及EDA的應用領域,并為LRP及其擴展問題提供一種有效的求解方法,本文將GWO 及EDA 相結合,使其相互取長補短,設計了一種分布估計灰狼算法(Grey Wolf Optimizer with Estimation of Distribution Algorithms,GWOEDA),并將其用于所構建的LCLRP模型的求解。

1 基于碳定價機制的低碳選址-路徑模型(LCLRP)

本文考慮的LCLRP可被描述為:給定M個候選設施點和N個需求點(任意需求點間均聯通),從M個候選設施點中選擇開放若干設施并規劃配送路徑,以完成對N個需求點的配送任務,并使總成本(包括設施啟用成本、運輸成本和碳排放成本)最小。

1.1 碳排放成本

構建優化模型時,由于車輛詳細參數以及行駛過程的瞬時速度難以預測,故通常將車輛行駛時的速度設為勻速[9-11],在模型中僅考慮車輛的負載與行駛距離。車輛行駛過程中的油耗與負載呈線性關系,可近似表示為[9]

式中:ρ(h)為車輛載貨時單位行駛距離的油耗量,h為其負載量;ρ*與ρ0分別為滿載與空載時的油耗量;m為車輛最大容量。

以往研究中,減少油耗量通常被視作減碳的等價手段[10-11],在此基礎上,本文模型合理地計算了總運輸成本,并添加了碳稅項以表現決策方在碳定價背景下的碳排放成本。載重為h的車輛從點i行駛至點j的碳排放成本為

式中,碳排放量由單位油耗量ρ(h)、i與j之間的距離oij和燃油轉換系數η相乘得到。碳排放量與碳排放成本(碳稅或碳交易價格)可以通過固定價格φ進行轉化[13]。

1.2 模型假設與符號說明

為便于構建模型,給出如下假設:

(1) 候選設施點的位置、最大容量以及建設成本已知。

(2) 需求點的位置和需求量已知。

(3) 車輛單位負載單位行駛距離的運輸成本、車輛最大負載以及啟用成本已知。

(4) 車輛必須由某設施點出發并回到該設施點。

(5) 設施點間無車輛往來。

(6) 每輛車只被啟用一次。

模型所用符號說明:

集合

I——需求點集合,I={1,2,…,n}

J——候選設施點集合,J={n+1,n+2,…,n+m}

G——G=I∪J

K——車輛

集合

參數

di——需求點i的需求量,i∈I

ej——設施j的開放成本,j∈J

cj——設施j的最大容量,j∈J

sk——車輛k的啟用成本,k∈K

mk——車輛k的最大容量,k∈K

rk——車輛k的燃油價格,k∈K

oij——點i至點j的距離,i,j∈G

φ——交易市場中單位指標碳排放價格

ηk——車輛k的油耗轉換碳排放 量系數,k∈K

——車輛k滿載時單位行駛距離的油耗量,k∈K

決策變量

xijk——0-1變量(若車輛k從節點i訪問j則為1,否則為0),?i,j∈G,k∈K

yjk——0-1變量(若車輛k分配給設施點j則為1,否則為0),?j∈J,k∈K

zj——0-1變量(若設施點j啟用則為1,否則為0),?j∈J

hjk——實數變量,表示車輛k離開節點j時的負載,?j∈G,k∈K

1.3 LCLRP的非線性混合整數規劃模型

在上述假設條件與參數設定的基礎上,本文所構建的碳定價背景下的LCLRP模型描述如下:

目標函數式(3)最小化總成本,包括:設施開放成本、車輛啟用成本、油耗成本和碳排放成本。式(4)為碳定價情景下的碳排放計算公式。約束條件式(5)～(7)表示只有開放的設施才能服務需求點,且每個需求點必須有且僅有一輛車為其提供服務;式(8)表示車輛駛入需求點后也必須駛出;式(9)表示每輛車至多被啟用一次;式(10)表示每個需求點必須被服務一次;式(11)表示設施點間無車輛往來;式(12)表示每輛車不能超過其最大負載;式(13)表示設施點不能超過其最大容量;式(14)表示車輛負載的連續性;式(15)為消除子回路約束;式(16)表示車輛離開設施點時負載為0;式(17)～(19)為決策變量取值范圍。

混凝土澆筑主要質量控制點之一“澆筑前”，嚴格控制“人、材、機”。人員方面，配置有經驗的工人進行混凝土振搗；材料方面，在現場進行混凝土坍落度試驗，保證混凝土和易性適合肋拱施工；在機械方面，對臨時發電機、拌合站、罐車、吊車進行檢查保養；倉面使用2個50 mm軟軸振搗棒，備用2個50 mm軟軸振搗棒。

2 分布估計灰狼算法

原始GWO 通過模仿自然界中灰狼的分級和狩獵制度對解空間進行搜索[20],種群中適應度最優的個體被稱作α狼,排名第2及第3的個體為β狼和δ狼,其余狼均為ω狼。在狩獵(搜索)階段,ω狼同時利用3個領導狼的信息來更新自身位置,逐步逼近獵物(最優解),進行捕獵[20]。

GWOEDA 在GWO 的基礎上加入EDA,以提高算法對于路徑問題的求解性能,在整個灰狼種群的進化過程中,每個個體中的路徑編碼依據EDA估計得到的概率模型來生成。GWOEDA 的基本思路為:首先,初始化概率模型生成初始種群;然后,利用灰狼算法的進化規則更新ω狼,并對領導狼執行鄰域搜索進一步改進優良解的質量;最后,根據種群中的精英個體更新概率模型。上述過程循環迭代直至滿足終止條件。

2.1 編碼方式

使用整數編碼表示個體(可行解),每個個體包含一條或多條配送路徑;每條路徑由一組需求點和一個設施點組成,表示某一配送車輛從該設施點出發,按照需求點的排列順序完成收集任務。例如:給定具有3個候選設施點和10個需求點的LCLRP,圖1給出了該問題的一個可行解編碼。該可行解由3條收集路徑組成,路徑1車輛由11號設施出發,完成對需求點6和5的收集任務后返回11號設施;路徑2和3均從12號設施出發,路徑2完成需求點7,1,3的收集任務,路徑3完成需求點2,10,8,4,9的收集任務。候選設施點13未出現在該可行解的編碼中,表示其不開放。

圖1 解的表示

2.2 概率模型

利用EDA 算法中的概率模型表示LCLRP 中節點間的相關性,本文中的概率模型設置為二維矩陣,矩陣元素的值越大,表示連接對應兩個節點的路徑在精英灰狼中出現的次數越多。

為了保留迭代中的歷史信息,對每一代種群采樣得到的矩陣At進行累加得到相關性矩陣,即

式中,ρ為相關性矩陣的衰減比例,目的是防止算法過早地陷入局部最優。

利用距離矩陣D和相關性矩陣Ct構建概率矩陣,即

Ct中的最大值在αt對應位置轉化為最小值,以保證其符合距離矩陣D的價值排序。矩陣DTB中的數據元素值越小,表示對應路徑在最優解中出現的概率越大。生成初始種群時僅利用距離矩陣(即h=1)生成初始解,并且由于迭代初期種群的適應度值較差,在算法迭代初期,令相關性矩陣Ct所占比重較小。而隨著迭代次數增加,相關性矩陣所占比重逐漸增加且距離矩陣所占比重由h逐漸衰減至0。

2.3 解的生成

利用概率矩陣構建可行解,具體流程如下:

步驟1隨機選擇一個未被訪問的需求點作為初始點;

步驟2構造當前需求點的允許訪問節點集合allowk;

步驟3根據式(24)計算allowk中節點的選擇概率,并依概率選擇下個需求點

步驟4若滿足2.4節中的路徑終止條件,則依據2.5節中的設施分配原則,為該配送路徑分配設施,并返回步驟1;否則,轉步驟2。

2.4 路徑終止條件

LCLRP中一條路徑的運輸成本與車輛負載呈正相關,因此,在車輛接近滿載時繼續訪問下一節點所帶來的成本可能會超過啟用新車輛。為此,需要控制車輛的平均載重率,平衡每輛車的行駛距離和負載。

通過路徑終止條件控制車輛的平均載重率。路徑終止概率p由下式計算得到,

若訪問下一需求點將違反車輛容量約束,則路徑終止概率p=1,終止路徑;若尚未違反車輛容量約束,則生成[0,1]的隨機數rand,當rand

式(25)中,dtemp為下一個將被加入路徑的節點的需求量,通過調整式(25)中的參數a,可以控制車輛的平均載重率,且不會固定所有解中路徑的數量。

2.5 倉庫分配原則

對所有可用設施點,一方面,按其已被使用容量進行升序排列,得到每個可用設施點的排序值rankCT;另一方面,按其與當前配送路徑中所有需求點的距離之和降序排列,得到每個可用設施點的排序值rankDT。綜合考慮每個可用設施點的排序值rankCT和rankDT,由下式可計算得到所有可用設施點對當前路徑的得分GradeT,選擇GradeT值最高的候選設施為當前路徑提供服務,

式中,v為調整容量與距離在評分時所占的權重。

2.6 多父代交叉

采用多父代交叉[24](Multi-parent Sequential Constructive Crossover,MPSCX)的方法模擬原始GWO 算法中ω狼利用α、β和δ狼的位置信息對其更新。具體方法為:首先,剔除ω狼與領導狼中的設施節點,保留需求點的排序不變;其次,隨機選擇某一待訪問需求點作為一條配送路徑的第1 個節點,并將ω狼與領導狼中需求點排列順序中位于當前需求點之后的待訪問需求點組成允許訪問集合allowk;再次,利用概率矩陣判斷allowk中各需求點的重要程度,依概率選擇所訪問的需求點;最后,通過路徑終止條件決定是否終止路徑并分配設施點。

給定如圖2所示的ω、α、β和δ狼中需求點的排列順序,假設隨機選擇8號需求點為某一配送路徑的初始訪問節點,則8 號需求點的允許訪問集合allowk為{4,2,6,5}。根據式(24)得到訪問集合中待訪問需求點4,2,6,5 的選擇概率分別為0.8、0.1、0.04和0.06,若依概率選擇4號需求點作為下個訪問的需求點,則4號需求點的allowk為{9,5,2,10},再依據概率從該允許訪問集合中選擇所訪問的需求點。依此類推,每次進行節點選擇時判斷是否需要終止路徑,插入候選設施點。

圖2 多父代交叉

2.7 兩點交換

兩點交換算子首先采用輪盤賭方法選擇一條路徑,并從中選擇一個需求點,將其與另一條路徑中的節點交換,步驟如下:

步驟1計算出個體中所有車輛在各自路徑上的花費,并依據輪盤賭法分配選擇概率。

步驟2依概率選擇其中一條路徑,選擇該路徑中距離設施點最遠的節點記作p1,該路徑所使用的設施點記作F1。找到距離p1最近的設施點記為F2。

步驟3計算由F2服務的所有需求點對應的scores,其值由與F2及F1距離的差值決定,依概率選擇scores高的節點作為p2,即

步驟4交換p1、p2的位置,若滿足約束條件,則輸出交換后的解;若不滿足約束條件,則輸出初始解。

圖3是一個兩點交換的例子。假設對于3條路徑的運輸成本(路徑1 >路徑2 >路徑3),用輪盤賭法從路徑1中選擇距離其設施點11較遠的節點7。接著利用式(27)計算分數得到節點8作為被交換節點,交換7與8并判斷編碼的可行性。

圖3 兩點交換算子

2.8 單點插入

單點插入會依概率選擇成本高的路徑,從中選擇距離其設施點最遠的需求點插入其他路徑。

步驟1計算出個體中所有車輛在各自路徑上的成本,并依據輪盤賭法選擇花費較大的路徑。

步驟2依概率選擇其中一條路徑,選擇該路徑中距離設施點最遠的節點記作p1,該路徑所使用的設施點記作F1。找到距離p1最近的設施點記為F2。

步驟3隨機選擇F2中的一條路徑插入p1。

圖4中存在3條路徑,依據各自的路徑成本用輪盤賭法選出路徑1,找到其中距離設施點最遠的節點7,距離節點7最近的設施點為12,隨機將節點7插入12所在的路徑中。

圖4 單點插入算子

2.9 算法流程

GWOEDA 的具體流程如下:

步驟1根據式(22)初始化概率模型,此時h=1,即等價于距離矩陣。

步驟2利用貪心算法,根據2.3節中的個體生成規則生成初始種群。

步驟3對種群中的個體進行排序,確定領導狼與被領導狼,并采樣種群,更新概率圖和系數h。

步驟4更新ω狼的位置,生成隨機數rand(0,1),若小于系數p,則使用多父代交叉算子進行引導,否則使用生成初始種群的方法替換該狼,以增加種群多樣性。

步驟5使用兩種鄰域搜索算子對領導狼改進次。改進后的結果若比之前更優,則改進被接受;若劣于原個體,則以概率b接受。

步驟6滿足終止條件,則輸出結果,否則返回步驟3。

2.10 時間復雜度分析

從種群規模popsize,迭代次數iteration,父代數量parent,路徑截斷系數k,以及鄰域搜索系數c和算法流程評估最壞時間復雜度。

在算法主程序調用的所有函數中:初始化距離矩陣的時間復雜度為O(n2);初始化個體編碼的時間復雜度為O(n+f(k)),其中f(k)為不同的系數k所決定的路徑數量,由此可得生成初始種群的時間復雜度為O(popsize(n+f(k)));對每個個體進行解碼的時間復雜度為O(popsize(n+f(k)));利用快速排序對種群個體進行排序的時間復雜度為O(popsiez log popsize);對非父代個體一次MPSCX 算子的時間復雜度為O((n+f(k))(n+f(k)+1)/2);兩點交換與單點插入算子的時間復雜度均為O(2n)。記popsize=S,iteration=I,parent=P,計算得到GWO 的時間復雜度為

式中,g(c)為算法中由系數c所決定的鄰域搜索次數。

GWOEDA 在GWO 的基礎上每次迭代更新一次分布矩陣,其時間復雜度為O(n2),則GWOEDA的時間復雜度為

3 算例分析

為了驗證分布估計策略對算法性能的提升效果,使用結構相同的兩種灰狼算法進行對比,一種僅利用距離矩陣作為決策信息(固定式(22)中的h=1),另一種利用分布估計迭代更新的概率矩陣作為決策信息。所有程序均由Matlab R2019b編寫,并運行在配置為16.0 GB RAM,AMD Ryzen 3 700X 3.6 GHz,操作系統為64位的Windows 10主機。

3.1 測試算例

為了驗證基于分布估計策略的混合灰狼算法在求解LCLRP 模型上的有效性,實驗部分求解了CLRP 標準算例 (http://prodhonc.free.fr/Instances/instances_us.htm)中的Prins數據,并在其基礎上進行相應改造來進行實驗。

對于Prins標準算例,其運輸成本計算公式為

將其改造后的運輸成本計算公式為

根據對現階段國內市場情況的調研,式(31)中:單位燃油價格rk=250;燃油轉換碳排放系數ηk=2.63;單位碳排放定價φ=20。式(4)中:空載單位距離油耗ρ0=0.77;滿載單位距離油耗ρ*=1.54。

表1 給出了標準算例庫中測試所用的8 個算例,為了區別原始CLRP 算例與經改造所得的LCLRP算例,將LCLRP算例編號用*加以標記。

表1 算例數據

3.2 參數設置

為了得到最優的參數組合,對GWO 與GWOEDA分別采用L16(43)和L25(45)正交表進行參數選取,選用算例3作為測試數據。由于MPSCX算子對于父代個數有相當程度的敏感性[24],故算法中對原始灰狼算法中的領導狼個數進行調整,使其作為參數進行選擇。表2 中,popsize 為種群規模,parent為領導狼個數,h為分布初始化時距離矩陣所占比重,p為選擇全局搜索算子的系數,c為影響鄰域搜索次數的系數(系數越小,每次迭代中鄰域搜索的比重越大)。參數水平如表2所示。

表2 參數水平

本文主要列出GWO 與GWOEDA 在不同parent水平上的參數分析。圖5所示為兩種算法在不同parent水平下的正交實驗結果。圖中曲線顯示了算法求解性能隨著parent數量增加而提高的過程,同時,隨著parent數量的增加,算法運行時間也有一定增長。

圖5 GWO 與GWOEDA 的parent參數水平分析

為了更進一步分析parent對算法性能與求解時間的影響,將在其余參數確定的情況下擴展parent的取值范圍進行算法效率分析。實驗方法如下:固定一組相同的初始種群,設置迭代次數為1 000次。記錄不同parent水平下每次迭代的運行時間tn和當前迭代搜索到的最優解bestn。記錄每次迭代中最優解的變化impn=bestn-bestn-1,并得到最優解在單位時間內的變化率efficiencyn=impn/tn。

圖6所示為GWO 與GWOEDA 在parent水平6、9、12、15、18、21下算法運行的累計時間曲線。不同的parent取值在很大程度上影響算法的求解時間,parent=21的計算時間相比parent=12增加了50%～90%,相比parent=6 增加了150%～180%。

圖6 GWO 和GWOEDA 不同parent下的求解時間

圖7、8分別刻畫了GWO 和GWOEDA 在不同parent水平下搜索到的最優解bestn以及對應的最優解變化率。不同parent參數在兩種算法中的表現較為一致:較小的取值(parent=6)在時間成本上表現良好,但在最優解bestn和最優解變化率efficientn上表現不佳;而較大的取值(parent=21)通常可以使算法在迭代初期快速收斂,但相對的是高額的時間成本,并且隨著算法迭代次數的上升,在最優解的表現上與其余取值相差不大。當parent=12時,算法在求解能力bestn上與更高數量的父代表現相近,并且由于其較小的時間成本,在迭代次數接近1 000時具有最佳的求解效率。

圖8 GWO 和GWOEDA 不同parent下的求解效率

綜上可知,取parent=12 作為最終取值,完整的參數設置如表3所示。

表3 參數設置

3.3 分布估計策略性能分析

分別使用GWO 與GWOEDA 對8個CLRP算例和8個LCLRP算例進行求解。將每個算例使用兩種算法獨立運行20次,最大迭代次數為800,求解結果如表4、5所示。其中,Avg為20次的平均結果,Max和Min表示最好與最差結果。

表5 GWO與GWOEDA在LCLRP數據集上的結果

表4、5 的結果表明,在標準CLRP 與LCLRP中GWOEDA 都表現出了更好的效果,對于8個標準CLRP算例以及與其相應的8個LCLRP 算例,GWOEDA 對絕大多數算例的求解結果均優于GWO 算法的求解結果。這說明,使用概率模型的GWOEDA 算法不僅在尋優能力上更有優勢,而且算法的自適應性更強。由于加入了分布估計的步驟,GWOEDA 相比GWO 在求解時花費了更多時間,但仍在可接受范圍內。

3.4 低碳模型的效用分析

為了更好地說明本文所構建的LCLRP模型的可行性及其對物流配送減少碳排放量的實際應用性,將利用GWOEDA 算法求解標準CLRP算例求得的最優配送路徑代入所構建的LCLRP 模型中,計算得到的目標函數值如表6所示。表6給出了標準CLRP 和LCLRP 的最優目標函數值,并將CLRP所得到的最優路徑代入LCLRP 的目標函數中得到結果RS。比較表6給出的3組目標函數值,不難發現,LCLRP 算例的最優目標函數值遠小于CLRP 算例得到的路徑。這表明,本文所構建的LCLRP模型可以有效降低物流配送中的碳排放成本,從而降低物流配送總成本。

表6 CLRP的最優解在LCLRP上的成本

3.5 GWOEDA的有效性評估

為了說明GWOEDA 在求解CLRP上的性能,本節用GWOEDA 求解了10組Barreto算例,并將其求解結果與GRASP[25]、LRGTS[26]、2-phaseHGTS[27]、HGA[28]、HPSO[29]和GWO 的求解結果對比分析,如表7 所示。其中,BKOV 是算例已知的最優解,BOV 是算法求解到的最好結果,T為運算時間。GRASP、LRGTS和2-phaseHGTS由C++編寫,運行環境參照文獻[25-27],HGA、HPSO、GWO 和GWOEDA 均 由Matlab 編寫,并運行在配置為16.0 GB RAM,AMD Ryzen 3700X 3.6 GHz的主機上。由于后4種算法為進化算法,為了保證公平的比較,本節中將終止條件統一設置為:最好結果經過n次迭代未有改進,其中n為相應算例規模,此時表明算法已找到全局或局部最優解。

表7 Barreto算例的求解結果

由表7 可知,GWOEDA 與HPSO 均能得到9個最好結果,在性能上領先其余算法。在時間效率層面,GWOEDA 雖然得到了規模在50以下問題的所有最優解,但在小規模問題的求解時間上表現并不突出。與GWO 對比時,GWOEDA 對于更大規模的問題在性能和效率上會表現更好。可能的原因是,由于分布估計策略需要對每一代的種群進行漸進學習,同時按照概率選擇生成個體,故搜索能力雖然更強,但收斂效率較慢。

4 結語

針對碳定價背景下的低碳選址-路徑問題進行建模,并設計了一種基于分布估計策略的混合灰狼算法對其進行求解。算法通過構建概率分布模型引導狼群搜索,有效地提高了算法的搜索性能。算例分析表明,本文所構建的LCLRP 模型能夠有效降低物流配送中的碳排放量,所設計的GWOEDA 算法具有較好的優化性能。

低碳物流配送優化問題本身屬于多目標優化問題,并在現實配送中涉及很多不確定性因素。因此,在后續研究中將進一步構建不確定性多目標LCLRP 模型,并設計其相應的GWOEDA 求解算法。