基于订单拆分的容量限制商超配送路径规划

潘 晓 ,鹿冬娜 ,王书海

（1.石家庄铁道大学 管理学院,石家庄 050043;2.石家庄铁道大学 信息科学与技术学院,石家庄 050043）

0 引 言

2020 年的中国社会消费品零售总额中涉及商超类型产品的零售额为193 323 亿元,占比达到了商品零售总额的54.85%.因此,商超配送是社会消费需求的重要组成部分,且其需求占比较大.商超配送主要是指在经济合理区域范围内,根据各商超和卖场的要求,对货物进行分拣、加工、分割、组配等作业,最后将货物由配送中心送达指定的商超门店的物流活动[1].

与其他配送问题相比,商超配送目前主要面临的问题有: 商超门店位置不一,分布较散;配送资源利用不足,车辆配载和路径规划难;配送场景复杂,商超门店需求差异大;货物品类繁杂,对运输和存储方式要求严格等.

为了解决上述问题,各大商超企业分别采取了不同的配送方式,例如,家乐福采取供应商直送的方式,由供应商实现配送资源的整合;沃尔玛采取自营配送的方式,适应了门店间的需求差异;一般中小型商超采取第三方物流的配送方式,满足了不同货物品类对运输和存储的需求[2].但无论哪种配送方式,都面临相同的且重要的问题: 车辆配载和路径规划.订单拆分可以充分利用车辆容量,合理安排货物装载.2006 年,Archetti 等[3]证明了订单拆分的可行性.

鉴于此,本文设计了基于订单拆分的容量限制商超配送路径规划方案,可在一定程度上解决商超配送的车辆配载和路径规划问题.首先,采用“20/10/5 规则”的订单拆分策略对每个商超客户的需求量进行拆分;然后,在该订单拆分策略的基础上,建立商超配送路径规划模型;最后,采用改进灰狼优化算法进行模型求解,得到具体的商超配送路径规划方案.通过实例分析,与求解该模型的代表性方法—遗传算法进行对比,验证了本文的改进灰狼优化算法的有效性.

1 相关工作

基于订单拆分的容量限制商超配送路径规划问题是一般带容量限制车辆路径规划问题(Capacitated Vehicle Routing Problem,CVRP) 中的一种.CVRP 最早由Dantzig 和Ramser[4]提出,其作为车辆路径问题 (Vehicle Routing Problem,VRP) 的一种常见形式,已被证明是典型的NP-难(Non-deterministic Polynomial Hard)组合优化问题[5].目前,针对CVRP 的研究主要集中在模型建立和算法求解这两个方面.

1.1 模型建立

在模型建立的目标方面,学者们大多倾向于以1 个或多个目标最优,如成本最低、路径长度最小、耗时最短、能耗和污染最低等,同时考虑现实场景中的约束条件建立模型.范厚明等[6]考虑生鲜品配送的时效性要求,以配送车辆运输成本、派遣成本、时间惩罚成本及货损成本最小为目标,建立了配送路径规划问题模型;曾正洋等[7]以应急配送中受灾点的累计等待时间最短为目标,建立了多车场车辆路径问题模型;周鲜成等[8]考虑物流配送领域的节能减排需求,以车辆油耗和碳排放成本、车辆使用成本之和最小为目标,建立了绿色配送车辆路径问题模型.

分析上述模型建立方式可发现,在建模时,应根据配送过程中需求的不同设置合理的目标及约束条件.本文所研究的商超配送路径规划问题,意在满足客户需求的同时,也能够充分利用配送资源,减少成本支出.因此,结合实际商超配送过程中的成本组成,本文以车辆行驶成本、车辆派遣成本之和为目标,建立基于订单拆分策略的容量限制商超配送路径规划模型.

