生鮮冷鏈配送區(qū)域劃分兩階段模型構(gòu)建

房慶軍，王 旭

（青島理工大學(xué) 管理工程學(xué)院，山東 青島 266520）

1 引言

隨著互聯(lián)網(wǎng)迅速普及，生鮮品線上需求日益增長(zhǎng)，生鮮領(lǐng)域已經(jīng)成為電商相互爭(zhēng)奪的“最后一片藍(lán)海”。但由于生鮮品高時(shí)效性、高腐損率等特性，給生鮮電商的物流配送環(huán)節(jié)帶來(lái)巨大挑戰(zhàn)，生鮮品物流配送質(zhì)量直接影響著生鮮電商運(yùn)營(yíng)的成敗。

目前對(duì)生鮮冷鏈配送區(qū)域劃分的相關(guān)研究比較成熟，大多學(xué)者主要應(yīng)用聚類(lèi)算法解決大規(guī)模配送點(diǎn)問(wèn)題，于曉寒等[1]針對(duì)城市內(nèi)快遞配送問(wèn)題，提出了基于障礙的約束聚類(lèi)算法，以“障礙距離”作為差異度度量標(biāo)準(zhǔn)，建立BSP樹(shù)簡(jiǎn)化距離進(jìn)行計(jì)算；何夢(mèng)軍等[2]采用改進(jìn)的吸引子傳播聚類(lèi)算法對(duì)同城物流網(wǎng)點(diǎn)配送區(qū)域進(jìn)行優(yōu)化。

通過(guò)上述文獻(xiàn)綜述發(fā)現(xiàn)，目前對(duì)配送區(qū)域劃分方面的研究缺少對(duì)生鮮品特性以及工人任務(wù)量的考慮，只有在配送過(guò)程中考慮生鮮品特性的影響才能更好地保證其品質(zhì)不受影響，只有保證工人配送任務(wù)量均衡，才能高效完成配送任務(wù)，提高用戶體驗(yàn)。因此，本文在前人研究的基礎(chǔ)上，將配送區(qū)域劃分問(wèn)題分為兩個(gè)階段，首先以配送時(shí)間最短為前提進(jìn)行初始區(qū)域劃分，在此基礎(chǔ)上加入對(duì)配送量均衡的考慮，進(jìn)行配送區(qū)域調(diào)整，保證配送效率。

2 問(wèn)題描述

本文的研究場(chǎng)景是基于生鮮O2O“冷鏈物流+終端自提”配送模式，在這一模式下，生鮮電商與便利店合作，在配送區(qū)域內(nèi)建立自營(yíng)店、便利店、餐館、小超市、小區(qū)自提柜等多種形式的線下體驗(yàn)店。通過(guò)線上下單購(gòu)買(mǎi)商品的消費(fèi)者，選擇一個(gè)合適的配送地點(diǎn)，接到到貨通知后進(jìn)行自提；在便利店、自營(yíng)店進(jìn)行消費(fèi)的顧客可以直接選擇自己所需的生鮮商品，同時(shí)所在的便利店、自營(yíng)店會(huì)自動(dòng)被定義為配送點(diǎn)，庫(kù)存水平降低到安全庫(kù)存，會(huì)有冷鏈運(yùn)輸車(chē)輛進(jìn)行配送補(bǔ)貨。O2O信息平臺(tái)會(huì)整合所有客戶的訂單信息，由冷鏈運(yùn)輸車(chē)輛對(duì)自營(yíng)店、便利店、餐館、小超市、小區(qū)自提柜等終端進(jìn)行配送，送達(dá)自營(yíng)店、便利店、小區(qū)自提柜的生鮮品，會(huì)根據(jù)顧客要求，等待顧客自提或者由配送員利用電瓶車(chē)在規(guī)定時(shí)間內(nèi)配送上門(mén)。

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

3 “區(qū)域劃分+區(qū)域調(diào)整”兩階段模型構(gòu)建

3.1 目標(biāo)函數(shù)及約束條件

目標(biāo)函數(shù)：

所有配送車(chē)輛遍歷完所有配送點(diǎn)完成所有配送任務(wù)的最少時(shí)間：

約束條件：

（1）保證每個(gè)配送點(diǎn)都有一個(gè)配送車(chē)輛進(jìn)行服務(wù)：

（2）保證每輛配送車(chē)輛到達(dá)和離開(kāi)的配送點(diǎn)數(shù)量相等：

（3）保證每輛車(chē)輛的載貨量不得超過(guò)最大承載量：

（4）車(chē)輛從配送中心出發(fā)的時(shí)刻為0：

（5）保證每個(gè)訂單一定有配送車(chē)輛服務(wù)：

（6）配送車(chē)輛的路徑是由配送點(diǎn)i到達(dá)配送點(diǎn)j:

（7）配送車(chē)輛從配送點(diǎn)i 到達(dá)配送點(diǎn)j 的時(shí)間迭代關(guān)系：

