王萬良，朱文成，趙燕偉

(1.浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023； 2.浙江工業(yè)大學(xué) 機械工程學(xué)院，浙江 杭州 310014)

0 引言

隨著社會經(jīng)濟飛速發(fā)展和居民生活水平的提高，全人類日益關(guān)注大氣污染等一系列環(huán)境問題。為保護大氣環(huán)境，改善空氣質(zhì)量，我國積極采取各種措施，并提出“十三五”期間單位GDP的二氧化碳排放下降18%。因此，物流行業(yè)作為溫室氣體排放大戶，理應(yīng)響應(yīng)國家“十三五”號召，節(jié)能減排、實施綠色物流。優(yōu)化物流調(diào)度來減少二氧化碳排放量不僅是節(jié)能減排的措施，并為企業(yè)減少了成本，提升本身的行業(yè)競爭力。

物流調(diào)度的優(yōu)化問題可以分為配送中心選擇問題，貨物配送問題，車輛路徑問題等。配送作為物流系統(tǒng)的核心功能，直接與客戶相關(guān)聯(lián)，配送功能完成質(zhì)量的好壞直接影響客戶對整個物流服務(wù)的滿意程度。而車輛配送路線的合理優(yōu)化作為配送的核心部分對整個物流運輸速度、成本、效益影響至關(guān)重要[1]。Salhi等[2]首先提出，在沒有考慮路徑優(yōu)化的情況下解決定位問題可能會導(dǎo)致次優(yōu)的解決方案。

物流選址-路徑優(yōu)化問題(Location Routing Problem, LRP)模型同時考慮選址和路徑優(yōu)化，多目標LRP模型還將選址及配送成本、配送時間、碳排放量等因素考慮進來。多目標LRP模型在實際應(yīng)用中更具有價值，使用此模型求解得到的調(diào)度方案在各方面都更具競爭力。因此，學(xué)者們對多目標LRP模型進行了廣泛的研究分析。Vahdani等[3]研究了在地震后的救援行動中,救災(zāi)物資和物資的有效分配，其將總成本和旅行時間作為目標，提出多目標混合的多期和多商品數(shù)學(xué)模型。Nedjati等[4]研究了帶服務(wù)時間限制的多目標問題：配送中心補貨以及客戶在預(yù)定步行距離內(nèi)移動的選址問題，提出一種新的雙目標整數(shù)線性規(guī)劃模型，該模型以總加權(quán)等待時間和總損失量最小化為目標。Asgari等[5]提出了考慮各種類型廢物和多種處理技術(shù)的廢物定位、路線問題的多目標模型，該模型包括3個目標函數(shù)，最大限度地處理設(shè)施的需求性，最小化與問題相關(guān)的各種成本，并最終減少未處理材料運輸?shù)娘L(fēng)險。Bozorgi-Amiri等[6]提出一個多目標的動態(tài)隨機規(guī)劃模型，用于人道主義救援物流問題。該模型提出了3個目標：最小化受災(zāi)地區(qū)所有時期的最大短缺量、總旅行時間以及災(zāi)前和災(zāi)后費用總和。Wang等[7]考慮配送中心的位置和可用交通網(wǎng)絡(luò)中的車輛路線問題，構(gòu)建了一個最小化旅行時間、總成本和最大化交貨可靠性的非線性LRP模型。在最新研究的LRP問題中，考慮低碳問題時，學(xué)者們多是將低碳作為其中一個約束條件或者將其作為懲罰系數(shù)[8]加入系統(tǒng)成本的目標函數(shù)中，在優(yōu)化過程中都會難以避免地對某一目標有偏好，或?qū)Σ煌繕诉M行了重要程度的設(shè)置。本文將碳排放量最小化作為第二個目標函數(shù)與系統(tǒng)成本共同構(gòu)成雙目標模型進行優(yōu)化，優(yōu)化過程中不會存在對目標值的任何偏好信息。

