0 引言

冷藏冷凍產(chǎn)品通常具有易腐性、時(shí)效性、損耗大等特點(diǎn)，使得冷鏈運(yùn)輸與常溫運(yùn)輸相比，具有更大的資金投入和成本耗費(fèi)，其中，配送路徑的選擇、客戶(hù)對(duì)產(chǎn)品損耗的要求、制冷溫度等因素都會(huì)令配送方案發(fā)生改變。除此之外，由于冷藏車(chē)在運(yùn)輸過(guò)程中產(chǎn)生的二氧化碳量遠(yuǎn)高于常溫運(yùn)輸，考慮到有關(guān)限碳政策和綠色物流理念，企業(yè)在安排產(chǎn)品配送時(shí)也需考慮冷藏車(chē)產(chǎn)生的碳排放影響。因此，對(duì)于冷鏈配送問(wèn)題的研究具有廣泛的應(yīng)用意義。本文涉及到考慮多配送中心的冷鏈物流優(yōu)化問(wèn)題，將從冷鏈物流配送問(wèn)題和具有多配送中心的車(chē)輛路徑優(yōu)化問(wèn)題這兩個(gè)部分展開(kāi)文獻(xiàn)綜述。

Chen等[1]考慮了交通擁堵、碳排放和碳稅關(guān)系的影響，假設(shè)四種不同的交通情況采用模擬退火回火算法進(jìn)行路徑最優(yōu)化測(cè)試。王旭坪等[2]考慮時(shí)空距離度量的冷鏈配送，先采用K-means聚類(lèi)構(gòu)造初始路徑，然后采用改進(jìn)的模擬退火算法進(jìn)行優(yōu)化。Zhang等[3]建立了冷鏈低碳物流路徑優(yōu)化模型，結(jié)合RNA計(jì)算和基本蟻群優(yōu)化算法的優(yōu)點(diǎn)，引入蟻群算法的迭代過(guò)程、RNA計(jì)算中的變換、重組和置換操作來(lái)優(yōu)化初始參數(shù)。Leng等[4]提出一個(gè)基于最小化物流成本和最大化網(wǎng)絡(luò)效率的低碳冷鏈雙目標(biāo)選址路徑模型，使用六種多目標(biāo)進(jìn)化算法，研究了每個(gè)算子的搜索機(jī)制。Al-Theeb等[5]結(jié)合庫(kù)存分配、車(chē)輛路徑以及冷鏈問(wèn)題構(gòu)建出IVRPCSC模型，設(shè)計(jì)了一種三階段算法進(jìn)行求解。

另一個(gè)相關(guān)的問(wèn)題是具有多配送中心的車(chē)輛路徑問(wèn)題（MDVRP）是VRP問(wèn)題的一種變體形式。Allahyari等[6]提出需求可以發(fā)生傳遞覆蓋的MDCTVRP模型，結(jié)合三種啟發(fā)式算法的思想進(jìn)行求解。Sadati等[7]提出了一種變鄰域禁忌搜索算法，在強(qiáng)化階段采用粒度局部搜索機(jī)制，多樣化階段采用禁忌振蕩機(jī)制，并在MDVRP的三類(lèi)變種問(wèn)題上進(jìn)行算法測(cè)試。Fan等[8]針對(duì)時(shí)變路網(wǎng)下的MDVRP問(wèn)題，綜合考慮各方面成本、車(chē)速、載荷以及道路坡度對(duì)燃料消耗的影響，引入時(shí)空距離聚類(lèi)，采用自適應(yīng)領(lǐng)域搜索機(jī)制，提出一種改進(jìn)的混合遺傳算法。Gulczynski等[9]研究需求可拆分的MDVRP問(wèn)題，采用改進(jìn)的CW算法產(chǎn)生初始解，再用一種兩階段啟發(fā)式算法進(jìn)行改進(jìn)，得到MDVRP的最優(yōu)解。

