基于時空相似測度的冷鏈物流分區(qū)配送路徑優(yōu)化

盧甲東，張世斌,b

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

0 引 言

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

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

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

1 冷鏈物流分區(qū)配送路徑優(yōu)化模型

1.1 問題描述和基本假設

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

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

1.2 數(shù)學模型

1.2.1 模型常量和變量

常量：N為客戶位置集合；L為客戶位置分類集合，K為配送車輛集合，|L|=|K|，其中|L|與|K|分別代表集合|L|和|K|中元素的個數(shù)；Q為配送車輛的載質(zhì)量；C1為單位運費；C2為早于客戶最佳配送時間窗配送的懲罰系數(shù)，即早到的單位損失成本；C3為晚于客戶最佳配送時間窗配送的懲罰系數(shù)，即晚到的單位損失成本；m為單位貨損成本；a1為運輸過程中的貨損比例；a2為裝卸過程中的貨損比例；qj為位置j的卸貨量；[T1j,T2j]為客戶j所要求的最佳配送時間窗；Tok為車輛k出發(fā)的時刻(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 基于時空相似度的客戶分區(qū)

(1)

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

1.2.3 分區(qū)配送路徑優(yōu)化模型

以冷鏈配送成本最小為目標構(gòu)建的配送模型為

(2)

s.t.

(3)

Tok=to

(4)

(5)

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

(6)

(7)

(8)

(9)

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

2 兩階段優(yōu)化求解分區(qū)配送問題

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

圖1 傳統(tǒng)固定分區(qū)圖例

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

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

3 算例驗證及分析

3.1 算例信息

假設某配送中心有5輛配送車輛，60個客戶點，配送車輛的車型規(guī)格統(tǒng)一，配送車輛的載質(zhì)量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%。每個客戶的坐標、作業(yè)時間和配送時間窗見表1。

表1 客戶訂單信息

3.2 3種分區(qū)方法的比較

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

a)固定分區(qū)配送

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

表2 基于固定分區(qū)的最優(yōu)配送路徑

表3 基于時空相似測度分區(qū)的最優(yōu)配送路徑

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

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

4 結(jié) 論

針對采用冷鏈物流傳統(tǒng)固定分區(qū)方式的路徑規(guī)劃難以求得全局最優(yōu)解和現(xiàn)有聚類分區(qū)配送僅考慮地理位置相似性對客戶進行分區(qū)等問題，提出基于時空相似測度進行分區(qū)的配送方式。在該分區(qū)方式下，冷鏈車輛對應的配送區(qū)域?qū)⒉辉俟潭ǎ峭瑫r根據(jù)客戶地理位置信息和訂單配送時間窗即時調(diào)整。根據(jù)冷鏈配送的特殊性，以最小配送成本為目標構(gòu)建模型，同時考慮時間懲罰成本和貨損成本，為單配送中心的冷鏈分區(qū)配送提出可行方案。冷鏈企業(yè)在進行冷鏈配送時，需綜合考慮時間和空間因素來優(yōu)化配送路徑，基于時空相似測度進行分區(qū)配送正融合了上述兩個關(guān)鍵因素，在保證時效性的前提下使物流企業(yè)冷鏈配送方案優(yōu)于考慮空間相似性的分區(qū)配送方案。

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