基于距离矩阵摹乘法的生鲜产品配送路径优化

涂志芳子, 羊 英

(上海第二工业大学 经济与管理学院,上海201209)

0 引言

随着互联网的飞速发展,网络应用几乎渗透到生活的各个方面,促进了商品交易与互联网结合的线上线下(online to offline business, O2O)模式的发展。同时,近年来随着生活水平的不断提升,人们对新鲜水果蔬菜等生鲜产品的需求也出现快速增长的趋势。而O2O 模式下的生鲜产品电子商务充分利用互联网信息的即时性和互动性等一系列特点,为消费者节省时间并提供生活上的便利。

前瞻产业研究院调查数据表明,中国的生鲜市场交易额自2011 年起一直逐年上升, 2012 年之后我国生鲜市场交易额保持在6.5%左右的增速,2017年我国生鲜市场交易规模达1.79 万亿元, 同比增长6.5%。预计2020 年生鲜市场交易额将达到2.16万亿元。由此可知, 中国生鲜市场还有很大的发展空间, 人们对生鲜产品的需求不断上升。同时通过O2O 模式下的生鲜电商平台购买生鲜产品的人数越来越多,且使用次数越发频繁,人们能够接受甚至习惯以网购形式获取所需生鲜商品。这也代表着生鲜产品配送物流在整个物流行业中的占比会逐渐提升,而配送环节也将在生鲜电商平台运营中发挥更加关键的作用。

但由于生鲜产品易腐烂、储存要求高等特性,消费者对生鲜产品新鲜度的需求,对该模式下生鲜产品的配送物流提出了较高要求。缩短配送距离不仅可以帮助O2O 模式下的商户对平台更有效的运营,还能提升用户体验感,进一步促进生鲜电商行业的发展。

近年来,生鲜产品物流问题得到了许多学者的关注。韩超[1]构建了依靠云配送互联网平台的O2O农产品物流资源配置和货运配送系统以提高农产品配送效率。白羽[2]运用超效率基于松弛的效率评价(slack based measure,SBM)模型对送货上门、智能配送柜、第三方代收3 种物流终端配送模式效率进行对比分析,并对生鲜产品的物流终端配送进行了方案设计。张瑜[3]对生鲜农产品冷链物流配送网络优化进行了研究,采用了节约成本算法。胡静怡等[5]对生鲜电商“最后一公里”配送问题进行了探讨,提出了配送优化方案;Nakandala 等[6]考虑生鲜产品质量和运输建立了成本优化模型;唐佩佩等[8]将遗传算法结合MATLAB 语言求得合理的车辆行驶路径以缩短配送时间;孟成斐等[9]基于最短路思想运用距离矩阵摹乘法对无水港进行区位分析,确定陕西地区无水港的选址; 汤齐等[10]针对生鲜产品配送对车辆路径优化进行研究,在时间约束条件下以求得最小配送成本。

通过对已有文献的研究发现,目前尚未发现将距离矩阵摹乘法用于对生鲜产品配送路径进行优化的文章。该方法对某一特定区域较密集的配送网络距离的缩短效果较好,所以本文拟对区域内生鲜产品配送点的布局和配送路线优化进行研究,以缩短配送距离提高配送效率从而降低配送成本。

1 生鲜电商配送问题分析

1.1 配送中心覆盖率不高

目前大部分生鲜产品供应商因为考虑到人口密度、交通状况和产品保鲜度等问题,大多将配送中心设置在市中心或人口密集区域,并设置配送区域,从而使得许多超出配送区域的社区得不到服务,而对生鲜产品有需求或潜在需求的人口覆盖率也不高。

1.2 运力调度不均衡

物流配送中心经常出现这样的情况,有的配送车辆满负荷运转,有的车辆长期搁置不用,而有的车辆平均满载率低, 造成一定程度的运力浪费[7]。同时也会出现配送中心调度不够协调,一辆车已经将货物配送完成,而下一个客户就在某个配送点附近,却又需要返回配送中心再取货或者调度其他车辆完成配送。

O2O 模式下的电商运营中,配送物流是用户整个购买过程中的末端环节, 也是很关键的部分。生鲜产品对于运输时间的要求较高,在配送过程中,配送中心的位置和配送速度决定着用户收到商品的时间长短,进而影响客户对生鲜产品的用户体验。

