基于距離矩陣摹乘法的生鮮產(chǎn)品配送路徑優(yōu)化

涂志芳子, 羊 英

(上海第二工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院,上海201209)

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展,網(wǎng)絡(luò)應(yīng)用幾乎滲透到生活的各個方面,促進(jìn)了商品交易與互聯(lián)網(wǎng)結(jié)合的線上線下(online to offline business, O2O)模式的發(fā)展。同時,近年來隨著生活水平的不斷提升,人們對新鮮水果蔬菜等生鮮產(chǎn)品的需求也出現(xiàn)快速增長的趨勢。而O2O 模式下的生鮮產(chǎn)品電子商務(wù)充分利用互聯(lián)網(wǎng)信息的即時性和互動性等一系列特點(diǎn),為消費(fèi)者節(jié)省時間并提供生活上的便利。

前瞻產(chǎn)業(yè)研究院調(diào)查數(shù)據(jù)表明,中國的生鮮市場交易額自2011 年起一直逐年上升, 2012 年之后我國生鮮市場交易額保持在6.5%左右的增速,2017年我國生鮮市場交易規(guī)模達(dá)1.79 萬億元, 同比增長6.5%。預(yù)計2020 年生鮮市場交易額將達(dá)到2.16萬億元。由此可知, 中國生鮮市場還有很大的發(fā)展空間, 人們對生鮮產(chǎn)品的需求不斷上升。同時通過O2O 模式下的生鮮電商平臺購買生鮮產(chǎn)品的人數(shù)越來越多,且使用次數(shù)越發(fā)頻繁,人們能夠接受甚至習(xí)慣以網(wǎng)購形式獲取所需生鮮商品。這也代表著生鮮產(chǎn)品配送物流在整個物流行業(yè)中的占比會逐漸提升,而配送環(huán)節(jié)也將在生鮮電商平臺運(yùn)營中發(fā)揮更加關(guān)鍵的作用。

但由于生鮮產(chǎn)品易腐爛、儲存要求高等特性,消費(fèi)者對生鮮產(chǎn)品新鮮度的需求,對該模式下生鮮產(chǎn)品的配送物流提出了較高要求?？s短配送距離不僅可以幫助O2O 模式下的商戶對平臺更有效的運(yùn)營,還能提升用戶體驗(yàn)感,進(jìn)一步促進(jìn)生鮮電商行業(yè)的發(fā)展。

近年來,生鮮產(chǎn)品物流問題得到了許多學(xué)者的關(guān)注。韓超[1]構(gòu)建了依靠云配送互聯(lián)網(wǎng)平臺的O2O農(nóng)產(chǎn)品物流資源配置和貨運(yùn)配送系統(tǒng)以提高農(nóng)產(chǎn)品配送效率。白羽[2]運(yùn)用超效率基于松弛的效率評價(slack based measure,SBM)模型對送貨上門、智能配送柜、第三方代收3 種物流終端配送模式效率進(jìn)行對比分析,并對生鮮產(chǎn)品的物流終端配送進(jìn)行了方案設(shè)計。張瑜[3]對生鮮農(nóng)產(chǎn)品冷鏈物流配送網(wǎng)絡(luò)優(yōu)化進(jìn)行了研究,采用了節(jié)約成本算法。胡靜怡等[5]對生鮮電商“最后一公里”配送問題進(jìn)行了探討,提出了配送優(yōu)化方案;Nakandala 等[6]考慮生鮮產(chǎn)品質(zhì)量和運(yùn)輸建立了成本優(yōu)化模型;唐佩佩等[8]將遺傳算法結(jié)合MATLAB 語言求得合理的車輛行駛路徑以縮短配送時間;孟成斐等[9]基于最短路思想運(yùn)用距離矩陣摹乘法對無水港進(jìn)行區(qū)位分析,確定陜西地區(qū)無水港的選址; 湯齊等[10]針對生鮮產(chǎn)品配送對車輛路徑優(yōu)化進(jìn)行研究,在時間約束條件下以求得最小配送成本。

通過對已有文獻(xiàn)的研究發(fā)現(xiàn),目前尚未發(fā)現(xiàn)將距離矩陣摹乘法用于對生鮮產(chǎn)品配送路徑進(jìn)行優(yōu)化的文章。該方法對某一特定區(qū)域較密集的配送網(wǎng)絡(luò)距離的縮短效果較好,所以本文擬對區(qū)域內(nèi)生鮮產(chǎn)品配送點(diǎn)的布局和配送路線優(yōu)化進(jìn)行研究,以縮短配送距離提高配送效率從而降低配送成本。