订单拆分策略在CVRP 上实现的方式主要有2 种: 一种是在建立模型的约束中添加订单拆分;另一种是在模型求解过程中实现订单拆分.这两种方式都可以降低配送成本,但后者计算时间较长[9].而商超配送货物品类繁杂,装载过程耗时较长.为了保证在时间窗内完成配送任务,本文采用在模型建立中进行订单拆分策略,即按照“20/10/5 规则”的订单拆分策略,依据车辆容量限制,将商超门店的订单需求进行拆分.

1.2 算法求解

在算法求解方面,当前解决CVRP 的方法主要分为精确算法、启发式算法和混合算法这3 类.

(1) 精确算法

精确算法适用于小规模的CVRP 求解,往往能够获得问题的最优解,其代表性方法主要是分支-切割-定价算法.Yang 等[10]利用分支-切割-定价算法,为农村最后1 km 的配送提供了合理的方案;揭婉晨等[11]针对需求可拆分的容量约束车辆路径问题模型,提出了一种改进的分支定价算法.

(2) 启发式算法

启发式算法在求解大规模的CVRP 时效果较好,能够在合理时间内获得相对最优解.具有代表性的启发式算法主要有遗传算法、蚁群算法、禁忌搜索算法等.张亚明等[12]设计了局部精英单亲遗传算法来求解满意度约束多车型冷链车辆的路径问题;Xu 等[13]针对实时变化的新客户需求下大规模车辆路径问题,设计改进了蚁群算法求解;符卓等[14]在综合考虑客户的订单拆分需求和服务时间需求后建立模型,并设计了禁忌搜索算法求解.

(3) 混合算法

混合算法是将各类精确算法、启发式算法进行混合,以加快算法收敛速度,跳出局部最优解.目前,混合算法主要有: Sitek 等[15]为解决带取送货车辆路径问题,提出的约束逻辑规划与启发式算法相结合的混合算法;李阳等[16]为求解CVRP 设计的混合变邻域生物共栖搜索算法;Gokalp 等[17]提出的用于解决CVRP 的基于迭代局部搜索和随机变量邻域下降元启发式的混合算法等.

综上所述,在设计大规模CVRP 模型的求解算法时,大多数学者选择对已有的解决CVRP的启发式算法进行改进,但仍存在容易而陷入局部最优解的弊端;也有不少学者将不同的算法进行结合,采用混合算法求解,但也会出现求得的最优解不理想的问题.

灰狼优化(Grey Wolf Optimization,GWO) 算法作为一种新兴的群体智能启发式算法,具有依赖参数少、寻优性能好的特点[18],适用于求解大规模的NP-难问题.GWO 算法利用系数向量和收敛因子,能够合理平衡问题求解时的全局搜索和局部开发能力,从而扩大最优解的搜索空间,有效避免了陷入局部最优解[18].但GWO 算法所得的最优解效果仍不够理想.因此,本文在GWO 算法的基础上添加遗传变异操作,提出了改进灰狼优化算法,增加了其在局部开发最优解过程的随机性.研究结果表明,与GWO 算法、遗传算法相比,在配送总成本方面,本文的改进灰狼优化算法结果更优.

2 问题描述与数学模型

2.1 问题描述

本文所研究的基于订单拆分的容量限制商超配送路径规划问题: 在经济合理区域范围内,已知商超类型的客户数量、位置以及订单需求,由单配送中心统一派出若干辆车,依据车辆容量将客户订单进行拆分,并在不超过车辆最大容量限制的前提下进行配载,为相应客户提供配送服务;设计配送总成本最小的路线规划方案,将货物按时送到各大商超和卖场,满足所有客户的订单需求.这里的配送总成本由依赖于行驶距离的车辆行驶成本和派遣成本构成.

如果1 个订单的需求量本身已超过配送车辆的最大容量限制,则必须对订单进行拆分,由1 辆以上的车辆进行配送.这种必须拆分的情况,不在本文研究范围内.本文只针对每个客户订单需求量未超过配送车辆最大容量限制的情形.对于某个客户需求量超过车辆最大容量限制的情况,本文默认对该客户订单先进行整车装载,剩余部分再采取订单拆分策略.

