新零售模式下单中心物流配送路径优化研究

王登清

(1. 福州大学经济与管理学院, 福建 福州 350108； 2. 福建船政交通职业学院管理工程系， 福建 福州 350007)

0 引言

新零售的概念是马云率先于2016年10月在阿里云栖大会上提出的. 自诞生以来， 线上线下和物流紧密结合， 创造了真正的新零售. 目前新零售已发展为商品流通的新业态， 2017年网络零售额7.18万亿， 占社会消费品零售总额的19.59%[1]. 新零售物流业务更新和迭代进一步支撑新零售模式的发展. 新零售模式下物流配送业务对传统的配送路径规划与优化方法提出了新的挑战， 主要呈现出如下特点： 配送的个性化需求更加强烈, 随着前置仓数量的增加物流配送路径问题更加复杂, 物流配送目标更加多元化等. 研究新零售模式下的物流配送路径优化问题， 以降低国内居高不下的物流成本， 具有重要的理论和现实意义.

近年来， 国内外学者对电商物流配送线路优化进行了大量的研究， 文献[2-4]对配送中心的线路进行研究， 取得了一定的成果， 主要集中在物流成本优化上. 国内的学者关注的是在电子商务时代网络购物者如何实现下订单后货物安全快速地送达， 具体详见文献[5-6]. 新零售物流路径优化理论明显滞后于迅猛发展的新零售实践， 仅有文献[7-8]对其进行分析. 在相关理论基础上， 本研究针对现有车辆路径规划模型在解决新零售物流线路优化问题时存在着静态性、 未考虑交通拥堵及忽视个性化配送的局限性情况， 以车辆承载量为约束条件， 综合考虑物流成本与服务时效性构建新零售物流线路优化模型， 并通过改进遗传算法求解该模型， 探索新零售物流线路优化问题的新途径.

1 问题描述与模型构建

1.1 问题描述

某电子商务超市拥有12家门店， 门店不对外营业， 由总仓的配送中心对旗下门店进行配送. 顾客通过APP从网上直接下单， 门店收到顾客订单后， 门店工作人员直接分拣并尽量在顾客要求的时段内配送到指定地址. 货物先由总仓配送中心配送至门店， 再由门店按照顾客订单需求数量、 时间和地点配送给顾客， 本研究需要解决的问题是物流企业如何在节省配送费用的同时尽量在指定的时段将货物送达门店.

该配送中心车辆有限， 且最大载重量为Qk， 门店对货物配送时间有一定的要求， 每条线路上的配送车辆早于或晚于顾客要求的配送时间窗将产生时间成本. 本研究根据道路拥挤状况合理安排车辆配送路线， 目标是达到配送中心配送费用最小且车辆到达门店的时间符合要求. 为简化目标问题， 提出如下假设条件：

1) 配送中心总仓拥有固定的车辆， 并且车型一致， 车辆最大载重量Qk.

2) 每辆车从总仓出发， 最后回到总仓.

3) 每个门店的需求量不超过车辆载重量Qk.

4) 每个门店客户需求得到满足， 并且只被一辆车服务.

5) 配送任务在门店要求的时间窗内完成， 否则产生惩罚成本.

6) 因交通拥堵造成配送时间增加， 考虑拥堵因素导致配送成本的增加.

7) 每条配送路径的长度不超过车辆一次配送的最大行驶的距离.

1.2 模型构建

模型构建的参数与变量说明如下：

N表示配送的门店数；k表示配送中心车辆数；Qk表示配送车辆最大载重量；gi表示门店配送量；dij表示i到j的距离；c0表示车辆每公里运输成本；D表示车辆最远行驶距离；qi表示门店i的需求量；c1表示Ei之前到达门店i等待的单位成本；c2表示li之后到达门店i的单位时间惩罚成本；ti表示到达门店i的时间；cijk表示k辆车经过ij路线的拥堵系数；xijk表示第k辆车从第i点行驶至j点， 取值为1， 未经过取值为0；yik表示第i个门店由第k辆车配送， 取值为1， 否则为0.

