陳嬋麗，鐘映竑

（廣東工業(yè)大學 管理學院，廣東 廣州 510520）

1 引言

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

2 研究背景

2.1 新零售背景

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

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

2.2 新零售模式下的傳統(tǒng)配送方法

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

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

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

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

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

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

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

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

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

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

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

4.1 遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

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

（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)的結果不再變小或當前的迭代次數(shù)達到最大迭代次數(shù)的閾值時停止重聚類。

5 實驗結果與分析

5.1 實驗數(shù)據(jù)

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

圖2 天河區(qū)10個配送中心的分布圖

5.2 實驗環(huán)境準備

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

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

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

表2 實驗環(huán)境的系統(tǒng)信息

5.3 實驗結果

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

圖3 傳統(tǒng)遺傳算法物流配送路徑

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

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

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

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

表3 實驗數(shù)據(jù)結果比較

6 結語

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