基于改進K-means聚類方法的新零售物流配送路徑優化

陳嬋麗，鐘映竑

（廣東工業大學 管理學院，廣東 廣州 510520）

1 引言

自2016年起，新零售概念越來越為人們所熟悉。隨著時代的發展，企業通過物流使得線上線下融合，互相補充實現共同發展。各企業為適應新零售時代的要求，進行了一系列戰略布局和合作，企業可通過共同平臺實現合作共贏。新零售時代的到來，使得消費者可以通過各種渠道進行購物，而用戶的購物體驗成為重中之重。物流配送路徑問題一直是物流領域的研究重點，然而目前的多數物流配送模式仍不適應新零售時代的特點，傳統的物流配送路徑方法的研究仍停留在適應于傳統的零售方式，并未將線上線下很好地融合以獲取良好的購物體驗。為了適應新零售時代，如何對物流配送進行優化，融合線上線下，減少物流配送路程以提升用戶體驗度是本文的研究重點。本文假設新零售各實體店面可實現協同合作，各實體店面具有一定的庫存量且可以作為配送中心，從末端實體店物流配送路徑角度出發，對新零售各實體店物流配送路徑優化方法進行研究。

2 研究背景

2.1 新零售背景

近年來，人們越發重視購物體驗，線上已無法滿足人們日益增長的體驗式消費，購物體驗始終不及線下。傳統的線下供應鏈體系必須通過更高效的互聯網技術實現轉型提效。2016年，馬云指出，“純電商和純零售都將結束。線上線下通過物流達到融合的新零售即將引領未來的商業模式”[1]。同年《國務院辦公廳關于推動實體零售創新轉型的意見》也明確了實體零售企業創新轉型的9項主要任務，定調實體零售轉型[2]。從近幾年開始，各企業為適應新零售制定了一系列的戰略布局和投資合作。阿里巴巴先后通過投資入股聯華超市、新華都和三江購物、高鑫零售和百聯集團達成戰略合作，構建創新型跨界超市。與此同時，騰訊也加快了新零售的步伐，與家樂福、沃爾瑪達成戰略合作伙伴關系，并投資永輝超市、京東。新零售背景下，生鮮社區店及各雜貨店B2B應運而生，如永輝超市和中百集團旗下鄰里生鮮及京東旗下錢大媽。阿里巴巴成立了多家盒馬鮮生，盒馬鮮生既是超市也是配送中心，更是倉儲中心，是對線下超市全面重構的新零售業態。騰訊和京東聯手構建無人超市和京東到家，騰訊三輪投資每日優鮮便利購，線上到家服務占據主要地位[3]。

新零售的核心在于推動線上線下的高度協同，達成戰略合作的末端實體店面可通過充分的庫存共享和快速的物流服務不斷提升客戶體驗度和滿意度。連接線上與線下兩者的關鍵點在于物流配送，物流配送行業不但要求所有貨物能及時送達，而且也要求盡可能降低整個運輸成本，所以物流配送車輛路徑優化問題是亟待解決的關鍵問題。傳統的優化方法搜索時間較長，且不適應新零售企業合作共贏模式，難以找出最優路徑，并且不同實體店對同一客戶點的配送路徑重復率高，造成配送成本高，效率低。為適應時代發展，提高車輛路徑優化率，如何利用新零售下各實體店面可協同配送的特點改進末端實體店物流配送路徑方法，使線上線下融合，最大程度地提升用戶體驗，增加銷量，降低企業物流配送成本，成為迫切需要解決的關鍵問題。

2.2 新零售模式下的傳統配送方法

2.2.1 TSP問題描述。本文對末端物流的物流配送策略進行優化，主要研究問題是TSP（traveling salesman problem）旅行商問題。這是一個非常經典的NP完全問題[4]，可描述為：已知n個城市相互之間的距離矢量，旅行商配送對象（通常是物流配送車輛）開始會選擇其中的某一個城市作為初始站，從初始站開始出發去遍歷訪問其他的所有城市一次，每個城市僅訪問一次，最后回到初始站，TSP問題就是如何規劃旅行商使其所走的路線最短。簡單地說，就是尋找n個城市的最短遍歷路徑，或者通過算法搜索自然子集X={C1,C2,…,Cn}(X的元素表示對n個城市的編號)的一個符合最短路徑條件的排列π(X)={D1,D2,…,Dn}，使Td取最小值，其中d(Di,Di+1)表示城市Ci到城市Ci+1的距離。

