冷龍龍，趙燕偉+，張春苗,2

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

0 引言

在供應(yīng)鏈管理和物流系統(tǒng)規(guī)劃中，選址—路徑問題(Location-Routing Problem, LRP)是重要的組合優(yōu)化問題之一，其在優(yōu)化物流配送成本與效率、客戶滿意度和環(huán)境問題中發(fā)揮著重要作用。作為LRP最熱門的變體，低碳LRP(Low-Carbon LRP, LCLRP)[1]綜合考慮了CO2等溫室氣體的車輛路線規(guī)劃和倉庫選址。近年來，考慮環(huán)境因素的路線規(guī)劃和選址分配問題的仿真優(yōu)化對經(jīng)濟(jì)、社會和環(huán)境越來越重要，本文針對考慮環(huán)境因素的LRP構(gòu)建數(shù)學(xué)模型，以降低配送過程中的燃料消耗和CO2等溫室氣體的排放量，優(yōu)化配送成本和效率。

道路速度限制在確保公眾安全方面發(fā)揮著重要作用[2]。大多數(shù)城市采用的特定路段限速方式一般可以簡化為具有不同速度區(qū)域的特殊情況[3]，速度區(qū)域化可以更加安全有效地調(diào)節(jié)交通流量，并合理平衡駕駛員和行人的公共道路需求與區(qū)域居民的關(guān)注點(diǎn)[4]。另外，研究表明通過合理的限速方式設(shè)置速度區(qū)域有利于減少超車現(xiàn)象、交通擁堵和事故[5]。區(qū)域化LCLRP(Regional LCLRP, RLCLRP)的主要特征為客戶和倉庫位于速度限制不同的嵌套區(qū)域，目標(biāo)是降低物流成本，包括倉庫成本、車輛成本和路徑成本，路徑成本為燃油消耗和CO2排放成本，通過最小化物流成本可以達(dá)到降低碳排量的目的。

針對RLCLRP,本文提出一種基于共享機(jī)制的自適應(yīng)超啟發(fā)式求解算法，即通過共享底層算子的近期性能信息自適應(yīng)地選擇優(yōu)質(zhì)合適的底層算子，并提出一種自適應(yīng)解的接收機(jī)制以提高算法的收斂速度和精度。最后通過仿真驗證了所提算法的有效性和魯棒性。本文的主要貢獻(xiàn)與創(chuàng)新如下：①從模型層面，首次考慮多車型、同時取送貨和區(qū)域化速度等實際約束對碳排放的影響，并構(gòu)建多車型同時取送貨的RLCLRP(RLCLRP with Simultaneous Pickup and Delivery and Heterogeneous Fleet, RLCLRPSPDHF)模型；②從算法層面，設(shè)計了一種基于共享機(jī)制的自適應(yīng)超啟發(fā)式求解算法，并提出一種自適應(yīng)接收機(jī)制；③評估車型構(gòu)成、倉庫和客戶分布等因素對碳排放和總成本的影響及其比重，為企業(yè)提供了應(yīng)對統(tǒng)籌規(guī)劃配送決策的管理指導(dǎo)與建議。

1 相關(guān)工作回顧

LRP集成了兩類經(jīng)典NP-hard問題，即選址—分配問題(Location-Allocation Problem, LAP)和車輛路徑問題(Vehicle Routing Problem, VRP)[6]，目前已經(jīng)成為運(yùn)籌學(xué)管理與城市貨物運(yùn)輸網(wǎng)絡(luò)優(yōu)化的重要工具和研究熱點(diǎn)之一，如物品回收和危險廢物管理等[7-8]。LCLRP是以降低物流配送中產(chǎn)生的碳排放等溫室氣體為目標(biāo)的LRP問題，同樣融合了LAP和污染路徑問題(Pollution Routing Problem, PRP)/綠色VRP(Green VRP, GVRP)兩類NP-hard問題，這兩類問題著重考慮貨物運(yùn)輸產(chǎn)生的碳排放量對社會和環(huán)境的影響。

為了降低貨物運(yùn)輸碳排放量，需要采用評估碳排放量的數(shù)學(xué)模型，根據(jù)模型性質(zhì)選擇合適的碳排放模型的類型，因此提出多種模型估算車輛的燃油消耗并將其最小化。表1所示為10種估算碳排放的模型，包括模型與文獻(xiàn)來源，這幾種模型涉及道路狀況、車輛參數(shù)、自然環(huán)境和負(fù)載狀況4類影響碳排放的因素，其中道路狀況考慮了道路擁堵情況與道路特征(坡度等)，車輛參數(shù)主要有車輛的尺寸、自重和發(fā)動機(jī)參數(shù)，自然環(huán)境主要是天氣狀況，此外駕駛員水平和習(xí)慣也是一種重要的影響因素。有關(guān)估算CO2等溫室氣體排放的數(shù)學(xué)模型可參閱文獻(xiàn)[9-12]。實際上，考慮所有影響因素來建立車輛的油耗模型十分困難且沒有必要[1]，本文研究多車型同時取送貨與區(qū)域化的LCLRP，即考慮多車型、同時取送貨和速度區(qū)域化等實際約束對碳排放量的影響。

表1 模型種類與來源

在城市物流中，多車型是降低物流成本和提高物流配送效率的重要方式之一[5,31]。近年來，多車型物流配送在PRP和GVRP中逐漸成為減少碳排放的主要形式[32-33]。Koc等[5,34]分析車隊規(guī)模和構(gòu)成對成本與碳排放的影響，表明多車型相對于單一車型的物流配送網(wǎng)絡(luò)存在優(yōu)勢；李進(jìn)等[19]構(gòu)建了具有固定車輛數(shù)的多車型低碳VRP模型，表明相比單一車型，采用多車型更能提高車輛的容量利用率、降低能耗與碳排放、減少使用車輛數(shù)；Pitera等[35]研究了多車型在逆向網(wǎng)絡(luò)回收物品中的作用，結(jié)果同樣表明了多車型為降低CO2排放的主要方式；Xiao等[36]考慮兩種不同排放模型的重型車輛，分析了多車型與單一車型對CO2等溫室氣體排放的影響。對車型構(gòu)成在物流配送成本或CO2等溫室氣體排放中的應(yīng)用感興趣的學(xué)者可參閱綜述文獻(xiàn)[37]。

