基于K-means聚類的生鮮自提柜選址及配送方案優化

徐昊源，繆鴻志

（大連海事大學 交通運輸工程學院，遼寧 大連 116081）

0 引言

生鮮電商逐漸成為人們獲取生活物資的新渠道，尤其是為了應對突如其來的新冠肺炎疫情，電商平臺、商超線上應用、社區微信團購等“云買菜”方式已成為大部分居民的首選。生鮮產品具有易腐特點，其末端配送對時效性和存儲條件相對較為嚴格。為了保持新鮮度，在城市社區紛紛設立了生鮮自提柜，自提柜選址不僅影響到消費者取貨的便利性，也影響商家末端配送的效率與成本。

生鮮自提柜選址起源于配送中心的選址。Bortolini，等[1]提出三目標線性規劃模型進行生鮮自提點的選址，考慮了典型的生鮮分配約束，即生鮮質量、市場需求和生產能力的約束；Katiyar，等[2]在考慮配送時間窗的基礎上，采用改進的蜂群算法進行生鮮自提柜選址，有效減少了生鮮品損耗；HOLMBERG，等[3]開發了一種PI算法，通過生鮮自提點的選址與共享，極大限度地減少了生鮮品浪費；Drezner，等[4]考慮從配送中心到銷售點的運輸成本以及銷售點的庫存成本，構建了易腐產品的配送中心選址模型；黃雨珊，等[5]基于深圳市盒馬鮮生、菜鳥驛站及相關設施興趣面（Area Of Interest，AOI）、興趣點（Point Of Interest，POI）數據，綜合運用空間分析、定量統計等方法，探究了社區化新零售與物流終端自提點代表之間的對接基礎與可行性路徑；李煒勤，等[6]采用改進的二進制教與學優化算法求解了最優選址和容量決策；王文川[7]構建了末端共同配送自提點選址-路徑問題模型，并采用兩階段啟發式算法進行了求解。K-means聚類方法具有收斂速度快、調參量小等優點，適用于以城市小區為數據點的結果簇密集選址。從研究現狀來看，基于Kmeans聚類的生鮮自提柜選址方法還不多見。

考慮到影響生鮮產品配送的因素比較復雜，不能僅僅基于運輸時間或距離指標進行決策，本文考慮新鮮度損耗因素，分析生鮮產品從商家到消費者的全鏈條運輸成本，運用K-means聚類算法建立以交通小區為選址依據的自提柜選址模型，并結合自提柜設置的建設與運營成本，從總成本最優的角度對選址點進行篩選。

1 生鮮品末端配送影響因素分析

生鮮產品與其他產品的不同之處就在于生鮮產品具有新鮮度，且其新鮮度會在運輸和儲存的過程中受到溫度和時間等因素的影響而發生變化。由于本文假設生鮮產品在生鮮自提柜中儲存的時間不長，消費者會盡快將其取走，因此認為在自提柜的儲存過程中不會造成生鮮產品新鮮度的損耗，只考慮運輸過程中由溫度和運輸問題引起的新鮮度的下降。

整個配送路線為三級配送網絡，配送流程為生鮮車輛從配送中心出發，前往生鮮自提柜放置點進行卸貨后返回，居民從生鮮自提點提貨后返回居民小區。在此運輸鏈中，影響自提柜選址的主要因素有：

（1）需求分布差異。不同城市的經濟狀態不同，相同城市不同區域的經濟狀態也有所差異，導致生鮮產品需求量存在差異。因此，生鮮自提柜的建設需要結合實際需求情況進行最終決策，以保證滿足多種用戶的不同需求。

（2）交通條件。自提柜應在盡可能靠近需求點的同時還具有交通便利的條件，保證配送的同時使用戶的取貨過程更加方便、快捷，滿足龐大的車流量和人流量的交通往來需求。

（3）自然環境條件。由于生鮮自提柜需安裝在公共區域，以便所有用戶進行自助取貨，安裝位置多處于室外，因此選址應考慮到自然環境的損害，不能選擇在風口位置，也要盡量使其有所遮擋，減少暴風雨和日曬導致的隱患和損毀。

2 成本分析

2.1 生鮮品的新鮮度損耗成本

