考慮碳排放的選址-路徑問題研究

，，，,2

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

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

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

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

1.1 問題描述

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

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

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

F=GD(aL+b)

(1)

式中：F為運(yùn)輸過程的燃油消耗量；G為地形坡度因子；D為車輛的行駛距離；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í)際問題可以得到

Eij=ηDij[aQij+b]

(3)

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

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

對模型中的變量進(jìn)行如下定義：M{m|m=1,2,…,M}為一系列配送中心；C{i|i=1,2,…,n}為一系列需要服務(wù)的客戶；V{k|k=1,2,…,K}為屬于各個配送中心的車輛；S{M∪C}為配送中心和客戶總和；Km為屬于配送中心m且同一車型的車輛；di為客戶i的需求；Cc為單位CO2排放成本；Cv為派車成本；Cr為單位車輛運(yùn)輸成本；Cd為單位車輛折舊成本；Cf為單位燃油成本；Cm為配送中心開放成本；Qk為車輛的容量；Qm為配送中心的容量；[Ei,Li]為時(shí)間窗；T0為配送中心開始送貨時(shí)間；Tik為車輛k到達(dá)客戶i的時(shí)間；tij為客戶i～j的行駛時(shí)間；sik為車輛k服務(wù)客戶i的時(shí)間；α為單位時(shí)間車輛提前到達(dá)客戶點(diǎn)的懲罰系數(shù)；β為單位時(shí)間車輛延誤到達(dá)客戶點(diǎn)的懲罰系數(shù)；決策變量1：Xijk，當(dāng)車輛k從客戶i～j為1，否則為0；決策變量2：Zm，配送中心開放為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個目標(biāo)函數(shù)；式(4)代表總碳排放量最少；式(5)代表總成本最少，第1項(xiàng)為配送中心開放成本，第2項(xiàng)為派車成本，第3項(xiàng)為車輛運(yùn)輸成本和汽車折舊成本，第4項(xiàng)為燃油成本，第5項(xiàng)為CO2排放成本，第6項(xiàng)為早到等待成本，第7項(xiàng)為超時(shí)成本；式(6)代表等待和遲到的總時(shí)間最少；式(7)保證每個客戶均被訪問1次；式(8，9)表明車輛從配送中心出發(fā)，必須回到原配送中心；式(10)保證每1個運(yùn)輸車輛的路徑最多從1個配送中心駛出；式(11)保證任何2個配送中心的車輛不會在同1條路徑上；式(12)保證訪問完客戶后必須離開；式(13)保證每個配送中心訪問的顧客總需求小于配送中心的容量；式(14)保證車的載重不大于它的載重能力；式(15)保證每個客戶的需求均被滿足；式(16)表示規(guī)定開始的送貨時(shí)間為0；式(17)表示車輛k到達(dá)客戶j處的時(shí)刻等于車輛k到達(dá)客戶i處的時(shí)刻與其在客戶i處服務(wù)時(shí)間，以及從客戶i處到客戶j處的行駛時(shí)間之和；式(18)表示車輛k到達(dá)客戶i處的時(shí)間需滿足客戶規(guī)定的時(shí)間窗；式(19，20)是對決策變量的描述.

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

2.1 超啟發(fā)式算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 求解LCLRPTW過程

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

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

步驟2將種群中每個個體轉(zhuǎn)換成可行路徑.按照約束條件(此處為車輛容量和配送中心庫存)，依次將解的每個客戶納入到車輛路徑中，當(dāng)1個客戶違背約束時(shí)，就重新開辟1條新的路徑并將這個客戶納入該路徑.例如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.類似地，若每1條染色體的每1段路徑均可行，則該染色體為有效染色體.

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

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

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

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

3) 選擇底層啟發(fā)式算子.根據(jù)底層啟發(fā)式算子的分?jǐn)?shù)，選擇1個不在禁忌表內(nèi)且分?jǐn)?shù)最高的算子k(若選中LLH5和LLH6這2個算子，即代表對配送中心進(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) 若滿足算法終止準(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個配送中心和30個客戶，其中每個客戶的坐標(biāo)、需求量、時(shí)間窗以及服務(wù)時(shí)間均已知.客戶點(diǎn)詳細(xì)信息見文獻(xiàn)[17]表5.2，配送中心相關(guān)信息如表1所示.基于禁忌搜索的多目標(biāo)超啟發(fā)式算法(Multi-objective hyper heuristic algorithm based on tabu search，MOHH_TS)以及進(jìn)行對比的NSGA-II算法[18]均采用MATLAB編程，運(yùn)行在CPU為Intel Core i5，2.6 GHz，RAM為4 G內(nèi)存的計(jì)算機(jī)平臺上，其他參數(shù)設(shè)置如下[8,17]：初始種群數(shù)為100，燃油消耗參數(shù)a=6.208×10-3，b=0.212 5，燃油轉(zhuǎn)換系數(shù)η=2.68，車輛行駛速度v=50 km/h，單位時(shí)間車輛提前到達(dá)或延誤到達(dá)客戶點(diǎn)的懲罰系數(shù)分別為α=0.5，β=1.

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

3.2 結(jié)果分析

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

3.2.1 收斂代數(shù)分析

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

表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次，說明MOHH_TS算法相比NSGA-II算法收斂速度更快，效率更高，這在求解更大規(guī)模問題時(shí)將會更加明顯；同時(shí)，MOHH_TS算法相比較于NSGA-II算法的收斂代數(shù)曲線更加平穩(wěn)，說明MOHH_TS算法更加穩(wěn)定.

3.2.2 Pareto面分析

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

表MOHH_TS算法，星號代表NSGA-II算法).

由圖2可以看到：MOHH_TS算法得到的Pareto數(shù)量更多，且更容易達(dá)到每個目標(biāo)函數(shù)的極值點(diǎn)；而NSGA-II算法得到的Pareto解分布得較為分散，對于3個目標(biāo)函數(shù)也不能均等對待.同時(shí)，從圖3中各個Pareto解的位置分布情況來看MOHH_TS算法的解幾乎落在同1個Pareto面上[19]，說明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個算法的各個目標(biāo)函數(shù)的優(yōu)劣情況，把所有代中各個目標(biāo)函數(shù)的平均值進(jìn)行比較，見圖3(a～c)(粗線代表MOHH_TS算法，細(xì)線代表NSGA-II算法).

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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