交通擁堵是影響車輛CO2等溫室氣體排放和燃油轉(zhuǎn)化效率的主要因素之一[28]。由文獻(xiàn)[17]可知，在實際行車過程中，當(dāng)車速低于30 mph時，CO2等溫室氣體的排放量和燃油消耗量快速非線性增長，即當(dāng)車速從30 mph下降到12.5 mph或從12.5 mph下降到5 mph時，每英里的CO2等溫室氣體排放量和燃油消耗量會增加一倍。因此，近年來許多研究人員致力于研究因交通擁堵造成的速度實時性(或行駛時間的不確定性)對成本或CO2排放量的影響，普遍利用速度的分段函數(shù)模擬交通擁堵，確保每段的速度為常數(shù)[21,36,38-43]。Poothalir等[44]采用三角概率分布函數(shù)曲線表征速度的時變性，給出速度變化有利于減少燃油消耗的結(jié)論；Koc等[5]采用速度區(qū)域化概念表征交通阻塞，每個區(qū)域中保持勻速行車。對因交通擁堵影響的速度時變性感興趣的學(xué)者可參閱文獻(xiàn)[45]。

然而，以上大部分文獻(xiàn)只分析了PRP或GVRP模型中的車隊構(gòu)成、交通擁堵、車輛負(fù)載和行車距離對碳排放的影響，僅有文獻(xiàn)[1,5]將LAP和PRP(或GVRP)融合，構(gòu)建LCLRP數(shù)學(xué)模型。文獻(xiàn)[1]和文獻(xiàn)[5]的主要區(qū)別為：前者僅優(yōu)化車輛運(yùn)輸過程中的碳排放量，后者將車輛行駛過程中的燃料消耗量折算為路徑成本，通過優(yōu)化物流總成本達(dá)到節(jié)能減排的目的。文獻(xiàn)[1]的主要不足為：①難以評估倉庫的固有碳排放，僅人為設(shè)定過于主觀；②不考慮倉庫固有碳排放時會浪費(fèi)現(xiàn)有資源，增加物流成本。文獻(xiàn)[5]的缺陷是通過優(yōu)化物流成本來降低碳排放而并非碳排放最小化?？紤]到倉庫的固有碳排放難以評估，采用文獻(xiàn)[5]的方法將油耗成本折算為路徑成本，通過優(yōu)化物流成本達(dá)到節(jié)能減排、提高企業(yè)經(jīng)濟(jì)效益的目的。本文在文獻(xiàn)[5]的基礎(chǔ)上進(jìn)一步展開研究，每個實例速度區(qū)域劃分的位置和面積隨機(jī)變化且為嵌套式，區(qū)域形狀為矩形，每個速度區(qū)域的速度亦隨機(jī)變化，即VZone3～U(60,80)，VZone2～U(40,60)，VZone1～U(20,40)；另外，本文還涉及同時取送貨等客戶實際需求，以及經(jīng)典CLRPSPD模型(MTC-2)、最小碳排放量(Minimum Carbon Emission, MCE)、最小距離(Minimum Total Distance, MTD)和最小行駛時間(Minimum Travel Time, MTT)4種RLCLRPSPDHF模型變體。目前，尚未有學(xué)者綜合研究車隊構(gòu)成、同時取送貨、速度區(qū)域化、倉庫、服務(wù)距離和車輛負(fù)載等約束對物流成本和CO2等溫室氣體的影響。

2 模型構(gòu)建

2.1 碳排放模型

本節(jié)主要介紹所采用的燃油消耗與碳排放模型，即綜合模態(tài)排放模型(Comprehensive Modal Emission Model, CMEM)。目前已有學(xué)者將CMEM運(yùn)用于PRP及其變型[5,13,16-19,34,41]。在多車型CMEM中，采用式(1)估算車型h∈H的車輛燃油消耗率FRh(單位：g/s)：

FRh=ξ(khNhVh+Ph/η)/κ。

(1)

式中：ξ為燃料與空氣質(zhì)量比；kh，Nh和Vh分別為車型為h的車輛發(fā)動機(jī)摩擦系數(shù)、轉(zhuǎn)速和排量；η為柴/汽油機(jī)的效率；κ為柴/汽油熱值；Ph為車型h的發(fā)動機(jī)輸出功率(單位：kW/s)，

(2)

MhgCrcosθ)v/1 000。

(3)

因此，車型為h的車輛以速度v(常數(shù))負(fù)載Mh行駛距離d(單位：m)所消耗的油耗Fh(單位：g)為Fh=FRh×t(t為時間，單位：s)，即

(4)

Fh=λ(khNhVhd/v+Mhγαd+βhγdv2)。

(5)

式中：khNhVhd/v為發(fā)動機(jī)模塊，與運(yùn)行時間成正比；Mhγαd為負(fù)載模塊，與整車質(zhì)量和距離成正比；βhγdv2為速度模塊，與距離和速度的平方成正比。圖1所示為車輛行駛100 km時耗油量與速度的關(guān)系圖，圖1a為不計車輛自重空載時的耗油量與車速的關(guān)系，圖1b為計入車輛自重空載時的耗油量與車速的關(guān)系，其中L1，L2，M為3種車型，車輛自身參數(shù)各不相同。由圖1可知油耗量與速度的關(guān)系呈現(xiàn)U型,并存在最優(yōu)速度，使得油耗量最小，即vbest=(khNhVh/2βhγ)1/3。另外，車輛的CO2排放量與油耗量呈線性正比關(guān)系，即油耗量越大，碳排放量也越大。根據(jù)文獻(xiàn)[5]，汽油轉(zhuǎn)換系數(shù)為2.32，即每消耗1L汽油會產(chǎn)生2.32 kg的CO2。

2.2 速度區(qū)域化