此外，目前國內(nèi)外的研究中，使用啟發(fā)式算法進行LRP模型求解居多。張春苗等[9]采用量子進化算法結(jié)合局部搜索算法對低碳定位—車輛路徑問題數(shù)學(xué)模型進行求解。錢曉明[10]等提出一種混合模擬退火算法，解決單相電能表集中檢定后的配送需求問題。啟發(fā)式算法被設(shè)計來解決特定模型，在求解其他模型時缺乏通用性。超啟發(fā)算法能很好地解決這個問題，并在求解大規(guī)模LRP問題(更復(fù)雜，在可接受的執(zhí)行時間內(nèi)不能由傳統(tǒng)方法解決的問題)時，該算法具有更快的速度，即使最終得到的結(jié)果是一個近似最優(yōu)解而不是全局最優(yōu)(這是由隨機搜索的性質(zhì)造成的)。

因此，本文創(chuàng)新性地使用超啟發(fā)算法來求解綠色LRP模型，提出一種新的選擇策略與接受策略組合；在解決傳統(tǒng)LRP的基礎(chǔ)上，考慮碳排放量的影響。通過提出算法對調(diào)度方案進行優(yōu)化，并運用啟發(fā)式規(guī)則，選擇出最優(yōu)調(diào)度路徑，最終得到科學(xué)、合理的調(diào)度方案。

1 多目標問題與超啟發(fā)算法框架

1.1 多目標優(yōu)化問題

多目標優(yōu)化問題又稱為多標準優(yōu)化問題[11]。不失一般性，一個具有n個決策變量，m個目標變量的多目標優(yōu)化問題可表述為

miny=F(x)=(f1(x),f2(x),…,fm(x))T。

s.t.

gi(x)≤0,i=1,2,…,q;

hj(x)=0,j=1,2,…,p。

(1)

其中：x=(x1,…,xn)∈X?Rn為n維的決策矢量，X為n維的決策空間，y=(y1,…,yn)∈Y?Rm為m維的目標矢量，Y為m維的目標空間。目標函數(shù)F(x)定義了m個由決策空間向目標空間的映射函數(shù)：gi(x)≤0(i=1,2,…,q)定義了q個不等式約束；hi(x)=0(i=1,2,…,p)定義了p個等式約束。在此基礎(chǔ)上，給出以下幾個重要的定義。

定義1可行解。對于x∈X，如果x滿足(1)中的約束條件gi(x)≤0(i=1,2,…,q)和hi(x)≤0(i=1,2,…,p)，則稱x為可行解。

定義2可行解集。由X中的所有的可行解組成的集合稱為可行解集合，記為Xf，且Xf?X。

定義3Pareto占優(yōu)。假設(shè)xA,xB∈Xf是式(1)所示多目標優(yōu)化問題的兩個解，則稱與xB相比，xA是Pareto占優(yōu)的，當(dāng)且僅當(dāng)

?i=1,2,…,m,fi(xA)≤fi(xB)∧?

j=1,2,…,m,fj(xA)

(2)

記作xA?xB，也稱為xA支配xB。

定義4Pareto最優(yōu)解。一個解x*∈Xf被稱為Pareto最優(yōu)解(或非支配解)，當(dāng)且僅當(dāng)滿足如下條件：

?x∈Xf:x?x*。

(3)

定義5Pareto最優(yōu)解集。Pareto最優(yōu)解集是所有Pareto最優(yōu)解的集合，定義如下：

P*?{x*|?x∈Xf:x?x*}。

(4)

定義6Pareto前沿面。Pareto最優(yōu)解集P*中所有的Pareto最優(yōu)解對應(yīng)的目標矢量組成的曲面稱為Pareto前沿面PF*：

PF*?{F(x*)=(f1(x),f2(x),…,

fm(x))T|x*∈P*}。

(5)

1.2 超啟發(fā)算法

定義7超啟發(fā)算法。一種選擇或者產(chǎn)生啟發(fā)式算法來解決計算搜索問題的搜索方法[12](或?qū)W習(xí)機制)。

