，，，,2

(1.浙江工業(yè)大學(xué) 特種裝備制造與先進(jìn)加工技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310014；2.嘉興職業(yè)技術(shù)學(xué)院 機(jī)電與汽車(chē)分院，浙江 嘉興314036)

隨著全球氣候變暖，低碳經(jīng)濟(jì)逐漸成為世界各國(guó)關(guān)注的焦點(diǎn)，而物流業(yè)是碳排放的主要來(lái)源之一，因此低碳環(huán)境下的選址路徑問(wèn)題(Location routing problem，LRP)受到學(xué)者的關(guān)注.在模型上，曹劍東等[1-2]以總成本最小化為優(yōu)化目標(biāo)研究了考慮碳排放因素的車(chē)輛路徑問(wèn)題(Vehicle routing problem，VRP).在實(shí)際的物流配送系統(tǒng)中，車(chē)輛路徑的優(yōu)化目標(biāo)往往不止1個(gè)，可能同時(shí)考慮包括最短配送路徑、最少總成本、最少碳排放量和最少車(chē)輛數(shù)等因素.Jemai等[3-4]研究了最小化運(yùn)輸路徑和碳排放的多目標(biāo)VRP模型；魯建廈等[5-6]研究了最小化成本和車(chē)輛數(shù)的LRP模型.然而在現(xiàn)實(shí)生活中，物流企業(yè)一方面在配送時(shí)要盡量降低運(yùn)營(yíng)成本，另一方面還要減少碳排放、增加客戶(hù)滿(mǎn)意度.客戶(hù)的滿(mǎn)意度主要體現(xiàn)在車(chē)輛的準(zhǔn)時(shí)到達(dá)，車(chē)輛在客戶(hù)要求的時(shí)間內(nèi)到達(dá)，則客戶(hù)的滿(mǎn)意度最高，提前或者推遲到達(dá)都會(huì)引起客戶(hù)滿(mǎn)意度的下降.在求解算法上，求解多目標(biāo)VRP或LRP模型的算法基本是線(xiàn)性權(quán)重處理法或者是NSGA-II算法等傳統(tǒng)的啟發(fā)式算法，不同LRP變種問(wèn)題的特殊性限制了這類(lèi)算法的通用性，對(duì)于不同LRP問(wèn)題都必須設(shè)計(jì)相對(duì)應(yīng)的搜索策略，所以設(shè)計(jì)一種通用性算法使其較好地運(yùn)用于一類(lèi)相似的問(wèn)題是目前研究的熱點(diǎn)，超啟發(fā)式算法就是這樣的方法之一.

基于此，在傳統(tǒng)LRP基礎(chǔ)上，研究考慮碳排放帶時(shí)間窗的選址路徑新模型，在優(yōu)化配送中心位置和數(shù)量的同時(shí)確定最佳的配送路線(xiàn)，降低配送過(guò)程中的碳排放，建立了包含碳排放、配送成本和客戶(hù)滿(mǎn)意度的多目標(biāo)LCLRPTW(Low-carbon location-routing problem with time windows)模型，并結(jié)合禁忌搜索設(shè)計(jì)超啟發(fā)式算法進(jìn)行求解.

1 選址-路徑問(wèn)題的描述及數(shù)學(xué)規(guī)劃模型

1.1 問(wèn)題描述

建立多目標(biāo)LCLRPTW模型描述如下：有M個(gè)配送中心，每個(gè)配送中心擁有相同容量的K輛車(chē)，車(chē)輛最大載重量為Qk，有n個(gè)客戶(hù)的運(yùn)輸任務(wù)需要完成，第i個(gè)客戶(hù)節(jié)點(diǎn)的需求量為di，且有maxdi

1.2 碳排放量的計(jì)算