限制速度有利于減緩駕駛、節(jié)省燃料、減少CO2等污染氣體排放[46]。速度區(qū)域化反映了與時間有關(guān)的交通擁堵所造成的速度時變性，對其進(jìn)行研究可有效減緩交通擁堵狀況，實現(xiàn)交通的可持續(xù)發(fā)展。圖2所示為速度區(qū)域化的一種簡單有效的方式，圖中將城市分為3個速度區(qū)域，Zone 1對應(yīng)市中心，體現(xiàn)為小巷和狹窄的道路等；Zone 2對應(yīng)市中心外部區(qū)域，包括商業(yè)區(qū)和大學(xué)城等；Zone 3對應(yīng)郊區(qū)，包括農(nóng)業(yè)區(qū)和公園等。VZone1，VZone2，VZone3表示各區(qū)域的行車速度(固定速度)，且VZone1

2.3 模型構(gòu)建

RLCLRPSPDHF定義為一個完全定向網(wǎng)絡(luò)G=(V,E)，其中：V由M候選倉庫和N客戶構(gòu)成，每個客戶均有配貨和集貨需求且地理位置已知，每個候選倉庫的容量和位置已知并告知其固定租賃成本；E為邊集，由N+M節(jié)點(diǎn)之間的距離構(gòu)成。不同型號的車輛從倉庫出發(fā)依次服務(wù)一系列客戶，滿足客戶的配集貨需求后返回原出發(fā)點(diǎn)。該模型的目標(biāo)為確定一系列倉庫位置和數(shù)量并分配行車路線，使總成本最小，包括倉庫與車輛的固定租賃成本和燃油消耗成本。

在建立RLCLRPSPDHF數(shù)學(xué)模型之前，首先針對RLCLRPSPDHF的實際情況作如下合理假設(shè)：①每個客戶只能被一個車輛和倉庫服務(wù)一次；②車輛服務(wù)所有客戶后必須返回原出發(fā)點(diǎn)；③每兩個節(jié)點(diǎn)間的弧段上的車輛負(fù)載不能超過容量限制；④任何時期倉庫的負(fù)載不能超過其容量限制；⑤不考慮陸續(xù)不定發(fā)車情況，且每個倉庫有足夠的車輛服務(wù)所有客戶；⑥以最高滿載率的原則分配車輛。模型中出現(xiàn)的符號變量含義如表2所示。

表2 參數(shù)符號含義

根據(jù)上述假設(shè)條件，構(gòu)建如下模型：

(6)

s.t.

(7)

(8)

(9)

j∈I,i≠j,h∈H；

(10)

(11)

(12)

k∈J,i≠j；

(13)

(14)

(15)

(16)

(17)

Qijh≤CVhxijh,?i,j∈V,i≠j,h∈H；

(18)

Qijh≥(qj-pj)xijh,?i∈V,j∈I,h∈H。

(19)

其中：式(6)為目標(biāo)函數(shù)，包括所租賃車輛和倉庫的固定成本與燃油消耗成本，F(xiàn)ijh由式(5)求得；式(7)和式(8)保證每個客戶只能被服務(wù)一次；式(9)和式(10)表示每個客戶只能被一個倉庫和車輛服務(wù)；式(11)～式(13)確保服務(wù)車輛返回原倉庫；式(14)為倉庫容量約束；式(15)和式(16)分別為車輛出發(fā)和返回時的負(fù)載量；式(17)為車輛負(fù)載量的動態(tài)平衡約束；式(18)和式(19)為車輛容量約束。

3 算法設(shè)計

超啟發(fā)式(Hyper-Heuristics, HH)算法是由Cowling等[47]于2000年提出的一種新型理論，將其定義為“啟發(fā)式選擇啟發(fā)式”算法，該算法為組合優(yōu)化問題的求解提供了一種新思路。后來，Burke等[48]拓展了超啟發(fā)式算法——啟發(fā)式選擇和啟發(fā)式生成。在HH框架中，存在底層啟發(fā)式方法(Low-Level Heuristic, LLH)和高層啟發(fā)式方法(High-Level Heuristic, HLH)兩個相互隔離的領(lǐng)域。前者用于處理與問題領(lǐng)域相關(guān)的數(shù)據(jù)，包括所優(yōu)化問題的數(shù)據(jù)信息、底層算子(用于搜索問題空間)和種群信息(染色體和適應(yīng)度等)；后者涵蓋了算子的選擇策略和解的接收機(jī)制兩類不同性質(zhì)的策略，選擇策略的目的在于搜索由算子構(gòu)成的空間并監(jiān)測算子的歷史性能信息，以選擇優(yōu)質(zhì)合適的算子，接收準(zhǔn)則計算劣質(zhì)子代解的接收概率用于判斷是否取代父代解，并控制著算法搜索的方向和收斂速度。另外，在HLH和LLH之間存在信息交換器，用于傳輸算子選擇信息、解的接收信息、解的改進(jìn)率、算子運(yùn)行時間和次數(shù)，以及當(dāng)前解連續(xù)無法改進(jìn)的次數(shù)等與問題領(lǐng)域無關(guān)的信息。

本文從以下4個方面研究RLCLRPSPD和超啟發(fā)算法。

3.1 解的編碼與初始種群的產(chǎn)生

本文所采用的編碼方法如下：將V={v1,v2,…,vK}表征為一個完整的解，其涵蓋所有路線；每條行駛路線對應(yīng)染色體中第i個基因，即vi，每條路線起止于所屬倉庫，客戶訪問順序存儲于起止倉庫之間，而且每條路線對應(yīng)一個元胞數(shù)組；一個完整的染色體長度是取值為2K+N的非定長自然數(shù)列(K為所需車輛數(shù)，N為客戶規(guī)模)，同時染色體對應(yīng)K個子元胞數(shù)的集合；為了降低計算復(fù)雜度和迅速計算適應(yīng)度，采用定義“屬性行”的方法保存每條行駛路線的各類參數(shù)，包括車輛的起始負(fù)載、行駛費(fèi)用(車輛租賃費(fèi)用和油耗費(fèi)用等)和車輛類型等，因此在計算適應(yīng)度時只需調(diào)用每條路線的行駛費(fèi)用并求和，避免了重復(fù)計算。圖3所示為一個簡單實例，圖中客戶集I∈{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}，倉庫集J∈{16,17,18,19}，CV∈{70,80,90}，車型H={L1,L2,L3}。該圖類似于分層樹形編碼方法[6]，即樹根為行車路線，每條路線為枝干的構(gòu)成之一；樹葉對應(yīng)路線的各類屬性，包括起止載重量、行駛費(fèi)用和車輛類型等。