2 生鲜产品配送路径优化方法研究

2.1 问题描述

配送路径的优化即在配送中心到用户地理位置的几条路径中选出最短路径,节约配送时间,以便配送人员快速将商品送至客户手中。配送路径的问题一直困扰着生鲜电商,配送过程中若没有选择最短路径容易造成配送超时,一方面影响用户的体验,另一方面也会增加配送成本,甚至可能影响整个物流体系。

假设某地区有n 个配送中心和m 个社区,求不同的配送中心将商品送至不同社区的最短路径; 采用距离矩阵摹乘法求配送网络中各点至各点的最短路来规划“最后一公里”的周边地区的最优配送路径。距离矩阵摹乘法是运筹学中一种用以解决最短路问题的典型方法,可以求解某一路径网络中各点至某一定点、某一定点至各点及各点至各点之间的最短距离。

O2O 有极强的地域属性,它既不同于传统电商,又有别于线下商业,在空间尺度有差异;和传统电商相比,O2O 注重本地消费,而在很多情况下本地消费配对本地用户是更高效的方式,故在某一特定区域的各订单的配送中,路径优化这一步骤显得尤为重要。在本地密集且错综复杂的配送网络中, 距离矩阵摹乘迭代可以更精确有效地求出配送最短距离,节省配送时间并节约配送资源,使商户的运营状况和用户的客户体验达到双赢。

一步距离矩阵方法求解如下: 记矩阵Dk=(d(ijk))m×n为k 步距离矩阵, 即网络中各点最多经过k 步到达其他各点的最短距离矩阵, 则D1=(d(ij1))m×n=W。

式中: Dk表示至多经过k 步到达各点之间的最短距离矩阵,Dk−1表示至多经过k −1 步到达各点之间的最短距离矩阵;而

式中: d(ijk)为vi到vj经过k 步的最短距离; d(isk−1)为vi到vs经过k −1 步的最短距离;d(skj−1)为vs到vj经过k −1 步的最短距离; vi, vj, vs为网络中各点。

若计算中出现Dk= Dk−1, 则停止计算,表示到了k −1 步以后,再走一步并不能有任何作用,从而求得从各点到各点的最短距离。从而计算出各个配送中心到各个社区的最短距离,进而划分哪些社区由哪个配送中心负责配送,之后不同社区发出的订单需求就可以有条不紊由最近配送中心安排配送,由此减少配送成本。

2.2 求解步骤

计算过程如下:

(1)测出各点之间的距离,得到一步距离矩阵

式中: D1和W 为网络中各点到各点的一步距离矩阵; d(ij1)为vi到vj经过1 步的距离; vi,vj(i,j =1,··· ,n)为网络中各点。

(2)通过距离矩阵摹乘迭代得到二步距离矩阵

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

(3)用第二步所得结果进行下一步的摹乘迭代得到三步距离矩阵,以此类推,直到Dk= Dk−1,即(d(ijk))m×n= (d(ijk−1))m×n时, 则可获得最后的点到点最短距离矩阵,而对应的d(ijk)为vi到vj的最短距离。

3 每日优鲜(v1)物流配送体系案例

3.1 物流配送现状

生鲜电商一直被看作是电商行业中的最后一片蓝海,但我国生鲜电商由于冷链物流基础设施建设滞后, 损耗率居高不下等原因发展不太理想。目前我国大部分生鲜电商的产品损耗率都在10%以上,有的甚至高达30%[7]。

为了降低损耗率,每日优鲜平台选择采用“前置仓模式”,在华北、华东、华南等地区建立城市分选中心,并根据订单密度在商圈和社区建立前置仓即配送中心,每个配送中心覆盖周边半径3 km。商品在入库后,经过城市分选中心的品控、分选、加工等环节,根据智能补货系统提供的补货系数,被分发到各个前置仓,全程通过冷链物流运输。用户下单后,配送员从前置仓提货,保证了商品的新鲜品质和交付速度。但是从前置仓将商品送至用户手中这一配送过程,俗称“配送的最后一公里”,如果没有进行路径优化,同样会给平台增加配送成本。以下对这“最后一公里”的配送路径优化问题进行研究。

3.2 v1 配送路径优化