由于要滿(mǎn)足同一條路線(xiàn)上各個(gè)客戶(hù)的需求，車(chē)輛在運(yùn)輸過(guò)程中的裝載量會(huì)發(fā)生變化，所以CO2的排放量不是一成不變的，除了行駛距離外還需要考慮每一段運(yùn)輸過(guò)程中實(shí)際的貨物裝載量.根據(jù)文獻(xiàn)[8]，CO2排放量和燃油消耗量成正比例關(guān)系，CO2排放量與行駛距離成正比例關(guān)系，與車(chē)輛裝載量成正線(xiàn)性相關(guān).在計(jì)算車(chē)輛燃油消耗和CO2排放量的時(shí)候，只考慮車(chē)輛行駛距離和裝載量對(duì)兩者的影響，暫不考慮行駛速度、交通路況和天氣等因素的影響.燃油消耗量和CO2排放量的計(jì)算公式為

F=GD(aL+b)

(1)

式中：F為運(yùn)輸過(guò)程的燃油消耗量；G為地形坡度因子；D為車(chē)輛的行駛距離；L為載貨重量；a,b分別為燃油消耗參數(shù).

計(jì)算出燃油消耗量，需要轉(zhuǎn)化為CO2排放量，同樣根據(jù)文獻(xiàn)[8]有

ECO2=Fη

(2)

式中：ECO2為CO2排放量；η為燃油轉(zhuǎn)換系數(shù).

為了驗(yàn)證模型的有效性，取地形坡度因子G為單位1，根據(jù)實(shí)際問(wèn)題可以得到

Eij=ηDij[aQij+b]

(3)

式中:Eij為車(chē)輛從客戶(hù)i后到客戶(hù)j的CO2排放量；Dij為客戶(hù)i到客戶(hù)j的行駛距離；Qij為離開(kāi)客戶(hù)i后前往客戶(hù)j的車(chē)輛裝載的將要派送的客戶(hù)的貨物總量.

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

對(duì)模型中的變量進(jìn)行如下定義：M{m|m=1,2,…,M}為一系列配送中心；C{i|i=1,2,…,n}為一系列需要服務(wù)的客戶(hù)；V{k|k=1,2,…,K}為屬于各個(gè)配送中心的車(chē)輛；S{M∪C}為配送中心和客戶(hù)總和；Km為屬于配送中心m且同一車(chē)型的車(chē)輛；di為客戶(hù)i的需求；Cc為單位CO2排放成本；Cv為派車(chē)成本；Cr為單位車(chē)輛運(yùn)輸成本；Cd為單位車(chē)輛折舊成本；Cf為單位燃油成本；Cm為配送中心開(kāi)放成本；Qk為車(chē)輛的容量；Qm為配送中心的容量；[Ei,Li]為時(shí)間窗；T0為配送中心開(kāi)始送貨時(shí)間；Tik為車(chē)輛k到達(dá)客戶(hù)i的時(shí)間；tij為客戶(hù)i～j的行駛時(shí)間；sik為車(chē)輛k服務(wù)客戶(hù)i的時(shí)間；α為單位時(shí)間車(chē)輛提前到達(dá)客戶(hù)點(diǎn)的懲罰系數(shù)；β為單位時(shí)間車(chē)輛延誤到達(dá)客戶(hù)點(diǎn)的懲罰系數(shù)；決策變量1：Xijk，當(dāng)車(chē)輛k從客戶(hù)i～j為1，否則為0；決策變量2：Zm，配送中心開(kāi)放為1，否則為0.

LCLRPTW數(shù)學(xué)模型如下：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

T0=0

(16)

Tik+sik+tij=Tjk?i,j∈C,k∈Km

(17)

ai≤sik≤bi?i∈S,k∈Km

(18)

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

(19)

Zm∈{0,1} ?m∈M

(20)