本文的超啟發(fā)式算法所采用的機(jī)制為非種群策略，即單點(diǎn)搜索框架(Single-Point Search Framework, SPSF)。因為SPSF易于陷入局部最優(yōu)解，所以在算法初始執(zhí)行階段從初始種群隨機(jī)選擇任意個體進(jìn)行優(yōu)化。初始種群采用隨機(jī)生成方法構(gòu)建，首先隨機(jī)生成客戶順序，利用貪婪法則分配客戶，直至車輛容量無法滿足下一個客戶；然后根據(jù)重心原則隨機(jī)選擇所需倉庫，并保證符合倉庫容量要求，計算每條路線的屬性；最后構(gòu)造完整的車輛路線集。

3.2 高層策略的構(gòu)造

3.2.1 選擇策略設(shè)計

在超啟發(fā)式算法成為許多組合優(yōu)化領(lǐng)域研究熱點(diǎn)的同時，構(gòu)建了諸多優(yōu)質(zhì)的選擇策略，包括CF(choice function)[47], FRR-MAB(fitness rate rank based multi-armed bandit)[49]等。本文提出一種新型選擇策略——基于共享機(jī)制的自適應(yīng)選擇策略(Shared and Self-Adaptive Choice Mechanism, SSACM)，其主要有3個特點(diǎn)：①利用滑動窗口(Sliding Windows, SW)存儲近期算子性能信息，并將上次迭代中的算子性能有條件地共享至滑動時間窗的其余底層算子；②依靠算子性能表現(xiàn)將底層算子分為精英算子(Elite Heuristics, EH)和劣性算子(Poor Heuristics, PH)，根據(jù)算子近期階段性能自適應(yīng)地選擇合適的EH或PH；③針對EH和PH設(shè)計不同的性能評估方法。

SW為W×2維矩陣，其第1列儲存所使用的算子，第2列儲存算子的適應(yīng)度改進(jìn)率FIR。如式(20)所示，本文采用先進(jìn)先出(First-in-First-Out, FIFO)機(jī)制排除滑動窗口中算子的早期性能參數(shù)，僅記錄FIR>0的優(yōu)質(zhì)算子，當(dāng)FIR<0時，立刻清空滑動窗口。

(20)

共享策略將上一次底層算子的FIR共享至滑動窗口內(nèi)其他的底層算子，方法為按照先后順序依次按特定比例分配FIR，例如比例為{r1,r2,…,rW}，保證滿足r1+r2+…+rW=1和r1>r2>…>rW，即與目前階段越相近，比例越大，所得性能越高，r1為最近使用的底層算子。

采用算子全局歷史性能將底層算子分為兩類(EH和PH)，如式(21)所示。如果算子i的GFIR(i)≥0，則將該算子歸類為EH，否則屬于PH；如果GFIR<0，則將GFIR按降序排列，取前1/2的底層算子為EH，其余為PH。在算法迭代中，底層算子在不同優(yōu)化階段的性能表現(xiàn)可能不一致：當(dāng)EH中的所有底層算子無法改進(jìn)當(dāng)前解時，可認(rèn)為算法無法跳出局部最優(yōu)解，此時應(yīng)盡可能選擇PH中的算子；當(dāng)獲得擾動解時(跳出了局部最優(yōu)解后)，立刻采用EH中的算子有利于加快算子搜索過程，因此提出一種自適應(yīng)選擇機(jī)制，即PH的選擇概率隨TQ的增加而增加，TQ為當(dāng)前解未改進(jìn)算子的使用次數(shù)，NT為底層算子數(shù)，如式(22)所示。

(21)

(22)

在分配算子信用值時，對EH的內(nèi)部算子采用FRR-MAB信用值分配方法，即

(23)

3.2.2 接收準(zhǔn)則設(shè)計

接收準(zhǔn)則(Acceptance Criterion, AC)的作用在于計算劣質(zhì)的子代解cf取代父本pf的概率，用于控制算法的收斂速度和優(yōu)化精度。在對已有接收準(zhǔn)則分類時，所有接收準(zhǔn)則均可采用以下公式(求最小化問題)概括：

(24)

式中：CF為下一次迭代的當(dāng)前解；p為控制概率；r為0～1間的隨機(jī)數(shù)。一般地，當(dāng)cf優(yōu)于pf時，cf直接取代父本進(jìn)入下一次迭代，否則利用概率公式(24)計算cf取代pf的概率并做出抉擇。另外，大部分接收標(biāo)準(zhǔn)僅利用改進(jìn)率信息，忽略了算子的階段性能信息，即算子的優(yōu)化性能在不同計算階段表現(xiàn)不一致。本文利用算子的階段性能信息構(gòu)建一種簡單的自適應(yīng)接收標(biāo)準(zhǔn)，即采用計數(shù)器TQ記錄底層算子達(dá)到FIR≤0的迭代次數(shù)，接收子代解的概率隨TQ值的增大而增大，如果所選算子獲得了優(yōu)質(zhì)解，則重置TQ，即自適應(yīng)接收(Adaptive Acceptance, AA)機(jī)制以概率p=(2TQ/|ξ|)ψ接收劣質(zhì)解，當(dāng)TQ≥|ξ|/2時，cf被接收。其中ψ為接收控制參數(shù)，用于控制概率p的大小。

3.3 底層算子設(shè)計

底層算子庫(Pool of Low-level Operators, PLLO)中為直接搜索問題領(lǐng)域解空間的啟發(fā)式搜索算子，由領(lǐng)域?qū)＜姨峁LLO可視為無法操作的黑箱，其算子可根據(jù)優(yōu)化性質(zhì)分為變異算子和爬山算子兩類。變異算子在搜索過程中提供足夠的隨機(jī)性以防止陷入局部最優(yōu)解，所采用的機(jī)制為微小地擾動當(dāng)前解，而且不要求獲得優(yōu)質(zhì)解；爬山算子則嚴(yán)格要求算子具有改進(jìn)當(dāng)前解的能力，其能夠促使算法快速收斂并提高收斂精度。這兩類優(yōu)化算子在組合優(yōu)化問題領(lǐng)域中不可或缺，下面為本文構(gòu)造的6種爬山算子和9種變異算子：