本文研究的物流配送路徑問題類似這類TSP問題。假定已知的多個互不協同的配送中心（實體店面如超市、便利店等）的位置和其在一個特定城市區域各自的需求量，其中物流配送車輛有最大的配送范圍限制（默認為3km），且每一個配送中心有且只有一輛物流配送車輛。在滿足目標函數最小和多個約束條件的前提下要求每一個配送車輛從各自的配送中心出發，把貨物分別送到各自的配送目標位置，每個配送目標位置有且只有一輛物流配送小車進行一次配送，完成所有配送貨物的配送任務后從最后一個配送目標位置返回至配送中心。整個過程中最關鍵的問題就是配送路線的優化和如何有效地分配配送資源，對區域內的所有配送需求進行配送，使總體的配送路徑最短。

2.2.2 新零售模式下傳統配送問題。目前，絕大多數的物流配送有很成熟的配送策略和方案。通常都是結合各類智能算法，如遺傳算法、啟發式算法[5]、粒子群算法[6]和模擬退火算法[7]等，針對特定的場景和特征進行對應的改造，從而提高物流配送效率。石紅國等[8]提出使用Hopfield神經網絡與歸約結合求解大規模TSP，通過提取原TSP較優解間的公共邊以縮小規模，再利用原神經網絡得到較優解后將TSP還原并求較優解。苑光明等[9]針對路徑規劃中收斂速度慢的問題對遺傳算法引入了拐彎因素，改進傳統的精英保留策略以提高AGV運行效率。Doerr B等[10]研究優化時間如何依賴于參數的選擇，提出(1+(λ，λ))遺傳算法(GA)，得到如何靜態與動態地選擇種群大小、變異概率和變異偏差的結果。劉二輝等[11]通過改進遺傳算法和灰狼優化算法引導小車路徑規劃，可用于求解復雜靜態環境中的移動機器人路徑規劃問題。Gong D W等[12]利用遺傳算法對區間優化問題進行研究，提出一種解決區間多目標優化問題的方法[6]。

然而，在末端物流的現實配送場景中，很多物流配送中心（各類實體店面比如超市、便利店等）的配送效率并不是特別高效。通常在某一個特定的物流配送區域范圍內，多個不同的物流配送中心有著相同的配送點，如果沒有一個統一的配送平臺對這些物流配送中心進行綜合管理和分配，那么這些配送中心只能配送各自范圍內的配送點。這樣在同一個物流配送區域內，同一個目標配送點（比如小區）可能會由多個不同的配送中心負責配送。這類情況在現實生活中非常常見。圖1采用seaborn對廣州市天河區的幾個實際配送實體店面及其配送點進行了模擬仿真。從圖中圓圈中的點可以看到，對于B實體店和H實體店，它們的位置不同，但是各自有一個訂單在同一個配送點。根據傳統的配送模式，B實體店和H實體店必須同時分配兩個配送車輛到同一個配送地點，造成浪費。如何結合協同配送和重聚類的方式重組這些配送資源，是一個值得研究的問題。

隨著新零售時代的來臨，用戶體驗度成為最重要的提升指標。對于用戶來說，不僅要求線上預訂要快，更要求線下配送與線上同步。線下的配送效率是影響新零售發展的一個核心因素，如何快速響應用戶的配送需求，成為目前亟待解決的關鍵問題。

圖1 不同實體店重復配送目標示范圖

3 用遺傳算法改進的K-means聚類方法

針對新零售模式下傳統物流配送存在的問題，本文提出了一種新型的混合聚類算法。通過改造K-means聚類，結合遺傳算法求解TSP問題進行重聚類。配送點重聚類時，配送中心采用了共同配送的新模式來提高響應度，并且對其中存在的重復配送點進行了合并優化。共同配送后可以使配送中心具有更大的配送范圍，從而提高了物流配送效率，實現了新零售的快速配送。本文提出的新型混合聚類算法主要有以下貢獻：

（1）相比較于其他傳統的遺傳算法，本文提出的混合聚類算法可以通過協同配送和TSP最短路徑重聚類的方式來提高區域物流的整體配送效率，通過對同區域內不同配送中心的模擬仿真，基于Tensor-Flow機器學習平臺[13]、改進K-means算法和遺傳算法對所有配送需求點進行重聚類，更加合理和高效地重組了物流配送資源，提高了物流配送效率。

（2）對于實際中存在的重復配送點問題，通過協同配送優化的方式，對這類配送需求點進行了合并優化，用同一個配送資源（如外賣人員）匹配不同配送中心的多個重復配送點的配送需求，優化這部分物流配送成本，從而提高了整體的配送響應度。

4 物流配送的數學模型求解算法描述

4.1 遺傳算法