綜上所述，已有大量成果為進(jìn)一步研究具有多配送中心的冷鏈物流問(wèn)題奠定了良好的基礎(chǔ)，但依舊存在一定的研究缺口：（1）已有文獻(xiàn)在研究MDVIRP時(shí)，大多以客戶(hù)間的空間距離為基礎(chǔ)進(jìn)行研究，較少考慮時(shí)間距離對(duì)于路徑安排的影響；（2）已有冷鏈配送文獻(xiàn)大多假設(shè)冷藏車(chē)從單個(gè)配送中心出發(fā)，但實(shí)際中，單個(gè)配送中心通常無(wú)法解決整體配送問(wèn)題。鑒于此，本文提出了基于時(shí)空距離聚類(lèi)的多配送中心冷鏈路徑優(yōu)化問(wèn)題，以綜合成本最小化為目標(biāo)，構(gòu)建相應(yīng)的數(shù)學(xué)模型。設(shè)計(jì)了一種兩階段算法求解該問(wèn)題，在第一階段考慮路徑安排的合理性，先基于時(shí)空距離對(duì)配送中心及客戶(hù)點(diǎn)進(jìn)行聚類(lèi)處理并構(gòu)造初始解，第二階段分別對(duì)每個(gè)聚簇的初始解進(jìn)行優(yōu)化，并對(duì)算法可行性進(jìn)行分析。

1 問(wèn)題描述及數(shù)學(xué)模型

1.1 問(wèn)題描述

研究的問(wèn)題可以描述為：企業(yè)的多個(gè)配送中心向特定客戶(hù)點(diǎn)配送產(chǎn)品，運(yùn)輸工具為具有制冷設(shè)備的冷藏車(chē)，每個(gè)客戶(hù)點(diǎn)的需求、地理位置以及配送時(shí)間窗、冷藏車(chē)的裝載量均已知，完成服務(wù)后車(chē)輛從客戶(hù)點(diǎn)返回原配送中心。在此基礎(chǔ)上提出以下假設(shè)：（1）每個(gè)客戶(hù)點(diǎn)只能由一輛車(chē)服務(wù)，僅能被服務(wù)一次，且需求固定；（2）每輛車(chē)從某個(gè)配送中心出發(fā)必須返回原配送中心；（3）車(chē)輛行駛速度相同且固定不變；（4）每條配送路徑上的客戶(hù)需求量之和不能超過(guò)車(chē)輛最大裝載量；（5）車(chē)輛必須在指定時(shí)間窗內(nèi)到達(dá)，早到晚到都需要承擔(dān)懲罰。

1.2 相關(guān)變量及參數(shù)

使用有向圖G=

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

構(gòu)建出相關(guān)的冷鏈配送路徑優(yōu)化模型如下：

其中：式（1）表示目標(biāo)函數(shù)，目標(biāo)是使配送總成本最小化。式（2）表示車(chē)輛裝載量約束，即每條配送路徑上的客戶(hù)需求量之和不能超過(guò)車(chē)輛最大裝載量。式（3）表示每個(gè)客戶(hù)點(diǎn)只能由一個(gè)配送中心服務(wù)，且僅被服務(wù)一次。式（4）表示每輛車(chē)只能被使用一次。式（5）表示車(chē)輛進(jìn)出平衡約束，到達(dá)某個(gè)客戶(hù)點(diǎn)必須從該客戶(hù)點(diǎn)離開(kāi)。式（6）表示車(chē)輛出發(fā)和返回的節(jié)點(diǎn)都是同一個(gè)配送中心。式（7）表示產(chǎn)品新鮮度約束，實(shí)時(shí)新鮮度不得低于最低新鮮度。式（8）表示前一個(gè)節(jié)點(diǎn)和后繼節(jié)點(diǎn)之間的時(shí)間關(guān)系，M為一個(gè)足夠大的常數(shù)。式（9）至式（11）為決策變量的取值。C1為使用車(chē)輛的固定成本，C2為運(yùn)輸和卸貨過(guò)程產(chǎn)生的制冷成本，C3為時(shí)間窗懲罰成本，C4為運(yùn)輸過(guò)程中的燃油消耗成本，其中燃油消耗率ρm采用負(fù)載估計(jì)法[10]計(jì)算可得，C5和C6分別為運(yùn)輸和卸貨過(guò)程產(chǎn)生的貨損成本以及碳排放成本[11]。

1.4 時(shí)空距離度量

在VRP問(wèn)題中，通常只用歐式距離來(lái)衡量遠(yuǎn)近。但實(shí)際上，時(shí)間也是衡量可行性的標(biāo)志之一，將地理位置相近但時(shí)間窗相差很大的客戶(hù)點(diǎn)放在同一路徑中，雖然路徑運(yùn)輸成本較小但會(huì)產(chǎn)生較大的時(shí)間窗懲罰成本。若只考慮時(shí)間窗限制，將地理位置相距甚遠(yuǎn)的客戶(hù)點(diǎn)放在同一路徑中則會(huì)造成較大的路徑運(yùn)輸成本，因此對(duì)兩者綜合考慮。由于兩者屬性量綱不一致，先對(duì)兩者進(jìn)行歸一化處理后進(jìn)行加權(quán)平均，根據(jù)參考文獻(xiàn)[12]的時(shí)空距離計(jì)算公式為：

