基于K-means和蟻群算法的配送網(wǎng)絡(luò)優(yōu)化問(wèn)題研究
——以南平延平區(qū)J速遞公司為例

宋李玉，黃建華

（福建林業(yè)職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)管理系，福建 南平 353000）

隨著電子商務(wù)的迅猛發(fā)展，快遞包裹配送業(yè)務(wù)量大大增加。福建省南平市延平區(qū)地處山區(qū)，城市交通線路復(fù)雜且客戶需求隨機(jī)無(wú)法預(yù)測(cè)。另一方面，延平區(qū)大多數(shù)快遞企業(yè)在網(wǎng)點(diǎn)布局、配送區(qū)域劃分及配送線路選擇等方面帶有隨意性，普遍依據(jù)配送員的主觀判斷，缺乏科學(xué)規(guī)劃，配送效率并不高。

在配送線路優(yōu)化方面，國(guó)內(nèi)外提出了貪婪啟發(fā)式算法、遺傳算法、蟻群算法、聚類算法等體系模型求解算法，進(jìn)行了較為豐富的研究。Lawrence 等[1]（P488-490）首次采用傳統(tǒng)遺傳算法求解車輛路徑調(diào)度問(wèn)題。Clarke等[2]（P568-581）運(yùn)用貪婪啟發(fā)式算法研究了VRP問(wèn)題。Dorrigo等[3]（P73-81）詳細(xì)闡述了旅行商問(wèn)題 (Travelling Salesman Problem)，并首創(chuàng)蟻群算法進(jìn)行求解。Bullnheimer 等[4]（P319-328）把蟻群算法應(yīng)用于VRP問(wèn)題研究。張令甜等［5］（P7-12）從南昌市某生鮮電商公司面臨的同城生鮮農(nóng)產(chǎn)品配送線路優(yōu)化問(wèn)題入手，建立數(shù)學(xué)模型，創(chuàng)造性地設(shè)計(jì)混合遺傳算法求解配送線路優(yōu)化問(wèn)題。蔣麗等[6]（P244-249）以O(shè)2O外賣平臺(tái)的眾包配送路徑優(yōu)化為研究對(duì)象，建立帶有單側(cè)軟時(shí)間窗的、需求可延遲的開(kāi)放式車輛路徑優(yōu)化模型，改進(jìn)蟻群算法將下一步移動(dòng)的潛在客戶數(shù)量作為路徑選擇的影響因素，對(duì)配送路徑進(jìn)行優(yōu)化。閻宇婷[7]對(duì)我國(guó)快遞行業(yè)的區(qū)域劃分做了詳細(xì)探究，采用改進(jìn)FCM聚類算法劃分配送范圍內(nèi)的客戶點(diǎn)，并通過(guò)車輛配載量檢驗(yàn)劃分結(jié)果是否符合目標(biāo)條件。以上研究方法為本次研究提供了方法支撐。本次研究以J速遞公司的延平區(qū)配送網(wǎng)絡(luò)為例，通過(guò)K-means聚類法進(jìn)行配送區(qū)域劃分，并應(yīng)用蟻群算法對(duì)每一個(gè)配送區(qū)域內(nèi)的配送線路進(jìn)行優(yōu)化，以此為延平區(qū)和福建其他山區(qū)城鎮(zhèn)快遞行業(yè)配送線路優(yōu)化提供參考借鑒。

一、J速遞公司配送網(wǎng)絡(luò)基本情況

J速遞公司是一家互聯(lián)網(wǎng)快遞企業(yè)，福建代理業(yè)務(wù)經(jīng)營(yíng)范圍已覆蓋含延平區(qū)在內(nèi)的41個(gè)縣（市、區(qū)），設(shè)有5個(gè)集包中心，68個(gè)營(yíng)業(yè)網(wǎng)點(diǎn)。延平區(qū)轄15個(gè)鄉(xiāng)鎮(zhèn)，6個(gè)街道辦事處，總?cè)丝?9.5萬(wàn)人，面積2659.66平方公里。目前，J速遞公司在延平區(qū)設(shè)有1個(gè)中轉(zhuǎn)站（以T表示）和22個(gè)自提點(diǎn)。來(lái)自外地的貨物通過(guò)集包中心分撥，到達(dá)T點(diǎn)后再轉(zhuǎn)向22個(gè)自提點(diǎn)，見(jiàn)表1。J速遞公司在延平區(qū)平時(shí)的配送包裹量穩(wěn)定在3500～4000件，若遇“雙11”等活動(dòng)，包裹量可達(dá)平時(shí)的2.5倍左右，見(jiàn)表2～3。

表1 J速遞公司中轉(zhuǎn)站及自提點(diǎn)地理坐標(biāo)

表2 2020年8月份J速遞公司在延平區(qū)的配送包裹量

表3 2020年8月份J速遞公司在延平區(qū)各自提點(diǎn)的最大包裹量

二、基于K-means聚類法劃分配送區(qū)域?qū)崿F(xiàn)分區(qū)配送