1 生鮮電商配送問題分析

1.1 配送中心覆蓋率不高

目前大部分生鮮產(chǎn)品供應(yīng)商因?yàn)榭紤]到人口密度、交通狀況和產(chǎn)品保鮮度等問題,大多將配送中心設(shè)置在市中心或人口密集區(qū)域,并設(shè)置配送區(qū)域,從而使得許多超出配送區(qū)域的社區(qū)得不到服務(wù),而對生鮮產(chǎn)品有需求或潛在需求的人口覆蓋率也不高。

1.2 運(yùn)力調(diào)度不均衡

物流配送中心經(jīng)常出現(xiàn)這樣的情況,有的配送車輛滿負(fù)荷運(yùn)轉(zhuǎn),有的車輛長期擱置不用,而有的車輛平均滿載率低, 造成一定程度的運(yùn)力浪費(fèi)[7]。同時也會出現(xiàn)配送中心調(diào)度不夠協(xié)調(diào),一輛車已經(jīng)將貨物配送完成,而下一個客戶就在某個配送點(diǎn)附近,卻又需要返回配送中心再取貨或者調(diào)度其他車輛完成配送。

O2O 模式下的電商運(yùn)營中,配送物流是用戶整個購買過程中的末端環(huán)節(jié), 也是很關(guān)鍵的部分。生鮮產(chǎn)品對于運(yùn)輸時間的要求較高,在配送過程中,配送中心的位置和配送速度決定著用戶收到商品的時間長短,進(jìn)而影響客戶對生鮮產(chǎn)品的用戶體驗(yàn)。

2 生鮮產(chǎn)品配送路徑優(yōu)化方法研究

2.1 問題描述

配送路徑的優(yōu)化即在配送中心到用戶地理位置的幾條路徑中選出最短路徑,節(jié)約配送時間,以便配送人員快速將商品送至客戶手中。配送路徑的問題一直困擾著生鮮電商,配送過程中若沒有選擇最短路徑容易造成配送超時,一方面影響用戶的體驗(yàn),另一方面也會增加配送成本,甚至可能影響整個物流體系。

假設(shè)某地區(qū)有n 個配送中心和m 個社區(qū),求不同的配送中心將商品送至不同社區(qū)的最短路徑; 采用距離矩陣摹乘法求配送網(wǎng)絡(luò)中各點(diǎn)至各點(diǎn)的最短路來規(guī)劃“最后一公里”的周邊地區(qū)的最優(yōu)配送路徑。距離矩陣摹乘法是運(yùn)籌學(xué)中一種用以解決最短路問題的典型方法,可以求解某一路徑網(wǎng)絡(luò)中各點(diǎn)至某一定點(diǎn)、某一定點(diǎn)至各點(diǎn)及各點(diǎn)至各點(diǎn)之間的最短距離。

O2O 有極強(qiáng)的地域?qū)傩?它既不同于傳統(tǒng)電商,又有別于線下商業(yè),在空間尺度有差異;和傳統(tǒng)電商相比,O2O 注重本地消費(fèi),而在很多情況下本地消費(fèi)配對本地用戶是更高效的方式,故在某一特定區(qū)域的各訂單的配送中,路徑優(yōu)化這一步驟顯得尤為重要。在本地密集且錯綜復(fù)雜的配送網(wǎng)絡(luò)中, 距離矩陣摹乘迭代可以更精確有效地求出配送最短距離,節(jié)省配送時間并節(jié)約配送資源,使商戶的運(yùn)營狀況和用戶的客戶體驗(yàn)達(dá)到雙贏。

一步距離矩陣方法求解如下: 記矩陣Dk=(d(ijk))m×n為k 步距離矩陣, 即網(wǎng)絡(luò)中各點(diǎn)最多經(jīng)過k 步到達(dá)其他各點(diǎn)的最短距離矩陣, 則D1=(d(ij1))m×n=W。

式中: Dk表示至多經(jīng)過k 步到達(dá)各點(diǎn)之間的最短距離矩陣,Dk?1表示至多經(jīng)過k ?1 步到達(dá)各點(diǎn)之間的最短距離矩陣;而

