路世昌,刘丹阳
辽宁工程技术大学工商管理学院,辽宁 葫芦岛 125105
冷链物流运输是指客户所需货品在整个运输网络体系中始终处于预先设定的低温环境中,从而确保货品的质量。近年来,社会经济的快速发展推动了居民饮食结构体系的转变,人们对瓜果、水产品及新鲜肉禽制品等冷链食品的需求量快速上升。一方面,高品质的生活需求极大地促进了我国冷链产业的发展。同时,以上货品对环境温度、运输包装等因素敏感性强,且存在易腐烂、易变质、新鲜度难以长效保持等特征,必须依托冷链物流进行配送[1-2]。结合以上背景,开展冷链物流配送方面的研究具有极为重要的意义。
冷链物流运输问题可归结为复杂问题特征、目标体系和约束限制下的车辆路径问题(vehicle routing problem,VRP)[3]。本文所研究的多车场冷链物流配送问题相比于经典的VRP模型增加了以下三方面的复杂因素:(1)以总成本为指标、优化目标组成结构复杂,成本体系囊括了车辆成本、运输成本、制冷成本和货损成本;
(2)考虑了多中心联合配送,需要兼顾不同中心的运输线路构造特征以及配送能力(具体表现为各中心运输车数目约束);
(3)要求遵循严格的时效约束,即严格限制每个客户接受服务的最晚时间,旨在确保每个客户能够在满意的时间范围内获取所需货品。VRP 问题已被证明具有NP 难复杂性,而当前模型的复杂特征更加剧了问题的求解难度。鉴于此,决策算法的设计开发在冷链物流配送研究中占据重要地位。
冷链物流配送问题的决策方法可分为精确算法、构造式算法和进化算法三大类[4]。精确算法包括整数规划建模、分支定界、分支定价等,例如:Deng 等[5]研究了一类带有时效约束、货物不兼容因素、取送同步等特征冷链物流配送问题,并构建了分支定价算法以优化运输、制冷和货损成本总和。尽管此类方法获取小规模问题的精确解,但运行时间随着问题规模的增加呈现爆炸式增长,且该类方法无法处理具有复杂约束和目标的问题。构造式算法通过组合调度规则获取运输方案,该算法对问题设置有较高依赖性,对当前模型的约束、目标进行调整将导致原先性能较优的调度规则生成糟糕方案的情形[6]。近年来,进化算法取得了长足发展,这为具备复杂目标体系和约束条件的冷链物流配送问题提供了新的求解思路。Zhang等[7]研究了一类考虑碳排放因素的冷链物流配问题,借助蚁群算法构建决策方法体系,优化包含运输成本、货损、碳排放等六类成本指标总和,该研究通过实例分析以验证算法的有效性。Dou等[8]学者对冷链物流配送与中心选址的组合问题进行了建模,构建以最优化总成本指标为目标的数学模型,并创立了免疫狼群混合求解算法,该研究通过算法对比实验验证了所构建算法的高效性。尽管如此,借助进化算法求解冷链物流配送问题仍需合理解决以下问题:(1)构建高效的编解码方法,实现算法与问题适配;
(2)提升基本算法的搜索性能,克服易陷入局部最优、搜索停滞等缺陷[9]。鉴于此,本文构建了改进正余弦算法(ESCA)求解多车场冷链物流配送问题。
正弦余弦优算法,简称SCA,是由Mirjalili[10]于2016年提出的一种新型的高效进化算法。SCA 算法具有架构简单、控制参数少、迭代效率高等优势,相关研究表明SCA算法相较于遗传、粒子群等经典进化算法具有更优的寻优性能[11]。目前,SCA已经在众多工程领域获取了应用,包括机器人路径规划、图像处理、车间调度等[12]。例如:马莹莹等[13]构建了基于SCA 的混合算法,并将其应用于机器人路径规划问题,通过各类环境的下算法的对比实验证明了改进算法求解机器人路径规划问题的高效性。鉴于SCA 算法的良好表现,本文将其运用于本文所研究的冷链物流配问题。
由以上文献综述可知,尽管本文所研究的冷链物流问题的特征在相关文献中有所涉猎,但综合考虑客户单边硬时间窗、多中心联合调度和各中心车辆使用数约束的冷链物流调度研究相对较少,同时鲜有文献构建基于SCA算法这一优质进化算法的冷链调度方法。由No-Free-Lunch 理论可知,尚不存在一种决策方法能够完美地解决所有的冷链调度问题[14]。鉴于冷链物流的实际意义和调度算法研究的工程价值,本文针对一类考虑多中心联合配送和时间窗约束的冷链物流配送问题进行了建模,并提出了改进正余弦算法,通过案例研究和算法对比实验证明了该算法的优化性能。
如图1所示,展示了当前所研究的多车场冷链物流配送问题的示意图。
图1 问题示意图Fig.1 Schematic diagram of considered problem
运输车从多个中心出发向客户供应物资,为提升配送效率与客户满意度,需综合考虑网络结构、客户需求、车辆载荷和配送时效等因素,在此基础上合理规划配送方案。本文从成本优化视角对当前问题进行建模,力求在满足客户需求的同时降低运输过程所产生的成本费用,具体包括车辆成本、运输成本、制冷成本和货损成本。
为对当前运输网络进行合理化建模,在此作如下假设:(1)配送中心和客户的空间位置已知,网络中任意两点间的路径距离和用时均已知且为定值;
(2)每个中心的车辆总数已知,运输车从各自中心出发、完成配送任务后返回所属中心;
(3)所有客户的需求均已知,且要求每个客户接受服务的时间不得晚于规定的时间阈值;
(4)采用同型运输车负责配送任务,当前车型的载荷和成本系数等均一致且为已知量;
(5)规划期内每辆运输车只能被调度一次,运输过程不得超载;
(6)每个客户仅能由一辆运输车访问一次,不允许需求拆分;
(7)相比于不同空间节点之间的运输用时而言,每个客户点处的装卸时长较短,建模过程不予考虑。
为实现降本增效的目标,需合理决策以下三个子问题:(1)确定每个中心覆盖的客户范围;
(2)指定每辆运输车服务的客户集合;
(3)规划各辆运输车的行进路线。
基于以上问题描述,在此定义问题参数和决策变量以便于构建多车场冷链物流配送问题的数学模型。
(1)集合
ND:配送中心集合。
NC:客户节点集合。
N:所有位置节点集合,即N=ND∪NC。
K:车辆集合。
(2)下标
k:车辆索引,k∈K。
i,j:节点索引,i,j∈N。
(3)参数
dij:i和j间的路径距离,i,j∈N且i≠j。
τij:i和j间的路径用时,i,j∈N且i≠j。
qi:客户点i的需求量,i∈Nc。
Q:运输车的载重。
Li:客户点i允许的最晚到达时间,i∈NC。
Ki:配送中心i处可用的车辆总数,i∈ND。
cveh:运输车启动成本。
cvar:单位里程的油耗成本。
cpri:单位需求量的单价。
r:需求的损耗系数。
ccool:单位时长的制冷成本。
(4)变量
xijk:若车辆k从i驶向j,xijk=1;
否则,xijk=0,其中i,j∈N,k∈K,且i≠j。
yki:若节点i由车辆k服务,yki=1;
否则,yki=0,其中i∈NC,k∈K。
ti:节点i接受服务的时间,i∈N。
(1)车辆成本
冷链物流依托冷藏车向所有客户供应所需物资,启动冷藏车需耗费一笔车辆成本,其组成包括驾驶员工资、车辆折旧与保养费用等。冷链物流配送所需车辆成本仅与所启动的车辆数目相关,计算公式为:
其中,cveh表示单辆冷藏车的启动成本。
(2)运输成本
运输成本的核心组成为车辆配送过程所消耗的燃油成本,其数值大小与车辆总行驶距离呈正相关。借鉴同类相关研究成果[7],运输成本f2的计算公式定义为:
其中,cvar表示冷藏车单位里程的油耗成本。
(3)制冷成本
冷链配送的制冷成本主要来自维持车厢内温度所消耗的制冷剂成本。研究表明,制冷剂的消耗量与运输车的裂化程度、车厢内外温度、车辆辐射面和传热率等因素相关。鉴于本文中的运输网络采用同型运输车,车辆各类参数均一致,同时配送过程中车厢内外环境相对稳定。参考同类研究[7],制冷成本近似为与车辆运输时长正相关,公式为:
其中,ccool表示单位时长所产生的制冷成本。
(4)货损成本
随着运输时间的增长,所配送产品(包括疫苗、生鲜等)将产生一定货损。依据相关研究[7],选取公式α=1-e-r·t表述产品损耗量占比与运输时长的关系,其中α为损耗量,r表示当前货品对时间的敏感系数,t为运输时长,基于此货损成本可定义为:
其中,cpri表示单位需求量的单价。
1.3.2 数学模型
基于问题描述、符号定义及成本分析,参照相关文献研究[7],构建多车场冷链物流配送问题的数学模型,内容如下:
其中,公式(5)为目标函数,表示优化整个运输网络的总成本,包括车辆成本、运输成本、制冷成本和货损成本。约束(6)表示每个客户点仅被一辆车服务一次,约束(7)和(8)表示每个客户节点的出入度均为1,约束(9)表示每辆运输车从配送中心出发且完成配送任务后再返回原配送中心,约束(10)用于约束车辆不在配送中心间通行,约束(11)表示用于限制每个中心可使用的车辆数,约束(12)表示运输车的装载能力约束,约束(13)表示配送连续性约束,约束(14)用于限制每个客户接受服务的时间不得晚于规定的阈值,约束(15)~(17)用于表示自变量取值范围约束。
本文提出的ESCA算法以SCA算法为模板,同时融合了生物搜索算法(symbiotic biology search algorithm,SOS)的进化机制,在此归纳相关的算法原理。
SCA算法以随机方法构建初始解,同时借助正余弦变换生成子代解,相关内容包括:
(1)构建初始解
以D表示编码长度,∀d=1,2,…,D,各维编码取值范围定义为。以D维数组x=(x1,…,xd,…)表示解,其初始化公式为:
其中,rand(0,1)为[0,1]上的随机量。
(2)生成子代解
给定候选解x,SCA算法借助正余弦变换以及候选解同当前最优解间的位置差分量生成子代解x′,数学公式为:
其中,xd和x′d分别为父代解向量和子代解向量在维度d上的编码取值,x*d为当前最优解x*在维度d上的编码取值。r2、r3和r4为随机参数,r2∈[0,2π],r3∈[0,2],r4∈[0,1]。r1为自适应参数,其更新公式为:
其中,a为常数,建议取值为2,g为当前迭代次数,G为最大迭代次数。迭代初期,r1取值较大,算法侧重全局搜索;
迭代后期,r1取值较小,算法倾向于局部开发。
基于以上描述,如图2展示了SCA算法的完整运行流程。
图2 SCA算法框架Fig.2 Framework of SCA
SOS 算法通过模拟生态系统中生物间的共生行为实现数学问题的决策寻优,其运行过程包括互利共生、偏利共生、寄生三点概念[15]。本文借鉴并升级SOS算法的互利共生行为以强化SCA算法的寻优性能,以x和x͂分别表示当前种群的两个相异个体,SOS算法的婚礼共生环节采用以下公式生成子代个体x′和x͂′:
其中,MV表示x和x͂的共同载体,rand(0,1)为[0,1]上的随机数,x*为当前最优解,学习参数BF1、BF2 为随机整数,取值集合为{0,1}。
编码过程:采用实数编码机制,编码长度等于客户总数|NC|,取值范围定义[0,1]。
解码过程:采用最小位置值规则将实数编码映射为1~|NC|的客户优先级排列,其中位置靠前的客户享有较高优先级接受配送[16]。基于此融合启发式规则构造配送线路,规则包括:(1)选中客户序列中尚未接受配送服务的第一个节点作为新配送线路的首客户;
(2)综合考虑各中心车辆使用数约束和最短距离规则确定发车中心,若所有中心均无剩余用车,则构建虚拟路线,发车中心选中距离最近的中心;
(3)遍历客户序列中尚未接受服务的客户节点,依据运输车装载能力和各客户的时间窗约束确定配送线路。
如图3 所示,给出示意说明以辅助理解上述过程,问题参数定义如下:(1)两个中心服务11 个客户,客户的需求量均设置为1(单位:t),中心1、2的车辆数分别置为3和2,车辆载重为3 t;
(2)在空间维度,图3中各个节点的坐标位置反应了各个设施(中心或客户)间的远近;
(3)在时间维度,为方便阐述,假设各个设施间的路径用时均为10(单位:min),除客户9~11 接受服务的最晚时间设置为30 min,剩余客户最晚时间设置为10。给定编码(0.08,0.18,0.46,0.61,0.28,0.32,0.62,0.71,0.73,0.36,0.45),采用最小位置值规则可得序列(1,2,7,8,3,4,9,10,11,5,6),并依照上述路径构造规则生成图中的五条线路。
图3 编码与解码示意图Fig.3 Encoding and decoding diagram
结合前述内容可知,本文提出的编解码方法综合考虑了就近装载、中心可使用车辆数、车辆装载能力和客户时间窗约束等问题特征,简洁高效、易于实现。同时,鉴于部分节点的时间窗约束和中心车辆数约束尚未满足,在此借助惩罚函数法构造评价函数以协助种群进化,数学公式为:
其中,F和f分别表示候选解的评价函数和目标函数值,后两项分别表示时间窗与中心用车数这两类约束的违反量总和,惩罚系数λ1和λ2取值为正。
随机初始化方法一定程度上限制了寻优效率,鉴于此,本文将反向学习机制嵌入种群初始化过程,旨在提升初始解的质量[17]。
给定编码长度D,∀d=1,2,…,D,编码取值范围置为。候选解以D为数组x=(x1,…,xd,…) 表示,x对应的反向解定义如下:
基于此,给出改进初始化的运行流程:
步骤1令i←1,d←1,转步骤2。
步骤2若满足i≤P转步骤3;
否则转步骤7。
步骤3若满足d≤D转步骤4;
否则转步骤5。
步骤4随机生成,据此获取,转步骤5。
步骤5令d←d+1,若满足d >D转步骤6;
否则转步骤3。
步骤6生成随机解xi和反向解,令i←i+1,转步骤2。
步骤7选择中表现良好前P个解组建初始种群。
其中,P为种群规模,xi为采用随机方式生成的第i个解,为xi的反向解,和分别表示xi和在维度d上的编码数值。上述过程将构造随机解和反向解这两类集合,随后挑选其中优质解组建初始种群。
ESCA算法通过耦合SCA和SOS两种算法,构建以正余弦进化和互利共生进化为特征的两阶段混合进化机制,旨在增强标准SCA算法的性能,实现内容梳理如下:
(1)正余弦进化
在算法每次迭代的初期,采用随机方式将整个种群分成两个大小相等的子种群Pop1和Pop2,两个子种群分别采取正弦和余弦方式构建子代解:
其中,xd和分别表示父代解向量x和子代解向量x′在维度d上的编码取值,为当前最优解x*在维度d上的编码取值。r2、r3和r4为随机量,r2∈[0,2π],r3∈[0,2],r4∈[0,1]。自适应参数r1采用非线性调节机制[18]:
其中,g和G分别为当前和最大迭代次数。
(2)互利共生进化
种群完成正余弦进化后,算法采用随机方式匹配Pop1和Pop2中的解。以x和͂表示一对配匹配个体,子代个体x′和x͂′更新如下:
其中,rand(0,1)为区间[0,1]内的随机量,x*为当前最优解,̑为采随机选择的解个体,参数BF1 和BF2 调整为连续量。
为进提升算法后期跳出局部最优的能力,本文将变邻域下降搜索融合于ESCA算法[19]。变邻域下降搜索具有较优的局部发掘能力,该方法通过系统地探索候选解的邻居解以获得问题的优质局部解,其核心在于邻域结构的设计。本文采用交换和插入两种邻域结构,对应的实现过程梳理如下:
(1)交换:随机选择候选解的两处位置,交换相应的编码生成新的解(图4(a))。
图4 变异算子Fig.4 Mutation operators
(2)插入:随机选择候选解的两处位置,并将其中一处位置上的编码插入到另一处位置前面生成新的解(图4(b))。
结合前述内容,图5 给出了基于ESCA 算法求解多车场冷链物流配送问题的框架。
图5 ESCA算法框架Fig.5 Framework of ESCA
为验证ESCA 算法求解多车场冷链物流配送问题的寻优性能,在此开展数值仿真实验。实验包括以下两部分:(1)实例仿真分析,旨在展示当前模型和算法的有效性;
(2)算法性能验证,开展不同规模算例的仿真实验,分析改进策略的有效性,验证ESCA 算法同其他优秀算法相比的有力竞争性。模拟平台选用Matlab2017b,计算机处理器参数为2.4 GHz、内存4 GB、Intel®CoreTMi5-2430M。
4.1.1 实例参数
某市25个客户点亟需物资供应,表1归纳了每个客户点的空间位置坐标(以x、y坐标表示,单位:km)、需求量(单位:t)和时间窗(单位:min)。同时,存在三个中心提供物资配送服务,表2梳理了每个中心的空间位置坐标以及可供使用的运输车数目。
表1 客户点参数Table 1 Information of clients
表2 配送中心参数Table 2 Information of distribution centers
在配送过程中,车辆匀速行驶且车速为30 km/h,车辆额定载荷Q值为1.2 t。同时,整个运输网络体系中不同节点间的距离数值选用欧氏距离。其他参数定义如下:运输车启动成本参数cveh设定为50 元/车,油耗成本参数cvar设定为5 元/km,需求量单价参数cpri设定为2 000 元/t,需求损耗参数r设定为0.005,制冷成本参数ccool设定为40 元/h。
4.1.2 结果分析
为演示当前模型的有效性和算法的性能,结合以上参数分别测算不考虑时间窗和考虑时间窗两个案例的模型。测试算法选用SCA、ISA(improved simulated annealing algorithm)[20]和ESCA。其中,SCA 和ESCA算法的对比用于验证总体改进措施的有效性,ISA为近年来提出的一种求解车辆调度问题的高效算法,ISA和ESCA 的对比用于展示本文提出的改进算法与目前优秀算法的竞争力对比。
依据实际测试效果及相关研究,算法参数设置如下:所有算法的种群规模取20、总迭代次数取500,ESCA算法中邻域搜索方法的循环次数取5,ISA 算法的其他参数选用参考文献的推荐数值。对于每个算例,三种算法均独立模拟仿真20 次,表3 梳理归纳了三种测试算法所得的最优、均值和最劣目标函数值和相应的相对偏差百分比RPD(relative percentage deviation),RPD 定义如下[21]:
表3 实例优化结果Table 3 Simulation results of case study
其中,fbest为三种测试算法在共计60 次独模拟仿真中所得最优目标函数值,f对应最优、均值和最劣目标函数的数值。
同时,图6 和图7 分别给出SCA、ISA 和ESCA 三种算法所获取的最优路径以及相应的算法进化曲线对比图。
图6 不考虑时间窗的算例的最优解Fig.6 Optimum of model without time windows
图7 考虑时间窗的算例的最优解Fig.7 Optimum of model with time windows
此外,对考虑时间窗的算例,表4 归纳了三种算法所获取的最优线路的明细,表5给标识了相应的客户接受服务的时间。
表4 考虑时间窗模型中的最优线路Table 4 Final routes of model with time windows
表5 考虑时间窗模型中的客户到达时间Table 5 Reach times of model with time windows
观察实验结果,可得如下结论:
(1)基于实例参数,图6 和图7 中的路径曲线、表4中最优线路明细和表5 中每个客户接受服务的时间点数值可验证三种算法的可行性和有效性,即算法所寻得的结果均满足模型的约束设置,包括中心可供使用的车辆数约束、每条运输线路的装载负荷约束、时间窗约束等,并且验证了本文所构建的编解码方法以及个体评估函数能够较好地适配算法与决策问题。
(2)对比不考虑时间窗与增加时间窗约束可知,时间窗约束的设定增加了算法的优化难度。具体而言,求解不考虑时间窗约束的配送模型,SCA、ISA和ESCA三种算法所得均值偏差百分比数值分别为6.82%、5.60%和4.54%;
对于增加时间窗约束的配送模型,三种算法所得均值偏差百分比数值分别为8.85%、6.45%和5.16%。
(3)由算法求解同一模型的结果对比可知,本文所构建的ESCA 算法求解多车场冷链物流配送问题在最优、均值和最劣三个方面均获得了最优表现。针对不考虑时间窗约束的模型,ESCA算法所得均值百分比偏差为4.54%,相较于SCA 和ISA 算法有2.27%和1.05%的优势;
对于增加时间窗约束的模型,ESCA 算法所得均值百分比偏差为5.16%,相较于SCA 和ISA 算法有3.68%和1.29%的优势。
4.2.1 实验准备
为进一步验证改进措施的有效性和ESCA 算法同其他优秀算法相比的有力竞争性,在此开展不同规模算例的仿真实验。鉴于当前问题尚无标准测试数据集,依据同类研究构建不同规模下多车场冷链物流配送问题的算例。
客户总数取值范围为[16,50]且步长为2,中心总数取3,据此生成18 个算例。每个算例均可以客户数标识,例如P-16表示客户总数为16的算例,各算例的其他参数设置如下:
(1)所有节点的坐标采用随机方式生成,取值范围为[0,20],单位为km,测算选用欧氏距离。
(2)需求量参数qi采用随机方式生成{0.2,0.3,0.4},单位为t。
(3)时间窗参数Li采用随机方式生成{20,25,30,35,40,45},单位为min。
(4)在配送过程中,车辆匀速行驶且车速为40 km/h,车辆额定载荷Q值设定为0.8 t,运输车总数为且均分到每个中心。
(5)运输车启动成本参数cveh为50 元/车,油耗成本参数cvar为5 元/km,需求量单价参数cpri为2 000 元/t,需求损耗参数r为0.005,制冷成本参数ccool为40 元/h。
4.2.2 改进策略分析
为评估改进策略的有效性,开展多个版本SCA 算法的对比实验,包括:(1)SCA;
(2)SCA-OBL(SCA with opposition-based learning),即融合反向学习初始化方法的SCA 算法;
(3)SCA-HUM(SCA with hybrid update mechanism),即融合混合进化机制的SCA算法;
(4)SCA-NS(SCA with neighbor search),即融合邻域搜索的SCA算法;
(5)ESCA。
依据实际测试效果及相关研究,算法参数设置如下:种群规模取20,总迭代次数取500,ESCA 算法中邻域搜索方法的循环次数取5。对于每个算例,各算法均独立模拟仿真20 次,表6 梳理归纳了不同SCA 算法仿真结果。其中,OPT 所在列给出了表示最优解数值,AVG(average)、STD(standard deviation)和RPD 参数分别标识了各算法20 次独立实验的均值、标准差和均值的相对偏差百分比。此外,表格的倒数第2行计算了各算法求解18 个算例的RPD 均值,最后一行定义了当前算法求解各算例的排名情况,例如SCA-OBL中的2/4表示该算法在4个算例中RPD值排名第2。
表6 不同SCA算法优化结果Table 6 Simulation results of different SCA-versions
观察上述实验结果可知就RPD 均值而言,ESCA>SCA-HUM>SCA-NS>SCA-OBL>SCA,其平均RPD 值分别为7.84、9.39、9.54、9.78 和12.46。对全部18 个算例,ESCA 算法的平均求解效果均最佳,SCA 算法的平均求解效果均最劣。三种改进措施均一定程度上提升了算法的优化效果。对于SCA-HUM 算法,其在7 个算例中排名2,在10个算例中排名第3,在1个算例中排名第4;
对于SCA-NS 算法,其在7 个算例中排名2,在1 个算例中排名第3,在10个算例中排名第4;
对于SCA-OBL算法,其在4个算例中排名2,在7个算例中排名第3,在7 个算例中排名第4。换而言之,混合进化机制对SCA算法的性能提升最大,其次是离散邻域搜索机制,最后反向学习机制也在一定程度上提升了SCA算法所得结果的表现性能。此外,改进后的算法所得标准差值均优于基本SCA 算法,这表明改进措施对于提升寻优过程的稳定性具有积极意义。
4.2.3 算法对比分析
为进一步评估ESCA算法的性能,将其同近年来提出的求解车辆调度问题的高效算法进行对比,具体包括:(1)HGA,混合遗传算法(hybrid genetic algorithm)[22];
(2)IFWA,改进型烟花算法(improved fireworks algorithm)[23];
(3)ISA。
依据实际测试效果及相关研究,算法参数设置如下:四种算法的种群规模取20、总迭代次数取500,ESCA算法中邻域搜索方法的循环次数取5,对比算法的其他参数维持与参考文献推荐值相同的取值。对于各测试算例,每个算法均独立模拟运行20 次,表7 梳理归纳了不同算法的优化结果。其中,OPT所在列给出了表示最优解数值,AVG、STD和RPD参数分别标识了每个算法20次独立实验的均值、标准差和均值的相对偏差百分比。此外,表格最后一行定义了当前算法在排名情况。此外,表格的倒数第2 行计算了各算法求解18 个算例的RPD均值,最后一行定义了当前算法求解各算例的排名情况。
表7 不同测试算法优化结果Table 7 Simulation results of different test algorithms
由以上测试结果可知,就RPD 均值而言,ESCA>ISA>IFWA>HGA,其平均RPD值分别为7.84、8.63、8.89和10.06。对全部18 个算例,ESCA 算法的平均求解效果均最佳,HGA算法的平均求解效果均最劣。对于ISA算法,其在12个算例中排名第2,在6个算例中排名第3;
对于IFWA算法,其在6个算例中排名第2,在12个算例中排名第3。此外,ESCA 算法所得标准差值均优于对比算法,这表明其求解过程更稳定。
上述仿真实验证明了本文所构建的冷链配送模型的有效性,同时验证了所提出的ESCA算法的有力竞争性。综合而言,ESCA调度算法的优异性能归功于以下四点:(1)通过编解码规则以及个体评估方法,实现问题模型与决策算法的适配;
(2)借助反向学习机制创建初始种群,有力提升了初始种群的性能;
(3)构建了融合双种群、非线性调整和随机解扰动的混合进化机制,平衡了搜索过程的全局探索和局部挖掘行为;
(4)嵌入了离散邻域搜索方法,充分发掘候选解附近的优质邻居解,有效避免搜索停滞。
如图8 所示,展示了不同规模下ESCA 算法所得RPD值的变动趋势。据此可知,RPD值随着问题规模的扩大逐步增加,针对客户总数为50 的算例,ESCA 算法多次运行结果的均值误差百分比达到12.9%。换而言之,当问题规模较大时,ESCA 算法搜索过程的稳定性仍存在提升的空间。同时,ESCA算法基于所有客户优先级序列、并采用启发式规则构造路线,算法所需探索的解空间随着问题规模的扩大急剧增加,且线路质量存在提升空间。
图8 RPD变动图Fig.8 RPD under different instance scales
针对以上缺陷,借鉴国内外学者处理大规模、超大规模VRP问题方面的学术研究[24-25],后续求解大规模算例时可考虑在以下方面进一步完善ESCA 算法的运行架构:(1)结合客户节点的时空特征,将聚类算法与当前寻优过程相融合,旨在确保求解精度的前提条件下降低决策难度;
(2)组合高效经验式规则并应用于路径构造过程,着力提升线路质量;
(3)完善路径构造-路径改善过程,构建多阶段决策体系,分阶段提升所得结果的性能。
本文研究了一类多车场冷链物流配送问题,综合考虑运输网络结构、客户需求、车辆载荷和配送时效等因素,从成本视角建模构建了数学模型,并提出了ESCA算法。在算法设计阶段,首先创建了融合构造式规则的编码与解码方法,并与个体评估函数相配合,旨在适配问题模型与决策算法。同时,借助反向学习机制创建高质量的初始种群。此外,构建了融合双种群、非线性调整和随机解扰动的混合进化机制以平衡算法的全局探索和局部挖掘性能,并通过离散邻域搜索方法避免搜索停滞。
在实验部分,通过实例仿真分析展示了模型和算法的有效性。同时,开展了不同规模算例的仿真实验,分析了改进策略的有效性,并证明了ESCA算法同其他优秀算法相比的有力竞争性。
后续可从客户满意、准时化角度对当前模型作进一步精准刻画,着力贴合实际配送过程。同时,具有动态因素的多车场冷链物流配送问题也具有较高探索价值,诸如考虑时变网络、动态需求等。此外,可考虑将本文提出的ESCA 算法运用于同类问题,例如库存路径优化、供应链网络优化等。
猜你喜欢 物流配送冷链约束 要不要做冷链物流?中国储运(2022年6期)2022-06-18山西将打造高效农村快递物流配送体系今日农业(2021年19期)2022-01-12“碳中和”约束下的路径选择加油站服务指南(2021年4期)2021-07-21约束离散KP方程族的完全Virasoro对称数学年刊A辑(中文版)(2020年1期)2020-05-19基于Flexsim的饮品物流配送中心仿真优化研究太原科技大学学报(2019年3期)2019-08-05无人机物流配送路径及布局优化设计电子制作(2018年23期)2018-12-26直企物流配送四步走知识经济·中国直销(2018年5期)2018-05-26冷链物流用复合蓄冷材料的研究制冷技术(2016年2期)2016-12-01劲达电装联手开发冷链物流市场专用汽车(2016年5期)2016-03-01适当放手能让孩子更好地自我约束人生十六七(2015年6期)2015-02-28扩展阅读文章
推荐阅读文章
老骥秘书网 https://www.round-online.com
Copyright © 2002-2018 . 老骥秘书网 版权所有