本文通過(guò)SPSS中K-均值的功能來(lái)實(shí)現(xiàn)J速遞公司中轉(zhuǎn)站的配送區(qū)域劃分。K-means聚類分析其本質(zhì)就是非系統(tǒng)聚類法中的K-均值聚類法。首先將22個(gè)自提點(diǎn)的序號(hào)、地理坐標(biāo)輸入到SPSS中，以自提點(diǎn)的地理坐標(biāo)作為標(biāo)簽變量，然后根據(jù)李軍[8]（P28-34）所提出的確立車輛數(shù)公式確定中轉(zhuǎn)站的車輛數(shù)：

其中，α為參數(shù)，是對(duì)貨物裝卸復(fù)雜程度和約束條件多少的估計(jì)。通常來(lái)講，約束越多，裝卸越復(fù)雜，則α越小。“[]”表示計(jì)算結(jié)果取整數(shù)。qi表示各個(gè)自提點(diǎn)的需求量，Q表示車輛最大配載量。本文α取0.95，車輛最大配載量取1000個(gè)單位。結(jié)合表3可計(jì)算出本文m={5,6}。根據(jù)確定的車輛數(shù)來(lái)確立初始的聚類中心個(gè)數(shù)，即 k={5,6}。

通過(guò)SPSS聚類完成后，需要對(duì)每個(gè)類別中自提點(diǎn)需求量進(jìn)行加總，檢驗(yàn)各點(diǎn)需求量是否大于車輛的最大配載量。為了保證不出現(xiàn)需求量大于車輛裝載量的情況，在每個(gè)自提點(diǎn)加入時(shí)，都會(huì)檢驗(yàn)總的載貨量是否超標(biāo)，若超出則該類別會(huì)彈出一個(gè)犧牲點(diǎn)。犧牲點(diǎn)的選擇依據(jù)是距離聚類中心最遠(yuǎn)的樣品點(diǎn)。然后，將該點(diǎn)加入到另一個(gè)類別中，直至沒(méi)有犧牲點(diǎn)彈出。具體實(shí)施步驟如下：

（1）讀取自提點(diǎn)的相關(guān)數(shù)據(jù)：自提點(diǎn)數(shù)量、各自提點(diǎn)的需求量以及自提點(diǎn)的地理坐標(biāo)值。

（2）計(jì)算中轉(zhuǎn)站所需車輛數(shù)，確定初始聚類中心。

（3）執(zhí)行分類操作，直至所有自提點(diǎn)被分類完為止。

（4）檢驗(yàn)各個(gè)區(qū)域內(nèi)自提點(diǎn)的需求量是否超出車輛最大載貨量。若超出，執(zhí)行步驟（5），反之執(zhí)行步驟（9）。

（5）將距離聚類中心點(diǎn)最遠(yuǎn)的自提點(diǎn)剔除，直至區(qū)域內(nèi)的各自提點(diǎn)需求量之和符合容量限制標(biāo)準(zhǔn)。

（6）檢驗(yàn)是否存在其他類別區(qū)域有多余的容量。如果存在，則執(zhí)行步驟（7），若不存在多余容量的類別，則執(zhí)行步驟（8）。

（7）在不影響其他類別容量的同時(shí)，將被剔除的自提點(diǎn)就近加入該類別，執(zhí)行步驟（9）。

（8）為中轉(zhuǎn)站增加一輛車服務(wù)，即M=m+1,回到步驟（3）。

（9）分類結(jié)束。

根據(jù)上述步驟運(yùn)行自提點(diǎn)的聚類過(guò)程，當(dāng)k=5時(shí)，運(yùn)行結(jié)果如圖1和表4。將上面的運(yùn)行結(jié)果在配送網(wǎng)絡(luò)圖上表示出來(lái)，如圖2。

圖1 每個(gè)聚類中的案例數(shù)（k=5）

圖2 K-means(k=5)聚類分析區(qū)域劃分圖

表4 K-means(k=5)聚類分析運(yùn)行結(jié)果

（續(xù)表 4）

根據(jù)上述區(qū)域劃分結(jié)果，檢驗(yàn)各區(qū)域內(nèi)自提點(diǎn)需求量是否超出車輛最大配載量，檢查結(jié)果如表5。經(jīng)查，各個(gè)區(qū)域1和4內(nèi)自提點(diǎn)的需求量超出車輛最大載貨量，k=5聚類方式不合理。將距離聚類中心點(diǎn)最遠(yuǎn)的自提點(diǎn)剔除，直至區(qū)域內(nèi)各自提點(diǎn)需求量之和符合容量限制標(biāo)準(zhǔn)。在不影響其他類別容量的同時(shí)，將被剔除自提點(diǎn)就近加入容量未滿的類別，得到修正后聚類結(jié)果見(jiàn)表6。當(dāng)k=6時(shí)，運(yùn)行結(jié)果如圖3和表7，將結(jié)果在配送網(wǎng)絡(luò)圖上表示出來(lái)，如圖4。根據(jù)區(qū)域劃分結(jié)果，檢驗(yàn)各區(qū)域內(nèi)自提點(diǎn)需求量是否超出車輛最大配載量，見(jiàn)表8。經(jīng)查，各區(qū)域1和5內(nèi)自提點(diǎn)的需求量超出車輛最大載貨量，k=6的聚類方式需修正。將距離聚類中心點(diǎn)最遠(yuǎn)的自提點(diǎn)剔除，直至區(qū)域內(nèi)各自提點(diǎn)需求量之和符合容量限制標(biāo)準(zhǔn)。在不影響其他類別容量的同時(shí)，將被剔除自提點(diǎn)就近加入容量未滿類別，得到修正后聚類結(jié)果為表9。