參考1889年阿侖尼烏斯（Arrhenius）提出的阿侖尼烏斯方程（反應速度與溫度呈指數關系）描述新鮮度的損耗過程[8]。假設生鮮產品的新鮮度損失表示為運輸時間的指數關系式。用生鮮產品新鮮度函數來表示生鮮產品的新鮮度隨運輸時長的變化規律，見式（1）。

θ為生鮮產品在配送過程中發生的變質率，取0.008。當運輸時間t=0時，φt=1表示生鮮產品在配送初始時間新鮮度為1。φt是關于t的單調遞減函數，即φt隨t的增加而減少，與生鮮產品的新鮮度隨運輸時長增加而減少的實際情況相符合。

由上述新鮮度函數可以得到，生鮮產品從配送中心m經生鮮自提柜備選點i，最終到需求點j的過程中消耗的總時長為：

其中，r為城市交通擁堵系數，假設在交通順暢時進行配送，取t=1.2；dmi為區域配送中心m到生鮮自提柜i的距離；dij為生鮮自提柜i到小區需求點j的距離；v1為生鮮配送車輛在城市內的平均行駛速度，交通順暢時取8.8m/s；v2為消費者取貨后的平均步行速度，取1.3m/s。

新鮮度為φt=(1-θ)t，則生鮮產品的新鮮度在此過程中下降了1-φt，生鮮產品變質損耗成本可表示為μ(1-φt)cijdmij。根據上文的變質損耗成本分析，可得到損耗成本的表達式為：

其中，μ為生鮮產品單位損耗成本，取0.5元/(t·km)；cij為小區j消費者從生鮮自提柜i取出的生鮮產品數量；dmij為配送中心m到生鮮自提柜i再到小區需求點j的總距離。

2.2 配送成本

配送運輸成本是指生鮮產品由配送中心運輸到自提點的過程中所消耗的運輸費用，是運輸量、距離、單位費率的乘積。配送成本表示如下：

其中,cmi為從配送中心m到自提點i的貨物運輸量；dmi為配送中心m到自提點i的距離；a為運輸貨物單位費率，取0.5元/（t*km）；式（7）、式（8）表示每一個生鮮自提點只由一個配送中心進行配送。

2.3 建設與運營成本

建設成本指生鮮自提柜在選址建設中產生的不可變的成本，主要包含生鮮自提柜的購買成本、安置生鮮自提柜時的相關設施成本、安裝的人工成本以及所處位置的土地租賃成本等。由于本文涉及的區域較小，因此將此部分成本設置為一個固定值。運營成本也可以說是可變成本，主要指生鮮產品在流通過程中（如短期儲存以及裝卸搬運過程）投入的人力物力成本。

建設與運營成本可表示為：

其中fi為生鮮自提柜的年單位建設成本，取7 500元/（套*年）；n為流通過程中單位運營成本，取5元/t；cij為小區j消費者從生鮮自提柜i取出的生鮮產品數量。

3 基于K-means聚類的生鮮自提柜選址

3.1 K-means聚類

MacQueen首次提出了K均值聚類算法，它屬于非監督學習的硬聚類算法，通過迭代尋找最優聚類。聚類的一個核心問題就是如何合理地定義相似性度量函數。在此采用應用較為普遍的歐氏距離來度量樣本間的距離。點x=(x1，x2，...，xn),y=(y1，y2，...，yn)之間的相似度見式（13）。

3.2 “手肘”法確定聚類中心個數

本文中，聚類中心個數對應著自提柜的數目。“手肘”法[9]的判斷指標是誤差平方和，隨著聚類數K的增大，樣本劃分會更加精細，每個簇的聚合度會逐漸提高，誤差平方和SSE會逐漸變小。當聚類數K＜Kbest時，隨著K的增大SSE的下降幅度會較大；當K＞Kbest時，隨著K的增大每個簇的聚合度趨向于穩定，SSE的下降幅度會更加平穩，此時“肘部”對應的位置即為最佳聚類數K=Kbest。

式（14）中，Sk為第k簇，j為Sk的樣本點，ik為Sk的質心，即Sk中所有樣本的均值。

