生鮮冷鏈配送區域劃分兩階段模型構建

房慶軍，王 旭

（青島理工大學 管理工程學院，山東 青島 266520）

1 引言

隨著互聯網迅速普及，生鮮品線上需求日益增長，生鮮領域已經成為電商相互爭奪的“最后一片藍海”。但由于生鮮品高時效性、高腐損率等特性，給生鮮電商的物流配送環節帶來巨大挑戰，生鮮品物流配送質量直接影響著生鮮電商運營的成敗。

目前對生鮮冷鏈配送區域劃分的相關研究比較成熟，大多學者主要應用聚類算法解決大規模配送點問題，于曉寒等[1]針對城市內快遞配送問題，提出了基于障礙的約束聚類算法，以“障礙距離”作為差異度度量標準，建立BSP樹簡化距離進行計算；何夢軍等[2]采用改進的吸引子傳播聚類算法對同城物流網點配送區域進行優化。

通過上述文獻綜述發現，目前對配送區域劃分方面的研究缺少對生鮮品特性以及工人任務量的考慮，只有在配送過程中考慮生鮮品特性的影響才能更好地保證其品質不受影響，只有保證工人配送任務量均衡，才能高效完成配送任務，提高用戶體驗。因此，本文在前人研究的基礎上，將配送區域劃分問題分為兩個階段，首先以配送時間最短為前提進行初始區域劃分，在此基礎上加入對配送量均衡的考慮，進行配送區域調整，保證配送效率。

2 問題描述

本文的研究場景是基于生鮮O2O“冷鏈物流+終端自提”配送模式，在這一模式下，生鮮電商與便利店合作，在配送區域內建立自營店、便利店、餐館、小超市、小區自提柜等多種形式的線下體驗店。通過線上下單購買商品的消費者，選擇一個合適的配送地點，接到到貨通知后進行自提；在便利店、自營店進行消費的顧客可以直接選擇自己所需的生鮮商品，同時所在的便利店、自營店會自動被定義為配送點，庫存水平降低到安全庫存，會有冷鏈運輸車輛進行配送補貨。O2O信息平臺會整合所有客戶的訂單信息，由冷鏈運輸車輛對自營店、便利店、餐館、小超市、小區自提柜等終端進行配送，送達自營店、便利店、小區自提柜的生鮮品，會根據顧客要求，等待顧客自提或者由配送員利用電瓶車在規定時間內配送上門。

本文的模型假設如下：（1）配送中心及各個客戶點位置已知，且短時間內不會發生變化；（2）一個客戶訂單配送任務有且只能由一輛車完成；（3）將配送員及冷鏈配送車輛看做一個整體，即一次配送任務由一個配送員配備一輛運輸工具完成；（4）配送的起點是各個配送中心，配送的終點是各個自營店、便利店、餐館、小超市、小區自提柜；（5）每個配送中心的輻射范圍相互不重合，一個客戶點只能被一個配送中心服務；（6）每輛車在任何時刻裝載的生鮮品不能超過最大載重量。

3 “區域劃分+區域調整”兩階段模型構建

3.1 目標函數及約束條件

目標函數：

所有配送車輛遍歷完所有配送點完成所有配送任務的最少時間：

約束條件：

（1）保證每個配送點都有一個配送車輛進行服務：

（2）保證每輛配送車輛到達和離開的配送點數量相等：

（3）保證每輛車輛的載貨量不得超過最大承載量：

（4）車輛從配送中心出發的時刻為0：

（5）保證每個訂單一定有配送車輛服務：

（6）配送車輛的路徑是由配送點i到達配送點j:

（7）配送車輛從配送點i 到達配送點j 的時間迭代關系：

（8）配送車輛是否經過路徑，是否經過配送節點，訂單對配送時間是否有要求限制：

3.2 第一階段初始區域劃分模型

3.2.1 確定初始k值

其中，R 表示在一個配送周期中的生鮮配送總量；Q表示每輛生鮮冷鏈運輸車的最大載貨量。

3.2.2 確定初始聚類中心。選擇合適的初始點可以使算法收斂更快，因此本文選用均分選擇法來確定初始點，其主要思想是：若需要初始點的個數k=p·q，則將整個配送區域地圖劃分成p 行q 列，每個區域的正中心附近的節點可選擇為初始節點，這樣選擇的節點更趨于均勻，有利于聚類收斂，且不會出現明顯的分布不均勻的起始狀態。

3.2.3 收斂性檢驗。K-means 聚類算法要求計算每個新聚類得到的聚類中心，不斷重復這一過程直到符合收斂條件。對上述運算得到的k 個聚類中心進行檢驗，若已經達到收斂條件，則下轉進行第二階段的聚類調整；否則根據重心法重新計算聚類中心，再次聚類，反復迭代，直到算法達到收斂條件為止。

3.3 第二階段劃分區域調整模型

3.3.1 均衡指標計算。均衡載貨量指標Wi的現實意義是實現各個劃分區域內的配送量達到均衡。Wj表示第j個聚類的Warea值。從計算得到的k個W中，找出最大值Wmax和最小值Wmin，調整的目的是為了讓各個區域內的載貨量均衡，因此需要將載貨最大值Wmax和載貨最小值Wmin的差控制在合理范圍內，ε 表示可接受的殘差，該數值通常由人工設定輸入，且取值大小取決于可接受的載貨量差異。