（8）配送車(chē)輛是否經(jīng)過(guò)路徑，是否經(jīng)過(guò)配送節(jié)點(diǎn)，訂單對(duì)配送時(shí)間是否有要求限制：

3.2 第一階段初始區(qū)域劃分模型

3.2.1 確定初始k值

其中，R 表示在一個(gè)配送周期中的生鮮配送總量；Q表示每輛生鮮冷鏈運(yùn)輸車(chē)的最大載貨量。

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

3.2.3 收斂性檢驗(yàn)。K-means 聚類(lèi)算法要求計(jì)算每個(gè)新聚類(lèi)得到的聚類(lèi)中心，不斷重復(fù)這一過(guò)程直到符合收斂條件。對(duì)上述運(yùn)算得到的k 個(gè)聚類(lèi)中心進(jìn)行檢驗(yàn)，若已經(jīng)達(dá)到收斂條件，則下轉(zhuǎn)進(jìn)行第二階段的聚類(lèi)調(diào)整；否則根據(jù)重心法重新計(jì)算聚類(lèi)中心，再次聚類(lèi)，反復(fù)迭代，直到算法達(dá)到收斂條件為止。

3.3 第二階段劃分區(qū)域調(diào)整模型

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

.3.2 點(diǎn)集的調(diào)整。若上一步的檢驗(yàn)沒(méi)有通過(guò)，則需要對(duì)此時(shí)的聚類(lèi)結(jié)果進(jìn)行調(diào)整。不成立意味著此時(shí)聚類(lèi)劃分的各個(gè)區(qū)域之間的工作量極差較大，說(shuō)明在這種情況下，有些地區(qū)配送任務(wù)很快就可以完成，但是有些地區(qū)的配送則需要耗時(shí)很長(zhǎng)，這樣會(huì)拉低整個(gè)區(qū)域的配送效率。因此，就需要對(duì)區(qū)域劃分進(jìn)行如下調(diào)整：

在包含最大值Wmax的點(diǎn)集中，篩選出與聚類(lèi)中心距離最遠(yuǎn)的數(shù)據(jù)點(diǎn)，將其彈出該聚類(lèi)，這樣該聚類(lèi)的W值就會(huì)降低，同時(shí)，將彈出的數(shù)據(jù)點(diǎn)加入到該點(diǎn)的k個(gè)T中數(shù)值次小的另一個(gè)聚類(lèi)中。

為了防止某個(gè)數(shù)據(jù)點(diǎn)被反復(fù)彈出，需要對(duì)被彈出的數(shù)據(jù)點(diǎn)進(jìn)行標(biāo)記，當(dāng)下次檢驗(yàn)時(shí)又識(shí)別到標(biāo)有特殊標(biāo)記的該數(shù)據(jù)點(diǎn)時(shí)，則不予處理，轉(zhuǎn)而遍歷別的數(shù)據(jù)點(diǎn)，彈出聚類(lèi)中距離次遠(yuǎn)的點(diǎn)。這種機(jī)制可以有效避免出現(xiàn)某個(gè)數(shù)據(jù)點(diǎn)無(wú)法加入到任何一個(gè)聚類(lèi)中的情況，也就是不會(huì)出現(xiàn)為某個(gè)客戶點(diǎn)單獨(dú)送貨的情況。

3.3.3 重新迭代。在對(duì)點(diǎn)集進(jìn)行調(diào)整后，有兩個(gè)聚類(lèi)的W 值發(fā)生變化，需要對(duì)這兩個(gè)聚類(lèi)重新計(jì)算W值，再次檢驗(yàn)；不斷迭代，直到劃分的各個(gè)區(qū)域之間的載貨量基本均衡，即各個(gè)區(qū)域的工作量極差在可接受的范圍之內(nèi)；最后，停止迭代，最終聚類(lèi)結(jié)果以點(diǎn)集的形式輸出。

3.4 兩階段區(qū)域劃分模型實(shí)施步驟

改進(jìn)的兩階段K-means 聚類(lèi)算法流程如圖1 所示，兩階段區(qū)域劃分模型具體實(shí)施步驟總結(jié)如下：

Step1：選取k個(gè)初始點(diǎn)聚類(lèi)中心。

Step2：建立坐標(biāo)系，標(biāo)記每一個(gè)點(diǎn)的位置坐標(biāo)，坐標(biāo)值用經(jīng)緯度表示；利用公式計(jì)算每一個(gè)點(diǎn)到k個(gè)聚類(lèi)中心的時(shí)間T，錄入初始數(shù)據(jù)庫(kù)表中。

Step3：在計(jì)算的k個(gè)配送時(shí)間T中選取最小數(shù)值對(duì)應(yīng)的點(diǎn)加入到對(duì)應(yīng)類(lèi)中。

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