为了研究方便,提出以下假设.

(1) 已知各商超类型的客户数量、客户位置、订单需求,所有订单任务均由单配送中心完成.

(2) 配送中心有若干配送车辆,车型相同,车辆容量已知,且装载量不可超过车辆最大容量.

(3) 配送车辆总是由配送中心出发,完成各个客户的配送任务后,再返回配送中心.

(4) 每个配送车辆只允许被派遣1 次.

(5) 保证所有客户均被服务,允许每个客户被服务多次,即不要求一次性满足客户需求.

(6) 送货和收货的时间皆在规定范围内,即不考虑客户对时间的要求.

为避免过细拆分造成的计算负担过重问题,本文修正了Chen 等[9]提出的“20/10/5/1 规则”的先验拆分策略,结合商超配送的特殊性,采用“20/10/5 规则”的订单拆分策略,在算法求解前先对订单进行拆分.具体的拆分规则: 将每个商超客户的订单需求按20%、10%和5%的车辆最大容量分别拆分为不同的份数,且每个订单在拆分时,最多允许有1 份少于5%的车辆最大容量,例如,当某商超客户需求量为649,车辆最大容量为2050 时,根据“20/10/5 规则”,该订单将被拆分为3 份,即410、205、34.

2.2 模型构建

基于订单拆分的带容量限制商超配送路径规划问题可以用1 个有向图G=(N,E) 来表示,其中,点集N={i|i=0,1,2,···,n},{0}表示配送中心节点,{1,2,···,n}表示各商超客户节点;弧集E={〈i,j〉|i,j ∈N},弧〈i,j〉表示车辆从商超客户i向商超客户j行驶的路径.问题示意图如图1 所示.

图1 商超配送路径规划问题示意图Fig.1 Schematic diagram of the distribution routes planning problem in supermarkets

图1(a)表示无订单拆分的配送路径方案,配送过程中每个客户只允许被服务1 次;图1(b)表示有订单拆分的路径规划方案,每个客户允许被多次服务,其中红色圈圈出的商超客户被进行了多次配送服务.

根据提出的假设和订单拆分策略,以最小化配送总成本为目标,构建车辆路径配送模型.

设置的各参数及含义如下.

K—车辆集合,K={k|k=1,2,···,m},k表示配送中心派出的车辆.

n—商超客户数量.

qi—商超客户i的订单需求量,i∈{1,2,···,n}.

Qk—车辆k的最大容量.

dij—从商超客户i到商超客户j的距离.

ce—单位距离的车辆行驶成本.

ck—车辆的派遣成本.

xijk—若车辆k从商超客户i直接到达商超客户j,则xijk=1,否则为0.

—若车辆k服务于商超客户i,则,否则为0.

构建基于订单拆分的容量限制商超配送路径模型

表示配送总成本,由车辆行驶成本和派遣成本构成: 车辆行驶成本主要取决于车辆的行驶距离,由每辆车的行驶距离之和乘以单位距离的车辆行驶成本计算得出;车辆派遣成本主要取决于使用车辆数,由配送方案使用的总车辆数乘以每辆车的固定成本计算得出.

约束条件是

公式 (1) 为目标函数,表示配送的总成本最小.公式 (2)—公式 (4) 为“20/10/5 规则”的订单拆分策略：公式 (2) 表示商超客户i的订单需求量中所拆分出的20%车辆最大容量的数量;公式 (3) 表示经过公式 (2) 的拆分后,剩余商超客户i的订单需求量中所拆分出的10%车辆最大容量的数量;公式 (4)表示经过公式 (2) 和 公式(3) 的拆分后,商超客户i的订单需求量中所拆分出的5%车辆最大容量的数量.公式 (5) 和公式 (6) 表示车辆的容量限制: 公式 (5) 表示没有订单拆分时,根据客户需求安排的车辆装载量不能超过配送车辆的最大容量;公式 (6) 表示基于订单拆分所安排的车辆装载量不能超过配送车辆的最大容量.公式 (7) 表示车辆从配送中心出发,并最终回到配送中心.公式 (8) 和公式 (9)表示每个客户都将至少被服务1 次,即车辆k到达和离开商超客户j的次数分别至少为1 次.公式 (10)表示车辆的进出平衡关系,即若车辆k为商超客户j服务,则需要在商超客户j处完成进和出,且进出次数保持平衡.