遺傳算法（genetic algorithm，GA）是模擬生物在自然環境中的遺傳和進化過程而形成的一種全局優化搜索算法[14]。目前有很多種通過遺傳算法求解TSP問題的優化算法的方案，但對于實際場景中具有不同配送資源的獨立實體門店來說，傳統的遺傳算法求取最短路徑的策略比較乏力。從整體的物流配送效率來看，由于不同實體店面在同一個區域內需要各自配送貨物，所以在相同范圍的同一個物流區域內，這種算法求取出來的并不是整體的最優解。

遺傳算法求取TSP的主要計算步驟如下：

（1）編碼。選擇實際問題參數集，即對n個配送目標點的TSP問題進行染色體的分段編碼，其中每一段為對應配送目標點的編號；

（2）種群初始化。完成染色體編碼后產生一個初始種群作為初始化對象；

（3）定義適應度函數。設{k1,k2,…,kn}為染色體種群，其中Dkikj表示配送目標點ki到配送目標點kj的距離，則適應度函數為:

其中，fitness表示剛好從配送中心k1出發，遍歷n-1個配送目標點后再返回到配送中心的距離的倒數。因此適應度函數應當選擇盡可能大的染色體目標，適應度值越大的染色體越優質，反之亦然；

（4）選擇操作。從原種群中選擇染色體個體到新種群中，個體被選中的概率與適應度值相關，適應度值越大，則概率越大；

（5）交叉操作。采用部分映射雜交法，確定交叉操作的父代染色體個體；

（6）變異操作。采用隨機選取兩個點并互換位置的方式，產生兩個[1,n]范圍內的隨機整數p1和p2，確定位置后互換；

（7）計算路線長度。若迭代未結束，繼續執行（4）-（6）步，直到迭代結束。

4.2 共同配送模式下基于遺傳算法改進的K-means聚類方法

K-means算法最早在1967年由Macqueen提出，K-means在聚類算法中最簡單、最高效。其核心思想是，由用戶指定k個初始質心以作為聚類的類別，重復迭代直至算法收斂[15]。本文對K-means聚類算法進行針對性的改造，對其中的集合分簇和收斂規則進行修改。集合分簇開始之前，將當前所有的目標配送地點作為輸入數據集。與其他K-means方法的不同之處在于，本文的整體輸入數據集是不會發生變化的。收斂規則為：除了以歐幾里德的中心距離平方和之外，利用上述的遺傳算法求取TSP的距離，對每一個分簇中的所有數據對象與當前的聚類中心進行路徑求和，當迭代次數達到閾值或中心距離平方和與路徑求和不再變化時，結束聚類過程。整個混合聚類算法的步驟如下：

（1）根據配送中心點選擇聚類中心分簇。設k為聚類中心數目，xi表示第i個目標對象，K-means算法以k為參數，將具有n個目標對象的集合D={x1,x2,…,xn}分為k個簇C={C1,C2,…,Ck}。本文采用實際配送中心的數量作為k參數，將實際物流區域中的多個配送中心作為初始化的聚類中心T={t1,t2,…,tk}；在整個集合的重聚類過程中，配送中心的位置不會發生改變。

（2）初始化分簇。當完成聚類中心的初始化后，就對簇進行初始化，對集合D中的n個目標對象，計算xi(i=1,2,…,n)到中心向量tj(j=1,2,…,k)的歐幾里德距離dij，將dij中最小的值對應的xi標記為相應的簇類，直到D集合中所有的對象被標記完成；算出每個聚類簇的所有歐幾里德距離的平方和Oj(j=1,2,…,k)，作為收斂條件。

（3）分簇后的最短路徑求和。對于j=1,2,…,k的所有Cj中的目標對象，通過遺傳算法求得簇內的最短路徑rm(m=1,2,…,k)，并將所有簇內求出的最短路徑求和，得Sm(m=1,2,…,k)，作為收斂條件，并計算出首個收斂條件Esum1=Oj+Sm。

（4）重聚類。對于j=1,2,…,k的所有Cj中的最長歐幾里德距離的向量xm(m=1,2,…,k)，計算xm到其他k-1個聚類中心向量tj(j=1,2,…,k-1)的歐幾里德距離，將最小值重新隨機分配到其余的聚類中心；分配后重新計算所有簇中的Oj和Sm的求和結果Esum2作為判斷條件，若Esum2＜Esum1，則使用該重聚類的結果；否則重新使用重聚類之前的結果；

（5）重復（3）和（4），直到Esum=Om+Sm(m=1,2,…,k)的結果不再變小或當前的迭代次數達到最大迭代次數的閾值時停止重聚類。