3.3 生鮮自提柜選址的算法實現

算法分為兩部分，第一部分為根據小區的位置與需求量，結合K-means聚類法確定最佳的自提柜選址；由于配送中心數量有限，第二部分采用貪心算法篩選出各個自提柜對應的最佳配送中心，具體步驟如下：

步驟1：在所有M個小區中選取s個居民小區作為自提柜的設置點，即作為初始聚類中心；

步驟2：測算各個小區用戶至聚類中心（自提點）的歐式距離，并根據各個小區的生鮮產品需求量計算新鮮度損耗成本，按照成本最小的準則將各個小區分到距離他們最近的聚類中心（自提點）所對應的類；

步驟3：以每組中每個小區為備選聚類中心（備選自提點）重新計算本組的新鮮度損耗成本，將每組最小總成本所對應的備選聚類中心作為新一代聚類中心（自提點）；

步驟4：重復步驟2與步驟3，直到聚類中心（自提點）不再變化或者達到最大迭代次數；

步驟5：計算每個配送中心送貨到自提點的運輸成本與生鮮度損耗成本之和，根據貪心算法選取成本和最小值對應的配送中心作為自提點的供貨方。

4 案例分析

4.1 基礎數據

本文以長春市南關區及其周邊部分區域為研究對象，選取其中三個超市作為生鮮配送中心，周邊31個小區作為生鮮產品的需求點，所有需求點同時作為生鮮自提柜安置的備選點，都有擺放生鮮自提柜的可行性，通過高德地圖獲取配送中心與小區需求點的地理坐標，區域配送中心位置信息見表1，居民小區及配送中心的位置如圖1所示。

圖1 生鮮產品需求點及配送中心位置

表1 區域配送中心位置信息表

考慮到各需求點居民樓分布情況不同，因此采用重心法計算各個小區的中心，將其作為自提點的備選位置。并且基于對實際道路情況的考慮，以高德地圖的路徑搜索結果為準進行測距，分別計算配送中心到各居民小區需求點的路徑距離以及各居民小區之間的步行距離。

根據各個小區的人口規模，選取一定比例的人群作為生鮮自提柜的使用人群，同時考慮自提柜的最大容積等約束，根據實地調查估算各個需求點的年生鮮需求數量（單位：t/年），見表2。

表2 各需求點的年需求量

4.2 聚類結果分析

本文使用總誤差平方和SSE度量聚類質量。顯然隨著簇數K值的增大，SSE的值會逐漸減小。當K值小于實際簇數時，SSE下降趨勢明顯，隨著K值接近最優簇數，SSE下降的趨勢逐漸變緩慢。因此，本文以SSE遞減趨勢開始明顯變緩作為聚類結束的判斷條件。由圖2可知，K＞5時，下降趨勢明顯變緩。最后結合成本分析確定最佳分類數。

圖2 SSE的變化趨勢圖

上述聚類分析結果以新鮮度損耗成本與配送成本為依據，沒有考慮到生鮮自提柜的建設與運營成本。因此，考慮自提柜的建設與運營成本，分別對比聚類數為5與6時兩種聚類結果下的成本，結果見表3。

表3 成本對比表

由對比可知，聚類數為6時，總成本最低，各生鮮超市、生鮮自提柜與需求點的對應關系見表4，自提柜的選址示意圖如圖3所示。

圖3 生鮮自提柜選址方案圖

按照上述條件計算，優化之前點對點運輸的總成本為30.539 6萬元，按照表4設置生鮮自提柜，優化后總成本為18.709 5萬元，成本節約38.74%。由此可知，該配送方案經濟可行。

表4 配送中心-自提柜-小區對應關系表

5 結語

隨著生鮮市場的不斷擴大，線上購買線下收貨的方式獲得了消費者的認可，為了滿足消費者需求，生鮮自提柜應運而生。本文以新鮮度為依據，基于Kmeans聚類算法對自提點進行選址優化，并進行了算例驗證，從需求點中進行生鮮自提柜選址，兼顧了經濟效益和社會效益。本文仍然存在著不足，如各小區的生鮮需求量預測不夠精確，沒有考慮到自提柜的數量及容量限制等，將會在下一步研究中加以分析。