3 算法设计

灰狼优化(GWO)算法是由Mirjalili 等[18]于2014 年提出的,是模拟自然界中灰狼群体的社会等级制度和狩猎行为而衍生出的一种群体智能启发式算法.启发式算法中的代表性算法是遗传算法[12].与遗传算法一样,GWO 算法也适用于求解CVRP[18],但通过其所得的最优解效果仍不够理想.因此,本文通过对GWO 算法添加遗传变异操作,设计改进GWO 算法,来求解基于订单拆分的容量限制商超配送车辆路径问题.为便于理解,表1 给出了本文改进灰狼优化算法中的常用术语以及其与车辆路径规划问题的必要对应关系.

表1 灰狼优化算法的术语说明Tab.1 Glossary of grey wolf optimization algorithm

基于改进灰狼优化算法的路径规划流程见算法1 所示.算法1 中,行1—行9,对9 对灰狼种群进行初始化,即根据商超配送问题规模的大小,为每个灰狼个体确定其所有车辆的初始经过商超客户序列.本文采用随机初始化的方式产生灰狼种群,具体的步骤将在3.1 节详细介绍.

行10—行16,利用适应度函数计算种群中每个灰狼个体的适应度值,并保留种群中适应度值最佳的前3 只狼α、β、δ(配送总成本最低的3 个方案) .适应度函数计算将在3.2 节的算法2 中详细介绍.

行17—行24,在最大迭代次数范围内,以3 只狼α、β、δ为依据,对灰狼种群进行位置更新.具体的灰狼位置更新方式将在3.3 节详细介绍.对更新后的灰狼个体,重新计算其适应度值,可以在每次迭代中都获得新的3 只狼α、β、δ.

行25—行33,在设定的变异次数上限内,借鉴遗传算法中的变异操作,采用部分单点移动的方式,对最后一次迭代中狼α(第一最佳配送方案) 所对应的配送路径规划方案进行改进.具体的变异操作方法将在3.4 节详细介绍.判断改进后的方案适应度值是否优于狼α,输出适应度值最佳的灰狼个体所对应的车辆行驶路线及配送总成本.

3.1 初始化灰狼种群步骤

初始化灰狼种群是改进灰狼优化算法的基础步骤.在商超配送路径规划问题中,初始化灰狼种群是指产生多种可能配送方案的所有车辆,初始经过的商超客户序列.具体分为以下3 个步骤.

步骤1: 确定配送方案所需车辆数k.为了满足所有商超客户的服务需求,本文通过公式

计算完成配送任务所需最少的配送车辆数k,即计算所有商超客户总需求量qi与配送车辆最大容量Qk的比值,并向上取整,得到所需车辆数.若无法在最少车辆数基础上得到可行的配送方案,则依次增加1 辆配送车辆,直至能够得到可行方案,确定所需车辆数.

步骤2: 随机产生灰狼个体.采用随机初始化的方式产生灰狼个体,即为步骤1 中的k辆车随机确定初始经过的商超客户坐标,k辆车的全部初始经过的商超客户坐标共同组成灰狼个体.本文设置配送车辆的初始经过的商超客户坐标须在规定的配送范围内产生.

步骤3: 根据问题规模,产生灰狼种群.重复执行步骤2,产生多个灰狼个体,形成灰狼种群,即产生多种可能的k辆车的初始经过的商超客户坐标.

3.2 适应度值计算过程

