基于時空相似測度的冷鏈物流分區配送路徑優化

盧甲東，張世斌,b

(上海海事大學 a.物流科學與工程研究院; b.文理學院，上海 201306)

0 引 言

隨著我國經濟的快速增長和人民生活水平的穩步提高，人們對生鮮品的需求量越來越大。2017年，冷鏈市場規模已達4 600億元。然而，冷鏈運輸成本的居高不下嚴重制約著冷鏈產業的發展，難以滿足人們消費升級的熱切期望。冷鏈品配送作為冷鏈物流的最后一個環節，配送路徑的合理規劃對降低整個物流運作成本和提高冷鏈品配送質量至關重要。[1]因此，針對冷鏈物流時效性[2]強的特點，提供合理有效的配送方案是冷鏈物流企業亟待解決的問題。

冷鏈物流配送問題主要考慮在一定約束條件下配送路徑的合理優化，其約束條件涉及特定商品、軟硬時間窗、隨機環境和多周期等因素。例如：TARANTILIS等[3]針對希臘的鮮肉配送問題，提出了一種新的隨機搜索元算法；邵舉平等[4]針對生鮮農產品時效問題，建立了生鮮農產品的配送路徑多目標優化模型；CALVETE等[5]基于軟時間窗建立了車輛路徑規劃的多目標優化模型，并采用枚舉法選擇較優的配送方案；王淑云等[6]利用了k-means聚類算法和蟻群算法解決隨機需求下多溫共配的冷鏈品路徑優化問題。由于車輛路徑問題(vehicle routing problem,VRP)為NP難問題，其求解方法多為啟發式算法。TAN等[7]建立了帶時間窗的VRP (VRP with time window,VRPTW)的多目標優化模型，提出了求解模型的混合遺傳算法；DONDO等[8]利用混合整數線性規劃方法對VRP進行了優化；DING等[9]提出一種混合蟻群算法求解VRPTW；KASSEM等[2]采用模擬退火算法和爬山算法求解VRPTW。利用聚類算法對客戶地理位置進行分類，再利用啟發式算法求解是一種新思路。谷煒等[10]在分析了k-means聚類算法的優劣后，設計了一種配送區域劃分方法——改進的兩階段k-means聚類算法；高學東等[11]提出了一種考慮配送路網結構和配送量約束的聚類算法以避免以往不考慮配送道路狀況的研究缺陷；王旭坪等[12-13]采用“聚類-路徑優化”思想，基于客戶地理位置確定配送方案，并以最小化平均有效訂單服務時間為目標函數，構建了考慮訂單完成期限的在線訂單分批混合整數規劃模型。

與傳統的配送方式相比，在冷鏈物流配送前，根據客戶地理位置先進行聚類，再按訂單類別進行分區配送，無疑可以大大節約運輸成本。[6]然而，傳統的k-means聚類[10]是僅基于客戶的地理位置利用空間位置相似性進行的。另外，當配送系統中客戶數目較多且受嚴格的時間窗和車輛數目限制時，用VRPTW優化模型往往無法得到可行配送方案。[4]鑒于此，對于考慮時間窗的冷鏈物流分區配送問題，本文主要對客戶分區方法進行進一步改進。首先，同時考慮客戶地理位置的相鄰性和訂單配送時間窗的相似性，提出了時空相似測度的概念。然后，在最小化配送成本時，基于時空相似測度利用改進的k-means聚類算法對客戶進行分區。最后，利用遺傳算法對分區配送路徑進行優化，并設計算例來驗證基于時空相似測度的客戶分區策略在配送路徑優化方面的優勢。

1 冷鏈物流分區配送路徑優化模型

1.1 問題描述和基本假設

考慮“一對多”配送模式，即一個配送中心服務多個客戶。優化目標是使冷鏈配送成本最小。目前，分區配送主要是借助空間相似測度通過對客戶的地理位置進行聚類實現的。在對客戶進行分區時，本文同時考慮客戶地理位置的相鄰性和訂單配送時間窗的相似性，提出時空相似測度，對客戶進行聚類以實現客戶分區。