超啟發(fā)算法是“一個獨立于問題的算法框架，它提供了一套策略來開發(fā)啟發(fā)式優(yōu)化算法”[13]。超啟發(fā)算法的特點就是，作為高層策略，它的搜索空間是由一組用來對解空間進行搜索的底層啟發(fā)式算子組成。底層的啟發(fā)式算子可以是(鄰域)操作算子，如交叉、變異、本地搜索，或者就可以是啟發(fā)式算法。典型的超啟發(fā)算法在邏輯結(jié)構(gòu)上由控制域和問題域兩個部分組成，如圖1所示。

問題域中包含由領(lǐng)域?qū)＜以O(shè)計的問題描述、基本函數(shù)、評價函數(shù)以及若干低層啟發(fā)式算法(Low-Level Heuristics, LLH)；高層策略由超啟發(fā)算法專家進行設(shè)計，包含了如何利用底層啟發(fā)式算法構(gòu)造可行解或者提升解質(zhì)量的方法。問題域及控制域之間是領(lǐng)域屏蔽，需要定義兩層結(jié)構(gòu)之間進行信息傳遞的標準接口。

在最初提出的框架下，高層超啟發(fā)式控制策略和底層啟發(fā)式算子之間存在邏輯上的分離，使得基于組件的開發(fā)成為可能[14]。超啟發(fā)式算法允許訪問問題域的獨立信息(如解的目標函數(shù)值)，并進行一些記錄(如記錄每個底層算子的性能指標)。

考慮到啟發(fā)式搜索空間的性質(zhì)，超啟發(fā)算法可以根據(jù)不同的標準用不同的方法進行分類。目前，有兩種主要的超啟發(fā)式算法：①啟發(fā)式選擇方法，在給定的時間內(nèi)，選擇底層啟發(fā)式算法之一應(yīng)用；②啟發(fā)式生成方法，用給定的組件構(gòu)成新的啟發(fā)式算法。

2 綠色LRP問題描述及模型建立

在物流和運營問題的研究中，多數(shù)問題已經(jīng)考慮到運輸對環(huán)境的影響以及工業(yè)環(huán)境對運輸活動成本的影響[15]。

2.1 問題描述

本文提出一個新的LRP數(shù)學(xué)模型，考慮燃料消耗最小化。該問題說明如下：

給定一組配送中心M和客戶C，目標是找到最佳的配送中心及其與客戶點連接的路徑。每個配送中心都有設(shè)置開放成本Cm。在每兩個客戶點(i,j)i,j∈C之間運輸有一個運輸成本Cf。每個客戶i∈C都有一個需求di，該需求只能由一輛車配送。有K輛容量為QK的車可供調(diào)用。每輛車在每兩個客戶點(i,j)i,j∈C之間運輸有一個折舊成本Cd。在傳統(tǒng)的LRP模型中只考慮一個目標函數(shù)：最小化總運營成本，其中包括設(shè)施的設(shè)置成本，車輛折舊成本和兩個客戶點之間的運輸成本。本文模型除了運營成本之外，還包括第二個目標函數(shù)，即考慮到由于運輸中的油耗產(chǎn)生的碳排放量，將LRP作為一個雙目標問題來進行優(yōu)化。

2.2 符號與變量說明

M{m|m=1,…,M}為一系列配送中心；

C{i|i=1,…,I}為一系列客戶點；

V{k|k=1,…,K}為屬于各個配送中心的車輛；

Km為屬于配送中心m且同一車型的車輛；

S{M∪C}為配送中心和客戶點的集合；

di為客戶i的需求；

yij為離開客戶點i后前往客戶點j的車輛裝載的貨物總量；

Cd表示單位車輛折舊成本；

Cf表示單位燃油成本；

Cm表示配送中心開放成本；

Dij表示客戶i到客戶j的距離；

Qk為車輛的容量；

Qm為配送中心的容量；

模型中的決策變量：

2.3 碳排放量計算

影響燃油消耗和二氧化碳排放量的因素很多，如裝載率、行駛距離、行駛速度和地形坡度等。對以上所有因素進行定量分析是不現(xiàn)實的，必須進行適當(dāng)?shù)募僭O(shè)和簡化。

