基于K均值聚類算法的生鮮運輸路徑優(yōu)化模型

周蓉蓉 陳 棟 劉思遠

（1.南京國家現(xiàn)代農(nóng)業(yè)產(chǎn)業(yè)科技創(chuàng)新中心，南京 211800；2.國家農(nóng)業(yè)信息化工程技術(shù)研究中心，北京 100097；3.智慧農(nóng)業(yè)技術(shù)集成與應(yīng)用創(chuàng)新農(nóng)業(yè)農(nóng)村部重點實驗室，南京 211800；4.廣西大學計算機與電子信息學院，南寧 530004）

1 引言

近年來，隨著生活水平的提高，人們對生鮮農(nóng)產(chǎn)品的需求不斷增加，我國的生鮮市場規(guī)模不斷擴大，對生鮮的冷鏈配送服務(wù)要求日益增加；由于冷鏈配送受交通狀況與配送地分散程度的影響較大，尤其在一線城市普遍面臨著生鮮配送成本高、配送訂單分散的問題。目前，我國大型生鮮供應(yīng)企業(yè)每日的貨物配送仍舊需要人工根據(jù)配送地址對配送車輛進行調(diào)度安排，耗費的人力時間成本較高，而且無法保證配送成本的最優(yōu)化。如今隨著物流技術(shù)[1]的快速發(fā)展，生鮮冷鏈配送的調(diào)度、路徑選擇正向智能化方向發(fā)展?；谝陨媳尘埃ㄟ^引入車輛路徑問題（Vehicle Routing Problem，VRP）[2]求解方法，研究生鮮冷鏈配送路徑優(yōu)化算法，對提高物流效率，降低成本具有重要意義。

冷鏈物流路徑優(yōu)化問題(Vehicle routing problem,VRP)于1959年提出后[2],成為運籌學與組合優(yōu)化領(lǐng)域的熱點問題，而生鮮農(nóng)產(chǎn)品物流作為冷鏈物流分支，也受到了學界的極大關(guān)注。生鮮農(nóng)產(chǎn)品物流涵蓋包裝、裝卸、運輸、儲存、加工和配送等多個環(huán)節(jié)，涉及從農(nóng)業(yè)生產(chǎn)到銷售終端，跨越不同行業(yè)及不同企業(yè)，參與主體多元、組織化程度不一，從業(yè)人員專業(yè)能力和知識水平參差不齊，加上農(nóng)產(chǎn)品運輸成本、儲存加工保鮮成本、流通中介費用等層層疊加，導(dǎo)致物流成本上升。在物流成本占比中，糧食類農(nóng)產(chǎn)品為40%左右，蔬菜、水果等生鮮農(nóng)產(chǎn)品超過60%[3]。國內(nèi)冷鏈物流近些年取得了高速發(fā)展[4]，但仍然存在冷鏈物流流通率較低、地區(qū)發(fā)展不均衡、冷鏈物流體制不健全，以及第三方物流發(fā)展緩慢等問題。當前，國內(nèi)冷鏈物流網(wǎng)絡(luò)優(yōu)化主要包括配送中心選址和配送路徑優(yōu)化兩個問題，對于冷鏈物流配送中心選址問題的研究，需要考慮的不確定變量較多，因此研究的范圍也比較廣泛，主要研究的還是被選擇的配送中心點與輻射半徑的距離之間的約束、用戶需求量與配送中心點之間的約束等問題，采用的方法也較多，包括采用啟發(fā)式算法[5]、混合算法[6]、元啟發(fā)式算法[7]、模擬退火算法[8]、禁忌搜索算法[9]、蜂群算法[10]等現(xiàn)代智能優(yōu)化算法。冷鏈物流配送路徑優(yōu)化問題的研究目前主要考慮對不同成本因子的約束研究，包括配送過程中的運輸成本、時間窗約束下的懲罰成本、貨損成本等，有的也考慮了碳排放成本[11-15]，王芳等對帶時間窗的多目標蔬菜運輸配送路徑優(yōu)化進行了研究[16],吳亮然等提出了基于車輛配送線路的區(qū)域協(xié)同配送方法[17],趙志學考慮擁堵區(qū)域的多車型綠色車輛路徑問題優(yōu)化[14],杜琛等將客戶滿意度和最小損耗加入了目標函數(shù)，對冷鏈配送路徑優(yōu)化問題進行了求解[18]，以上研究為本研究提供了求解參考。