假設：(1)配送中心每天有一定數量的訂單需要配送，并且客戶的位置信息已知；(2)每個客戶都有固定的配送時間窗，如果不在該時間窗內配送，就會產生相應的時間懲罰成本；(3)配送中心的每輛車負責一個配送區域，且該區域總配送量不超過車輛的最大載質量，即不考慮回程補貨因素；(4)車輛只負責送貨。

1.2 數學模型

1.2.1 模型常量和變量

常量：N為客戶位置集合；L為客戶位置分類集合，K為配送車輛集合，|L|=|K|，其中|L|與|K|分別代表集合|L|和|K|中元素的個數；Q為配送車輛的載質量；C1為單位運費；C2為早于客戶最佳配送時間窗配送的懲罰系數，即早到的單位損失成本；C3為晚于客戶最佳配送時間窗配送的懲罰系數，即晚到的單位損失成本；m為單位貨損成本；a1為運輸過程中的貨損比例；a2為裝卸過程中的貨損比例；qj為位置j的卸貨量；[T1j,T2j]為客戶j所要求的最佳配送時間窗；Tok為車輛k出發的時刻(o為配送中心位置)；dij為從位置i到位置j的距離；v為配送車輛的平均速度。

變量：Nl為第l類客戶位置集合，l∈L;Nol為包含配送中心位置的分類客戶位置集合，l∈L；xijk為0-1變量，若車輛k從位置i到達位置j則為1，否則為0；Tik為車輛k到達位置i的時刻；Ti為車輛在位置i的工作時間。

1.2.2 基于時空相似度的客戶分區

(1)

式中，θ表示時空成本轉化系數，為單位時間損失成本折算成的運費。在本文中，θ=2C1/(C2+C3)，即把單位運費與不按期(早于或晚于最佳配送時間窗)配送的平均懲罰系數的比值作為將時間在成本等效意義下轉化為距離的比例系數。在對ti用θ修正后，由式(1)定義的時空相似測度的本質是三維空間上的兩點(xi,yi,θti)與(xj,yj,θtj)之間的歐氏距離相似測度。基于時空相似測度，利用k-means聚類算法，即可實現對所有客戶的分區，得到Nl,l∈L。

1.2.3 分區配送路徑優化模型

以冷鏈配送成本最小為目標構建的配送模型為

(2)

s.t.

(3)

Tok=to

(4)

(5)

xijk∈{0,1},i∈Nol,j∈Nl,k∈K

(6)

(7)

(8)

(9)

式(2)為目標函數，表示使配送成本最小，配送成本包括運輸成本、時間懲罰成本和貨損成本,其中x+=max(x,0)。式(3)～(9)為約束條件：式(3)為車輛的實際裝載量不超過車輛的載質量；式(4)給出配送車輛從配送中心出發的時刻(to)；式(5)為配送車輛到達位置j的時刻；式(6)為0-1變量約束；式(7)表示每個客戶訂單只能由一輛車進行配送，不能拆分；式(8)表示車輛完成客戶訂單后必須離開；式(9)表示所有車輛在完成配送任務后都必須回到配送中心。

2 兩階段優化求解分區配送問題

對于單配送中心問題，如果采用傳統固定分區方式將配送區域劃分為幾個獨立區域(見圖1，其中° 為客戶位置)，則只會求得每個分區的最優解，與整個區域內的全局最優解尚有很大差別。采用時空相似測度對配送區域進行分區，然后再對每個分區進行配送路徑優化，這樣比基于空間相似測度進行分區的方法更接近整個配送區域的全局最優解。

圖1 傳統固定分區圖例

在給定分區數目的情況下，k-means聚類算法是最經典的分割式聚類算法。取分區數目與配送車輛|K|相同，隨機選擇|K|個點作為個分區的起始質心，分別計算剩下的客戶位置點與這|K|個點的相似度，將剩下的客戶位置點分別劃歸到相似度最高的分區中。重新計算|K|個分區的質心重復上述過程，直至迭代至聚類結果不再發生變化。本文基于時空相似測度(式(1))，將整個客戶集合N分成|K|個類，以便于下一步對每個客戶群l(l∈L)進行配送路徑優化。