二氧化碳排放量有不同的計算方法，根據(jù)Kirby等[16]的理論，二氧化碳排放量與燃油消耗量成正比例關(guān)系。本文采用文獻[17]的方法三計算燃油消耗量和二氧化碳排放量：

F=G×D×(a×L+b)。

(6)

式中：F為運輸過程的燃油消耗量；G為地形坡度因子；D為車輛的行駛距離；L為載貨重量；a,b為燃油消耗參數(shù)。二氧化碳排放量

Eco2=F×η。

(7)

式中：Eco2為二氧化碳排放量；η為燃油轉(zhuǎn)換系數(shù)。

由式(6)可知，影響二氧化碳排放量的因素有地形坡度、行駛距離和裝載量3個。文獻[18]證明地形坡度對于碳排放量并無明顯影響，因此設(shè)式(6)中的G=1，忽略地形坡度因素。

2.4 數(shù)學(xué)模型

雙目標低碳LRP的數(shù)學(xué)模型如下：

(8)

(9)

s.t.

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

yij-(Qk-di)Xijk≤0,?i,j∈S,k∈Km；

(19)

yij-Xijkdj≥0,?i,j∈S,k∈Km；

(20)

(21)

Xijk∈{0,1},?i,j∈S,k∈Km；

(22)

Zm∈{0,1},?m∈M。

(23)

其中：式(8)和式(9)為目標函數(shù)，其中第一部分為配送中心開放成本加汽車折舊成本加燃油成本，第二部分為二氧化碳排放量；式(10)保證每個客戶均被訪問一次；式(11)和式(12)表明車輛從配送中心出發(fā)，必須回到原配送中心；式(13)保證每一個運輸車輛的路徑最多從一個配送中心駛出；式(14)保證任何兩個配送中心的車輛不會在同一條路徑上；式(15)保證訪問完客戶后必須離開；式(16)保證每個配送中心訪問的顧客總需求小于配送中心的容量；式(17)保證車的載重不大于它的載重能力；式(18)保證每輛車的載貨量滿足客戶的需求量；式(19)和式(20)保證當(dāng)Xijk=1時yij>0，否則yij=0;式(21)是子回路消除約束;式(22)和式(23)是對決策變量的描述。

3 基于全局邊緣排序的超啟發(fā)式算法

本章詳細描述了所提出的基于全局邊緣排序的超啟發(fā)算法(Hyper-Heuristic based on Global Margin Ranking,GMR_HH)框架以及上層策略的細節(jié)。

3.1 GMR_HH算法框架

算法1GMR_HH。

1． h:底層算子索引號；Pin:輸入種群；Pnew:新生成種群

2. 初始化種群;

3. while(滿足終止條件停止迭代)do

4.h←選擇底層算子；

5.Pnew←執(zhí)行底層算子(h,Pin);//執(zhí)行底層算子h，對Pin進行操作產(chǎn)生新的種群Pnew

6.更新種群；

7.Pin←應(yīng)用接受準則(Pin,Pnew);//全局邊緣排序接受(Pin,Pnew)集合中最優(yōu)解進入下次迭代

end

GMR_HH的算法框架如算法1所示。首先是初始化過程，包括產(chǎn)生初始解和建立選擇式超啟發(fā)算法的相關(guān)數(shù)據(jù)結(jié)構(gòu)(步驟2)；在此過程之后，使用多個底層算子進行迭代，改進得到一組新解。每次迭代都會使用啟發(fā)式選擇方法選擇一個底層啟發(fā)式算子(Low-Level Heuristic,LLH)(步驟4)并將選擇的底層算子應(yīng)用到(步驟5)輸入的解集合上(Pin)來生成新的解集合(Pnew)。然后對與算法組件相關(guān)的一些數(shù)據(jù)/參數(shù)進行更新(步驟6)，并進行接收策略的工作(步驟7)，從由當(dāng)前解和新生成解的組合構(gòu)成的解集合中挑選出下次迭代的輸入解集合。整個過程在進行固定迭代次數(shù)后終止，最后返回Pareto最優(yōu)解集。