Step7：將第n 類(lèi)中到聚類(lèi)中心配送時(shí)間最長(zhǎng)的點(diǎn)彈出，加以標(biāo)記，在之后的循環(huán)迭代中遇到有標(biāo)記的數(shù)據(jù)點(diǎn)則不予處理，而處理配送時(shí)間次短的數(shù)據(jù)點(diǎn)；將該數(shù)據(jù)點(diǎn)加入到除n之外配送時(shí)間最短的聚類(lèi)中，重新計(jì)算W 值，跳轉(zhuǎn)step5，繼續(xù)檢驗(yàn)、迭代，直至算法滿足收斂條件。

圖1 改進(jìn)的兩階段K-means聚類(lèi)算法流程圖

4 案例分析驗(yàn)證

4.1 案例介紹及參數(shù)設(shè)置

本文選取生鮮電商企業(yè)的一個(gè)配送中心一天的配送訂單信息，包括該配送中心一天的客戶點(diǎn)位置、配送量以及客戶時(shí)間窗要求等。配送中心及其20個(gè)客戶節(jié)點(diǎn)位置坐標(biāo)及其他信息見(jiàn)表1，位置散點(diǎn)圖如圖2所示。

表1 配送中心及各個(gè)客戶節(jié)點(diǎn)基本信息

圖2 配送中心及各個(gè)客戶節(jié)點(diǎn)位置散點(diǎn)圖

模型中各參數(shù)的取值情況見(jiàn)表2。

4.2 區(qū)域劃分模型驗(yàn)證及結(jié)果分析

在第一階段，延續(xù)傳統(tǒng)的K-means 聚類(lèi)過(guò)程，應(yīng)用Matlab軟件，以總配送時(shí)間最短為聚類(lèi)準(zhǔn)則，進(jìn)行初始區(qū)域劃分，其聚類(lèi)結(jié)果如圖3所示。

表2 模型中參數(shù)取值

圖3 初始配送區(qū)域劃分結(jié)果

從圖3中可知，初始區(qū)域劃分結(jié)果為五個(gè)配送區(qū)域，A 區(qū)域、B 區(qū)域、C 區(qū)域、D 區(qū)域以及E 區(qū)域，分別覆蓋3個(gè)客戶點(diǎn)、6個(gè)客戶點(diǎn)、4個(gè)客戶點(diǎn)、3個(gè)客戶點(diǎn)以及4個(gè)客戶點(diǎn)，各個(gè)區(qū)域覆蓋的客戶節(jié)點(diǎn)見(jiàn)表3。

表3 初始配送區(qū)域劃分及覆蓋客戶節(jié)點(diǎn)

4.3 區(qū)域調(diào)整模型驗(yàn)證分析

在第二階段，引入均衡載貨指標(biāo)，對(duì)初始區(qū)域進(jìn)行調(diào)整，使各個(gè)劃分區(qū)域內(nèi)的配送量達(dá)到均衡，從而保證配送效率。調(diào)整后配送區(qū)域劃分結(jié)果如圖4 所示。

由圖4 可知，配送區(qū)域仍被劃分為五個(gè)區(qū)域，但是各個(gè)區(qū)域覆蓋的客戶節(jié)點(diǎn)有所調(diào)整，C區(qū)域初始覆蓋范圍由1 號(hào)、7 號(hào)、9 號(hào)、13 號(hào)客戶點(diǎn)調(diào)整為1 號(hào)、7號(hào)、9號(hào)、19號(hào)客戶點(diǎn)，D區(qū)域初始覆蓋范圍由6號(hào)、17號(hào)、19號(hào)客戶點(diǎn)調(diào)整為6號(hào)、13號(hào)、17號(hào)客戶點(diǎn)，調(diào)整后的配送區(qū)域及各個(gè)區(qū)域覆蓋的客戶節(jié)點(diǎn)見(jiàn)表4。

圖4 調(diào)整后的配送區(qū)域劃分結(jié)果圖

表4 調(diào)整后的配送區(qū)域劃分及覆蓋客戶節(jié)點(diǎn)

從調(diào)整后的配送區(qū)域可以看出，劃分的各個(gè)區(qū)域不僅考慮到配送時(shí)間因素，而且加入了對(duì)車(chē)輛載貨量均衡的考慮，從而保證在快速響應(yīng)的前提下，使各個(gè)劃分區(qū)域內(nèi)的配送任務(wù)量達(dá)到均衡，提高配送效率。

5 結(jié)語(yǔ)

本文構(gòu)建了生鮮冷鏈配送“區(qū)域劃分+區(qū)域調(diào)整”兩階段模型，首先進(jìn)行初始區(qū)域劃分，延續(xù)傳統(tǒng)K-means 聚類(lèi)過(guò)程，以配送時(shí)間最短為聚類(lèi)準(zhǔn)則，可以保證生鮮配送的快速響應(yīng)，在此基礎(chǔ)上，引入均衡載貨指標(biāo)，對(duì)初始配送區(qū)域進(jìn)行調(diào)整，使各個(gè)劃分區(qū)域內(nèi)的配送任務(wù)量達(dá)到均衡，保證配送質(zhì)量，提高配送效率。