(1)爬山算子有線路內(nèi)部2-Opt(Inside-2Opt)、線路間2-Opt(Inter-2Opt)、線路內(nèi)交換客戶(Inside-Swap)、線路間交換客戶(Inter-Swap)、線路內(nèi)移動客戶(Inside-Shift)和線路間移動客戶(Inter-Shift)。局部優(yōu)化算子每次執(zhí)行的約束條件為：①改進(jìn)率FIR≥0；②任意弧段的車輛負(fù)載必須小于額定容量；③倉庫的負(fù)載不能超過額定容量。對線路內(nèi)部進(jìn)行局部優(yōu)化時采用完全優(yōu)化策略[50]，對線路間進(jìn)行局部優(yōu)化時采用V-1機(jī)制，即隨機(jī)選定一條路徑與其他路線的客戶逐一交換優(yōu)化，可知算子復(fù)雜度從V(V-1)/2降低為V-1。

(2)變異算子分為兩類，一類針對車輛路線擾動的變異算子，包括Inside-2Opt-M，Inside-Or-Opt，Inter-Shift-M，Inter-Swap-M，Shaw[51]，Decompose，Merge。前5種變異算子的策略為隨機(jī)選取1/4～1/2的路徑，隨機(jī)擾動路徑內(nèi)或路徑間的客戶；Decompose分解隨機(jī)選中的路線，并獲得兩條子路線；Merge隨機(jī)選擇兩條路線合并為一條路線。另一類針對倉庫選用的編譯算子，包括Add-Swap和Relocation。Add-Swap算子將隨機(jī)選取的1/3～2/3路線分配給一個新的倉庫，或關(guān)閉一個倉庫并將該倉庫的所有路線安排到另一倉庫，以防止過少的倉庫導(dǎo)致過快收斂；Relocation算子將每條車輛路線坍塌于一個Super-Client，然后將倉庫插入每條路線中，將獲得的最小插入代價作為該倉庫與該路線之間的成本，類似于文獻(xiàn)[52]。變異算子必須滿足倉庫和車輛的負(fù)載約束。底層算子庫中的所有算子必須滿足所有約束條件后才能計算適應(yīng)度，以保證路線的可行性，避免使用修復(fù)技術(shù)。

3.4 算法復(fù)雜度分析

算法復(fù)雜度用于衡量算法運(yùn)行的時間性能，分析算法復(fù)雜度的關(guān)鍵在于分析運(yùn)行時間的相對量度。根據(jù)超啟發(fā)式算法的流程框架，超啟發(fā)式算法迭代一次的復(fù)雜度分為高層選擇策略復(fù)雜度、底層算子執(zhí)行復(fù)雜度、高層解的接收復(fù)雜度和精英保留策略復(fù)雜度4部分。在采用單點(diǎn)搜索框架的算法中，迭代次數(shù)為Tmax、客戶數(shù)為N、車輛數(shù)為K、底層算子數(shù)為NL，滑動窗口大小為W，算法迭代一次的復(fù)雜度包括高層選擇策略復(fù)雜度O(HS)、底層算子最大復(fù)雜度O(N2)、高層解接收機(jī)制最大復(fù)雜度O(3)和精英保留策略復(fù)雜度O(1)，迭代之外有種群初始化復(fù)雜度Npop×O(N2)和適應(yīng)度計算復(fù)雜度Npop×O(N2)(Npop為初始種群大小)。因此，算法的總體復(fù)雜度為

O(HH)=Npop×O(N2)+Npop×O(N2)+

Tmax×(O(HS)+O(3)+O(N2)+O(1))。

(25)

式中O(HS)包括底層算子性能更新O(1)和性能滑動時間窗更新O(W)。性能時間窗內(nèi)算子性能共享復(fù)雜度為O(W)，底層算子分類復(fù)雜度為O(NL)，自適應(yīng)概率計算復(fù)雜度為O(1)，劣性算子性能計算復(fù)雜度為O(1)，信用值計算復(fù)雜度為O(NL),輪盤賭策略復(fù)雜度為2×O(NL)，因此執(zhí)行一次選擇策略的最大復(fù)雜度為

O(HS)=O(3)+2×O(W)+4×O(NL)。

(26)

超啟發(fā)式算法總體復(fù)雜度為

O(HH)=2Npop×O(N2)+Tmax×

(O(4NL+2W+7)+O(N2))=2Npop×O(N2)+

Tmax×O(4NL+2W+7)+Tmax×O(N2)。

(27)

根據(jù)以上分析可知，所提算法的整體時間復(fù)雜度約為Tmax×O(N2)，即可忽略高層策略的時間復(fù)雜度，所提超啟發(fā)式算法的總體計算復(fù)雜度約為底層算子計算復(fù)雜度的總和，和大部分啟發(fā)式算法為同一個量級，是一種有效的算法。

4 仿真實驗與比較分析

仿真實驗的目的如下：①驗證算法的求解準(zhǔn)確性與模型的正確性；②驗證所提組合策略SSACM-AA的高效性；③分析客戶和倉庫分布以及車型構(gòu)成對物流成本與碳排放的影響。根據(jù)實驗?zāi)康?，生成如下算例：①實?隨機(jī)生成15個小規(guī)模算例，客戶數(shù)N∈{10,15,20}(各5個)，倉庫數(shù)M∈{2,3,5}，客戶取送貨量q，p∈[0,4 000](kg)；②實驗2采用適用于LRP的Barreto[51]標(biāo)準(zhǔn)實例庫以及適用于CLRPSPD的KBAM和YLBAM實例庫[53]的W類型實例，N∈[21,150]，M∈[5,15]；③建立LCLIENT，LDEPOT，LVEHICLE 3類不同性質(zhì)的實例庫，每個實例庫中客戶數(shù)N∈{25,50,75,100}。