式中: d(ijk)為vi到vj經(jīng)過k 步的最短距離; d(isk?1)為vi到vs經(jīng)過k ?1 步的最短距離;d(skj?1)為vs到vj經(jīng)過k ?1 步的最短距離; vi, vj, vs為網(wǎng)絡(luò)中各點(diǎn)。

若計算中出現(xiàn)Dk= Dk?1, 則停止計算,表示到了k ?1 步以后,再走一步并不能有任何作用,從而求得從各點(diǎn)到各點(diǎn)的最短距離。從而計算出各個配送中心到各個社區(qū)的最短距離,進(jìn)而劃分哪些社區(qū)由哪個配送中心負(fù)責(zé)配送,之后不同社區(qū)發(fā)出的訂單需求就可以有條不紊由最近配送中心安排配送,由此減少配送成本。

2.2 求解步驟

計算過程如下:

(1)測出各點(diǎn)之間的距離,得到一步距離矩陣

式中: D1和W 為網(wǎng)絡(luò)中各點(diǎn)到各點(diǎn)的一步距離矩陣; d(ij1)為vi到vj經(jīng)過1 步的距離; vi,vj(i,j =1,··· ,n)為網(wǎng)絡(luò)中各點(diǎn)。

(2)通過距離矩陣摹乘迭代得到二步距離矩陣

式中: d(is1)為vi到vs走一步的距離;d(s1j)為vs到vj走一步的距離。

(3)用第二步所得結(jié)果進(jìn)行下一步的摹乘迭代得到三步距離矩陣,以此類推,直到Dk= Dk?1,即(d(ijk))m×n= (d(ijk?1))m×n時, 則可獲得最后的點(diǎn)到點(diǎn)最短距離矩陣,而對應(yīng)的d(ijk)為vi到vj的最短距離。

3 每日優(yōu)鮮(v1)物流配送體系案例

3.1 物流配送現(xiàn)狀

生鮮電商一直被看作是電商行業(yè)中的最后一片藍(lán)海,但我國生鮮電商由于冷鏈物流基礎(chǔ)設(shè)施建設(shè)滯后, 損耗率居高不下等原因發(fā)展不太理想。目前我國大部分生鮮電商的產(chǎn)品損耗率都在10%以上,有的甚至高達(dá)30%[7]。

為了降低損耗率,每日優(yōu)鮮平臺選擇采用“前置倉模式”,在華北、華東、華南等地區(qū)建立城市分選中心,并根據(jù)訂單密度在商圈和社區(qū)建立前置倉即配送中心,每個配送中心覆蓋周邊半徑3 km。商品在入庫后,經(jīng)過城市分選中心的品控、分選、加工等環(huán)節(jié),根據(jù)智能補(bǔ)貨系統(tǒng)提供的補(bǔ)貨系數(shù),被分發(fā)到各個前置倉,全程通過冷鏈物流運(yùn)輸。用戶下單后,配送員從前置倉提貨,保證了商品的新鮮品質(zhì)和交付速度。但是從前置倉將商品送至用戶手中這一配送過程,俗稱“配送的最后一公里”,如果沒有進(jìn)行路徑優(yōu)化,同樣會給平臺增加配送成本。以下對這“最后一公里”的配送路徑優(yōu)化問題進(jìn)行研究。

3.2 v1 配送路徑優(yōu)化

選擇v1在浦東新區(qū)曹路鎮(zhèn)的配送路徑進(jìn)行優(yōu)化。該平臺在曹路鎮(zhèn)設(shè)置的前置倉為位于川沙路的錦繡東路店, 該配送中心覆蓋周邊半徑3 km, 以下社區(qū)在其配送范圍內(nèi):豐怡苑(v2)、龔新西苑(v3)、諧苑(v4)、龔路新城(v5)、河濱城市花園(v6)、金海華城永華苑(v7)、萬科第五園(v8)、星曉家園(v9)、金鉆苑(v10)、陽光花城同景園(v11)、睿翔園(v12)、大灣名苑(v13)、鑫港苑(v14)、鉑尊公寓(v15)、銀豐苑(v16)。通過高德地圖算出配送中心與各社區(qū)及社區(qū)與社區(qū)之間的實(shí)際距離, 如表1 所示。因考慮到算例中調(diào)查的曹路鎮(zhèn)區(qū)域的道路正反向都能進(jìn)行配送, 故此為雙向矩陣, 表1 中上三角和下三角數(shù)據(jù)對稱。

表1 v1 與社區(qū)各點(diǎn)間的距離(單位: km)Tab.1 The distances between v1 and communities(unit: km)