在改进灰狼优化算法中,通过适应度函数计算适应度值,用适应度值来度量种群中每个灰狼个体的优劣程度,即依据全部配送车辆的初始经过商超客户坐标,利用适应度函数得出完整的商超配送路径规划方案,并计算该方案的配送总成本作为灰狼个体的适应度值.适应度函数的流程如算法2所示.

算法2 中,行1,初始化参数;行2—行13,对商超客户i与配送车辆k进行匹配,其中,行3—行6是商超客户i与配送车辆k的初步匹配,即为配送车辆k分配与其距离最近且需求量最大的商超客户i,且优先配送.本文通过公式

为每个商超客户i计算其与所有配送车辆之间的距离以及其需求量的比值,选择需求量比值最小的配送车辆k与商超客户i进行匹配,以保证所有商超客户均得到服务.公式 (12) 中:fik表示商超客户i与配送车辆k的初步匹配标准;dik表示商超客户i与配送车辆k之间的距离;qi表示商超客户i的需求量.

行7—行12,初步匹配方案的调整.由于初步匹配没有考虑到配送车辆k的容量限制,因此,需要进一步判断商超客户i的需求量是否超过配送车辆k的剩余车辆容量: 若未超过,则不改变初始匹配方案;若超过,则调整商超客户i由其他配送车辆服务.最终,得出符合车辆容量限制的完整商超配送规划方案.

行14—行16,计算种群中每个灰狼个体的适应度值.利用目标函数计算灰狼个体的适应度值,即计算方案所需配送总成本.适应度值计算的表达式为

公式 (13) 中:ffit表示灰狼个体的适应度值;z表示方案的配送总成本 (车辆行驶成本与车辆派遣成本的和).

行17,返回每个灰狼个体所对应的车辆行驶路线和适应度值.

3.3 灰狼位置更新方式

灰狼位置更新的目的是实现狩猎行为.在狩猎期间,灰狼群体主要进行包围猎物、追捕猎物、攻击猎物和搜索猎物4 项活动.在改进灰狼优化算法中,灰狼位置的更新方式与灰狼社会等级制度有关.灰狼的社会等级制度是指,依据适应度值从小到大将灰狼种群中的个体划分为α、β、δ、ω这4 个等级,如图2 所示.图2 中,狼ω以狼α、狼β、狼δ的位置为依据进行狩猎行为,即种群中的全部配送方案均以适应度值最佳的前3 个方案 (狼α、狼β、狼δ) 为依据进行调整.

图2 灰狼社会等级划分[18]Fig.2 Hierarchy of grey wolf[18]

(1) 包围

包围本质上是一种灰狼位置更新的法则,是指当假定的猎物位置已知时,灰狼种群如何实现逐渐接近猎物.因此,在商超配送路径规划过程中,包围表示,在有多个配送方案的集合中,选定某一方案并将其视为猎物,此时集合中其他方案将以该方案为依据进行调整,这种做出调整的法则即为包围猎物的过程.具体的调整方式为[18]

(2) 追捕

由于在实际情况下,求解之前无法得知适应度值的最佳配送方案,改进灰狼优化算法假.设狼α、狼β、狼δ(适应度值最佳的前3 个配送方案所对应的所有车辆经过的商超客户序列) 更了解猎物 (全局最佳配送方案所对应的所有车辆经过的商超客户序列) 的潜在位置,有能力带领狼ω(其余配送方案所对应的所有车辆经过的商超客户序列) 识别并包围猎物.

因此,追捕是在包围的基础上,分别将狼α、狼β、狼δ视为猎物,综合考虑这3 只灰狼的位置进行狼ω的位置更新.在商超配送车辆路径规划过程中,追捕表示,利用包围中的配送方案调整法则,将适应度值最佳的前3 个方案作为猎物,分别得到3 种配送方案调整方式,再利用公式[18]

综合3 种调整方式,得出每辆车初始经过的商超客户,作为最终调整方案.