其中：式(4～6)為3個(gè)目標(biāo)函數(shù)；式(4)代表總碳排放量最少；式(5)代表總成本最少，第1項(xiàng)為配送中心開(kāi)放成本，第2項(xiàng)為派車(chē)成本，第3項(xiàng)為車(chē)輛運(yùn)輸成本和汽車(chē)折舊成本，第4項(xiàng)為燃油成本，第5項(xiàng)為CO2排放成本，第6項(xiàng)為早到等待成本，第7項(xiàng)為超時(shí)成本；式(6)代表等待和遲到的總時(shí)間最少；式(7)保證每個(gè)客戶(hù)均被訪(fǎng)問(wèn)1次；式(8，9)表明車(chē)輛從配送中心出發(fā)，必須回到原配送中心；式(10)保證每1個(gè)運(yùn)輸車(chē)輛的路徑最多從1個(gè)配送中心駛出；式(11)保證任何2個(gè)配送中心的車(chē)輛不會(huì)在同1條路徑上；式(12)保證訪(fǎng)問(wèn)完客戶(hù)后必須離開(kāi)；式(13)保證每個(gè)配送中心訪(fǎng)問(wèn)的顧客總需求小于配送中心的容量；式(14)保證車(chē)的載重不大于它的載重能力；式(15)保證每個(gè)客戶(hù)的需求均被滿(mǎn)足；式(16)表示規(guī)定開(kāi)始的送貨時(shí)間為0；式(17)表示車(chē)輛k到達(dá)客戶(hù)j處的時(shí)刻等于車(chē)輛k到達(dá)客戶(hù)i處的時(shí)刻與其在客戶(hù)i處服務(wù)時(shí)間，以及從客戶(hù)i處到客戶(hù)j處的行駛時(shí)間之和；式(18)表示車(chē)輛k到達(dá)客戶(hù)i處的時(shí)間需滿(mǎn)足客戶(hù)規(guī)定的時(shí)間窗；式(19，20)是對(duì)決策變量的描述.

2 求解算法設(shè)計(jì)

2.1 超啟發(fā)式算法

超啟發(fā)式算法(Hyper-heuristicalgorithm，HHA)是近年來(lái)發(fā)展起來(lái)的一種新型啟發(fā)式算法，旨在提高算法的通用性[9-10].超啟發(fā)式算法提供一種高層啟發(fā)式策略，通過(guò)管理或操縱一系列底層啟發(fā)式算子，用于求解各種組合優(yōu)化問(wèn)題.

圖1給出了超啟發(fā)式算法的框架，分為2個(gè)部分[9]：在控制域部分，由智能計(jì)算專(zhuān)家進(jìn)行設(shè)計(jì)高層啟發(fā)式策略，包括如何利用底層啟發(fā)式算子構(gòu)造可行解或改進(jìn)解的質(zhì)量；在問(wèn)題域部分，由應(yīng)用領(lǐng)域?qū)＜姨峁┮幌盗械讓訂l(fā)式算子(Low-level heuristic,LLH)、問(wèn)題定義和目標(biāo)函數(shù)等信息.由于2個(gè)部分之間實(shí)現(xiàn)了領(lǐng)域屏蔽，只要修改問(wèn)題域的LLH、問(wèn)題定義和目標(biāo)函數(shù)等信息，一種超啟發(fā)式算法可以方便地移植到新的問(wèn)題上.超啟發(fā)式算法已經(jīng)被廣泛運(yùn)用在多種領(lǐng)域，大多用于求解排課問(wèn)題[11]，流水車(chē)間調(diào)度問(wèn)題[12]，裝箱問(wèn)題[13]等約束較少的組合優(yōu)化問(wèn)題，對(duì)于更為復(fù)雜的問(wèn)題實(shí)際應(yīng)用潛力巨大.因此提出一種禁忌搜索的超啟發(fā)式算法對(duì)多目標(biāo)LCLRPTW模型進(jìn)行求解，為超啟發(fā)式算法進(jìn)一步在LRP領(lǐng)域的應(yīng)用提供參考.

圖1 超啟發(fā)式算法框架Fig.1 Framework of hyper-heuristic algorithm

2.2 基于禁忌搜索的超啟發(fā)式算法

根據(jù)超啟發(fā)式算法的特點(diǎn)，算法設(shè)計(jì)需要考慮問(wèn)題域中底層啟發(fā)式算子的構(gòu)建和控制域中如何設(shè)計(jì)禁忌搜索作為高層啟發(fā)式策略.

2.2.1 底層啟發(fā)式算子