在LCLIENT實例庫中生成4種不同的客戶分布：CC1為60%的客戶位于Zone 1；CC2為60%的客戶位于Zone 2；CC3為60%的客戶位于Zone 3；CR為客戶隨機(jī)分布。倉庫隨機(jī)分布，倉庫數(shù)量M=5，位于Zone 1，Zone 2，Zone 3，倉庫的固定成本分別為1 000元、700元和400元，令每個倉庫均能服務(wù)所有客戶。在LDEPOT實例庫中，客戶位置隨機(jī)分布，同樣有4種不同的倉庫分布：DC1為所有倉庫位于Zone 1；DC2為所有倉庫位于Zone 2；DC3為所有倉庫位于Zone 3；DR為倉庫隨機(jī)分布。倉庫參數(shù)與實例庫LCLIENT相同。在LVEHICLE實例庫中，倉庫和客戶隨機(jī)分布，共生成15個實例，每個實例由不同車隊服務(wù)，包括L1，L2，L3和多車型，車輛參數(shù)可參閱文獻(xiàn)[5]。

SMSAHH-AA采用MATLAB 2015b并行編程，計算機(jī)環(huán)境為Intel(R)Core(TM)CPU i7-6700K@4.00GHz, 8 GB RAM, Windows 10。終止條件為算子的最大使用次數(shù)Tmax=min(10×(M+N+K)2,104)；每次獨(dú)立運(yùn)行(20次)的個體為初始種群中的隨機(jī)個體(Npop=10)；滑動窗口大小W=4；性能分配比例為r1～U(0.4,0.6)，r2=0.5(1-r1)，r3=0.3(1-r1)，r4=0.2(1-r1)；權(quán)衡因子C=0.5[54]；接收控制參數(shù)ψ=2。

4.1 驗證模型的正確性和算法求解的準(zhǔn)確性

為了驗證所提模型的正確性與算法求解的準(zhǔn)確性，采用小規(guī)模實例進(jìn)行初步實驗。本節(jié)對SMSAHH-AA和CPLEX取得的最優(yōu)解(1次獨(dú)立運(yùn)行)進(jìn)行比較，結(jié)果如表3所示。其中：第1列的實例名稱為LN×M-No.，N與M分別表示客戶數(shù)和倉庫數(shù)，No.表示相同規(guī)模下的序號；TC為總成本，Gap為兩個TC之間的百分比差距，SD為5次獨(dú)立運(yùn)行總成本的標(biāo)準(zhǔn)差，MT為5次獨(dú)立運(yùn)行的平均運(yùn)行時間。結(jié)果表明，所提算法能夠在合理的計算時間內(nèi)求得最優(yōu)解，因此本文所提模型正確，而且算法求得最優(yōu)解的準(zhǔn)確性較高。然而，小規(guī)模實例并不能判斷本文算法的高效性，實驗2采用適用于CLRP和CLRPSPD的Barreto標(biāo)準(zhǔn)實例來檢驗SMSAHH-AA的高效性。

表3 小規(guī)模實例結(jié)果

續(xù)表3

4.2 SSACM-AA高效性分析

為了驗證SSACM-AA的高效性，采用SMSAHH-AA求解CLRP/CLRPSPD標(biāo)準(zhǔn)算例，實驗結(jié)果如表4所示。其中：BKS為已知最好解；BF，MF，SD，MT分別為求得的最好解、平均解、標(biāo)準(zhǔn)差和平均運(yùn)行時間；Gap表示BF和BKS的百分比差距；黑體字表示數(shù)字等于BKS，黑斜體表示新的最好解。本節(jié)設(shè)置Tmax=min(5×(M+N+K)2,80 000)。

從表4可知，SSACM-AA獲得了所有CLRP算例的最優(yōu)解和11個CLRPSPD算例的最優(yōu)解(占所有測試問題的84.38%)，僅未獲得CLRPSPD中D88×8和C100×10的最優(yōu)解，同時獲得了3個新的最好解，最大改進(jìn)率為6.6‰，足以驗證所提算法求解LRP/LRPSPD的有效性，可以推斷本文的SMSAHH-AA能實時準(zhǔn)確地監(jiān)控底層算子的性能信息并選擇合適的底層算子，從而驗證了算法的高效性。

表4 求解Barreto算例CLRP和CLRPSPD的結(jié)果

續(xù)表4

4.3 模型的有效性分析

(1)客戶分布對成本與碳排放的影響

表5所示為SMSAHH-AA采用LCLIENT算例的計算結(jié)果，其中：TC為物流成本，包括車輛與倉庫固定租賃成本和燃油成本；CD為啟用的倉庫費(fèi)用；CV為車輛費(fèi)用；FF為燃油費(fèi)用；FL為燃油量；CE為碳排放量；Dist.為車輛行駛距離；TT為車輛行駛時間；MT為算法的運(yùn)行時間。

表5 LCLIENT算例結(jié)果

由表5可知，相比于Zone1和Zone2，客戶分布方式為CR與CC3有利于減少物流成本，其中CC1相對于CR和CC3類可減少3.1%TC，CC2相對于CR和CC3類減少2.4%TC。同一規(guī)模的實例中，客戶的其他數(shù)據(jù)完全相同，包括取貨量和送貨量，因此除了100CR和100CC3，其他實例的車輛費(fèi)用幾乎相同。類似地，燃油費(fèi)用、燃油量和碳排放量與客戶分布密切相關(guān)，相比于CC1和CC2，客戶坐落于CC3能有效降低燃油費(fèi)用、燃油量和碳排放量，其中CC1相對CR和CC3可平均減少22%碳排放量，CC2相對CR和CC3可平均減少16%碳排放量，但100CC2所得碳排放量卻分別大于100CR和100CC3的0.2%和9%的碳排放量，究其原因為車隊構(gòu)成和行駛速度對物流成本和碳排放有一定影響，Dist.的情況與此類似。車輛行駛時間與客戶分布關(guān)系不明顯，但從平均TT大小可知CC2和CC3算例均小于CR和CC1，原因是Zone 2和Zone 3的車輛可以較高速度行駛。以上9種數(shù)據(jù)均表明9種決策變量隨客戶數(shù)量的增加而增加。