根据问题的描述和变量说明， 建立新零售多门店模式的下单中心物流配送路径优化模型[9-10]：

(1)

s.t.yik=0或1 (i=1， 2， …,n；k=1, 2, …,m)

(2)

xijk=0或1 (i,j=1， 2， …，n；i≠j, ∀k)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

模型中目标函数(1)表示总费用最小， 包含运输费用(含线路拥堵成本)、 等待成本和惩罚成本； 式子(2)～(3)表示变量的定义； 约束(4)表示每个客户只由一辆车配送； 约束(5)配送任务覆盖所有客户； 约束(6)～(7)表示送货点车辆唯一性； 约束(8)表示每条配送线路上门店的需求量之和不超过车辆最大载重量； 约束(9)表示每条配送线路长度不超过最大行驶距离D.

2 算法设计

遗传算法是一种基于模拟自然进化过程搜索最优解的方法， 具有使用方便、 鲁棒性强、 便于并行处理等优点， 但算法的主要遗传算子是在随机状态下进行迭代搜索， 种群不可避免陷入退化状态， 产生局部最优状态. 为避免算子过早进入退化状态， 本研究拟采用精英选择策略， 对遗传算子实施改进求解， 以下是详细的算法设计.

2.1 染色体编码

本研究采用自然编码方式进行编码， 总仓编码为0， 使用M辆车向门店进行配送， 然后返回总仓.K+M+1的染色体, 其中一条染色体“0987065403210”表示3辆车给9个客户配送， 第一辆车从总仓出发， 经过9、 8、 7节点后回到总仓； 第二辆车从总仓出发， 经过6、 5、 4节点后回到起点； 第三辆车从总仓出发， 经过3、 2、 1节点后回到起点. 第m辆车从总仓出发， 经过若干节点后回到总仓， 构成第m条路径.

2.2 初始化种群

根据遗传算法原理， 初始化种群需要一定的量使得算法收敛全局最优. 但种群过大， 会增加计算时间. 为保证群体的多样性， 防止算法收敛于局部最优解， 群体规模应在合理的范围内选择, 约80个左右. 本研究设计了最大载重量限制的初始化染色体方法.

步骤1： 从总仓开始， 染色体编码为0， 然后给1～N的客户进行随机编号.

步骤2： 从染色体0的客户点开始， 随机抽取遍历， 形成一条客户需求量小于最大载重量Q的线路， 插入其他客户则大于最大载重量， 在这条线路的最后客户点插入总仓基因0.

图1 初始染色体生成示例Fig.1 Sample of the initial chromosomes generated

步骤3： 遍历染色体新插入基因0后面的客户点重新进行遍历， 重复步骤2， 形成第二条线路. 如此反复， 覆盖所有客户点.

步骤4： 在步骤3中的最后一条线路， 当客户总需求小于最大载重量Q时， 直接插入总仓0， 得到一条初始的染色体， 如图1所示.

2.3 计算适应度函数

适应度函数可以用来评价配送路径的优劣程度， 是获得最优染色体的依据, 对个体进行优胜劣汰. 配送路径适应度公式表达为：

(10)

其中:a是常数;Zj是j条配送路径的运输成本;Z′是种群中最优配送路径的运输成本.

(11)

式中：Pj表示染色体遗传到下一代的概率， 其中fj表示第j条配送路径的适应度.

2.4 交叉与变异算法

1) 交叉算法. 遗传算法中最具特色的机制是交叉和变异算子， 通过基因的交叉与变异， 实现对生物的进化. 本研究采用类双点交叉方法， 现举例说明, 在父代个体中随机选择交配区域， 如两个父代个体及交配区域选择如下： 1)A=45|3 216|987，B=93|8 542|716. 2)将AB的交配区域互放置至前面， 得到A′=8 542|453 216 987，B′=3 216|938 542 716. 3)将A′与B′中与交配区相同的自然数删除， 获得A″=854 231 697,B″=321 698 547.