在v1的算例中, d(1)ij表示vi到vj兩地區(qū)在模型優(yōu)化前的初始距離。

例設(shè)v1～v10(西北門) 的初始距離d(1)1.10=2.7 km,對其進(jìn)行優(yōu)化:

(1) 測算各點(diǎn)之間的距離, 其中v1～v10(西北門)的初始距離d(11.1)0=2.7;

(2)利用D1的數(shù)據(jù)進(jìn)行摹乘迭代

v1至各點(diǎn)的初始距離分別為:

各點(diǎn)到達(dá)v10(西北門)的初始距離分別為:

將兩列單位矩陣相同位置數(shù)據(jù)相加:

選取數(shù)據(jù)相加后形成的新矩陣中的最小值:

(3)通過(2)摹乘迭代所得數(shù)據(jù)D2進(jìn)行下一步計算得到D3,同上;

(4)由于(2)、(3)所得結(jié)果并未一致,表明距離未達(dá)到最優(yōu),故需將(3)摹乘迭代所得數(shù)據(jù)D3進(jìn)行下一步計算得到D4,此時v1～v10(西北門):

在本算例中,(d(ij4))16×16= (d(ij3))16×16,(1≤i≤16,1≤j≤16),故在(4)計算中得到了各點(diǎn)與各點(diǎn)之間的最短路徑D4,如表2 所示。將最初數(shù)據(jù)和代入模型所得數(shù)據(jù)進(jìn)行對比,計算出距離的差值如表3 所示,數(shù)據(jù)表明,距離有所縮短,說明此模型有效。

而就上述舉例中的v1～v10(西北門)的距離而言, 優(yōu)化后的最短距離d(14.1)0= 2.4 km。相對于由v1直接到v10(西北門) 的初始距離2.7 km, 從v1→v15→v10(西北門) 所需路程會更短, 減少0.3 km。匯總計算的所有社區(qū)數(shù)據(jù)可知,經(jīng)過模型的優(yōu)化后,整體減少3.74 km。假設(shè)計算配送費(fèi)用時不考慮其他因素,各點(diǎn)之間的配送費(fèi)用與配送距離成正比, 則此次優(yōu)化可為該區(qū)域配送中心節(jié)省1.24%的配送費(fèi)用。

表2 路徑優(yōu)化后各點(diǎn)間的距離(單位: km)Tab.2 The distances between points after route optimization(unit: km)

表3 優(yōu)化的路徑距離差值(單位: km)Tab.3 Optimized path distance difference(unit: km)

4 結(jié) 論

隨著人們對生鮮產(chǎn)品需求的增加,O2O 模式下的生鮮電商的配送量也逐漸增大。這需要將人們更多的視線轉(zhuǎn)移到配送物流這一環(huán)節(jié)中,更加注重配送物流的規(guī)劃以及路徑的優(yōu)化,不僅能夠減少資源的浪費(fèi), 同時降低交易成本, 給用戶帶來更好的體驗(yàn),也為生鮮企業(yè)提供更廣闊的發(fā)展空間。

本文著重分析O2O 模式中導(dǎo)致生鮮電商行業(yè)成本居高不下主要問題:運(yùn)力調(diào)度不均衡。對O2O模式下的配送路徑進(jìn)行規(guī)劃,建立模型,采用一步距離矩陣摹乘迭代法對配送路徑進(jìn)行優(yōu)化,以降低成本、保持生鮮產(chǎn)品的新鮮度并提升用戶的體驗(yàn)度。最后采用v1算例,收集實(shí)際數(shù)據(jù)代入模型進(jìn)行驗(yàn)算,結(jié)果表明配送路徑得到優(yōu)化, 說明此模型有效。由于現(xiàn)實(shí)生活中交通狀況是實(shí)時變化的,配送時間受較多因素影響,無法保證在每次配送中以優(yōu)化后的路徑進(jìn)行配送是用時最短的路線,但是此次優(yōu)化通過模型提供了距離更短的路徑選擇。

未來想嘗試節(jié)約里程法對生鮮產(chǎn)品配送路徑進(jìn)行優(yōu)化,通過建立相關(guān)模型更全面地使配送這一過程中的資源得到有效配置而不僅限于縮短配送的距離, 會將交通擁擠狀況、道路狀況及生鮮產(chǎn)品的保鮮時間等需要考慮的因素以一定參數(shù)的形式加進(jìn)模型中,使其更貼近生活并更具實(shí)用性。