0 引言

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

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

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

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

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

1.1 問題描述

研究的問題可以描述為：企業(yè)的多個配送中心向特定客戶點配送產(chǎn)品，運輸工具為具有制冷設(shè)備的冷藏車，每個客戶點的需求、地理位置以及配送時間窗、冷藏車的裝載量均已知，完成服務(wù)后車輛從客戶點返回原配送中心。在此基礎(chǔ)上提出以下假設(shè)：（1）每個客戶點只能由一輛車服務(wù)，僅能被服務(wù)一次，且需求固定；（2）每輛車從某個配送中心出發(fā)必須返回原配送中心；（3）車輛行駛速度相同且固定不變；（4）每條配送路徑上的客戶需求量之和不能超過車輛最大裝載量；（5）車輛必須在指定時間窗內(nèi)到達，早到晚到都需要承擔(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）表示車輛裝載量約束，即每條配送路徑上的客戶需求量之和不能超過車輛最大裝載量。式（3）表示每個客戶點只能由一個配送中心服務(wù)，且僅被服務(wù)一次。式（4）表示每輛車只能被使用一次。式（5）表示車輛進出平衡約束，到達某個客戶點必須從該客戶點離開。式（6）表示車輛出發(fā)和返回的節(jié)點都是同一個配送中心。式（7）表示產(chǎn)品新鮮度約束，實時新鮮度不得低于最低新鮮度。式（8）表示前一個節(jié)點和后繼節(jié)點之間的時間關(guān)系，M為一個足夠大的常數(shù)。式（9）至式（11）為決策變量的取值。C1為使用車輛的固定成本，C2為運輸和卸貨過程產(chǎn)生的制冷成本，C3為時間窗懲罰成本，C4為運輸過程中的燃油消耗成本，其中燃油消耗率ρm采用負(fù)載估計法[10]計算可得，C5和C6分別為運輸和卸貨過程產(chǎn)生的貨損成本以及碳排放成本[11]。

1.4 時空距離度量

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

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

(1）若LTj'

(2）若ETj'>LTj，即冷藏車在客戶點j的最晚開始服務(wù)時間后到達，令其遲到的懲罰系數(shù)為τ2，時間距離τ2(ETj'-LTj)。

(3）若ETj≤ETj'

2 算法設(shè)計

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

2.1 客戶點聚類與初始解構(gòu)造

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

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

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

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

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

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

3 算例測試

3.1 測試算例

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

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

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

3.3 算法有效性檢驗

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

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

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

4 結(jié)論

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

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