在初始化(步驟2)和更新(步驟6)過程中，啟發(fā)式選擇函數(shù)策略分別被用來進行初始化和在一組新解產(chǎn)生時對每個底層算子進行評分計算以此選擇底層算子。

3.2 改進的選擇函數(shù)選擇策略

Maashi[19]等提出選擇函數(shù)(Choice function,CF)啟發(fā)式選擇策略，為每一個底層啟發(fā)式算子打分，用來指示其性能，并在每次迭代中選擇分數(shù)最高的底層啟發(fā)式算子進行操作。這種方法旨在平衡最優(yōu)化(選擇最佳表現(xiàn)的底層啟發(fā)式算子)和多樣化(給予長時間未選擇的啟發(fā)式算子機會)。

本文使用以下指標對算子進行評分：空間覆蓋大小[20](SSC)、均勻分布[21](UD)、非支配解比例[21](RNI)。SSC被定義為Pareto前沿面相對于參考點覆蓋的空間大小，通常被用于評估多目標算法的收斂能力；UD是[0,1]中的一個值，用于度量Pareto前沿面上Pareto最優(yōu)解集分布的均勻性，較高的UD值表示Pareto前沿面上的解分布更均勻；RNI是[0,1]中的一個值，是種群中非支配解占種群總數(shù)的百分比。針對本文算子，提出一個新的評價指標：優(yōu)化率(OE):

(24)

式中(本文均以最小化目標函數(shù)為例)：m為種群大?。籲為目標函數(shù)個數(shù)；fj(x),j=1,2,…,n為第j個目標函數(shù)；ai(i=1,2,…,m;a為上一代種群)；bi(i=1,2,…,m;b為下一代種群)。通過所提方法，可以綜合考慮所有目標函數(shù)的影響，并計算出經(jīng)算子操作后，下一代種群優(yōu)化效率。該方法需根據(jù)不同應(yīng)用場景進行分析，如多目標值之間存在量級差距，需先進行歸一化處理。

選擇函數(shù)法首先使用上述指標：SSC，UD，RNI，OE對所有底層算子根據(jù)得分進行排序，然后根據(jù)每個算子得到最好指標的頻率選擇算子。例如超啟發(fā)框架中有3個底層算子：h1,h2,h3，如果h1在SSC，UD，RNI評價中得到最好的排名，h2在UD和RNI中得分最高，但h3只在OE中排名最高，則h1,h2,h3得到最好指標的頻率排名(Freqrank(h))就是1，2，3。

最終，某個算子h的得分可以用選擇函數(shù)式(21)計算得到:

CF(h)=αf1(h)+f2(h),?h∈H。

(25)

式中：α為正相關(guān)系數(shù)，H是底層算子的集合，h底層算子的索引號。(f1)函數(shù)定義為：

f1(h)=2(N+1)-{Freqrank(h)+RNIrank(h)}。

(26)

式中N是所有底層算子的數(shù)量。假設(shè)h1,h2,h3三個算子的RNIrank(h)={1，1，3}；且Freqrank(h)={1，2，3}，就能得到f1(h)={6，5，2}。f2(h)是算子從上次被調(diào)用到現(xiàn)在的CPU時間(s)。每次迭代，CF(h)得分最高的算子被調(diào)用。

下面給出選擇函數(shù)法步驟的具體說明：

Choice function。

Start

1． 初始化種群

2． 運行底層算子庫中所有算子

3． 根據(jù)評價規(guī)則，對所有算子進行評價

4.計算得到CF(h),選擇CF(h)值最高的算子h作為初始算子

5.repeat

6. 執(zhí)行選擇的算子h

7. 更新所有算子的評價

8. 更新所有算子的CF(h)值，選擇CF(h)值最高的算子

9. until(達到終止條件)

End