兩點(diǎn)間空間距離為歐式距離。兩個(gè)客戶(hù)點(diǎn)間的時(shí)間距離通過(guò)時(shí)間窗被滿(mǎn)足的程度來(lái)描述，根據(jù)參考文獻(xiàn)[2]，客戶(hù)點(diǎn)i,j的時(shí)間窗分別為[ETi,LTi]和[ETj,LTj]，假設(shè)ETi≤ETj，若車(chē)輛在規(guī)定時(shí)間窗內(nèi)達(dá)到i點(diǎn)，即ATi∈[ETi,LTi]，則到達(dá)j點(diǎn)的時(shí)間為ATj∈[ETi+si+Tij,LTi+si+Tij]，記ETj'=ETi+si+Tij,LTj'=LTi+si+Tij，時(shí)間距離分為以下三種情況：

(1）若LTj'

(2）若ETj'>LTj，即冷藏車(chē)在客戶(hù)點(diǎn)j的最晚開(kāi)始服務(wù)時(shí)間后到達(dá)，令其遲到的懲罰系數(shù)為τ2，時(shí)間距離τ2(ETj'-LTj)。

(3）若ETj≤ETj'

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

本文研究的本質(zhì)問(wèn)題為車(chē)輛路徑問(wèn)題，是NP-Hard問(wèn)題，求解此類(lèi)問(wèn)題的主要方法為啟發(fā)式算法和精確算法。本文設(shè)計(jì)了一種兩階段啟發(fā)式算法，基本思想為：在第一階段計(jì)算各點(diǎn)之間的時(shí)空距離，并基于時(shí)空距離采用k中心點(diǎn)算法對(duì)各客戶(hù)點(diǎn)進(jìn)行聚類(lèi)，形成不同的聚簇；第二階段，先用一個(gè)小型啟發(fā)式算法即改進(jìn)的CW算法構(gòu)造初始解，隨后采用引入了變鄰域搜索思想的模擬退火算法對(duì)初始路徑進(jìn)行優(yōu)化，以提高算法的全局搜索能力。

2.1 客戶(hù)點(diǎn)聚類(lèi)與初始解構(gòu)造

考慮到K-means聚類(lèi)算法受極端值影響較大，且算法選擇最開(kāi)始的質(zhì)心時(shí)具有很大的隨機(jī)性，因此采用k中心點(diǎn)算法對(duì)客戶(hù)進(jìn)行聚類(lèi)，并采用改進(jìn)的CW算法進(jìn)行初始解構(gòu)造，算法流程如圖1所示。

2.2 改進(jìn)模擬退火算法的設(shè)計(jì)

模擬退火算法（SA）的核心思想是以一定的概率接受使目標(biāo)函數(shù)上升的解，從而使溫度下降，不斷進(jìn)行重復(fù)搜索，直到滿(mǎn)足終止準(zhǔn)則。本文借鑒文獻(xiàn)[13]的改進(jìn)模擬退火算法，引入變鄰域搜索的思想，在隨機(jī)搜索的過(guò)程中，改變鄰域結(jié)構(gòu)，拓展搜索范圍，從而提升算法全局搜索能力。算法流程如圖2所示：

2.3 鄰域結(jié)構(gòu)設(shè)計(jì)

本文算法在設(shè)計(jì)可用于搜索的鄰域結(jié)構(gòu)時(shí)，采用了兩種交換算子，分別是Cross＿Exchange[14]和i Cross＿Exchange[15]。Cross＿Exchange算子是指隨機(jī)選取兩條路徑，分別從中抽取一部分子路徑后進(jìn)行交換。i Cross＿Exchange算子是指在進(jìn)行交換的過(guò)程中，將抽取出來(lái)的子路徑反向逆序插入，具體如圖3所示。鄰域結(jié)構(gòu)以不同概率選取兩種算子，選取Cross＿Exchange算子的概率為p，選取i Cross＿Exchange算子為1-p。

多配送中心問(wèn)題中進(jìn)行交換的路徑以及相應(yīng)的子路徑可以在一個(gè)配送中心所涉及的路徑中選擇，也可以在不同配送中心的路徑中選擇。本文借鑒文獻(xiàn)[16]定義的鄰域結(jié)構(gòu)集合，如表2所示。該集合由12個(gè)鄰域結(jié)構(gòu)組成，每個(gè)鄰域結(jié)構(gòu)都有各自對(duì)應(yīng)的配送中心數(shù)量以及子路徑最大長(zhǎng)度，其中Cr表示路徑r中的客戶(hù)數(shù)量。

3 算例測(cè)試

3.1 測(cè)試算例

本文采用Solomon Benchmark測(cè)試集中混合隨機(jī)聚類(lèi)分布的客戶(hù)點(diǎn)算例，即RC101、RC102、RC201、RC202的前25、50、100個(gè)客戶(hù)點(diǎn)算例，并自主設(shè)定四個(gè)配送中心數(shù)據(jù)對(duì)算例改造后，在Matlab＿R2018a上進(jìn)行算法測(cè)試。增加的配送中心坐標(biāo)分別設(shè)定為(15,10),(25,25),(45,40),(65,60)。

3.2 參數(shù)設(shè)定

設(shè)定車(chē)輛使用成本Ck=200元，最大裝載量Q=200kg，單位路徑成本S=20元，Pet=10元，Plt=15元，制冷成本分別為a=7元，b=10元，每單位燃油價(jià)格P0=5元，新鮮度衰減系數(shù)分別為δ1=0.005,δ2=0.01，每單位碳排放成本Ce=2元，碳排放系數(shù)β=0.08，空載時(shí)燃油消耗率ρ0=0.1，生鮮產(chǎn)品單位價(jià)值P=5元/kg，最低新鮮度θ=0.6。改進(jìn)模擬退火算法的參數(shù)分別為內(nèi)循環(huán)迭代次數(shù)iter=300，降溫系數(shù)r=0.98，初始溫度T0=5 000。

3.3 算法有效性檢驗(yàn)

本文通過(guò)將考慮時(shí)空路徑的改進(jìn)SA算法（ST-CWSA）與只考慮空間路徑的CWSA算法、考慮時(shí)空路徑的傳統(tǒng)SA算法（ST-SA）進(jìn)行比較來(lái)驗(yàn)證算法的有效性，算法參數(shù)設(shè)置與ST-CWSA的參數(shù)設(shè)置相同。本文將三種算法分別對(duì)上述16組算例進(jìn)行10輪求解后取平均值，表3展示了三種算法各自最優(yōu)值，表4展示了三種算法分別對(duì)算例求解后的結(jié)果及各自標(biāo)準(zhǔn)差。

通過(guò)表3和表4的結(jié)果可知，隨著樣本算例規(guī)模的增大，三種算法下的標(biāo)準(zhǔn)差隨之增大。同時(shí)，ST-CWSA算法相對(duì)于其他兩種算法的成本優(yōu)化率呈現(xiàn)出先增大后減小的趨勢(shì)，在算例規(guī)模為100時(shí)優(yōu)化率最高，隨后開(kāi)始減小。與只考慮空間路徑的CWSA算法與ST-SA算法相比，ST-CWSA算法的最優(yōu)值與平均值都相對(duì)較小。

ST-CWSA求解RC101，其最優(yōu)解如表5所示，總配送成本為2 645 679.91，所需車(chē)輛數(shù)為15。

4 結(jié)論

本文綜合冷鏈物流以及多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題，同時(shí)考慮客戶(hù)時(shí)間窗限制以及位置的影響，以最小化多成本之和為目標(biāo)函數(shù)，構(gòu)建基于時(shí)空距離聚類(lèi)的冷鏈路徑優(yōu)化數(shù)學(xué)模型，設(shè)計(jì)了一種兩階段啟發(fā)式算法進(jìn)行求解。通過(guò)算例測(cè)試可知，考慮時(shí)空距離后，算法求得的平均值與最優(yōu)值都比只考慮空間距離有一定程度的提升。除此之外，改進(jìn)的模擬退火算法在引入變鄰域搜索算法的思想后，與傳統(tǒng)模擬退火算法相比，其性能也有所提高。

本文所設(shè)定的情況基于配送中心之間無(wú)資源共享、配送過(guò)程中無(wú)路況變化以及客戶(hù)點(diǎn)需求固定。為了使問(wèn)題更加具有實(shí)際意義，還可以考慮設(shè)定為開(kāi)放式車(chē)場(chǎng)即車(chē)輛配送完成不返回原始配送中心，且配送過(guò)程中考慮實(shí)時(shí)路況及車(chē)速的影響等情況。