基于時空距離聚類的冷鏈物流路徑優化研究

張建同，經 科 （同濟大學 經濟與管理學院，上海 200092）

0 引 言

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

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

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

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

1 問題描述及數學模型

1.1 問題描述

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

1.2 相關變量及參數

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

表1 相關參數及變量

1.3 數學模型

構建出相關的冷鏈配送路徑優化模型如下：

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

1.4 時空距離度量

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

（1） 若LT'j

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

（3） 若ETj≤ET'j

2 算法設計

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

2.1 客戶點聚類與初始解構造

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

圖1 改進CW 算法流程圖

2.2 改進模擬退火算法的設計

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

圖2 改進模擬退火算法流程圖

2.3 鄰域結構設計

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

圖3 Cross_Exchange 和iCross_Exchange 示意圖

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

表2 鄰域結構集合

3 算例測試

3.1 測試算例

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

3.2 參數設定

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

3.3 算法有效性檢驗

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

表4 三種算法求解得到的平均值及標準差

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

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

表5 RC101 的最優解

4 結 論

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

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