基于混合遗传算法的生鲜配送路径优化研究

陈雄寅,韦妙花

(1.黎明职业大学 商学院,福建 泉州 362000;2.浙江师范大学 教师教育学院,浙江 金华 321004;3.泉州职业技术大学商学院,福建 泉州 362000)

0 引言

随着我国生鲜农产品的市场需求量的日益增长和对其品质需求的不断提升,生鲜农副产品流通过程中存在的不足逐渐显现,特别是我国当前农副产品物流基础设施和信息化程度仍存在很多欠缺。生鲜农副产品品类众多、保鲜方式差异大、储存周期短、消费者需求点分散、路径网络繁杂,生鲜农副产品物流配送路径的优化设计是相关企业亟待解决的难题。而且,市场对生鲜农副产品的选择性、多元性、新鲜度等品质要求的提升,生鲜农副产品的配送的时间方面的要求也为路径优化提出了新的要求。配送是生鲜农产品流通过程中一个非常关键的环节,科学、合理的设计配送车辆路径对消费者、企业和社会都有着举足轻重的影响。通过配送车辆路径优化设计,可以提高配送效率,降低配送成本,准时快速地完成配送任务,从而提高消费者的满意度和企业经济效益,还可以节约车辆使用数量,减轻城市拥堵,减少汽车噪声和尾气排放量,保护了生态环境。

生鲜农产品配送车辆路径优化(Vehicle Routing Optimization,VRP)问题属于带时间窗的车辆路径(Vehicle Routing Optimization with Time Windows,VRPTW)问题,该问题是由Pullen等[1](1967),Knight等[2](1968)考虑提供服务间隔时间约束时提出的。我国对该类问题的研究主要集中在模型构建和求解方法两个方向。2014年,杨磊等以顾客满意度为目标函数,以客户的时间要求为约束条件,建立带时间窗口的鲜活农产品配送模型进行配送车辆路径优化研究[3]。2016年,葛显龙等考虑路程等因素,以物流企业的最小成本(车辆成本和货损成本)为目标函数,建立了带时间窗口约束的优化模型,并给出最优车辆路径[4]。2017年,朱莉等以最短车辆运行时间为最优目标提出了一种带时间窗口的紧急救援路线优化模型,解决了带时间窗的跨区救援线路优化问题[5]。2019年,冀巨海等以配送成本最小为目标函数,建立了基于软硬时间窗口限制和取送两种方式相结合的配送车辆路径优化模型[6]。2017年,郭咏梅等针对突发事件中的应急物流VRPTW问题,提出一种蚂蚁算法和人工鱼群算法相结合的混合算法[7]。2018年,邓红星等构建了公路零担物流配送路径优化模型,并提出置换算法求解得出最优方案[8]。2010年,汪勇等将协同进化思想引入遗传算法,解决了传统遗传算法已陷入局部最优点的不足,并在VRPTW问题上得到较优的优化结果[9]。2012年,石兆等以费用和最小为目标函数,考虑运输、制冷、货损和惩罚成本约束,构建了配送车辆路径优化模型,再利用两阶段HGA算法给出最优配送方案[10]。2019年,葛显龙利用时空泊松分布来仿真客户位置,考虑客户的时间和空间随机性,构建了多商品同时配送的数学模型。同时,他通过GA和禁忌搜索相结合的优化方法进行问题求解[11]。2020年,赵志学把交通拥堵情况引入VRPTW数学问题,构建了配送车辆路径优化的数学模型,并采用GA进行问题求解[12]。

文章在现有研究成果的基础上,针对生鲜农副产品配送问题构建配送路径优化模型,并提出一种改进的遗传算法进行路径优化研究,为企业生鲜农产品配送车辆及路径决策提供理论参考。

1 配送车辆路径优化模型

文章以生鲜农产品配送路径优化为研究对象,以配送路径最短构造优化模型,寻找最优配送方案。

1.1 模型假设

(1)假设存在一个配送中心和多个客户,配送车辆充足;

(2)配送车辆匀速行驶且燃料充足,无故障;

(3)配送中心货物充足,能满足多个客户需求;

(4)所有货品运输储存温度一致;

(5)车辆的载重量相同;

(6)车辆服务完最后一个顾客后返回配送中心。

1.2 符号定义

A:表示客户节点数量,A={0,1,2,…,A}, 0表示配送中心;

K:配送中心车辆数量;

Q:配送中心车辆的容量;

ti:到达第i个客户点的时间;

wi:第i个客户点的等待时间;

dij:第i个客户点与第j个客户点的距离;

qi:第i个客户点的需求量;

fi:第i个客户点的服务时间;

Ei:第i个客户点的最早服务时间;

Li:第i个客户点的最晚服务时间;

Tk:第k辆车的最大行驶时间。

1.3 决策变量

1.4 目标函数

根据符号定义及决策变量,运输车辆路径最短的目标函数可以表述为:

(1)

1.5 约束条件

(1)配送中心车辆数量约束

(2)

(2)车辆配送完成后返回配送中心

i=0,1,2,…,A;k=1,2,…,K

(3)

(3)每个客户点都被一辆车服务一次

(4)

(5)

(4)每辆车的容量约束

(6)

(5)车辆最大行驶时间约束

(7)

(6)客户服务时间约束

(8)

Ei≤(ti+wi)≤Lii=1,2,…,A

(9)

t0=w0=f0

(10)

2 混合遗传算法

2.1 混合遗传算法