在研究的LCLRPTW模型中，底層啟發(fā)式算子根據(jù)文獻(xiàn)[14]的分類(lèi)標(biāo)準(zhǔn)，構(gòu)建變異算子、破壞與重構(gòu)算子、局部搜索算子和交叉算子.算子具體詳情如下：

1) 變異算子.變異算子是一種對(duì)解產(chǎn)生微小擾動(dòng)的突變算子.所有這些算子都將返回任何滿(mǎn)足約束的路徑，無(wú)論目標(biāo)函數(shù)值是改進(jìn)或惡化.LLH1～ LLH4為路徑變異算子；LLH5，LLH6為配送中心選址變異算子.

LLH1：2-opt.選擇1條路徑，交換相鄰兩客戶(hù)點(diǎn)的位置.

LLH2：Or-opt.選擇1條路徑，把相鄰2客戶(hù)點(diǎn)插入到其他位置.

LLH3：Interchange.選擇2條路徑，交換任意2個(gè)客戶(hù)點(diǎn)位置.

LLH4：Shift.選擇2條路徑，1條路徑上的任意1個(gè)客戶(hù)點(diǎn)插入到另1條路徑合適的位置.

LLH5：Shift.選擇1條路徑，使用1個(gè)新的配送中心替換此路徑的配送中心.

LLH6：Interchange.選擇2條路徑，交換2個(gè)配送中心.

2) 破壞與重構(gòu)算子.破壞與重構(gòu)算子共有3類(lèi)，分別為徑向破壞與重構(gòu)算子、隨機(jī)破壞與重構(gòu)算子和序列破壞與重構(gòu)算子[15].使用第1類(lèi)算子，即根據(jù)與“基準(zhǔn)客戶(hù)”的接近程度從路徑中刪除一些客戶(hù).

LLH7：Location-based radial ruin.隨機(jī)選擇1個(gè)客戶(hù)作為基準(zhǔn)客戶(hù)，根據(jù)客戶(hù)位置接近基準(zhǔn)客戶(hù)位置的原則，以[1%,10%]的概率將客戶(hù)從路徑中刪除.

LLH8：Time-based radial ruin，在整個(gè)調(diào)度期間內(nèi)隨機(jī)選擇1個(gè)時(shí)間，根據(jù)其時(shí)間窗口的接近時(shí)間以[25%,75%]的概率從解決方案中刪除客戶(hù).

3) 局部搜索算子.與變異算子一樣，經(jīng)常是以交換或插入的形式產(chǎn)生新路徑.但與變異算子不同的是局部搜索算子只會(huì)返回1個(gè)改進(jìn)解.

LLH9：Interchange.與LLH3一樣，不同的是此算子只接受改進(jìn)解.

LLH10：Shift.與LLH4一樣，不同的是此算子根據(jù)衡量準(zhǔn)則來(lái)選擇客戶(hù)，被選客戶(hù)插入到另一條路徑的任意位置，且只接受改進(jìn)解.

LLH11：2-opt*.選擇2條路徑，根據(jù)衡量準(zhǔn)則選擇交換位置點(diǎn)，交換此位置后的所有客戶(hù)點(diǎn)，且只接受改進(jìn)解.

LLH12：GENI.計(jì)算不同路線(xiàn)上的任意2個(gè)客戶(hù)的距離，采用最短的距離作為基準(zhǔn)距離，選擇移除距離最接近基準(zhǔn)距離的客戶(hù)，且只接受改進(jìn)解.

4) 交叉算子.選擇2個(gè)父代路徑作為輸入，生成1條子代路徑的方法，通?？梢酝ㄟ^(guò)1點(diǎn)、2點(diǎn)和均勻交叉等方法完成.

LLH13：Combine，選擇2個(gè)父代，以[25%,75%]的概率將1個(gè)父代復(fù)制得到1條子路徑， 添加來(lái)自另一個(gè)父代中非沖突的路徑，并隨機(jī)插入剩余的客戶(hù).

