張建同，經(jīng) 科 （同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 200092）

0 引 言

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

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

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

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

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

1.1 問題描述

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

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

使用有向圖G=表示整個(gè)冷鏈配送網(wǎng)絡(luò)，其中V= ｛1,2,…,n+m ｝表示配送網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，其中包括客戶點(diǎn)集合N= ｛1,2 ,…,n ｝以及配送中心集合M= ｛n+1,n+2,…,n+m ｝兩部分，E= ｛（i, j ）｜i≠j ｝表示配送路線的弧集，K= ｛1,2 ,…,k ｝表示冷藏車的集合。表1 為相關(guān)變量和參數(shù)及其各自定義。

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

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

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

其中：式（1） 表示目標(biāo)函數(shù)，目標(biāo)是使配送總成本最小化。式（2） 表示車輛裝載量約束，即每條配送路徑上的客戶需求量之和不能超過車輛最大裝載量。式（3） 表示每個(gè)客戶點(diǎn)只能由一個(gè)配送中心服務(wù)，且僅被服務(wù)一次。式（4） 表示每輛車只能被使用一次。式（5） 表示車輛進(jìn)出平衡約束，到達(dá)某個(gè)客戶點(diǎn)必須從該客戶點(diǎn)離開。式（6） 表示車輛出發(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為使用車輛的固定成本，C2為運(yùn)輸和卸貨過程產(chǎn)生的制冷成本，C3為時(shí)間窗懲罰成本，C4為運(yùn)輸過程中的燃油消耗成本，其中燃油消耗率ρm采用負(fù)載估計(jì)法[10]計(jì)算可得，C5和C6分別為運(yùn)輸和卸貨過程產(chǎn)生的貨損成本以及碳排放成本[11]。

1.4 時(shí)空距離度量

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

（1） 若LT'j

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

（3） 若ETj≤ET'j

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

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

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

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

圖1 改進(jìn)CW 算法流程圖

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

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

圖2 改進(jìn)模擬退火算法流程圖

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

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

圖3 Cross_Exchange 和iCross_Exchange 示意圖

多配送中心問題中進(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 中的客戶數(shù)量。

表2 鄰域結(jié)構(gòu)集合

3 算例測(cè)試

3.1 測(cè)試算例

本文采用Solomon Benchmark 測(cè)試集中混合隨機(jī)聚類分布的客戶點(diǎn)算例，即RC101、RC102、RC201、RC202 的前25、50、100 個(gè)客戶點(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è)定車輛使用成本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)

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

表4 三種算法求解得到的平均值及標(biāo)準(zhǔn)差

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

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

表5 RC101 的最優(yōu)解

4 結(jié) 論

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

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