(3) 攻击和搜索

在完成包围、追捕的活动后,灰狼种群可以做出2 种选择: 攻击或搜索.攻击是指确定输出当前最优解;搜索是指放弃当前最优解,探索其他可行解.因此,在商超配送车辆路径规划过程中,攻击表示,在追捕活动后,将得到的最终配送方案输出,作为全局最佳配送方案;搜索表示,放弃追捕活动得到的最佳方案,以跳出局部最优解,去探索其他更佳的配送方案.

如何在攻击和搜索中做出选择,取决于系数向量.改进灰狼优化算法设置:时,攻击猎物,即确定最佳配送方案;时,搜索猎物,即探索其他更佳配送方案.

3.4 变异操作方法

与遗传算法的目的一致,变异操作是为了产生新的商超配送路径方案.对狼α所对应的配送路径规划方案进行部分单点移动的变异操作.变异操作的过程如图3 所示,具体可以分为以下2 个步骤.

图3 变异算子示意图Fig.3 Schematic diagram of the mutation operator

步骤1: 在狼α对应的配送路径规划方案中,随机选择某辆车所服务的2 个商超客户.

步骤2: 将服务顺序靠后的商超客户向前移,移至服务顺序靠前的下一个,并进行配送服务.同时,2 个客户之间的其他商超客户的服务顺序依次后移,产生新的配送方案.

4 实例分析

4.1 实例数据

本文选用中国外运公司商超项目中2020 年6 月6 日北京配送中心的需求订单数据来验证本文方法的有效性.该数据包含1 个配送中心的位置信息、20 个商超类型客户的位置信息和订单需求量.配送中心的所有客户总需求量为6 035 个货物,车辆派遣成本为850 元/辆,平均的车辆行驶成本为0.5 元/km.

已知该配送中心所服务的商超类型客户均位于北京市内.为了便于研究,利用地学大数据平台①http://www.giscalculator.com/将数据中的文本位置信息转换为位置经纬度,并应用大地坐标系与空间直角坐标的关系转换公式[19]将经纬度投影到空间直角坐标系下.其位置分布和订单需求如图4 所示.图4 中,商超客户和配送中心旁边括号内的数字分别表示商超客户结点的编号及其订单需求量.

图4 北京配送中心商超配送信息Fig.4 Beijing distribution center supermarket delivery information

图5 为订单需求分布箱线图.从图5 中可以看出,商超客户的需求量差异较大,取值范围为[10,1 600],呈长右尾分布,平均需求量为300.图6 采用热力气泡式数据图展示了北京配送中心的所有商超客户需求分布情况.其中,气泡的位置表示每个客户的坐标,气泡的大小和颜色均表示每个客户的需求量大小(需求货物的个数).根据图6,结合北京市的实际情况来看,各客户的订单需求量大致呈环状分布: 内环靠近北京市中心,订单大多来自人流量较大的卖场,而此类卖场仓储面积较小,订单需求量较小;外环靠近郊区,大多是商超的自建仓储物流中心或仓储型超市,订单需求量较大.

图5 订单需求分布箱线图Fig.5 Boxplot of order demand distribution

图6 订单需求分布热力图Fig.6 Heat map of order demand distribution

根据“20/10/5 规则”的订单拆分策略,将北京配送中心的20 条需求订单数据进行拆分.以配送车辆容量限制为2050 (总需求量∶车辆容量=2.9) 为例,得39 个新订单.订单需求信息展示在了表2 中,其中最后一列即为拆分后的新订单.

表2 订单拆分后的商超配送信息Tab.2 Supermarket delivery information after order split

4.2 算法分析

采用改进灰狼优化算法求解,设置算法的参数取值如表3 所示.使用Python3.8 语言编程运行,实现改进灰狼优化算法.经过多次实验并观察算法的收敛趋势.本文发现将迭代次数设置为300 次最为合理.