首先進行種群初始化(步驟1)，然后運行底層算子庫中所有的算子，并根據(jù)評價規(guī)則，對所有算子進行評價，得到評價值后計算出所有算子的CF(h)值，并選擇CF(h)值最高的算子h作為初始算子(步驟2～步驟4)。接下來是循環(huán)過程，先執(zhí)行選擇的算子，執(zhí)行后根據(jù)本代數(shù)據(jù)更新所有算子的評價，并根據(jù)評價值計算所有算子的CF(h)值，選擇CF(h)值最高的算子作為下一代的執(zhí)行算子，直到達成終止條件(步驟5～步驟9)。

3.3 基于全局邊緣排序的接受準則

接受準則在超啟發(fā)式中具有重要地位，其決定了是否接受或拒絕由選定的底層算子產(chǎn)生的候選解決方案。Li等[20]將3種選擇策略：隨機選擇(Random Choice, RC)、固定順序選擇(Fixed Sequence, FS)、選擇函數(shù)法(Choice Function, CF)與3種接受策略：全接受(All-Moves, AM)、大洪水接受(Great Deluge Acceptance, GDA)、最好值接受(Best Acceptance, BA)兩兩組合，進行實驗。實驗結(jié)果表明RC-GDA組合策略性能最優(yōu)，因此本文將其作為對比算法之一，用于與本文算法進行實驗結(jié)果對比。目前有多種接受準則，但大多用于單目標優(yōu)化。Maashi等[22]改進了GDA策略，將其用于多目標優(yōu)化。

現(xiàn)有的基于帕累托主導(dǎo)框架的多目標排序效率較低[23]，本文選取了一種基于排名的新型主導(dǎo)機制，稱為全局邊緣排序(Global Margin Ranking, GMR)。該機制針對基于Pareto排序的方法在處理大量弱優(yōu)勢關(guān)系(對支配其他個體數(shù)量相同的個體進行排序)時，排序性能急劇下降的問題，使用了目標函數(shù)值乘積的方法，為排序過程中存在的弱優(yōu)勢情況提供了解決方法，同時也能保障非支配解的排序比支配解更優(yōu)。該機制在簡化和加速優(yōu)勢關(guān)系評估的過程中，不僅考慮了整個種群所有個體的目標值信息，還使用了一種考慮群體中個體間距離的密度估計器，來保證種群個體具有更好的分布性。下面給出全局邊緣排序的定義：

定義8全局邊緣排序(GMR)。個體的GMR定義為個體的目標值與其他所有個體目標值差值的總和，定義如下：

(27)

式中：Xi,Xj是兩個不同的解，M是目標個數(shù)。結(jié)合Pareto占優(yōu)的概念，GMR(Xi)越小，Xi支配的解越多。根據(jù)式(27)，對任何兩個解，當(dāng)且僅當(dāng)GMR(Xi)

定義9全局密度(Global Density,GD)。定義如下：

(28)

式中：GD(Xi)表示Xi的全局密度；di,j是[f1(Xi),f2(Xi),…,fm(Xi)]與[f1(Xj),f2(Xj),…,fm(Xj)]之間的歐式距離，m為目標個數(shù)。GD(Xi)值越大，Xi周圍的個體越少，個體間的差異越大，分布性越好。

定義10全局綜合排序(Global general ranking,GGR)。定義如下：

(29)

式中GGR(Xi)表示Xi的全局綜合排序。GGR(Xi)越小，Xi越具優(yōu)勢，同時也表示Xi的GD值越小，Xi具有更好的分布。

4 實驗驗證