LLH14：Longest Combine，選擇2個(gè)父代，所有路徑以服務(wù)客戶(hù)點(diǎn)數(shù)量的降序來(lái)考慮，任何不重復(fù)客戶(hù)的路徑都會(huì)被添加生成1條子路徑，并隨機(jī)插入剩余的客戶(hù).

2.2.2 高層啟發(fā)式策略

高層啟發(fā)式策略主要是考慮對(duì)底層啟發(fā)式算子的選擇策略，即決定在1次迭代過(guò)程中選擇哪些底層啟發(fā)式算子用于改進(jìn)當(dāng)前解.

基于禁忌搜索的高層啟發(fā)式策略使用得分的方法來(lái)評(píng)價(jià)底層啟發(fā)式算子的表現(xiàn)，再依據(jù)分?jǐn)?shù)決定在迭代過(guò)程中使用哪些底層啟發(fā)式算子改進(jìn)當(dāng)前解.每個(gè)底層啟發(fā)式算子均有1個(gè)相同的初始分?jǐn)?shù)，采用強(qiáng)化學(xué)習(xí)的方法進(jìn)行分?jǐn)?shù)更新，當(dāng)算子改進(jìn)當(dāng)前解時(shí)，給算子加分，反之則減分.最后根據(jù)分?jǐn)?shù)，通過(guò)貪心法選擇底層啟發(fā)式算子，即總是選擇分?jǐn)?shù)最高的算子.具體過(guò)程：在搜索開(kāi)始時(shí)，每個(gè)底層啟發(fā)式算子k均有1個(gè)分?jǐn)?shù)，設(shè)rk=0(假設(shè)初始分?jǐn)?shù)均為0分).每個(gè)算子的分?jǐn)?shù)允許在間隔[rmin,rmax]中減少和增加，rmin和rmax分別為最低和最高的分?jǐn)?shù).每次迭代選擇1個(gè)不在禁忌表內(nèi)且分?jǐn)?shù)最高的算子k，計(jì)算目標(biāo)函數(shù)值f1并求得與上一個(gè)目標(biāo)函數(shù)值f2之間的變化量，即Δ=f2-f1.如果結(jié)果有改進(jìn)(若目標(biāo)為最小化問(wèn)題，即Δ>0)，則增加算子k的分?jǐn)?shù)，例如rk=rk+α，其中α為1個(gè)正數(shù).否則減少分?jǐn)?shù)，例如rk=rk-α，并把算子k放入固定禁忌長(zhǎng)度的禁忌表內(nèi)，根據(jù)先進(jìn)先出原則赦免禁忌表內(nèi)的算子.

對(duì)于多目標(biāo)問(wèn)題，對(duì)高層啟發(fā)式策略作如下設(shè)計(jì)：

1) 由于底層啟發(fā)式算子的性能不再只針對(duì)1個(gè)目標(biāo)進(jìn)行評(píng)估，而是針對(duì)每個(gè)目標(biāo)進(jìn)行評(píng)估，因此目標(biāo)函數(shù)變化量Δ變?yōu)棣，算子分?jǐn)?shù)rk變?yōu)閞k(u)，其中u=1,2,3(3為目標(biāo)個(gè)數(shù)).

2) 由于上述改變，因此在每次迭代過(guò)程中以均等的概率隨機(jī)選取1個(gè)目標(biāo)函數(shù)進(jìn)行求解.

2.3 求解LCLRPTW過(guò)程

LCLRPTW模型采用首先進(jìn)行配送中心選址分配，再進(jìn)行路徑優(yōu)化的方法進(jìn)行求解.即首先設(shè)計(jì)一種重心法選址方法進(jìn)行配送中心初始定位，以確定配送中心位置和其服務(wù)的客戶(hù)群；然后求解不同客戶(hù)群的配送路徑.具體流程如下：

步驟1初始化種群.每條染色體均采用客戶(hù)直接編碼的方式：假設(shè)有9個(gè)客戶(hù)點(diǎn)和有3個(gè)候選配送中心，其中1～9表示客戶(hù)點(diǎn)，0(1)-0(3)表示候選配送中心.對(duì)這9個(gè)客戶(hù)進(jìn)行隨機(jī)排列，假設(shè)生成的1條染色體2-5-6-4-3-7-8-1-9，隨機(jī)生成100條染色體構(gòu)成初始種群P.