綜上所述，當前的冷鏈物流車輛路徑優(yōu)化問題多以變化不同優(yōu)化因子作為研究目標函數(shù)，從而得出一種或多種約束因子的車輛路徑優(yōu)化模型。但針對大城市內(nèi)配送目的地分布范圍廣的場景，比如針對城市生鮮配送較為鮮見。陳棟等對跨省雛雞配送場景提出了訂單分群的求解方法[1]，為解決大城市生鮮配送路徑優(yōu)化問題提供研究思路。本研究通過引入K 均值聚類算法，根據(jù)配送目的地位置進行配送單元劃分，并以配送距離和貨物損耗最小、車輛使用數(shù)較少為目標函數(shù)，構(gòu)建生鮮配送路徑優(yōu)化模型，并使用改進的遺傳算法進行求解，以北京某生鮮農(nóng)產(chǎn)品供應(yīng)商實際配送車輛數(shù)據(jù)進行模型驗證。在此基礎(chǔ)上設(shè)計研發(fā)了適用于城市生鮮農(nóng)產(chǎn)品配送的車輛路徑優(yōu)化服務(wù)系統(tǒng)，實現(xiàn)了生鮮配送車輛調(diào)度優(yōu)化等功能。

2 模型構(gòu)建

2.1 問題描述

北京某生鮮農(nóng)產(chǎn)品企業(yè)每天負責北京各大商超的生鮮果蔬配送，配送的目的地跨越北京全市，地理位置跨度較大，每天需要針對不同配送需求進行車輛配送安排，并盡可能減少車輛所走的路程，同時需要滿足客戶的時間要求。本研究根據(jù)實際場景，對研究范圍進行約束如下：①此企業(yè)只有一個配送中心，每天所有生鮮果蔬貨物由此配送中心統(tǒng)一配送；②配送所使用的冷鏈車輛的型號、載重量、體積都相同；③配送的客戶目的地的位置固定，且每天的需求量一定；④配送安排盡可能達到路程最短，使用的配送車輛數(shù)量盡可能少。

2.2 模型構(gòu)建

基于以上問題的描述，構(gòu)建生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化目標函數(shù)，目標函數(shù)的約束條件為配送總里程、車輛數(shù)、時間窗約束條件，其數(shù)學表達如下。

一是確保每條路徑上各客戶的貨物需求量之和不超過配送車輛的載重量：

二是確保每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離：

三是確保每條路徑上的客戶數(shù)不超過總客戶數(shù)：

四是確保每個客戶都得到配送服務(wù)：

五是確保每條路徑的客戶的組成：

六是限制每個客戶僅能有一臺配送車輛送貨，當?shù)趉 輛車服務(wù)的客戶數(shù)≥1 時，說明該臺車參加了配送，則取sign(nk)=1，當?shù)趉輛車服務(wù)的客戶數(shù)＜1時,，表示未使用該臺車輛，則取sign(nk)=0。表達如下：

在本研究中，對于時間懲罰函數(shù)默認為一個常數(shù)，此參數(shù)不在本次研究中作為動態(tài)約束條件，為下一步深入研究做預(yù)留。

3 模型求解

3.1 求解流程

針對生鮮農(nóng)產(chǎn)品配送問題，本研究設(shè)計了兩種求解流程，一種是直接對所有配送訂單進行整體路徑優(yōu)化求解，如圖1 所示。①鮮配送訂單數(shù)據(jù)預(yù)處理，提取出訂單中訂單編號、地址（經(jīng)緯度）與訂單的需求量、客戶配送時間等信息；②將全部生鮮配送訂單信息與車輛信息作為參數(shù)輸入到遺傳算法中，按照優(yōu)化目標函數(shù)，匹配相應(yīng)的配送車輛，經(jīng)過算法的復(fù)制—交叉—變異等迭代操作，最終選擇表現(xiàn)最好的結(jié)果輸出。

圖1 整體優(yōu)化流程圖Fig.1 Overall optimization flow chart

另一種采用根據(jù)訂單目的地位置先進行聚類，然后分組進行路徑優(yōu)化求解，如圖2所示。

圖2 基于聚類的優(yōu)化求解流程圖Fig.2 Optimization flow chart based on clustering

①對生鮮配送訂單數(shù)據(jù)預(yù)處理，提取出訂單中訂單編號、地址（經(jīng)緯度）與訂單的需求量、客戶配送時間要求等信息；②根據(jù)配送目的地的經(jīng)緯度信息，采用基于位置的K均值的聚類方法，對生鮮配送訂單進行聚類劃分小組，形成多個訂單配送單元。③將劃分好的訂單配送單元中的配送信息作為算法參數(shù)進行輸入，調(diào)度優(yōu)化算法基于遺傳算法對每個訂單配送單元的配送信息按照目標函數(shù)進行求解，最終選擇表現(xiàn)最好的結(jié)果輸出。④將對每個訂單配送單元優(yōu)化的結(jié)果進行合并后輸出。