混合遗传算法是在基础遗传算法的基础上引入节约算法产生初始种群,进而降低遗传算法的搜索维度;引入大规模邻域搜索算法中的破坏算子和修复算子,增强算法的局部搜索能力。混合遗传算法流程如图1所示。

图1 混合遗传算法流程图

2.2 C-W节约算法改进种群初始化

C-W节约算法是为解决TSP问题提出的一种无约束算法,不能直接用于VRPTW问题求解的种群初始化,文章通过增加车辆负载量和配送时间窗口改进C-W算法,在满足客户需求量、时间窗口和车辆最大负载量的约束下,确定最短路径作为初始种群。具体改进及实现步骤如下:

Step1: 计算路径上任意两个点节省的里程值s(i,j),构造集合S={s(i,j)|s(i,j)>0},并对里程值从大到小排序。

Step2:若S=φ,终止计算。否则,判断第一项(i,j)两点间的最大s(i,j)是否满足以下条件之一,若符合,转Step2,否则,转Step6。

(a)点i和点j不在意配置的路径中;

(b)点i和点j已在意配置的路径上,但两点不属于同一条路径;

(c)点i和点j由多条直线连接,但它们不是路径内的点,点i和点j分别为起点和终点。

Step3:计算连接点i和点j后线路上的总载货量dij,若dij

Step4:计算每条路径上各点开始服务时间和返回配送中心时间。

Step5:连接点i和点j,计算车辆到达每个客户点的新时间和返回配送中心时间,判断是否违反TW约束。若满足TW约束,则生成较优的初始路径,否则,转Step6。

Step6:消除S中的元素s(i,j),点i和点j不能插入作为配送车辆服务的客户点。如果S=φ,终止计算,否则,转Step2。

2.3 大规模邻域搜索算法改进局部搜索

传统遗传算法的局部搜索容易出现过程停滞,在一定程度上影响了优化求解的效率和最优结果的精度,文章引入大规模邻域搜索算法的破坏和修复思想改进遗传算法的局部搜索操作,提高VRPTW问题配送路径优化精度。

对于带时间窗的配送路径优化问题,定义客户点i和客户点j之间的相关性为

(11)

(12)

根据式(11)和式(12)可知,客户点i和客户点j在同一配送路径上,相关性越大,则在破坏操作中越先移除。破坏操作选择移除客户点的过程中,为确保每次调用时都能破坏解决方案的不同部分,引入控制确定性的随机性参数。

移除若干客户后,再使用修复操作将移除的客户点重新插入车辆行驶路径增加最少的位置,并检验插入后是否满足车辆载重量和时间窗约束。具体修复过程为:首先,找到满足约束条件的位置,计算增加值最小的位置插入;然后,计算所有移除客户点插入最佳位置后的目标增加值,将增加值最大的客户作为第一个插入;重复上述操作,直至移除客户点全部插入配送路径。

3 仿真实验及结果分析

为检验混合遗传算法的求解性能,在Intel Core i5 2.7 Gz处理器, 8.0 GB内存, 64位Windows 10环境下,运用Python编程实现了求解VRPTW问题的混合遗传算法,并对算例进行仿真实验。

本算例来源于文献[13],配送中心标记为0点,20个客户点标记为1～20,车辆最大载重量为9吨,车辆行驶速度为40 km/h,以满足车辆载重量和时间窗约束为前提,规划最短配送路径及车辆数量。客户点和配送中心位置信息如表1所示。

表1 配送中心及客户点信息

针对上述算例,运用文章给出的混合遗传算法进行仿真实验,实验初始参数选取如表2所示。程序运行10次,实验结果见表3。

表2 仿真实验初始参数

表3 仿真结果及分析

由表3可知,10次仿真求解获得2种最优配送路径,方案1求得次数为7次,配送路径最短距离为68.72 km;方案2求得次数为3次,配送路径最短距离为68.87 km;两种方案的最短路径的绝对差为0.15 km。对比结果表明:文章提出的混合遗传算法求解过程稳定,结果精度高,虽然两种方案的最短配送路径存在一定的距离差异,但均可以指导企业配送路径规划。

运用传统遗传算法求解最短路径为86.24 km,配送车辆3辆,具体路径为:0-1-14-15-3-9-18-2-0,0-17-16-6-20-10-7-0,0-11-8-12-19-5-13-4-0。对比两种优化结果可以看出混合遗传算法所得路径优于传统遗传算法,生鲜配送车辆路径较传统算法大幅缩短。

文章提出的混合遗传算法可以有效避免陷入“局部收敛”的现象,加快了收敛速度,较好地解决了有时间窗的VRPTW问题,文章所述配送路径的优化结果是一个较优的方案,可以指导生鲜农产品规划配送车辆路径。

4 结论

文章以生鲜农产品配送路径优化为切入点,考虑时间窗约束构建了配送路径最短的优化模型,基于遗传算法、节约算法、大规模邻域搜索算法给出了一种混合遗传算法的实现流程,详细阐述了C-W节约算法初始化种群和大规模邻域搜索算法局部搜索操作的具体步骤,并通过算例仿真实验进行验证。仿真试验获得算例配送路径为4条,最多需要车辆数量为4辆,最短配送路径68.72 km,优于传统遗传算法所得最短路径。验证结果表明:本研究给出的混合遗传算法能较好地解决有时间窗的车辆路径问题,所得方案较优,可以指导企业规划配送车辆的路径。