选择v1在浦东新区曹路镇的配送路径进行优化。该平台在曹路镇设置的前置仓为位于川沙路的锦绣东路店, 该配送中心覆盖周边半径3 km, 以下社区在其配送范围内:丰怡苑(v2)、龚新西苑(v3)、谐苑(v4)、龚路新城(v5)、河滨城市花园(v6)、金海华城永华苑(v7)、万科第五园(v8)、星晓家园(v9)、金钻苑(v10)、阳光花城同景园(v11)、睿翔园(v12)、大湾名苑(v13)、鑫港苑(v14)、铂尊公寓(v15)、银丰苑(v16)。通过高德地图算出配送中心与各社区及社区与社区之间的实际距离, 如表1 所示。因考虑到算例中调查的曹路镇区域的道路正反向都能进行配送, 故此为双向矩阵, 表1 中上三角和下三角数据对称。

表1 v1 与社区各点间的距离(单位: km)Tab.1 The distances between v1 and communities(unit: km)

在v1的算例中, d(1)ij表示vi到vj两地区在模型优化前的初始距离。

例设v1∼v10(西北门) 的初始距离d(1)1.10=2.7 km,对其进行优化:

(1) 测算各点之间的距离, 其中v1∼v10(西北门)的初始距离d(11.1)0=2.7;

(2)利用D1的数据进行摹乘迭代

v1至各点的初始距离分别为:

各点到达v10(西北门)的初始距离分别为:

将两列单位矩阵相同位置数据相加:

选取数据相加后形成的新矩阵中的最小值:

(3)通过(2)摹乘迭代所得数据D2进行下一步计算得到D3,同上;

(4)由于(2)、(3)所得结果并未一致,表明距离未达到最优,故需将(3)摹乘迭代所得数据D3进行下一步计算得到D4,此时v1∼v10(西北门):

在本算例中,(d(ij4))16×16= (d(ij3))16×16,(1≤i≤16,1≤j≤16),故在(4)计算中得到了各点与各点之间的最短路径D4,如表2 所示。将最初数据和代入模型所得数据进行对比,计算出距离的差值如表3 所示,数据表明,距离有所缩短,说明此模型有效。

而就上述举例中的v1∼v10(西北门)的距离而言, 优化后的最短距离d(14.1)0= 2.4 km。相对于由v1直接到v10(西北门) 的初始距离2.7 km, 从v1→v15→v10(西北门) 所需路程会更短, 减少0.3 km。汇总计算的所有社区数据可知,经过模型的优化后,整体减少3.74 km。假设计算配送费用时不考虑其他因素,各点之间的配送费用与配送距离成正比, 则此次优化可为该区域配送中心节省1.24%的配送费用。

表2 路径优化后各点间的距离(单位: km)Tab.2 The distances between points after route optimization(unit: km)

表3 优化的路径距离差值(单位: km)Tab.3 Optimized path distance difference(unit: km)

4 结 论

随着人们对生鲜产品需求的增加,O2O 模式下的生鲜电商的配送量也逐渐增大。这需要将人们更多的视线转移到配送物流这一环节中,更加注重配送物流的规划以及路径的优化,不仅能够减少资源的浪费, 同时降低交易成本, 给用户带来更好的体验,也为生鲜企业提供更广阔的发展空间。

本文着重分析O2O 模式中导致生鲜电商行业成本居高不下主要问题:运力调度不均衡。对O2O模式下的配送路径进行规划,建立模型,采用一步距离矩阵摹乘迭代法对配送路径进行优化,以降低成本、保持生鲜产品的新鲜度并提升用户的体验度。最后采用v1算例,收集实际数据代入模型进行验算,结果表明配送路径得到优化, 说明此模型有效。由于现实生活中交通状况是实时变化的,配送时间受较多因素影响,无法保证在每次配送中以优化后的路径进行配送是用时最短的路线,但是此次优化通过模型提供了距离更短的路径选择。

未来想尝试节约里程法对生鲜产品配送路径进行优化,通过建立相关模型更全面地使配送这一过程中的资源得到有效配置而不仅限于缩短配送的距离, 会将交通拥挤状况、道路状况及生鲜产品的保鲜时间等需要考虑的因素以一定参数的形式加进模型中,使其更贴近生活并更具实用性。