.3.2 點集的調整。若上一步的檢驗沒有通過，則需要對此時的聚類結果進行調整。不成立意味著此時聚類劃分的各個區域之間的工作量極差較大，說明在這種情況下，有些地區配送任務很快就可以完成，但是有些地區的配送則需要耗時很長，這樣會拉低整個區域的配送效率。因此，就需要對區域劃分進行如下調整：

在包含最大值Wmax的點集中，篩選出與聚類中心距離最遠的數據點，將其彈出該聚類，這樣該聚類的W值就會降低，同時，將彈出的數據點加入到該點的k個T中數值次小的另一個聚類中。

為了防止某個數據點被反復彈出，需要對被彈出的數據點進行標記，當下次檢驗時又識別到標有特殊標記的該數據點時，則不予處理，轉而遍歷別的數據點，彈出聚類中距離次遠的點。這種機制可以有效避免出現某個數據點無法加入到任何一個聚類中的情況，也就是不會出現為某個客戶點單獨送貨的情況。

3.3.3 重新迭代。在對點集進行調整后，有兩個聚類的W 值發生變化，需要對這兩個聚類重新計算W值，再次檢驗；不斷迭代，直到劃分的各個區域之間的載貨量基本均衡，即各個區域的工作量極差在可接受的范圍之內；最后，停止迭代，最終聚類結果以點集的形式輸出。

3.4 兩階段區域劃分模型實施步驟

改進的兩階段K-means 聚類算法流程如圖1 所示，兩階段區域劃分模型具體實施步驟總結如下：

Step1：選取k個初始點聚類中心。

Step2：建立坐標系，標記每一個點的位置坐標，坐標值用經緯度表示；利用公式計算每一個點到k個聚類中心的時間T，錄入初始數據庫表中。

Step3：在計算的k個配送時間T中選取最小數值對應的點加入到對應類中。

Step4：采用K-means聚類法進行初始階段聚類，計算得到k 個聚類中心。計算每個聚類的W 值，Wj(j=1,2,...,k)為配送區域內車輛的總載貨量。

Step7：將第n 類中到聚類中心配送時間最長的點彈出，加以標記，在之后的循環迭代中遇到有標記的數據點則不予處理，而處理配送時間次短的數據點；將該數據點加入到除n之外配送時間最短的聚類中，重新計算W 值，跳轉step5，繼續檢驗、迭代，直至算法滿足收斂條件。

圖1 改進的兩階段K-means聚類算法流程圖

4 案例分析驗證

4.1 案例介紹及參數設置

本文選取生鮮電商企業的一個配送中心一天的配送訂單信息，包括該配送中心一天的客戶點位置、配送量以及客戶時間窗要求等。配送中心及其20個客戶節點位置坐標及其他信息見表1，位置散點圖如圖2所示。

表1 配送中心及各個客戶節點基本信息

圖2 配送中心及各個客戶節點位置散點圖

模型中各參數的取值情況見表2。

4.2 區域劃分模型驗證及結果分析

在第一階段，延續傳統的K-means 聚類過程，應用Matlab軟件，以總配送時間最短為聚類準則，進行初始區域劃分，其聚類結果如圖3所示。

表2 模型中參數取值

圖3 初始配送區域劃分結果

從圖3中可知，初始區域劃分結果為五個配送區域，A 區域、B 區域、C 區域、D 區域以及E 區域，分別覆蓋3個客戶點、6個客戶點、4個客戶點、3個客戶點以及4個客戶點，各個區域覆蓋的客戶節點見表3。

表3 初始配送區域劃分及覆蓋客戶節點

4.3 區域調整模型驗證分析

在第二階段，引入均衡載貨指標，對初始區域進行調整，使各個劃分區域內的配送量達到均衡，從而保證配送效率。調整后配送區域劃分結果如圖4 所示。

由圖4 可知，配送區域仍被劃分為五個區域，但是各個區域覆蓋的客戶節點有所調整，C區域初始覆蓋范圍由1 號、7 號、9 號、13 號客戶點調整為1 號、7號、9號、19號客戶點，D區域初始覆蓋范圍由6號、17號、19號客戶點調整為6號、13號、17號客戶點，調整后的配送區域及各個區域覆蓋的客戶節點見表4。

圖4 調整后的配送區域劃分結果圖

表4 調整后的配送區域劃分及覆蓋客戶節點

從調整后的配送區域可以看出，劃分的各個區域不僅考慮到配送時間因素，而且加入了對車輛載貨量均衡的考慮，從而保證在快速響應的前提下，使各個劃分區域內的配送任務量達到均衡，提高配送效率。

5 結語

本文構建了生鮮冷鏈配送“區域劃分+區域調整”兩階段模型，首先進行初始區域劃分，延續傳統K-means 聚類過程，以配送時間最短為聚類準則，可以保證生鮮配送的快速響應，在此基礎上，引入均衡載貨指標，對初始配送區域進行調整，使各個劃分區域內的配送任務量達到均衡，保證配送質量，提高配送效率。