步驟2將種群中每個(gè)個(gè)體轉(zhuǎn)換成可行路徑.按照約束條件(此處為車(chē)輛容量和配送中心庫(kù)存)，依次將解的每個(gè)客戶(hù)納入到車(chē)輛路徑中，當(dāng)1個(gè)客戶(hù)違背約束時(shí)，就重新開(kāi)辟1條新的路徑并將這個(gè)客戶(hù)納入該路徑.例如0-2-5-6-0-4-3-0-7-8-1-9-0，代表著共有3條配送路徑0-2-5-6-0，0-4-3-0，0-7-8-1-9-0.類(lèi)似地，若每1條染色體的每1段路徑均可行，則該染色體為有效染色體.

步驟3進(jìn)行配送中心初始化選址.對(duì)于多個(gè)配送中心選址問(wèn)題，為了使模型簡(jiǎn)單化，很多時(shí)候可以將它變成多個(gè)單一配送中心選址問(wèn)題來(lái)處理[16].結(jié)合重心法的思想，方案如下：1) 根據(jù)上述生成的3條配送路徑，由客戶(hù)坐標(biāo)和需求計(jì)算出各條路徑的重心；2) 根據(jù)求得重心，根據(jù)距離最小化原則，給每條路徑分配一個(gè)配送中心；3) 形成初始化選址方案.可以得到3條路線(xiàn)：0(2)-2-5-6-0(2)，0(1)-4-3-0(1)，0(3)-7-8-1-9-0(3).

步驟4通過(guò)2.2.2中設(shè)計(jì)的高層啟發(fā)式策略對(duì)初始種群P中每條染色體的路徑進(jìn)行優(yōu)化.

1) 設(shè)置相關(guān)算法參數(shù).包括底層啟發(fā)式算子的初始分?jǐn)?shù)，加減分值α，禁忌長(zhǎng)度，并令禁忌表為空.

2) 選擇目標(biāo)函數(shù).在3個(gè)目標(biāo)函數(shù)中(u,v,w)，以均等的概率隨機(jī)選擇1個(gè)目標(biāo)函數(shù)u.

3) 選擇底層啟發(fā)式算子.根據(jù)底層啟發(fā)式算子的分?jǐn)?shù)，選擇1個(gè)不在禁忌表內(nèi)且分?jǐn)?shù)最高的算子k(若選中LLH5和LLH6這2個(gè)算子，即代表對(duì)配送中心進(jìn)行操作).

4) 計(jì)算目標(biāo)函數(shù)值.使用3)選擇的算子k計(jì)算2)所選目標(biāo)u的函數(shù)值.

5) 計(jì)算目標(biāo)函數(shù)值的變化量Δu.如果Δu>0，則算子k分?jǐn)?shù)增加，即rk(u)=rk(u)+α,其中α=1，否則分?jǐn)?shù)減少，即rk(u)=rk(u)-α，并把算子k放入禁忌表中，根據(jù)先進(jìn)先出原則赦免禁忌表內(nèi)的算子.

6) 計(jì)算目標(biāo)函數(shù)v，w，如果Δv>0，則rk(v)=rk(v)+α，否則rk(v)=rk(v)-α；如果Δw>0，則rk(w)=rk(w)+α，否則rk(w)=rk(w)-α.

7) 進(jìn)行非支配排序，更新非支配解集.

8) 若滿(mǎn)足算法終止準(zhǔn)則結(jié)束算法，否則轉(zhuǎn)到2).

9) 產(chǎn)生非支配解集.

3 應(yīng)用實(shí)例及結(jié)果分析

3.1 應(yīng)用實(shí)例