5 實驗結果與分析

5.1 實驗數據

實驗數據均采集實際的城市坐標點。以廣州市天河區內的10個實體店面坐標作為實驗數據（如圖2所示），同時根據“美團”和“餓了么”兩個平臺的爬蟲數據，獲得附近居民住宅區的實際位置作為物流配送的目標點。根據百度地圖提供的定位功能，將這些居民住宅區對應的坐標數據作為配送目標點的坐標。由于是實際的GPS設備獲取的經緯度坐標，而在計算路徑時要用米制坐標，因此通過百度提供的坐標轉換服務API將經緯度坐標轉換為對應的米制坐標。為便于描述與展示，我們只對其中的物流配送中心的數據信息做展示，見表1。

圖2 天河區10個配送中心的分布圖

5.2 實驗環境準備

本文需要通過圖形計算來精確模擬整個物流配送過程，因此選擇了谷歌公司提供的Tensorflow作為實驗平臺。Tensorflow是Google提供的一個基于數據流編程的庫，目前被廣泛使用于各類機器學習和科學計算的編程實現方案中，它提供了一系列高效的基礎組件和各類API，可以為本文的實驗提供非常強大的功能支撐。

表1 各個配送中心之間的位置坐標和配送需求量

實驗環境方面，使用的是騰訊云服務器的Linux系統，發行版采用了Ubuntu，內核版本為Linux（4.15.0）；通過安裝python、pip等必要的基礎IDE和第三方庫Tensorflow，為計算提供基礎條件。實驗環境的系統信息見表2。在進行混合聚類算法的聚類計算過程中，需要使用python編程調用相關的程序接口來啟動畫圖，需要Tensorflow的圖形計算，還需要其他第三方庫的支持，因此在實驗系統Linux上面還要安裝Seaborn等必要的第三方庫。

表2 實驗環境的系統信息

5.3 實驗結果

圖3是傳統遺傳算法求取各個配送中心所遍歷的路徑，圖4是采用基于協同配送的混合聚類算法后的配送路徑。從圖3可以看出，每一個配送中心負責配送各自的物流需求，其中有一些配送目標點與其他配送中心的配送目標點重復，不同的配送中心對相同的目標點進行重復配送。由圖3可知，在相同配送范圍內，每一個配送中心都要遍歷比較冗長的配送路徑，區域內的整體配送過程也比較復雜和冗長。從圖4可以看出，基于協同配送混合聚類算法重聚分配后的路徑相比圖3而言，物流配送中心的配送路徑明顯得到優化。對于每個配送中心都通過重聚類，優先分配距離較近的配送目標點；并且對存在的重復配送目標點的配送需求進行合并優化，優先將合并后的配送需求分配給最近的配送中心負責。通過重聚類和協同分配后，在同樣區域內有效的減少物流配送路徑，同時可滿足大量的配送需求。

圖3 傳統遺傳算法物流配送路徑

圖4 基于改進K-means聚類方法的物流配送路徑

圖5是對每一個配送中心在聚類前與聚類后通過遺傳算法遍歷所有配送點的物流配送路徑統計情況，更直觀地證明了本文提出的混合聚類算法的有效性。橫坐標表示采集于真實地理位置的實體店面，也是配送中心；縱坐標表示配送中心分別通過傳統遺傳算法、共同配送模式基于遺傳算法改進的K-means聚類方法求得最短路徑后物流車輛的行駛路程（單位：m）。在同一個物流區域內，使用改進混合聚類方法后，大多數配送中心的行駛路程都得到優化。

從表3可以看出，整個物流區域的物流車輛行駛總路程在聚類后比聚類前減少了39.89%。值得注意的是，由于需要優先分配就近的配送需求目標點，在重聚類過程中會出現部分配送中心的配送路程要比之前大，但是區域內總體的配送路程得到明顯的改善，這符合協同配送的出發點，同時也能提高區域內整體配送效率。

圖5 TSP和改進后的混合聚類算法配送路程的比較

表3 實驗數據結果比較

6 結語

在新零售背景下，從末端物流配送路徑的角度出發，本文建立了車輛配送路徑最優化的數學模型，提出了一種用遺傳算法改進的K-means聚類方法。本文采用廣州市天河區實際數據，通過Tensorflow軟件仿真實驗進行驗證。實驗結果證明，和傳統遺傳算法相比，本文提出的用遺傳算法改進的K-means聚類方法在復雜的區域物流內可減少39.89%的配送路程。該算法解決了重復配送路徑問題，并且優化了物流配送路徑，提高了配送效率，從而改善了服務質量和用戶體驗度。