基于智能算法的社区团购配送路径优化

王 丹, 让桂芳

(沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳 110044)

绿色低碳是运输行业的关注热点[1]。随着电商的飞速发展,人们越来越愿意选择在线上购买生鲜商品,社区团购行业发展迅速,各大企业纷纷抢占市场份额与商机[2]。社区团购指的是以各个社区为单位,以社交软件为平台,用户通过小程序购买商品的新兴零售模式[3]。由于配送路径不合理而造成的运输成本高严重影响着企业的利润[4],因此,社区团购企业应该合理规划配送路径。

车辆路径问题(vehicle routing problem)指在多个约束的条件下,为满足客户的需求,由配送中心安排调度,从而给出配送方案,最开始是Dantzig等[5]在1957年提出的。范立南等[6]针对农产品的配送问题,考虑了碳排放成本的加入,使用遗传算法进行求解。张天瑞等[7]在碳税政策下考虑了疫情原因,引入了消毒成本,并使用细菌觅食-蚁群算法对模型求解。社区团购是中心仓配送到团长,团长再配送或用户自提的仓配模式,或者由中心仓配送到网格仓,然后由网格仓往团长站点进行配送。本文在以往的研究基础上研究了由中心仓配送到团长的过程。与已有研究不同的是,本文综合考虑了多方面成本,更贴合实际情况,同时利用一种新型的智能算法----鲸鱼算法,对配送路径进行优化,以追求总成本最小。

1 问题描述

对社区团购来说,城市中心仓为调度中心,团长为客户。可以描述为:当日车辆统一从城市中心仓出发,经过运输,在规定的时间内,到达团长站点的位置进行卸货,并且一个团长站点只能由一辆车进行服务,但同一车辆可为多个团长站点服务。调度中心合理安排配送路径,既能满足客户需求,又能降低配送总成本[8]。图1为社区团购中心仓配送示意图。

图1 社区团购中心仓配送示意图

2 社区团购配送路径优化模型

2.1 模型假设条件

在构建模型时,对问题做如下假设:

① 在单个区域内有1个中心仓,车辆由中心仓出发,完成后返回中心仓;

② 中心仓商品库存充足,单车配送量不大于车辆的最大载重量;

③ 已知固定的各个团长站点位置、需求和时间窗;

④ 货物到达时间不在时间窗内,将产生惩罚费用,但不考虑卸货时间消耗;

⑤ 碳排放成本仅考虑运输时,运输距离取实际距离且车辆匀速行驶无特殊情况;

⑥ 团长站点仅能被服务一次,车辆可以服务多个团长站点,不考虑逆向物流;

⑦ 中心仓拥有数量充足的配送车辆,车辆为燃油车,载重量相同且燃油和制冷剂充足。

2.2 设置参数说明

根据城市中心仓的地点和团长站点的位置进行数学模型的创建,模型中的符号定义见表1。

表1 符号说明

2.3 数学模型

根据实际配送情况,主要考虑的成本[9]分析如下。

1) 固定成本F1。固定成本与实际调度车辆数目相关,

2) 运输成本F2。运输成本主要与燃油的使用量相关,跟车辆的实际行驶距离成正比[10],

3) 货损成本F3。社区团购行业中,包含了大量的生鲜冷链商品,此类商品订单量大且在配送过程中容易发生商品变质、新鲜度降低等情况。本文考虑到商品的价值损耗,货损成本主要由货物总量Q,配送时间T及损耗系数ω影响,假设商品均价为P,

4) 制冷成本F4。运输生鲜商品时需要控温,所以考虑制冷剂的消耗量,

5) 碳排放成本F5。碳排放成本,主要是与运输过程中消耗燃油制冷剂产生的CO2排放造成的,

6) 时间窗惩罚成本F6。社区团购的优势是快速准时,所以对时间窗的要求比较高,当配送车辆为ti,若未在团长站点i预期的时间窗[Ei,Li]范围内送达,就会产生惩罚成本,

因此建立最小总成本(Z)为目标的数学模型:

minZ=F1+F2+F3+F4+F5+F6。

其余约束条件如下:

(1)

式(1)表示每个团长站点最多由一辆车提供配送服务;

(2)

式(2)限制了配送车辆的最大载重量;

(3)

式(3)表示每一辆车从城市中心仓出发后又返回中心仓。

3 鲸鱼优化算法

针对该数学模型,采用鲸鱼优化算法进行求解。

鲸鱼优化算法(whaleoptimizationalgorithm,WOA)是模仿自然界中鲸鱼捕捉猎物行为的新型智能优化算法,最近几年被广泛应用在组合优化或连续优化问题上[11]。鲸鱼优化算法搜索过程中,一个鲸鱼个体代表着一个解,若干个鲸鱼通过不断更新迭代自身位置,直到搜索出满意解为止[12]。鲸鱼进行优化搜索的捕食动作主要分为3种:包围猎物、发泡网攻击和搜索捕食[13]。如图2[14]所示。