為了體現(xiàn)算法的實(shí)用性，采用某地區(qū)的一家物流公司作為實(shí)際案例進(jìn)行求解[17]，該案例包括3個(gè)配送中心和30個(gè)客戶(hù)，其中每個(gè)客戶(hù)的坐標(biāo)、需求量、時(shí)間窗以及服務(wù)時(shí)間均已知.客戶(hù)點(diǎn)詳細(xì)信息見(jiàn)文獻(xiàn)[17]表5.2，配送中心相關(guān)信息如表1所示.基于禁忌搜索的多目標(biāo)超啟發(fā)式算法(Multi-objective hyper heuristic algorithm based on tabu search，MOHH_TS)以及進(jìn)行對(duì)比的NSGA-II算法[18]均采用MATLAB編程，運(yùn)行在CPU為Intel Core i5，2.6 GHz，RAM為4 G內(nèi)存的計(jì)算機(jī)平臺(tái)上，其他參數(shù)設(shè)置如下[8,17]：初始種群數(shù)為100，燃油消耗參數(shù)a=6.208×10-3，b=0.212 5，燃油轉(zhuǎn)換系數(shù)η=2.68，車(chē)輛行駛速度v=50 km/h，單位時(shí)間車(chē)輛提前到達(dá)或延誤到達(dá)客戶(hù)點(diǎn)的懲罰系數(shù)分別為α=0.5，β=1.

表1 配送中心相關(guān)信息Table 1 Related information of depot centers

3.2 結(jié)果分析

首先對(duì)MOHH_TS算法和NSGA-II算法在解決多目標(biāo)LCLRPTW問(wèn)題的性能進(jìn)行比較，通過(guò)收斂代數(shù)、Pareto面和目標(biāo)函數(shù)的收斂情況3個(gè)方面進(jìn)行分析.

3.2.1 收斂代數(shù)分析

求解多目標(biāo)LCLRPTW問(wèn)題的收斂代數(shù)見(jiàn)表2，取運(yùn)行10次的平均收斂代數(shù).收斂準(zhǔn)則為連續(xù)10代不再出現(xiàn)更優(yōu)個(gè)體.

表2 MOHH_TS和NSGA-II的收斂代數(shù)Table 2 Convergence times of MOHH_TS and NSGA-II 次

由表2可以看出：MOHH_TS和NSGA-II算法均可以找到最優(yōu)解，但MOHH_TS算法的平均迭代數(shù)為183.2次少于NSGA-II算法的232.6次，說(shuō)明MOHH_TS算法相比NSGA-II算法收斂速度更快，效率更高，這在求解更大規(guī)模問(wèn)題時(shí)將會(huì)更加明顯；同時(shí)，MOHH_TS算法相比較于NSGA-II算法的收斂代數(shù)曲線(xiàn)更加平穩(wěn)，說(shuō)明MOHH_TS算法更加穩(wěn)定.

3.2.2 Pareto面分析

為了能夠在相同的平臺(tái)進(jìn)行比較，設(shè)置2個(gè)算法均運(yùn)行300代，得到的Pareto面如圖2所示(圓圈代

表MOHH_TS算法，星號(hào)代表NSGA-II算法).

由圖2可以看到：MOHH_TS算法得到的Pareto數(shù)量更多，且更容易達(dá)到每個(gè)目標(biāo)函數(shù)的極值點(diǎn)；而NSGA-II算法得到的Pareto解分布得較為分散，對(duì)于3個(gè)目標(biāo)函數(shù)也不能均等對(duì)待.同時(shí)，從圖3中各個(gè)Pareto解的位置分布情況來(lái)看MOHH_TS算法的解幾乎落在同1個(gè)Pareto面上[19]，說(shuō)明MOHH_TS算法收斂得較好.

圖2 MOHH_TS和NSGA-II的Pareto最優(yōu)解Fig.2 Pareto optimal solution of MOHH_TS and NSGA-II

3.2.3 目標(biāo)函數(shù)分析

為了清楚地比較2個(gè)算法的各個(gè)目標(biāo)函數(shù)的優(yōu)劣情況，把所有代中各個(gè)目標(biāo)函數(shù)的平均值進(jìn)行比較，見(jiàn)圖3(a～c)(粗線(xiàn)代表MOHH_TS算法，細(xì)線(xiàn)代表NSGA-II算法).