圖5的目的為分析各費(fèi)用在物流成本中所占比例，其中ICD(%)為倉庫費(fèi)用比重，ICV(%)為車輛費(fèi)用比重，IFF(%)為燃油費(fèi)用比重。由圖可知ICD隨N的增大而減小，ICV隨N的增大而增大，且逐漸增大至80%以上，然而IFF受客戶數(shù)量的影響不明顯，平均約為11%。圖5a和圖5b表明在相同客戶數(shù)量下，ICD和ICV在CC1和CC2下比在CR和CC3下略大；ICD隨客戶分布的變化很小，可忽略不計，ICV在CR和CC3下約降低了1.67%和1.59%。由圖5c可知，當(dāng)N<100時，CR和CC3下的IFF大于CC1和CC2的IFF；當(dāng)N=100時，CC2下的IFF大于CR和CC3下的IFF。

為了驗證所提模型的有效性，采用SMSAHH-AA對MTC-2，MCE，MTD和MTT模型求解，對比結(jié)果如表6所示，其中ΔTC，ΔCE，ΔDist.，ΔTT分別為物流成本、碳排放量、行駛距離和行駛時間的變化量。相對于MTC-2模型，所提模型能夠有效降低3‰的物流成本和1.68%的碳排放量；相對于MTC，所提模型可降低43%的碳排放量，但增加了156%的物流成本；相比于MTD模型，所提模型能夠有效減少99.46%的物流成本，但會增加碳排放、運(yùn)輸距離和運(yùn)輸時間；相比于MTT，所提模型可有效減少88.75%的物流成本，但同樣會增加碳排放、運(yùn)輸距離和運(yùn)輸時間。因此，忽略倉庫和車輛固定費(fèi)用的模型(MCE，MTD，MTT)會獲得較低的碳排放量、車輛行駛距離和行駛時間，但會增加物流成本(如果無法忽略倉庫和車輛固定費(fèi)用)，相比于模型MTC-2，所提模型能有效減少物流成本和碳排放量。綜上所述，所提模型既能提高物流企業(yè)的經(jīng)濟(jì)效益，又可實現(xiàn)可持續(xù)發(fā)展，驗證了模型的有效性。

表6 4種模型與MTC的對比

續(xù)表6

(2)倉庫分布對成本與碳排放的影響

表7所示為求解LDEPOT算例的結(jié)果。可知，DR和DC3下的物流成本總小于DC1和DC2，DR相比DC1和DC2分別降低了17%和9%的物流成本，但分別增加了2%和7%的碳排放量與3%和6%的車輛行駛距離，DC3相比DC1和DC2分別降低了18%和10%的物流成本、9%和5%的碳排放量以及7%和5%的車輛行駛距離，說明位于Zone 3的倉庫不僅有利于降低物流成本，還有利于降低CO2排放量和運(yùn)行距離，因此在選擇或建立倉庫時，Zone 3既有利于近期利益(郊區(qū)地皮價格較低)，又有利于長期利益(降低物流成本和碳排放量)，屬于最優(yōu)選擇。

表7 LDEPOT算例結(jié)果

圖6所示為TC，CE，Dist.，TT與倉庫的分布關(guān)系，可知DC3更有利于降低物流成本、碳排放量和車輛行駛距離，DR在降低物流成本上僅次于RC3，但是在碳排放量、行駛距離和時間方面比其他3類要高，車輛行駛時間幾乎不受倉庫分布的影響。

圖7所示為ICD，ICV，IFF隨N和倉庫分布(DR→DC1→DC2→DC3)變化的趨勢圖。由圖可知倉庫費(fèi)用占比隨N的增大而減小，但呈現(xiàn)放緩趨勢；車輛費(fèi)用比重隨N的增大而增大，且逐漸增大至80%以上，但同樣呈現(xiàn)放緩趨勢；油耗費(fèi)用占比與N的關(guān)系不明顯。倉庫分布對ICD，ICV，IFF影響巨大，圖7a表明DC2和DC1的ICD大于DR與DC2的ICD，原因是倉庫費(fèi)用不同；圖7b表明ICV也與倉庫坐落位置相關(guān)，越靠近Zone 1的ICV越小，DR和DC3的ICV最大；圖7c表明DC3下的IFF最大，其次為DR(在N=75時反而最小)，DC1下的IFF最小。以上現(xiàn)象表明，倉庫因坐落位置不同而導(dǎo)致費(fèi)用不同時，對ICD，ICV，IFF產(chǎn)生的影響較大。

為了驗證模型在該算例庫上的有效性，采用SMSAHH-AA求解MTC-2，MCE，MTD，MTT模型，對比結(jié)果如表8所示。相對于MTC-2模型，所提模型能有效降低2.5‰的物流成本和1.16%的碳排放量；MCE模型為最小化碳排放量，相對于MTC可降低30.66%的碳排放量，但增加了151.697%的物流成本；MTD模型有利于降低ΔCE，ΔDist.，ΔTT，但增加了71.03%的物流成本；MTT模型有利于降低26.15%的車輛行駛時間，但增加了71.8%的物流成本。同上所述，忽略倉庫和車輛固定費(fèi)用的模型(MCE，MTD，MTT)往往會獲得較低的碳排放量、行駛距離和時間，但會增加物流成本(如果無法忽略倉庫和車輛固定費(fèi)用)，相比于模型MTC-2，所提模型能有效減少物流成本與碳排放量。

表8 4種模型與MTC的對比

續(xù)表8

(3)車隊構(gòu)成對成本與碳排放的影響

在LVEHICLE數(shù)據(jù)庫中，共有12個算例，客戶數(shù)N∈{25,50,75,100}。每個實例有4種變形，表現(xiàn)為不同的車隊構(gòu)成，包括L1，L2，L3，HF(多車型)。表9所示為計算結(jié)果，其中LR為平均滿載率(%)。表10所示為使用HF求解結(jié)果的變化量，其中ΔX為相對HF的X值的百分比差距(%)。

表9 不同車型構(gòu)成的算例結(jié)果