為驗證所建模型和提出算法的可行性與有效性，本文以Barreto基準測試實例中的算例(http://prodhonc.free.fr/Instances/instances_us.htm)作為計算對象，使用MATLAB R2016b進行編程，在Intel Core i5處理器，4 G內(nèi)存，64位Windows操作系統(tǒng)的計算機上進行實驗。

模型中的參數(shù)描述及其取值在表1中給出。

表1 相關(guān)參數(shù)表

4.1 實例驗證

本節(jié)實驗中選取了Barreto基準測試實例中的‘Christ100×10’測試場景(其中有100個客戶點，10個配送中心)進行實驗，并對結(jié)果的特征進行分析。

表2中給出了Christ100×10實例的Pareto前沿面以及Pareto最優(yōu)解的細節(jié)描述。將對該實例的3種解決方案進行分析：①對應(yīng)于目標函數(shù)f1值(總成本)最小的解；②對應(yīng)于目標函數(shù)f2值(碳排放量)最小的解；③符合最大—最小準則的解，這個解通常是Pareto前沿面的中間點。

從表中可以很直觀地看出，隨著配送中心數(shù)量的增加，配送中心的開放成本增加，相應(yīng)的總成本也會增加，即(n=5,f1=18 367)→(n=7,f1=19 023)。但是，隨著配送中心數(shù)量的增加，碳排放量會相應(yīng)的降低，這是因為配送中心增多，運送車輛需要行駛的距離會隨之變短，這就會直接促成碳排放量的降低，即(n=5,f2=7 018.1)→(n=7,f2=6 749.3)。

從表中可以看出，還有兩種較為特殊的情況，當(dāng)配送中心數(shù)量都為5的時候，兩個解的目標函數(shù)值分別為(f1=18 367,f2=7 018.1)和(f1=18 907,f2=6 845.0),雖然成本相差無幾，但碳排放量卻后者更少，這是因為兩種調(diào)度方案選擇的路徑不同，道路的地形坡度因子不同，導(dǎo)致碳排放量的區(qū)別；第二種當(dāng)配送中心數(shù)量不同，一個開放4個中心，另一5個中心時，兩個解的目標函數(shù)值分別為(f1=18 367,f2=7 018.1)和(f1=18 403,f2=6 910.0)與前一種情況類似。

4.2 對比分析

本文選取NSGA-Ⅱ、SPEA2以及使用RC-GDA策略的超啟發(fā)算法與所提GMR-HH超啟發(fā)算法(本文提出的超啟發(fā)算法使用CF-GMR策略，因此下列實驗結(jié)果中使用CF-GMR代表GMR-HH算法)進行優(yōu)劣對比。其中NSGAⅡ與SPEA2為多目標優(yōu)化算法中經(jīng)典的算法之一，RC-GDA為文獻[20]中所證明性能最優(yōu)的超啟發(fā)算法策略。

因為NSGAⅡ、SPEA2這兩種傳統(tǒng)啟發(fā)式算法與超啟發(fā)算法框架不同，算子無法統(tǒng)一，所以為了公平性只能保證種群大小、迭代次數(shù)、交叉變異率一致。對于RC-GDA算法，與CF-GMR同為超啟發(fā)算法，為了公平性，只需進行策略的比較，算子與本文所用相同，其余設(shè)置均與傳統(tǒng)算法設(shè)置相同。

實驗參數(shù)的具體設(shè)置如表3所示。

表3 算法參數(shù)設(shè)置

本節(jié)選用Christ100×10測試實例，分別使用CF-GMR、NSGAⅡ、SPEA2、RC-GDA算法進行計算，得出調(diào)度方案，并對4種調(diào)度方案進行對比分析。

從圖2和圖3可以看出，使用超啟發(fā)算法得出的Pareto前沿面完全支配NSGAⅡ、SPEA2計算得到的Pareto面。這說明，使用CF-GMR算法計算得到的調(diào)度方案，在總成本與碳排放量這兩個目標上，均少于其他兩個算法得到的調(diào)度方案。這是因為，傳統(tǒng)的多目標算法使用非支配排序，這在解決大規(guī)模的LRP(復(fù)雜的NP-Hard問題)時存在效率低下的問題[23]，通過對比，證明超啟發(fā)算法在解決大規(guī)模LRP上具有明顯優(yōu)勢。圖4中，與性能較為優(yōu)異的超啟發(fā)策略進行對比，雖然在總成本上優(yōu)勢并不明顯，但是在碳排放這個目標上，CF-GMR所得的調(diào)度方案均是優(yōu)于RC-GDA。說明所提策略相較于對比算法，有一定的優(yōu)勢。

本節(jié)還通過單目標值隨迭代次數(shù)的變化，對比分析在雙目標優(yōu)化的迭代過程中，單目標的收斂情況。圖5反映了CF-GMR與NSGAⅡ?qū)Ρ惹闆r，從左圖可以看出，在總成本這個目標的迭代過程中，NSGAⅡ的優(yōu)化效果差，從0代到80代只從2.7×104(元)降低到2.53×104(元)，但是本文算法可以從2.58×104(元)降低到1.86×104(元)，優(yōu)化效果明顯。在右圖中，雖然NSGAⅡ在30代到50代之間優(yōu)于CF-GMR，但是卻在38代提前收斂，陷入局部最優(yōu)，最終CF-GMR在碳排放量這個目標上的優(yōu)化效果依舊優(yōu)于NSGAⅡ。圖6左圖中，在0代到40代之間，SPEA2的總成本明顯低于CF-GMR，這是由隨機搜索的性質(zhì)造成的，在初始化時，隨機生成種群個體，得到的總成本低。但是40代之后，可以明顯得出，CF-GMR的收斂效率高，不會陷入局部最優(yōu)，右圖類似。在圖7中，是兩種超啟發(fā)算法策略組合的對比，總成本效率近乎相同，且都優(yōu)于傳統(tǒng)的啟發(fā)式算法，可以證明超啟發(fā)算法在求解大規(guī)模LRP模型時，效率、解的質(zhì)量均是優(yōu)于傳統(tǒng)算法的。在碳排放量的迭代過程中，RC-GDA在40代時陷入局部最優(yōu)，而CF-GMR能繼續(xù)收斂。證明CF-GMR算法相較于RC-GDA，在迭代兩個目標的優(yōu)化過程中都是具有優(yōu)勢的。