表3 灰狼优化算法参数取值Tab.3 Grey wolf optimization algorithm parameter values

(1) 与标准灰狼优化算法对比分析

改进灰狼优化算法是在标准灰狼优化算法的基础上添加遗传变异操作而设计的.为验证改进后算法的求解效果,将改进灰狼优化算法与标准灰狼优化算法进行实例对比分析.

由于设置的种群规模和迭代次数的不同,所得方案的配送总成本也会有所不同.因此,本文分别在不同的种群规模和迭代次数下进行了实验.表4 给出了不同迭代次数下的对比结果;表5 给出了不同种群规模下的对比结果.

表4 不同迭代次数下算法求解效果对比Tab.4 Comparison of algorithm solution effects under different iterations

表5 不同种群规模下算法求解效果对比Tab.5 Comparison of algorithm solution effects under different population sizes

为方便分析,表4 和表5 中均显示出了改进灰狼优化算法与标准灰狼优化算法的配送成本优化水平 (Δz) . Δz的计算公式为

公式(21)中:z表示标准灰狼优化算法的所得方案配送总成本;z′表示改进灰狼优化算法的所得方案配送总成本.通过计算配送总成本的 Δz,可以反映改进灰狼优化算法的优化水平.

从表4 和表5 中可以看出,随着种群规模和迭代次数的增加,2 种算法的运行时间也都在增长.因此,需要设置合理的种群规模和迭代次数,以便在时间允许范围内获得相对最佳的配送路径规划方案.此外,根据表4、表5 中的结果还可以发现,与标准灰狼优化算法相比,改进灰狼优化算法所得方案的配送总成本的降低比率为14%～ 20%.

可见,改进灰狼优化算法能够明显降低配送方案总成本.虽然运行时间比标准灰狼算法慢,但是在可接受的运行时间范围内 (大概500 s).

(2) 与遗传算法对比分析

通过与遗传算法的实例结果进行对比,验证改进灰狼优化算法求解基于订单拆分策略的容量限制商超配送路径问题的有效性.设置遗传算法的交叉概率和变异概率分别为0.65 和0.20,种群进化代数 (迭代次数) 为300,得到问题求解过程的目标函数适应度曲线对比图如图7 所示.为了更好地反映两种算法之间的差距,图7 中的目标函数值为真实值扩大10 倍后的可视化结果: 图7(a)显示了无订单拆分的2 种算法配送总成本变化趋势对比;图7(b)显示了有订单拆分的2 种算法配送总成本变化趋势对比.

图7 适应度变化曲线图Fig.7 Fitness change curve

从图7(a)、图7(b)中可以看出,无论是否进行订单拆分,改进灰狼优化算法都比遗传算法所得配送方案的配送总成本低.这是由于遗传算法都是直接在迭代过程中收敛至算法所能得到的最优解;而改进灰狼优化算法则能够突破局部最优解,在更广的范围内搜索其他更佳的配送方案,最终达到收敛.

将图7(a)、图7(b)进行对比,可以发现,有订单拆分的适应度曲线较没有订单拆分的收敛速度更慢.这是因为拆分会使订单数量增加,改进灰狼优化算法的计算量也会随之加大,适应度曲线的收敛速度就会相应减慢.所以,过细的订单拆分策略可能导致曲线无法收敛.但是,合理的订单拆分能够更充分地利用车辆容量,减少使用车辆数,降低配送总成本,这一点将在4.3 节详细介绍.

4.3 结果分析

为验证“20/10/5 规则”的订单拆分策略的适用性,本文在商超客户订单需求量确定的情况下,以总需求量为车辆容量的1.1 倍～ 3.5 倍,步长为0.2,设定车辆容量限制,分别做了13 组“有”“无”订单拆分的对比实验,分析不同的车辆容量限制和“有”“无”订单拆分对配送路径方案总成本的影响.图8 显示了在不同的“总需求量∶车辆容量”下配送总成本在有订单拆分 (蓝色虚线) 和无订单拆分(红色实线) 情况下的变化趋势.