2) 变异算法. 由于在选择机制中保留了最佳个体的方式， 为保持群体内个体的多样性和有效性， 采取精英选择策略. 具体策略为： 在父代种群Q(t)中， 计算个体的适应度函数并进行优劣排序， 将优秀的个体进行集合R(t)， 再在父代种群中随机选取个体进行量子变异产生子代种群P(t)， 其中量子变异以量子旋转门更新的方式进行[11]. 最后计算集合U(t)=P(t)∪R(t)中个体的适应度函数并进行排序， 选择适应度最大的前80个个体组成下一代父代种群. 如果集合U(t)种群的规模小于80， 则将适应度最大的个体添加至新种群， 使其规模达到80个后， 进行循环. 该策略的优点是删除了相同的种群， 避免陷入局部最优， 同时可以提高收敛速度.

3 算例验证与优化分析

某线上超市配送中心拥有最大载重量4 t的车辆6辆， 单车最大行驶距离100 km， 平均车速40 km·h-1， 主要面向12个前置仓配送商品. 车辆单位运输成本c0为8元·km-1，c1=100 元·h-1，c2=150 元·h-1. 拥堵系数为: 8： 00～9： 00系数1.3; 9： 00～10： 00系数1.2; 下午17： 00～19： 00系数1.4; 其他时间段系数为1.0. 配送中心标号为0， 配送总仓位置坐标(85， 60)， 各前置仓的位置坐标、 需求量、 服务时间、 时间窗如表1所示.

表1 各前置仓位置、 需求量、 服务时间及时间窗

配送总仓每天6点统一发货， 从发货时间开始计算， 车辆从配送总仓出发， 经过各前置仓后回到总仓， 选择总成本最小的配送方案.

采用改进的遗传算法求解， 算法参数如下： 种群规模N=80， 交叉概率Pc=0.8， 变异概率0.2， 迭代次数200. 算法运行200次发现目标函数最优值5 212.22, 最优适应度值为0.000 191 86. 与此对应的最优化路线0-1-5-0-2-7-8-0-6-3-0-4-9-0-10-12-11， 最优路线的过程见图2， 虚线表示最优化的配送路径图， 实线表示路径优化结果的过程.

图3是将改进GA和标准GA最优适应值收敛过程进行比较， 在该图中改进GA收敛速度明显优于标准GA. 改进GA在迭代次数超过56次后， 目标函数曲线趋于平缓， 逐步收敛于最优适应度值， 而标准GA在迭代次数超过156次后， 曲线趋于平缓. 表2是改进GA和标准GA各指标比较， 数据显示改进GA在车辆数使用、 总距离、 总成本等指标方面要优于标准GA.

图2 车辆配送路径优化路线

Fig.2 Optimized distribution routes for vehicles

图3 改进GA与标准GA最优化适应值比较

Fig.3 Comparison between the optimal adaptive values of standard GA and improved GA

表2 改进GA与标准GA比较

为进一步验证算法的有效性及稳定性， 对算法参数取不同的值， 表3列出参数的不同取值及对应的测算结果. 不同种群规模测算表明： 本研究设计的算法不完全依赖于参数的取值， 算法有效及稳定性较强.

表3 不同种群规模比较

4 结论

以新零售网上超市的总仓配送中心向前置仓物流配送路径优化为研究对象， 聚焦货物配送的时效性和成本两大目标. 建立新零售模式的下单中心物流配送路线整体优化模型, 综合考虑了运输成本、 道路拥堵程度以及配送业务的时效性， 突出解决新零售模式下单中心带时间窗、 个性化配送的物流路径优化问题， 更加贴近物流行业的现实需求.

通过算例研究结果表明， 本研究基于配送时间窗和成本考虑的目标优化模型及其算法是有效的， 改进的遗传算法运行效率更高， 求解结果对参数值的变化不敏感， 算法稳定可靠. 后续的研究工作将进一步完善模型， 兼顾考虑顾客满意度、 交通路况复杂性、 车辆资源增加导致成本提高等因素， 以及适用于多物流配送中心的场合.