5 結(jié)束語

本文通過對低碳LRP多目標優(yōu)化問題進行研究，綜合考慮配送中心開放、運輸、燃油等成本以及碳排放量等目標，通過建立雙目標模型，以總成本最小、碳排放量最少為目標，通過CF-GMR超啟發(fā)算法，對配送中心選址以及物流配送調(diào)度方案進行優(yōu)化，計算出最優(yōu)調(diào)度方案。利用Barreto基準測試實例中名為Christ100×10的測試場景進行驗證，與NSGAⅡ、SPEA2和RC-GDA等算法從Pareto前沿面、總成本和碳排放的收斂情況等方面進行對比，優(yōu)化結(jié)果和對比分析證明了調(diào)度方案的有效性與可行性。

LRP一直是物流領(lǐng)域研究的熱點，在本文的研究內(nèi)容之外，還有其他方面值得進一步探索和改進。例如帶時間窗的LRP(Location-Routing Problem with Time Windows, LRPTW)，對于帶配送時間限制的問題來說，如果嚴格按照客戶設(shè)定的服務(wù)時間為其服務(wù)，可能造成企業(yè)的配送成本增加；如果允許在某些客戶點適當(dāng)?shù)匮诱`,可能使運輸成本大為減少，但該延誤現(xiàn)象會造成客戶滿意度下降，決策者需對客戶滿意和成本二者進行權(quán)衡。此外結(jié)合本文，考慮配送時間對碳排放量的影響值得繼續(xù)研究。又例如動態(tài)LRP，動態(tài)LRP是LRP一個非常重要的領(lǐng)域，這在目前的文獻中暫未有明確的解決途徑。相比于配送中心的選址決策，將貨物運輸?shù)骄哂胁煌枨蟮目蛻魰r的路徑?jīng)Q策改變更頻繁[24]，這就導(dǎo)致傳統(tǒng)LRP模型不能很好地協(xié)調(diào)選址與路徑的規(guī)劃。因此，構(gòu)建動態(tài)LRP模型作為能解決上述問題的重要方法之一，也是后續(xù)研究的一個重點。同時，超啟發(fā)算法在LRP上得到很好的應(yīng)用，以及對于超啟發(fā)算法策略的改進，也值得繼續(xù)研究。