3.2 配送目的地聚類方法

在3.1 小節(jié)中，采用根據(jù)訂單目的地位置先進行聚類，然后分組進行路徑優(yōu)化求解。本研究采用K均值聚類算法根據(jù)配送訂單目的地經(jīng)緯度進行配送訂單位置聚類。K 均值聚類算法是一種非層次聚類算法，在最小誤差的基礎(chǔ)上將數(shù)據(jù)劃分了特定的類，類間利用距離作為相似度指標，兩個向量之間的距離越小，其相似度就越高[1]。其算法求解過程中，關(guān)鍵是確定K 的值，本研究使用肘部法與輪廓系數(shù)確定K的值。

本研究選用了北京某生鮮供應(yīng)企業(yè)的209 個真實訂單數(shù)據(jù)，其訂單的位置散點分布如圖3所示。

圖3 訂單位置散點圖Fig.3 Order Position Scatter Chart

通過肘部法確定聚類K（最終的簇數(shù)）值，如圖4所示。取不同K值的平均畸變程度曲線，曲線曲率最高的K值范圍在8～15之間。

圖4 K均值聚類肘部法則平均畸變曲線Fig.4 K-means clustering elbow rule average distortion curve

通過輪廓系數(shù)法確定K（最終的簇數(shù)）值，如圖5所示。由此確定K=10，系數(shù)最大。

圖5 K取不同值對應(yīng)的聚類效果圖Fig.5 Clustering effect with different K values

3.3 遺傳算法求解過程

通過對遺傳算法進行改進，實現(xiàn)對生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化的求解，結(jié)合實際生鮮果蔬訂單配送路徑優(yōu)化問題，確定問題求解的具體流程如下。

算法參數(shù)與數(shù)據(jù)初始化，對種群規(guī)模Population-Size、交叉概率Pc、變異概率Pm、進化代數(shù)GenerationNum 以及懲罰函數(shù)Pw 等參數(shù)進行初始化設(shè)置，提取生鮮農(nóng)產(chǎn)品配送訂單中的訂單編號、訂單經(jīng)緯度、訂單的貨物需求量等數(shù)據(jù)。②初始化種群，對種群個體進行編碼，生成對應(yīng)規(guī)模的種群矩陣。③計算種群中每個個體的目標函數(shù)值，根據(jù)目標函數(shù)值確定每個個體的適應(yīng)度，選取適應(yīng)度最優(yōu)的個體保留。④對種群中的個體進行交叉、變異操作，生成新的種群。⑤重復(fù)③—④步，直到滿足進化代數(shù)。⑥將適應(yīng)度最優(yōu)（適應(yīng)度值最?。┑膫€體作為最優(yōu)解輸出。

4 結(jié)果分析與模型應(yīng)用

4.1 數(shù)據(jù)的初始化及求解過程

本研究選用北京某生鮮供應(yīng)商的209 條配送訂單數(shù)據(jù)作為樣本數(shù)據(jù)。數(shù)據(jù)項包含訂單編號、客戶姓名、配送時間、最后達到時間、地址、經(jīng)度、緯度、農(nóng)產(chǎn)品數(shù)量、農(nóng)產(chǎn)品重量、農(nóng)產(chǎn)品體積、出貨倉庫編號、出貨倉庫名稱、客戶是否為VIP。篩選訂單編號、經(jīng)度、緯度、農(nóng)產(chǎn)品重量、農(nóng)產(chǎn)品體積、出貨倉庫地址數(shù)據(jù)項作為求解數(shù)據(jù)，數(shù)據(jù)概要如圖6所示。

圖6 實驗數(shù)據(jù)概要圖Fig.6 Schematic diagram of experimental data

求解過程如下：

（1）種群初始化：以配送訂單的順序作為一個種群的個體，即一個染色體。

（2）種群描述矩陣：生成一個矩陣，一行代表種群中一個個體，列代表客戶訂單編號。矩陣如下所示：

（3）結(jié)合實際情況，對配送車輛進行數(shù)字化描述，規(guī)定只有一種類型的車輛，載重為8噸、容積為50立方米；車輛數(shù)量滿足當日訂單數(shù)。

（4）求解：①數(shù)據(jù)初始化。②初始化種群生成。③計算種群適應(yīng)度：fitness-個體路徑的總里程，取倒數(shù)fitness=1/evaluation;一般適應(yīng)度越大越好，在總里程中約束中是越小越好，故在此去倒數(shù)。④計算種群中各個個體的累計概率:。⑤記錄種群中適應(yīng)度最好的個體。⑥生成新的種群：選擇上一代中最優(yōu)個體作為新種群的第一個個體，另外使用輪盤賭法選擇生成剩余m-1 個個體；按照交叉概率Pc 使用OX交叉法對種群進行交叉；按照變異概率Pm 對種群中個體進行變異。⑦判斷種群的代數(shù)是否達到設(shè)置數(shù)。不滿足則重復(fù)執(zhí)行③-⑦；滿足則輸出最優(yōu)的個體，求解結(jié)束。