續(xù)表9

表10 與多車型實例數(shù)據(jù)的對比結(jié)果

從表9可知，相對于單獨(dú)使用L1，L2，M，使用HF的實例的總成本平均降低85.83%，27.20%，3.60%，中位值分別為93.12%，30.09%，3.41%，均值與中位值相差不大；相對L1，L2，使用HF的實例可平均減少111.67%，28.68%的車輛行駛距離，但相對于單獨(dú)使用M類車輛增加了3.62%的車輛行駛距離；相對于單獨(dú)使用L1，使用HF的實例平均減少0.34%的碳排放量；相對于單獨(dú)使用L2與L3，使用HF的實例分別增加了1%和0.25%的碳排放量。從滿載率而言，使用HF的實例的LR和中位值分別以95.23%和95.6%位于第一，驗證了文獻(xiàn)[15]關(guān)于多車型在提高車輛容量利用率方面的結(jié)論。然而，由于本文將車輛的油耗量折算為車輛路徑成本加上車輛和配送中心的固定租賃成本，從而相比于單一車輛，使用HF的路徑安排并不能在所有算例上減少碳排放量(如L2和M求解的CE和ΔCE)，然而采用HF的統(tǒng)籌規(guī)劃(選址和路徑優(yōu)化)比單一車型可以進(jìn)一步降低物流成本，更符合實際配送的要求。

圖8所示為采用HF時各類車輛使用次數(shù)的餅狀圖?？梢?，雖然L1相對M更能節(jié)能減排(如圖1)，但是所有實例并未采用L1(占比為0%)，而將M作為RLCLRPSPDHF模型最常用的車型(占比為77.05%)，比使用L2車型的數(shù)量多(L2占比為22.95%)，原因是車輛的容量、自重及費(fèi)用對車型選擇的影響。另外，由MT值可見車輛容量對算法運(yùn)行時間的影響，即隨著車輛容量的增加，算法的計算時間呈多項式增加，如圖9所示，該結(jié)論尚未在任何文獻(xiàn)中提及。

根據(jù)以上分析，可從算法層面得出以下結(jié)論：①所提算法求解小規(guī)模實例的準(zhǔn)確性高；②SMSAHH-AA能夠在合理的計算時間內(nèi)求得優(yōu)質(zhì)解，具有有效性和魯棒性；③算法的時間性能與車輛容量正相關(guān)，即車輛容量越大，運(yùn)行時間越長。從RLCLRPSPDHF問題領(lǐng)域?qū)用婵芍孩倏蛻艏性赯one 1和Zone 2有利于減少物流成本和碳排放量，原因可能是Zone 3地理跨度大，而且VZone3～U(60 80)相比于VZone2～U(40,60)和VZone1～U(20,40)偏離vbest=(khNhVh/2βhγ)1/3(約在41 km/h)更嚴(yán)重；②由于位于Zone 1和Zone 2的倉庫租賃成本高，DC3更有利于降低物流成本、碳排放量和車輛行駛距離，DR在降低物流成本方面僅次于RC3，在碳排放量、行駛距離和時間方面相比其他3類高；③采用多車型統(tǒng)籌規(guī)劃比單一車型統(tǒng)籌規(guī)劃更能降低總成本和提高車輛容量利用率，但無法保證能夠降低碳排放量和車輛行駛距離；④總成本、能耗和碳排放量與服務(wù)距離和時間存在較高的相關(guān)性，降低成本、節(jié)約能耗和降低碳排放會在一定程度上增加服務(wù)距離與行駛時間；⑤RLCLRPSPDHF模型的統(tǒng)籌規(guī)劃比多車型MTC-2統(tǒng)籌規(guī)劃能更多地降低物流成本和碳排放量，但會增加服務(wù)距離和行駛時間，相比于其他3類，MTC能最大地降低物流成本，但會略微增加碳排放量、服務(wù)距離和行駛時間。因此，以上結(jié)論可在廣大物流企業(yè)(尤其第三方物流)提高經(jīng)濟(jì)效益和低碳環(huán)保的形勢下，為政府部門制定節(jié)能減排政策提供參考和借鑒。

5 結(jié)束語

同時考慮多車型、取送貨和速度限制等實際約束對碳排放影響的LCLRP研究對物流企業(yè)降低物流成本、保護(hù)生態(tài)環(huán)境具有重要的現(xiàn)實和理論意義，對可持續(xù)發(fā)展和節(jié)能減排的政策具有重要的支撐作用。本文將以上影響碳排放的因素考慮到LCLRP中，構(gòu)建了三維指數(shù)混合規(guī)劃模型。由于該模型為NP-hard問題，設(shè)計了基于共享機(jī)制的自適應(yīng)超啟發(fā)式求解算法，即將上一次迭代底層算子的性能條件共享至滑動窗口內(nèi)其他底層算子，認(rèn)為個體改進(jìn)是滑動窗口內(nèi)其余算子共同優(yōu)化的結(jié)果；在底層黑箱的作用下，由于無法得知算子的特性和種類，通過全局性能表現(xiàn)將其分為精英算子和劣質(zhì)算子，各司其職；利用上次擾動時的最優(yōu)解與當(dāng)前最優(yōu)解之間的改進(jìn)率表征劣質(zhì)算子的性能；利用算法底層算子的當(dāng)前階段性能指數(shù)，即無法改進(jìn)當(dāng)前解的次數(shù)(TQ)自適應(yīng)選擇精英算子和劣質(zhì)算子，充分利用兩類算子的特性；采用FRR-MAB信用值分配策略選擇準(zhǔn)確合適的算子。最后通過3組實驗充分論證了本文方法的有效性。

由于優(yōu)化物流總成本并不意味著減少服務(wù)距離和碳排放，下一步側(cè)重于設(shè)計多目標(biāo)超啟發(fā)式算法求解Pareto解集以供決策者選擇。另外，所提模型考慮了物流的經(jīng)濟(jì)效益和環(huán)境效益，尚未涉及客戶對物流配送的滿意度，因此下一步可在速度區(qū)域化假設(shè)的基礎(chǔ)上考慮客戶時間窗要求。