图2 泡泡网捕食法

1) 包围猎物。座头鲸在捕食时,首先会识别猎物的位置,然后再进行对猎物的围捕[15]。计算公式如下:

2) 气泡攻击。气泡攻击是座头鲸在捕食时特有的吐气泡的行为,当前鲸鱼个体选择螺旋运动的方式向当前最佳鲸鱼个体靠近[17],进行位置的更新,

式中:参数b为对数螺旋形状常数,控制鲸鱼个体进行螺旋式移动通常取值为1,当b=1时,鲸鱼的移动轨迹表现为普通的对数螺旋线;l代表一个取值范围为[-1,1]的随机数,与螺旋形状参数b一起,用于计算鲸鱼个体在进行螺旋移动时的位置更新,L的随机性为算法提供了多样性。座头鲸在捕食游走时,各以50%的概率选择包围圈或选择以螺旋式向猎物游走[18]。数学模型见式(4)。

(4)

3) 搜索捕食。因为在气泡攻击时,数学模型中的A1的取值范围是[-1,1],也就意味着当A1的取值不在此范围时,当前鲸鱼个体有可能不会向当前最佳鲸鱼个体进行游动,而是随机选择搜索其他鲸鱼个体[19]。这样的搜索捕食过程也就增加了该算法的全局搜索能力。Xrand为随机选择的鲸鱼位置。搜索捕食行为的数学模型如下:

式中,Xrand为鲸鱼群体中随机选择的一个鲸鱼个体的位置。

综上所述 ,WOA求解问题的流程图如图3所示。

图3 WOA求解问题流程

4 算例分析

为研究社区团购区域中心仓-团长环节的配送问题,本文在进行算例分析时,考虑到社区团购行业的配送活动范围的有限性,区域仓的配送范围覆盖分为200个左右的小区,单个小区团长站点数量在0～2个的范围内,同时也会因订单需求的不同,来决定是否需要进行配送活动,所以选取种群数量N=200,初始种群成员分别选取40、60、80和100,使用WOA进行求解,分别选取第7代和第22代的结果,对其总群数量的敏感性及其收敛性进行分析,得到的数据如图4与图5所示。

图5 不同种群数量最优解变化曲线(第22代)

分析图4、图5发现,无论是第几代,当初始种群数量为100时,目标函数取得满意值的速度更快,收敛性更好;而当初始种群数量为40时,目标函数取得满意值的速度相对较慢,即当区域内团长站点数量变得更少时,不易取得满意解。这也表明随着种群规模的增加,不仅能增强搜索能力,还能提升算法向最优解逼近的速度,收敛性更强。

在鲸鱼优化算法求解问题的过程中,一个鲸鱼可以用来代表一个解,搜索问题最优解的过程就可以看成是若干个鲸鱼个体不断地更新个体的位置,直到搜索出满意的解为止。鲸鱼优化算法能够随机选择其余一些非最优解的情况,这能够有效地避免陷入局部最优解。同时,在收敛的过程中也能够降低遗漏最优解情况的发生。同时鲸鱼优化算法具有结构简单、参数少、搜索能力强、易于实现等优点。种群成员数量越多,路径优化效果越好。因此,该算法在面向社区团购企业进行大规模配送的场景时是完全适用的,而且当团长站点数量越多,效果就越好。

5 结 论

为解决社区团购因配送路径不合理造成的成本增加,同时响应国家低碳政策的号召,本文研究了由区域中心仓到团长这一配送环节。构建了考虑碳排放的路径优化模型,考虑了固定成本、运输成本、货损成本、制冷成本、碳排放成本和时间窗惩罚成本等多种因素,将鲸鱼优化算法应用于面向社区团购的配送路径规划问题,不仅可以降低二氧化碳的排放量,还能为企业选择合理的配送路径方案,降低配送环节的成本,增大利润空间,有利于企业长远发展。

配送路径优化问题,就是在多个约束下,选择总成本最小方案。而对于社区团购这种线上购物平台来说,既要寻求多种成本的降低,又要考虑客户的满意度。鲸鱼优化算法具有搜索范围广、结构简单、搜索能力强等优点。本文验证了鲸鱼优化算法在种群成员数量越多的情况下,搜索能力越强和收敛效果越好,并且迭代次数越多,取得满意解越早,也就说明鲸鱼优化算法在区域内团长数量较多、需求零散的情况下,仍拥有较强的稳定性和收敛速度。在总成本最小的目标下,能在有限的迭代次数内,寻找到满意解,为配送车辆的提供路径方案,为社区团购企业提供了车辆配送路径优化的求解方法。