（5）對遺傳算法參數(shù)進行設(shè)置：種群數(shù)量為200個，交叉概率為0.5，變異概率為0.05，迭代次數(shù)為10000 次。經(jīng)過以上求解步驟，得到適應(yīng)度曲線，如圖7所示，在種群迭代進化5000次后，趨于平緩。

4.2 求解結(jié)果比較與分析

基于以上求解步驟，分別對整體路徑優(yōu)化求解結(jié)果和經(jīng)聚類后的路徑優(yōu)化求解，如圖8 所示，未聚類與聚類的配送區(qū)分明顯，使用聚類的方法對配送訂單分布更清晰。

圖8 配送訂單聚類前后效果對比圖Fig.8 Comparison of the effect before and after the clustering of delivery orders

如表1 所示。對比兩種方式的求解結(jié)果，配送優(yōu)化總里程和車輛使用數(shù)量，由表中可以看出，未經(jīng)聚類的優(yōu)化里程平均3753.01Km，使用車輛數(shù)平均32輛；經(jīng)聚類的優(yōu)化里程平均2105.4Km，使用車輛數(shù)平均輛34 輛；在車輛使用數(shù)量相差不大情況下，配送運行總里程大幅度降低。結(jié)果顯示使用聚類的方式具有合理性。

表1 不同算法求解算例計算結(jié)果Table 1 Calculation results of examples solved by diferent algorithms

4.3 模型應(yīng)用

本研究通過基于以上研究，設(shè)計研發(fā)了適用于城市生鮮農(nóng)產(chǎn)品配送的車輛路徑優(yōu)化服務(wù)系統(tǒng)，實現(xiàn)了生鮮配送車輛調(diào)度優(yōu)化等功能，為生鮮供應(yīng)企業(yè)減低配送成本，提升企業(yè)效率提供了科技支撐。系統(tǒng)采用B/S架構(gòu)，將模型打包成服務(wù)，提供API調(diào)用接口的形式來為生鮮供應(yīng)企業(yè)服務(wù)。系統(tǒng)功能運行流程如圖9所示。

圖9 配送路徑優(yōu)化服務(wù)流程Fig.9 Optimizing service progress

系統(tǒng)的服務(wù)API接口與應(yīng)用實例如圖10所示。

圖10 系統(tǒng)服務(wù)實例Fig.10 System running instance

5 結(jié)果與建議

本研究針對生鮮農(nóng)產(chǎn)品城市配送場景，針對其配送訂單分散，配送成本高，配送路線選擇人工依賴性強的問題，提出了基于K均值聚類算法的生鮮運輸路徑優(yōu)化模型，通過引入K 均值聚類算法，實現(xiàn)了根據(jù)配送目的地位置的配送單元劃分，并以配送距離和貨物損耗最小、車輛使用數(shù)量較少的情況做為目標函數(shù)，構(gòu)建生鮮配送路徑優(yōu)化模型，模型使用改進的遺傳算法進行求解。通過對北京某生鮮供應(yīng)企業(yè)實際的配送訂單的數(shù)據(jù)分析與求解，分別對未聚類與聚類情況下的求解結(jié)果進行對比，結(jié)果顯示配送目的地不進行聚類情況下配送的里程平均為3753.01 公里，使用的車輛數(shù)量平均為32 輛；在對配送目的地進行聚類情況下配送的里程平均為2105.4公里，使用過的車輛數(shù)量平均為34 輛；在使用車輛數(shù)量增幅不多的條件下對配送目的地聚類分組后模型讓配送總里程比未進行聚類分組的情況降低了43.9%。通過對城市生鮮農(nóng)產(chǎn)品配送的車輛路徑優(yōu)化服務(wù)系統(tǒng)的設(shè)計與研發(fā)實現(xiàn)了生鮮配送車輛調(diào)度優(yōu)化服務(wù)功能，為生鮮供應(yīng)企業(yè)降低配送成本和提升企業(yè)效率提供了技術(shù)支撐。

本研究對大城市范圍的生鮮配送路徑優(yōu)化問題中的訂單位置聚類問題進行了深入的研究，其優(yōu)化的約束條件只考慮了配送總里程與配送車輛，在下一步研究中，將對配送時間窗、碳排放等約束條件以及考慮不同聚類算法的使用對優(yōu)化結(jié)果影響性進行研究。