图8 实验结果对比Fig.8 Comparison of experimental results

从图8 可以看出,无论有订单拆分还是无订单拆分,随着“总需求量∶车辆容量”的增加,配送总成本呈梯度上升趋势.此外,当总需求量为车辆容量的1.9 倍和2.9 倍时,有订单拆分的配送总成本明显低于无订单拆分的情况,即当商超客户总需求量接近车辆容量的整数倍时,使用“20/10/5 规则”,订单拆分策略效果更好.这是因为“总需求量∶车辆容量”直接影响车辆的行驶距离和使用车辆数,进而影响车辆的行驶成本和派遣成本,造成配送总成本的变化.当总需求量接近车辆容量的整数倍时,采用订单拆分策略能够更充分地利用车辆容量,提高车辆容量利用率,减少使用车辆数,降低车辆派遣成本,进而节省配送总成本.

为验证订单拆分策略对总需求量接近车辆容量的整数倍的适用性,以总需求量∶车辆容量=2.9为例,表6 列出了其具体的商超配送路径规划方案,并在图9 中对有订单拆分和无订单拆分的配送路线进行了可视化.根据图9(a)、图9(b)的结果对比,可以看出,进行订单拆分后有2 个商超客户 (⑪、⑬) 被服务了多次,同时使用车辆数也减少了1 辆.

图9 配送路线图Fig.9 Delivery route map

表6 商超配送路径规划方案Tab.6 Supermarket distribution routes planning scheme

表7 从总成本、使用车辆数和平均车辆容量利用率这3 个方面,对上述商超有无订单拆分的配送方案的优劣进行了对比分析.从表7 可以看出,当总需求量为车辆容量的2.9 倍时,有订单拆分的方案比无订单拆分的方案配送总成本低了845.42 元,使用车辆数少了1 辆,平均车辆容量利用率高了24.53%;当商超客户总需求量接近车辆容量的整数倍时,“20/10/5 规则”订单拆分策略能够充分地利用车辆容量,减少使用车辆数,降低配送总成本.

表7 配送方案对比结果Tab.7 Delivery plan comparison results

5 结束语

本文针对商超配送中所存在的车辆配载和路径规划问题,构建了基于订单拆分的带容量限制的商超配送路径规划模型;结合遗传算法中的变异操作,设计改进了灰狼优化算法并进行了求解.通过实例分析,与求解CVRP 的代表性启发式算法—遗传算法进行了对比.结果显示,本文所提的基于订单拆分的模型和算法,在解决带容量限制商超配送路径规划问题时能够取得良好的效果;特别是通过选择合适的车型使商超客户总需求量接近车辆容量的整数倍时,更能够充分地利用车辆容量,降低车辆的空驶率,减少配送总成本.

通过真实案例的验证,本文有以下总结.

(1) 对于配送中心拥有多种可选车型的企业,建议其根据所有商超客户的全部需求量之和选择合适的车型,使商超客户总需求量接近配送中心车辆容量的整数倍.此时,企业可以采用订单拆分策略进行车辆配载和路径规划.

(2) 对于订单拆分方式,建议企业按照每个商超客户需求量相对于配送车辆容量的比例进行拆分.由案例分析结果中各项指标的对比可知,“20/10/5 规则”的订单拆分策略可作为企业进行订单拆分时的一种良好选择,企业也可以根据实际情况使用更合适的订单拆分方式.

(3) 对于求解算法,本文所提的改进灰狼优化算法,在可接受的运行时间范围内,能明显降低配送方案总成本,获得成本更低的商超配送路径规划方案.

本文在设计配送方案时,仅考虑了客户需求量和车辆容量限制.未来将会扩展到时间窗约束、车型限制、客户满意度、客户需求量变动等因素,进一步修订模型;同时,对于更大规模的配送路径问题,探究如何提高算法的工作效率,以增强其实际应用效果.