圖3 每個(gè)聚類中的案例數(shù)（k=6）

表5 K-means(k=5)聚類分析結(jié)果

表6 K-means(k=5)修正后的聚類分析結(jié)果

表7 K-means（k=6）聚類分析運(yùn)行結(jié)果

圖4 K-means（k=6）聚類分析區(qū)域劃分圖

表8 K-means(k=6)聚類分析結(jié)果

表9 K-means(k=6)修正后的聚類分析結(jié)果

比較k=5和k=6的聚類情況，k=6時(shí)類別6只有三個(gè)自提點(diǎn)為K，自提點(diǎn)需求量為340，而車輛最大配載量為1000，則在中轉(zhuǎn)站配送過(guò)程中會(huì)造成運(yùn)力浪費(fèi)，而k=5時(shí)則更加均衡，因此，采取聚類數(shù)為5的聚類方案，新的配送網(wǎng)絡(luò)圖分區(qū)如圖5。在運(yùn)行程序之前，先整理相關(guān)數(shù)據(jù)。根據(jù)圖5，可計(jì)算出區(qū)域內(nèi)各點(diǎn)的最短距離如表 10～14。

圖5 K-means（k=5）新的聚類分析區(qū)域劃分圖

表10 區(qū)域C內(nèi)各點(diǎn)之間的最短距離

表11 區(qū)域F內(nèi)各點(diǎn)之間的最短距離

表12 區(qū)域H內(nèi)各點(diǎn)之間的最短距離

表13 區(qū)域B內(nèi)各點(diǎn)之間的最短距離

表14 區(qū)域A內(nèi)各點(diǎn)之間的最短距離

三、基于蟻群算法的配送路徑優(yōu)化

為使蟻群算法在求解旅行商問(wèn)題時(shí)，更加貼近延平地區(qū)的實(shí)際路況。根據(jù)各點(diǎn)的最短距離，以中轉(zhuǎn)站T為坐標(biāo)原點(diǎn)，生成新的坐標(biāo)圖，再將區(qū)域內(nèi)各點(diǎn)的坐標(biāo)數(shù)據(jù)輸入算法。得到仿真運(yùn)行結(jié)果如圖6～10。

圖6 區(qū)域C蟻群算法運(yùn)行結(jié)果示意圖

圖7 區(qū)域F蟻群算法運(yùn)行結(jié)果示意圖

圖8 區(qū)域H蟻群算法運(yùn)行結(jié)果示意圖

圖9 區(qū)域B蟻群算法運(yùn)行結(jié)果示意圖

圖10 區(qū)域A蟻群算法運(yùn)行結(jié)果示意圖

由上圖可以得出各區(qū)域的最優(yōu)配送軌跡圖，并根據(jù)區(qū)域內(nèi)各點(diǎn)的最短距離表得到準(zhǔn)確的最短路程。若在MATLAB中運(yùn)行的最短路程與實(shí)際的最短路程有偏差，則以實(shí)際距離為準(zhǔn)。

四、結(jié)論

本文通過(guò)蟻群算法求解J速遞公司延平地區(qū)5個(gè)區(qū)域的最優(yōu)配送路徑，在求解過(guò)程中，充分考慮了各點(diǎn)之間的實(shí)際道路情況，將兩點(diǎn)之間的可達(dá)性問(wèn)題考慮在內(nèi)。因此，求解的路徑更加貼合延平地區(qū)的實(shí)際道路狀況，而不是簡(jiǎn)單地將各點(diǎn)之間的直線距離作為兩個(gè)自提點(diǎn)之間的實(shí)際距離。

從最優(yōu)配送路徑來(lái)看，區(qū)域C的最短路徑為：T-E-D-C-T，最短路程為 3.726km；區(qū)域 F的最短路徑為：T-L-M-G-F-T，最短路程為70.138km；區(qū)域H的最短路徑為：T-J-K-I-HT，最短路程為35.28km；區(qū)域B的最短路徑為：T-S-U-V-W-B-T，最短路程為46.27km；區(qū)域A的最短路徑為：T-A-N-P-O-Q-R-T，最短路程為90.36km。通過(guò)配送線路優(yōu)化將多配送員、小批量、散亂的配送方式，變更為少配送員、大批量、系統(tǒng)的配送方式，將為速遞企業(yè)縮短配送距離、節(jié)約配送成本、縮短配送時(shí)間，進(jìn)而提高服務(wù)質(zhì)量。