基于全局邊緣排序的超啟發(fā)算法在綠色物流選址—路徑優(yōu)化問題中的應(yīng)用

王萬(wàn)良，朱文成，趙燕偉

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

0 引言

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

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

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

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

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

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

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

多目標(biāo)優(yōu)化問題又稱為多標(biāo)準(zhǔn)優(yōu)化問題[11]。不失一般性，一個(gè)具有n個(gè)決策變量，m個(gè)目標(biāo)變量的多目標(biāo)優(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維的目標(biāo)矢量，Y為m維的目標(biāo)空間。目標(biāo)函數(shù)F(x)定義了m個(gè)由決策空間向目標(biāo)空間的映射函數(shù)：gi(x)≤0(i=1,2,…,q)定義了q個(gè)不等式約束；hi(x)=0(i=1,2,…,p)定義了p個(gè)等式約束。在此基礎(chǔ)上，給出以下幾個(gè)重要的定義。

定義1可行解。對(duì)于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)所示多目標(biāo)優(yōu)化問題的兩個(gè)解，則稱與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)解。一個(gè)解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)解對(duì)應(yīng)的目標(biāo)矢量組成的曲面稱為Pareto前沿面PF*：

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

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

(5)

1.2 超啟發(fā)算法

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

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

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

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

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

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

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

2.1 問題描述

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

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

2.2 符號(hào)與變量說明

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

C{i|i=1,…,I}為一系列客戶點(diǎn)；

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

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

S{M∪C}為配送中心和客戶點(diǎn)的集合；

di為客戶i的需求；

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

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

Cf表示單位燃油成本；

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

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

Qk為車輛的容量；

Qm為配送中心的容量；

模型中的決策變量：

2.3 碳排放量計(jì)算

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

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

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

(6)

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

Eco2=F×η。

(7)

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

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

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

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

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

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

3.1 GMR_HH算法框架

算法1GMR_HH。

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

2. 初始化種群;

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

4.h←選擇底層算子；

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

6.更新種群；

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

end

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

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

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

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

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

(24)

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

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

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

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

(25)

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

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

(26)

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

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

Choice function。

Start

1． 初始化種群

2． 運(yùn)行底層算子庫(kù)中所有算子

3． 根據(jù)評(píng)價(jià)規(guī)則，對(duì)所有算子進(jìn)行評(píng)價(jià)

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

5.repeat

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

7. 更新所有算子的評(píng)價(jià)

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

9. until(達(dá)到終止條件)

End

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

3.3 基于全局邊緣排序的接受準(zhǔn)則

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

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

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

(27)

式中：Xi,Xj是兩個(gè)不同的解，M是目標(biāo)個(gè)數(shù)。結(jié)合Pareto占優(yōu)的概念，GMR(Xi)越小，Xi支配的解越多。根據(jù)式(27)，對(duì)任何兩個(gè)解，當(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為目標(biāo)個(gè)數(shù)。GD(Xi)值越大，Xi周圍的個(gè)體越少，個(gè)體間的差異越大，分布性越好。

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

(29)

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

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

4.1 實(shí)例驗(yàn)證

本節(jié)實(shí)驗(yàn)中選取了Barreto基準(zhǔn)測(cè)試實(shí)例中的‘Christ100×10’測(cè)試場(chǎng)景(其中有100個(gè)客戶點(diǎn)，10個(gè)配送中心)進(jìn)行實(shí)驗(yàn)，并對(duì)結(jié)果的特征進(jìn)行分析。

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

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

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

4.2 對(duì)比分析

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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