遺傳算法操作步驟如下。(1)編碼。采用自然數編碼，產生與客戶群相同個數的自然數序列作為遺傳算法的染色體。(2)初始化種群。由上一步編碼形成的自然數序列作為遍歷客戶群的一個初始解，產生M個染色體，組成遺傳算法的初始種群。(3)配送中心設置。配送中心設置在整個客戶群分布的中心點位置。(4)適應度函數值計算。根據初始配送路徑，計算適應度函數值。(5)選擇、交叉、變異操作。先用輪盤賭選擇策略進行選擇操作，再隨機選擇2個優秀個體，以0.9的交叉概率進行交叉操作，然后以0.05的變異概率進行變異操作。(6)精英策略。在進化過程中，把每代最優秀的個體保留下來直接進入下一代遺傳操作，以此不破壞父代的優秀個體信息，加快算法的全局收斂速度。(7)迭代。根據給定的遺傳算法迭代次數進行迭代，得到所有的配送區域的最優路徑。

3 算例驗證及分析

3.1 算例信息

假設某配送中心有5輛配送車輛，60個客戶點，配送車輛的車型規格統一，配送車輛的載質量Q=30 t，配送車輛的平均速度v=45 km/h，配送車輛的單位運費C1=7.5元/km。早到的單位損失成本C2=5元/(h·kg)，晚到的單位損失成本C3=10元/(h·kg)，單位貨損成本m=400元/ t。冷鏈配送考慮運輸過程中的貨物損失，運輸過程中的貨損率a1=0.1%，裝卸過程中的貨損率a2=0.2%。每個客戶的坐標、作業時間和配送時間窗見表1。

表1 客戶訂單信息

3.2 3種分區方法的比較

基于傳統固定分區(分區方式見圖1)的最優配送路徑見圖2a，其詳細配送路徑見表2；基于時空相似測度進行分區的最優配送路徑見圖2b，其詳細配送路徑見表3。由圖2可見，基于時空相似測度進行分區優化后，許多客戶訂單所屬的配送區域發生了較大改變，例如，圖2a中屬于同一配送區域的兩個客戶訂單12和5(在點(90 km，50 km)附近)在圖2b中卻屬于不同配送區域。

a)固定分區配送

b)基于時空相似測度的分區配送

表2 基于固定分區的最優配送路徑

表3 基于時空相似測度分區的最優配送路徑

采用3種不同分區方法的配送成本見表4。由表4可見，與傳統分區配送、基于空間相似測度的分區配送相比，基于時空相似測度的分區配送的運輸成本和貨損成本與之相差不大，但時間懲罰成本明顯減少，從而使配送總成本分別降低16%和13%，且按時送達的訂單數也大有改觀。

表4 采用3種不同分區方式的配送成本比較

4 結 論

針對采用冷鏈物流傳統固定分區方式的路徑規劃難以求得全局最優解和現有聚類分區配送僅考慮地理位置相似性對客戶進行分區等問題，提出基于時空相似測度進行分區的配送方式。在該分區方式下，冷鏈車輛對應的配送區域將不再固定，而是同時根據客戶地理位置信息和訂單配送時間窗即時調整。根據冷鏈配送的特殊性，以最小配送成本為目標構建模型，同時考慮時間懲罰成本和貨損成本，為單配送中心的冷鏈分區配送提出可行方案。冷鏈企業在進行冷鏈配送時，需綜合考慮時間和空間因素來優化配送路徑，基于時空相似測度進行分區配送正融合了上述兩個關鍵因素，在保證時效性的前提下使物流企業冷鏈配送方案優于考慮空間相似性的分區配送方案。

本文的配送車輛不考慮回程補貨的情況，所有的配送任務均一次完成。融合現有多配送中心物流配送路徑優化的相關方法，基于時空相似測度進行分區的冷鏈物流配送路徑優化方法可以拓展到多配送中心冷鏈物流的聯合配送優化問題中。例如，將本文中時空相似測度引入到多配送中心物流配送車輛調度問題的分層算法模型[14]中進行分層求解，即利用聚類分析得到的時空距離最近方法劃定每個配送中心服務的客戶群，進而可以將多配送中心問題轉化為多個單配送中心車輛調度問題進行求解；還可以將時空相似測度引入到考慮碳排放的冷鏈物流聯合配送路徑優化[15]目標函數中的運費計量中，以進一步優化冷鏈物流的聯合配送路徑。