圖3 目標(biāo)函數(shù)收斂情況比較Fig.3 Comparison of objective function convergence

由圖3可知：MOHH_TS算法的3個(gè)目標(biāo)函數(shù)值好于NSGA-II算法，且曲線(xiàn)初期下降速度明顯，說(shuō)明算法收斂速度更快；MOHH_TS算法的末端值更小，說(shuō)明算法更有效，能更好地避免早熟現(xiàn)象，能找到更接近最優(yōu)解的Pareto解.

其次為了了解MOHH_TS算法中底層啟發(fā)式算子對(duì)解質(zhì)量的影響情況，運(yùn)行300代，運(yùn)行10次，統(tǒng)計(jì)14個(gè)底層啟發(fā)式算子的平均接受率，如圖4所示.

圖4 算子的平均接受率Fig.4 Average acceptance rate of LLH

由圖4可以看出：14個(gè)底層啟發(fā)式算子的平均接受率均超過(guò)0.6，其中算子LLH2，LLH3，LLH8，LLH13的平均接受率相對(duì)較高，超過(guò)了0.8，對(duì)解質(zhì)量的改進(jìn)作用較大；而算子LLH5和LLH6的平均接受率相對(duì)較低，不超過(guò)0.7.4個(gè)局部搜索算子(LLH9～LLH12)的接受率為1，這是由局部搜索算子本身的性能所決定的，因?yàn)楫a(chǎn)生的所有候選解為改進(jìn)解均會(huì)被接受.總體來(lái)說(shuō)，14個(gè)底層啟發(fā)式算子均能對(duì)解有不錯(cuò)的改進(jìn)作用，證明了算子構(gòu)建的有效性.

最后對(duì)于多目標(biāo)優(yōu)化問(wèn)題，決策者往往從實(shí)際需要出發(fā)選擇最為合適的解，從所得的Pareto解集中分別選擇碳排放最少、總成本最少和客戶(hù)滿(mǎn)意度最高(等待和遲到的總時(shí)間最少)的3組解作為配送方案，3組最優(yōu)解如表3所示.

表3 最優(yōu)解Table 3 Optimal solutions

對(duì)應(yīng)的最優(yōu)配送路線(xiàn)如表4所示.

表4 最優(yōu)路線(xiàn)Table 4 Optimal routes

由此可見(jiàn)，無(wú)論是從算法的收斂代數(shù)、收斂速度和穩(wěn)定性，還是從最優(yōu)解來(lái)看，MOHH_TS算法可以有效地解決多目標(biāo)LCLRPTW模型.

4 結(jié) 論

針對(duì)物流配送中選址路徑問(wèn)題，在車(chē)輛路徑安排時(shí)考慮碳排放的因素，首先構(gòu)建了同時(shí)考慮碳排放、總成本和客戶(hù)滿(mǎn)意度的多目標(biāo)LCLRPTW模型；其次構(gòu)建了和LCLRPTW問(wèn)題相關(guān)的底層啟發(fā)式算子，提出了基于禁忌搜索的超啟發(fā)式算法；最后進(jìn)行仿真實(shí)驗(yàn)，并和NSGA-II算法進(jìn)行比較.從底層啟發(fā)式算子的平均接受率來(lái)看，證明了算子構(gòu)建的有效性.從算法的收斂代數(shù)、Pareto面和目標(biāo)函數(shù)的收斂情況來(lái)看，證明了MOHH_TS算法可以有效地解決所提出的多目標(biāo)LCLRPTW模型，根據(jù)得到的Pareto最優(yōu)解也有利于決策者從實(shí)際需要出發(fā)選擇最為合適的配送方案.由于超啟發(fā)式算法具有較好的通用性，可以將該算法應(yīng)用到其他組合優(yōu)化問(wèn)題上，而不需改變框架，只需提供1組與問(wèn)題相關(guān)的底層啟發(fā)式算子.