混合超启发式算法求解复杂两级车辆路径问题.pdf

混合超启发式算法求解复杂两级车辆路径问题尹丹1,2，胡蓉1,2*，钱斌1,2，郭宁1,2(1.昆明理工大学信息工程与自动化学院,云南昆明650500；2.云南省计算机技术应用重点实验室,云南昆明650500)摘要：针对模糊需求下的绿色两级车辆路径问题，以最小化车辆运营成本和油耗成本之和为优化目标，提出一种混合超启发式算法进行求解.首先，考虑两级问题解空间庞大且相互耦合，设计一种聚类分解策略将该问题分解为多个子问题，以合理缩小问题搜索空间；然后，提出增强超启发式分布估计算法（enhancedhyper-heuristicestimationofdistributionalgorithm，EHHEDA）对各个子问题进行求解，进而获得原问题的解.EHHEDA基于超启发式算法框架，在高层策略域设计一种基于三维概率模型的分布估计算法，动态确定由底层操作域中各搜索算子所组成的排列（即高层个体），可有效控制和引导整个算法的搜索行为；同时，在底层操作域设计 10 种有效邻域搜索算子，并加入重升温操作的模拟退火机制作为问题解（即底层个体）的接受准则，有利于在问题解空间中执行深入搜索.仿真实验结果表明,所提出的算法在大多数测试集上优于近年来用于求解类似问题的算法,验证了所提出算法的有效性.关键词：绿色两级车辆路径问题；模糊需求；聚类分解；超启发式算法；分布估计算法；模拟退火中图分类号：TP18文献标志码：A文章编号：02587971(2024)01002315随着电子商务的快速发展，物流调度的重要性日趋显著.传统的车辆路径问题(vehicleroutingproblem,VRP)即仓库直接服务客户的运输方式，难以满足日益增长的需求量；并且多数城市对大型车辆采取限行措施，由此形成两级车辆路径问题(two-echelonvehicleroutingproblem,2E-VRP)1.2E-VRP 增加了中间设施中转站，中心仓库通过中转站间接服务客户的方式可将大型车辆限制在城市中心之外，在改善城市交通的同时，提高了服务效率2.同时，全球气候变暖愈加严重，物流调度中的交通运输已成为碳排放的主要来源之一，考虑运输车辆的燃油消耗或碳排放量受到重视3.此外，在实际情况中，客户的需求往往存在不确定性.譬如，快递公司提供揽收服务时，难以明确客户的需求4.在上述背景下，本文针对揽收货物的情况，研究模糊需求下的绿色两级车辆路径问题(greentwo-echelonvehicleroutingproblemwithfuzzydemand,G2E-VRPFD).由 于 G2E-VRPFD 属 于 NP-hard 问题.故研究 G2E-VRPFD 的建模及其求解算法具有理论价值和现实意义.2E-VRP 在快递服务、杂货店和电子商务等领域内应用广泛5.2E-VRP 最先由 Feliu 等1提出，并建立数学模型.随后，针对以最小化运输总成本为优化目标的2E-VRP 得到了广泛的研究，Zeng 等6设计一种基于贪婪随机自适应搜索算法与变邻域下降算法的混合算法进行求解；Breunig 等7设计一种改进大邻域搜索算法进行求解；Liu 等8设计一种混合模因算法进行求解；Yan 等9设计一种基于图的模糊进化算法进行求解；Wang 等10基于距离对客户分类将该问题划分为多个 VRP 子问题，并设计一种混合蚁群算法求解分解后的子问题；Wang 等11考虑了顾客的位置和购买行为等相似特征设计了一种结合聚类算法的增强遗传算法进行求解.针对绿色两级车辆路径问题(greentwo-echelonvehicleroutingproblem,G2E-VRP)研究较为有限，Wang 等12以最小化驾驶员工资、燃油收稿日期：2022-08-31；接受日期：2022-12-10；网络出版日期：2023-02-06基金项目：国家自然科学基金（62173169，61963022）；云南省基础研究重点项目（202201AS070030）.作者简介：尹丹（1998），女，湖南人，硕士生，主要研究智能算法与优化调度.E-mail：.*通信作者：胡蓉（1974），女，云南人，副教授，主要研究智能算法与优化调度、物流优化.E-mail：.云南大学学报（自然科学版），2024,46（1）:2337JournalofYunnanUniversity:NaturalSciencesEditionDOI:10.7540/j.ynu.20220439成本和装卸成本之和为优化目标，设计一种混合变邻域搜索算法进行求解；李正雯等13针对带时间窗的绿色多车型两级车辆路径问题(greentwo-echelon heterogeneous-fleet vehicle routing problemwithtimewindows,G2E-HVRP-TW)，以最小化车辆固定成本、时间窗惩罚成本和油耗成本之和为优化目标，设计一种学习型离散排超联赛算法进行求解.模糊需求车辆路径问题(vehicleroutingpro-blemwithfuzzydemand,VRPFD)是模糊车辆路径问题(fuzzyvehicleroutingproblem,FVRP)的一种.现有文献多采用模糊理论处理车辆调度中的不确定因素.王连锋等14针对 VRPFD，以最小化运输总成本为优化目标，建立其模糊期望值模型，设计一种混合并行粒子群算法进行求解.马艳芳等15针对模糊需求下的绿色同时取送货问题(greenvehicleroutingproblemwithsimultaneouspickupanddeliverywithfuzzydemand,GVRPSPDFD)，以最小化运输总成本为优化目标，将三角模糊数转化为模糊期望值，设计一种改进的遗传禁忌搜索算法进行求解.目前对于 VRPFD 已有一定研究，但对实际中广泛存在的 G2E-VRP 尚未看到模糊需求下的建模和智能算法求解方面的相关研究.G2E-VRPFD 综合考虑了 2E-VRP 和 GVRPFD的特点，更符合现实揽收要求.对 2E-VRP 的求解，智能算法已有一定研究.在大多数研究中，都将两级问题视为一个整体，对其进行编码和求解6-9，由于该类问题的两级问题相互耦合且决策变量复杂，造成解空间规模庞大且编码较为繁琐，仅凭智能算法本身的搜索机制难以在短时间内将算法搜索引导至解空间的较优区域，易造成算法的搜索效率低下.针对两级问题的特性，已有学者成功采用聚类分解将问题分解为多个相同的子问题，再设计智能算法依次对每个子问题进行求解，然后对各个子问题的解合并，获得原问题的解10-11,13；该类结合分解的方法能将智能算法搜索空间限制在较优区域内，提升智能算法对问题解空间的搜索效率.因此，本文采用结合聚类分解的智能算法对 G2E-VRPFD进行求解.超启发式算法(hyper-heuristicalgorithm,HHA)是解决复杂优化问题的一种新型算法.通常被描述为“搜索启发式算法的启发式算法”，该算法通过一种高层策略(high-levelstrategy,HLS)动态操控多个底层启发式算子(low-levelheuristic,LLH)实现对问题解空间的搜索.由于 HHA 较于传统的启发式算法拥有良好的通用性，并且无需进行复杂的参数设置即可获得稳定且高质量解16，因此被用于求解各类车辆路径问题17-19.基于文献17-19调研可知，高效的启发式算法作为 HLS 与结合问题特点构造的 LLH 是设计 HHA 的关键.分布估计算法(estimationofdistributionalgorithm,EDA)是基于概率模型的算法，能有效避免传统智能算法中存在对较优解模式破坏的问题20；然而，大部分学者均使用二维概率模型的 EDA 求解 VRP 相关问题21-22.由于二维概率模型只能学习操作块信息而无法学习操作块所在的位置信息，使算法在采样生成新个体时可能会因操作块放置不合理而导致算法搜索效率降低，这在引导算法搜索时具有较大的局限性.而三维概率模型通过学习优质解中操作块的位置信息23，在一定程度上减小对优良解的破坏，提升算法的搜索效率.因此，本文 HHA 的高层策略采用基于三维概率模型的 EDA 来优化高层个体.此外，HHA 已被成功用于求解多类 VRP 上，但尚未发现用于求解 2E-VRP 及其相关问题.综上所述，本文建立最小化车辆运营成本和油耗成本之和为优化目标的 G2E-VRPFD 模型.根据G2E-VRPFD 这类问题的解空间复杂且两级问题互耦合的特点，提出一种混合超启发式算法(hybridhyper-heuristicsalgorithm,HHHA)进行求解.首先，设计一种聚类分解算法将 G2E-VRPFD 分解成多个子问题，用以合理缩小问题的求解规模，实现对两级问题的解耦.其次，利用增强超启发式分布估计算法(enhancedhyper-heuristicestimationofdistri-butionalgorithm,EHHEDA)对各个子问题进行求解；然后将各子问题的解合并，得到原问题的解.在 EHHEDA 的高层策略域设计一种基于三维概率模型的分布估计算法，该概率模型用于描述优质个体的序结构信息，并通过采样该模型来动态确定由底层操作域中各搜索算子所组成的排列，更好的保护较优解模式不被破坏.在 EHHEDA 的底层操作域设计 10 种有效邻域搜索算子，对问题解执行深入的搜索，并在每个算子中加入重升温操作的模拟退火机制作为问题解的接受准则，在算法陷入局部最优解时能在一定概率下跳出.最后，通过在不同规模测试集下的仿真实验和算法对比，验证了所提算法在求解 G2E-VRPFD 的有效性.24云南大学学报（自然科学版）http:/第46卷1G2E-VRPFD 的问题描述及数学模型1.1G2E-VRPFD 问题描述及相关假设G2E-VRPFD 包括两级物流网络，如图 1 所示，第一级网络中含有一个中心仓库、多个中转站和多台可用的大型车辆；第二级网络中含有多个中转站、若干个客户点和多台可用的小型车辆.在揽收过程中，二级车辆先从中转站出发向若干个客户揽收货物，并存放在中转站内；一级车辆再从中心仓库出发为多个中转站揽收货物，其中客户的需求具有一定模糊性.该模型要求在给定目标(运输总成本最小)和约束条件下对客户进行服务，合理安排车辆及服务路线以实现运输总成本最小化.该模型假设：中心仓库、中转站和客户的信息已知；在物流网络中，同级网络揽收车辆相同；中转站仅负责货物中转，不储存货物，同一中转站或客户的货物不得拆分揽收，中心仓库不能直接服务客户；车辆从中转站或者中心仓库空载出发；每辆车所服务的客户总需求不能超过该车辆的最大载重量；中转站容量(或中心仓库容量)、可用车辆数、揽收能力满足客户点(或中转站)服务要求；车辆空载出发，可同时派出多辆车(不超过可用车辆总数)进行揽收服务.图1G2E-VRPFD 示意图Fig.1SchematicdiagramofG2E-VRPFD1.2期望模糊需求在现实揽收货物场景中，由于各种不确定因素，客户很难给出一个精确的需求量，通常会根据经验给出一个大致的范围，并在范围中取一个可能的需求值.因此，针对这种需求不确定的情况，本文参考文献 15 引用模糊变量，将客户需求设置为三角模糊数，使用三角模糊数的期望值对客户的模糊需求进行定量处理.A=(q1,q2,q3)0 q1 q2 q3设 一 客 户 的 模 糊 需 求，其 中,q1、q3分别为客户三角模糊数需求的最小值和最大值，q2为客户可能的需求量，其隶属度函数为：FA(x)=(xq1)/(q3q1),q1 x q2,(xq3)/(q2q3),q2 x q3,0，其它.(1)fAgAA=(q1,q2,q3)设 A 边为和的三角模糊数，可得：fA=(xq1)/(q2q1);q1 x q2，(2)gA=(xq3)/(q2q3);q2 x q3.(3)S R(A)定定义义 1区间随机集的期望值称为模糊数 A 的期望区间24，E(A)可表示为：E(A)=ES1,ES2，(4)式中：ES1=q2wq2q1fA(x)dx，(5)ES2=q2+wq3q2gA(x)dx.(6)定定义义 2模糊数 A 的期望区间的中心称为该数的期望值，用(A)表示24，即：(A)=12(ES1+ES2).(7)第46卷尹丹等：混合超启发式算法求解复杂两级车辆路径问题251.3问题建模F1E1F2E2F1F21.3.1 目标函数G2E-VRPFD 的优化目标为运输总成本最小化，其中运输总成本(F)包含 4 个部分，分别为一级车辆的运营成本()、一级车辆的油耗成本()、二级车辆的运营成本()和二级车辆的油耗成本().和的计算如下：F1=iV1jV1k1K1C1dsijxijk1，(i,j)，(8)F2=iV2jV2k2K2C2dcijyijk2，(i,j).(9)E1E2碳排放主要来源为车辆使用燃油量，文献 25表明，燃油消耗量与碳排放量成正比，因此本文采用文献 12 中考虑速度、载重、距离、发动机排量等因素的综合油耗模型计算油耗量，并通过油耗量折算为成本加入运输总成本中.其符号定义如表 1所示.根据该模型，一级车辆燃油消耗量成本()和二级车辆燃油消耗量成本()的计算如下：E1=cfiV1jV1k1K1xijk1c1dsijv1+c2dcijv21+c3(2+Qijk1)dsij，(10)E2=cfiV2jV2k2K2yijk2c1dcijv2+c2dcijv22+c3(2+Qijk2)dcij，(11)c1=KNV/kc2=/1 000kc3=(g(sin+Crcos)/1 000k式 中：，.1.3.2 混合整数线性规划模型本节所涉及的数学符号及说明如表 2 所示.问题优化目标为：min F=F1+F2+E1+E2.(12)约束条件：iV0jVsxijk1 m1,k1 K1;(13)表1油耗模型符号定义表Tab.1Fuelconsumptionmodelsymboldefinitiontable符号释义E1/元一级车辆油耗成本E2/元二级车辆油耗成本cf/(元L1)燃油单价v1/(kmh1)一级车辆平均行驶速度v2/(kmh1)二级车辆平均行驶速度燃料与空气质量比K摩擦系数k/(kJg1)柴油热值N/(rs1)发动机转速V/L发动机排量/(gL1)转换系数柴油机效率参数车辆传动系统效率1/kg一级车辆的整备质量2/kg二级车辆的整备质量Cd空气阻力系数A/m2迎风面积O/(kgm3)空气密度g/(ms2)重力加速度道路坡度Cr滚动阻力系数表2GVRPFD 模型符号定义表Tab.2GVRPFDmodelsymboldefinitiontable符号说明F/元运输总成本F1/元一级车辆运营成本F2/元二级车辆运营成本V0V0=v0中心仓库集VsVs=vs1,vs2,vsns,中转站集VcVc=vc1,vc2,vcnc客户集V1V1=VsV0一级物流网络节点集V2V2=VcVs二级物流网络节点集K1K1=1,2,m1一级车辆集K2K2=1,2,m2二级车辆集ns中转站总数量nc客户总数量m1一级车辆总数量m2二级车辆总数量Q1一级车辆载重量Q2二级车辆载重量dci客户i的模糊需求dsi中转站i的模糊需求Qijk1一级车辆点i到点j的车辆载重量Qijk2二级车辆点i到点j的车辆载重量C1一级车辆单位距离的运营成本C2二级车辆单位距离的运营成本dcij客户点i到客户点j的距离dsij中转站i到中转站j的距离xijk1k1决策变量，若一级车辆 从中转站i到中转站j时为1，否则为0yijk2k2决策变量，若二级车辆从点i到点j时为1，否则为0zki决策变量，若客户i由中转站k服务时为1，否则为026云南大学学报（自然科学版）http:/第46卷kVsjVcykjk2 m2,k2 K2;(14)dsi=jVcdcjzkj,i Vs;(15)kVszki=1,i Vc;(16)jVcdcjzki Q1,i Vs;(17)iVcxijk1=0,j V0,k1 K1;(18)jVcykjk2=jVcyjkk2=1,k Vs,k2 K2;(19)kVsyijk2=0,i,j V2,i=j,k2 K2;(20)iV1xijk1=0,j V1,i=j,k1 K1;(21)iV1xijk1=hV1xjhk1=1(i,j,h,j),jV1,k1K1;(22)iV1Qijk1xijk1 Q1,j V0,k1 K1;(23)iV2Qijk2yijk2 Q2,j Vs,k2 K2;(24)zik 0,1,i Vc,k Vs;(25)xijk1 0,1,i,j V1,k1 K1;(26)yijk2 0,1,k Vs,i,j Vc,k2 K2.(27)式(13)和式(14)表示各级网络中，使用的车辆总数不超过该级拥有的车辆总数.式(15)表示中转站的模糊需求为该中转站所服务的客户模糊需求之和.式(16)表示一个客户有且仅由一个中转站为其服务.式(17)表示中转站的容量约束.式(18)表示中心仓库不能直接服务客户.式(19)表示在第二级物流网络中，每条路径的起点与终点均为同一个中转站，且每个客户有且仅由一辆二级车辆对其进行服务.式(20)和式(21)表示相同节点无路径连接.式(22)表示在第二级物流网络中，开始和结束都应为中心仓库.且每个中转站有且仅由一辆一级车辆为其服务.式(23)和式(24)表示揽收过程中不能超过对应车辆的最大负载.式(25)(27)表示决策变量.1.4问题特点分析及求解思路由图 1 可知，G2E-VRPFD 第一级问题为 GVRPFD，第二级问题为模糊需求下的绿色多车场车辆路径问题(greenmulti-depot vehicle routing problem with fuzzy demand,GMDVRPFD).该问题的两级问题相互耦合，改变第二级问题的解会影响第一级问题的解.若直接使用智能算法对问题进行整体编码和求解，解空间为第一级问题和第二级问题解空间乘积，并且随着客户数量的增加，造成解空间规模十分庞大；若设计合理的聚类算法将第二级问题分解为 ns个相对简单的子问题，则共有 ns+1 个 GVRPFD 子问题，再对分解后的各个子问题进行求解，此时问题解空间为各子问题解空间之和，该方法可极大程度缩小问题解空间，并能将算法限制在较小且较优的区域进行搜索，缩短算法搜索时间，提升智能算法的搜索能力.因此，根据 G2E-VRPFD 的特点分析，本文先采用聚类分解策略分解为 ns+1 个 GVRPFD 子问题，再设计智能算法对其求解.2混合超启发式算法(HHHA)本文采用 K-medoids 聚类算法将问题分解为多个 GVRPFD 子问题，然后设计 EHHEDA 依次求解每个子问题，再合并各子问题之解，得到整个问题的解.2.1聚类分解策略由于 K-medoids 算法聚类结果相当紧凑，且对孤立点和噪声数据的敏感性小26.因此，本文将 K-medoids 的聚类算法应用到求解 G2-VRPFD 中，将第二级问题分解为 ns个GVRPFD.具体步骤为：步步骤骤 1将中转站坐标设为该算法的初始聚类重心.步步骤骤 2计算各个客户点到聚类重心的欧式距离.将客户点分配为最近的聚类重心.CiPi步步骤骤 3将每类中每个客户点均作为聚类重心，计算每个客户点到该类中其余客户点的欧式距离，然后选择欧式距离和最小的点作为新的聚类重心.是聚类重心，是非聚类重心.计算公式如下：c=CiVcPiCi|PiCi|2.(28)第46卷尹丹等：混合超启发式算法求解复杂两级车辆路径问题27步步骤骤 4重复步骤 2 和步骤 3，直至聚类重心不再改变.2.2增强超启发式分布估计算法求解子问题对于将 G2E-VRPFD 聚类分解后的每个 GVRPFD 子问题，均采用 EHHEDA 求解.EHHEDA 由高层策略域和底层操作域组成，在 EHHEDA 的高层策略域采用基于三维概率模型的 EDA，用于合理学习高层个体的优良模式，其高层个体是由底层操作域中各搜索算子所组成的排列.在底层操作域设计10 种有效邻域搜索算子，并加入重升温操作的模拟退火机制作为问题解（即底层个体）的接受准则，对问题解执行深入的搜索.LLHc2.2.1 编码与解码在高层策略域种群中，每个高层个体采用十进制的编码方式，一个序号代表相应的底层启发式算子；且每个个体都由 10 个底层启发式算子构成，可允许每个算子重复出现，一个高层个体编解码示意图如图 2 所示.解码时，按高层个体中底层启发式算子的排序，依次对问题解空间执行搜索.高层个体的评价值等于对相应的低层个体执行底层启发式算子搜索后的目标函数值.图2高层个体编解码示意图Fig.2Schematic diagram of coding and decoding of high-levelindividualsns+1iG=1,2,3,4,8,7,5,6iGiG=(1,2,3),(4,8),(7,5,6)在底层操作域种群中，每个底层个体为原问题的解.本文将 G2E-VRPFD 分解后的个子问题分别用相同的方式进行编码，编码方式采用基于客户以及中转站排序的十进制编码.譬如，在第 G代中转站 i 服务 8 个客户，可记为，解码过程中，在满足车辆容量约束的条件下，将中的客户从左到右分配给各车辆，解码后可得到该中转站所有车辆的服务路径.2.2.2 种群初始化为避免种群中的解分布过于集中，导致无法对问题解空间进行充分搜索，本文在初始化时，设置每个高层个体和底层个体均随机生成，且每个高层个体中的底层启发式算子不重复出现.2.2.3 底层启发式算子LLH 中每个底层启发LLH1LLH6LLH7LLH10式算子是直接对问题解空间进行搜索，因此 LLH设计的好坏决定了搜索能力与解的质量.本文根据问题特性，在算法底层操作域中设计了 10 种有效的邻域搜索操作算子，至为车辆内路径邻域操作算子，至为车辆间路径邻域操作算子.具体为：LLH1Swap(i,j,m,n),m,n i,ji,ji,j(1):.表示中转站i 中的车辆 j 服务路线.在中，随机选择两个不相邻客户 m 和 n，将 m 和 n 交换，生成新的路径.LLH22Opt(i,j,m,n)m,ni,ji,j(2):，.在中，随机选择两个客户 m 和 n，将 m 和 n 之间的客户服务顺序逆序，生成新的路径.LLH3Shift(i,j,m,n)m,ni,ji,j(3):,.在中，随机选择两个客户 m 和 n，将客户 m 插入在客户 n 之前，生成新的路径.LLH4Swap_two(i,j,m,n)m,ni,ji,j(4):,.在中，随机选择两个相邻的客户 m 和 n，将客户 m 与客户 n交换，生成新的路径.LLH5Shift_two(i,j,s,m,n)s,m,ni,ji,ji,j(5):,.在中，随机选择两个相邻的客户 m 和 n 插入到随机选取中的客户点 s 之前，生成新的路径.LLH6Swap_n(i,j,s,w,m,n),s,w,m,ni,ji,j(6):.在中，随机选择两对相邻的客户 s、w 与 m、n 交换，生成新的路径.LLH7Swap(i,j,m,i,l,n)j,li,ji,li,ji,l(7):,.在中随机选取一客户点 m；另外，在中随机选取一客户点 n，将 m 和 n 交换，生成新的路径和.LLH8Shift(i,j,m,i,l,n)j,li,ji,li,ji,l(8):,.在中随机选取一客户点 m；在中随机选取一客户点 n，将m 插入到 n 之前，生成新的路径和.LLH9Swap_two(i,j,m,n,s,w),j,l,m,n,s,wi,ji,li,ji,l(9):.在中随机选取两个相邻的客户点 m 和 n；在随机选取两个相邻客户点 s 和 w，将 m、n 和 s、w 交换，生成新的路径和.Swap_one(i,j,m,n,i,l,s),j,l,m,ni,ji,li,ji,l(10)LLH1 0:.在，随机选取两个相邻的客户点 m 和 n；在随机选取一个客户点 s，将 m、n 和 s 交换，生成新的路径和.在执行每个底层启发式操作时，若只接受较优解，算法收敛较快，较易陷入局部最优解无法跳出.因此本文采用一种重升温操作的模拟退火机制作为解的接受准则，在一定概率上接受较差解，避免算法陷入局部最优，而是趋于全局较优.具体来说，28云南大学学报（自然科学版）http:/第46卷在该算法中，设置当前温度 T，每次迭代时采用冷却系数 降温，温度更新公式为：T=T.(29)温度通过式(30)影响底层启发式操作.P=expfT,(30)ffr 0,1式中：为每执行一次底层启发式算子得到的新解与旧解适应度值的差值.迭代时，每个高层个体中的底层启发式操作对相应的解均内部执行 5 次，若0 时，三维概率模型更新公式为：gen(n1)nn(x,y,z)=(1)gen(n1)nn(x,y,z)+gen(n1)nn(x,y,z)/Sum_gen(x),x=1,2,n1,y,z=1,n.(36)G(n1)nn(x,y,z)G,k=LG,k1,LG,k2,LG,knLG,ki1,LG,kiG(n1)nn(i1)G,k2.2.5 高层策略域种群更新在算法每次迭代时，高层策略域通过轮盘赌采样三维概率模型更新种群，在学习较优解模式的同时 保 持 种 群 的 多 样 性.由 于 个 体中的操作块被采样选中的概率存储在概率模型中，故初始位置采样和其余位置采样使用两种不同的方法.采样生成高层个体中的启发式算子序列具体为：sen,kDG1init(y)y=1,n(1)生成中第一个位置上的底层启发式操作.先按式(37)计算，.DG1init(y)=nz=1G1(1,y,z)(37)gen,kLLHcr0,nh=1DG1init(h)r0,DG1init(1)c=1r DG1init(t),DG1init(t+1)t 1,n1c=t+1再采用轮盘赌选择中初始位置底层启发式操作.具体为：生成随机概率数，若则，若满足，则.G,kLLHcr 0,nh=1G1nnn(i1,LG,ki1,h)r 0,G1(n1)nn(i1,G,k(i1),1)c=1r mh=1G1(n1)nn(i1,G,ki1,h),m+1h=1G1(n1)nn(i1 G,k(i1),h)t 1,n1c=m+1(2)生成中剩余位置上的底层启发式操作.使用轮盘赌选择下一个底层启发式操作，具体为：生成随机概率数 r，其中.若满足则，若，则.2.2.6 算法流程求解子问题的 EHHEDA 具体步骤如下：步步骤骤 1算法参数初始化，三维概率矩阵初始化；步步骤骤 2随机初始化高层策略域种群和底层操作域种群.步步骤骤 3将高层个体中的每个底层启发式操作算子对相应的底层个体执行搜索，每执行一次搜索采用模拟退火机制判断是否要接受该解，直至种群中所有高层个体都执行完毕.步步骤骤 4评价底层种群，并将种群中底层个体和对应的高层个体按照目标函数值升序排序.Nmax步步骤骤 5选择高层种群中的个优质个体，更新统计矩阵.步步骤骤 6更新三维概率矩阵.步步骤骤 7轮盘赌采样更新高层策略域种群.步步骤骤 8若最优解持续超过 b 代未改变，模拟退火机制采用公式(31)重升温；否则，采用公式(29)降温.步步骤骤 9判断是否到达终止条件.若算法达到终止条件，则输出最优解；否则调整至步骤 3.3实验设计与分析20ncns目前暂无 G2E-VRPFD 的标准测试数据，故本文采用文献 6 中的部分算例组成的测试集，客户的需求量基于三角模糊数随机生成，改编后的数据地址：https:/ Python3.8对本文中所有算法进行编程测试，操作系统为Windows10,CPU 主频为 2.40GHz，8GiB 内存.对所选取的不同规模测试集，每种算法均在相同时间ms 下，运行 20 次.3.1关键参数设置G2E-VRPFD 模型中的油耗模型中的系数设定参考文献 13，燃油费用系数设参考文献 27；运营成本系数设定参考文献 28.第 2.2.3 节加入重升温操作的模拟退火机制中，初始温度 T=100，b=3，系数 u=10.在 HHHA 中，主要参数有种群规模 Nmax、学习率、精英个体所占比例 和冷却系数.为考察各参数设置对算法效果的影响，本节采用文献 29实验设计方法 DOE 确定 HHHA 的参数取值.上述4 个参数均取 4 个水平值，如表 3 所示.表3HHHA 各参数水平表Tab.3Leveltableofmainparameters参数水平1234Nmax203040500.20.40.60.80.10.30.50.70.800.850.900.9530云南大学学报（自然科学版）http:/第46卷755_1基于表 3，采用正交表 L16(44)，使用中等算例在 16 组不同水平参数组合下进行实验.每组参数在相同时间内独立运行 20 次，20 次结果的平均值作为平均响应值 AVG，AVG 越小则代表在相应的参数设置下算法性能越好.正交表和 AVG统计值如表 4 所示.根据表 4 中的 AVG 统计值，得到表 5 中各个参数在不同水平下的平均响应值和等级，其中等级一栏表示参数对算法性能的影响力等级排名，以及各参数的响应趋势图（图 4），每组水平的最低点表示算法性能占优.Nmax=40 =0.6 =0.5 =0.9由表 4、表 5 和图 4 可知，当 HHHA 的参数设置为：，时，其性能在不同参数组合下的各算法中占优.因此，后续测试中按此设置 HHHA 的参数.3.2仿真结果比较与分析本文通过所设计的接受准则、高层策略域算法以及整体算法这 3 个部表4正交表和R统计值Tab.4OrthogonaltableandRstatistics参数组合参数水平R/元Nmax111112027.1212222031.3313332025.5414442028.7521232026.4622142030.3723412026.8824322026.5931342022.41032432026.01133122025.91234212028.11341422032.91442312021.91543242024.51644132024.4表5HHHA 各参数响应值Tab.5ResponsevalueofHHHAparameters水平参数Nmax12028.22027.22026.92026.022027.52027.42027.62029.132025.62025.62024.02025.642025.62025.62024.02025.6极差2.61.74.63.6等级3412图4HHHA 各参数在不同水平下的响应趋势图Fig.4ResponsetrendofHHHAparametersatdifferentlevels第46卷尹丹等：混合超启发式算法求解复杂两级车辆路径问题31分，验证所提算法的有效性.其中，用 R1、R2和 R3分别表示一个算例独立运行 20 次输出本文目标函数值最小化运输总成本的平均值、最优值和最差值.基于所有算例独立运行 20 次结果的横向均值，得到 6 个不同智能算法与 HHHA 比较的 95%置信区间图如图 5 所示，纵坐标表示横向平均目标函数值.算法区间图所处的位置越低，表示该算法性能越好；区间越小，算法越稳定.图5HHHA 和 6 种不同算法比较的 95%置信区间图Fig.595%confidence interval diagram of HHHA and 6differentalgorithms3.2.1 验证接受准则有效性为验证 HHHA 中底层启发式算子嵌入的重升温操作的模拟退火机制作为接受准则的有效性，在文本问题上，将其与接受准则为只接受好解的 HHHA(HHHA_V1)和接受准则为模拟退火机制但是无重升温操作的HHHA(HHHA_V2)进行比较.实验结果见表 6，HHHA 与 HHHA_V1、HHHA_V2 的 95%横向均值区间置信图见图 5(a).由表 6 和图 5(a)可知，HHHA 优于 HHHA_V1和 HHHA_V2.原因在于，将只接受好解作为接受准则的 HHHA_V1，迭代过程中一直在贪婪搜索，算法容易较早的陷入局部最优状态，无法跳出，在后期浪费不必要的搜索时间，降低搜索能力.而将每个底层启发式算子中嵌入模拟退火机制，未加入重升温操作作为接受准则的 HHHA_V2，虽然在算法迭代前期，模拟退火机制以一定概率接受差解，避免算法较早陷入局部最小，但在后期随着温度的不断降低，导致模拟退火机制停滞，而 HHHA 中的重升温操作在达到一定条件下可激活模拟退火机制，提升算法全局的搜索能力.因此在将底层启发式算子嵌入重升温操作的模拟退火机制作为接受准则有一定有效性.3.2.2 验证高层策略有效性为验证 HHHA 中的 EHHEDA 高层策略有效性，在不同规模测试集上，分别将其与传统 GA 作为高层策略的超启发式算法(HHGA)和传统 EDA 作为高层策略的超启发式算法(HHEDA)进行实验对比，算法其余部分保持一致.实验结果见表 7，HHHA 与 HHGA、HHEDA的 95%横向均值区间置信图见图 5(b).由表 7 和图 5(b)可知，HHHA 优于 HHGA 和HHEDA，且 HHHA 更稳定.一方面，HHHA 作为一种学习型的智能算法，可避免 HHGA 这类经典进化算法在每次迭代时，通过交叉变异操作对种群中较优高层个体的破坏，导致过多无效的操作，降低算法的搜索效率；另一方面，HHHA 通过学习高层个体中操作块位置信息来更新高层种群，可在一定程度上避免 HHEDA 对优质操作块的破坏，更为合理地学习高层个体的优良解模式.3.2.3 验证本文整体算法有效性因目前无 G2E-VRPFD 的相关研究，为验证 HHHA 的整体有效性，在本文问题上，将 HHHA 与国际期刊上求解相似问题的 VNS12和 IGA30进行对比.其中 VNS 和IGA 均是对整个问题进行编解码，无聚类分解阶段.各算法比较结果如表 8 所示，HHHA 与 VNS、IGA 的 95%横向均值区间置信图见图 5(c).由表 8 和图 5(c)可知，随着客户数量的增加，HHHA 显著优于 VNS 和 IGA 算法，且 HHHA 算法稳定型更强.表明对两级问题整体编码并求解，难32云南大学学报（自然科学版）http:/第46卷以在短时间内获得满意的解.以算例 212_1（客户、中转站和中心仓库的数量分别为 21、2 和 1）为例，若对该算例整体编码与求解，解空间为 S1=21!2!.如果采用 k-medoids 算法将该算例的第二级问题分解为两个 GVRPFD 子问题：客户数分别为 12 和 9，则第一级问题中的 2 个中转站容量便可以根据这两个客户数固定下来，实现了两级问题间的解耦，而此时的解空间为 S2=12!+9!+2!.显然，S2远远小于 S1.因此，采用有效的分解策略可明显缩减搜索区域，将算法引导至较优区域进行搜索，有利于提高算法的搜索效率.此外，VNS 和 IGA 这类常规的智能算法，在迭代循环时，均采用固定顺序的几个局部搜索操作对问题解空间进行搜索，未考虑到操作顺序对搜索能力的影响，使算法在对解空间搜索时有一定局限性.而 HHHA 中的 EHHEDA 通过采用高层策略学习优质个体中启发式操作顺序，动态混合多种底层启发式算子更新种群，实现对问题解空间的搜索，可较易发现解空间不同区域的优质解，表6接受准则性能验证Tab.6Performanceverificationofacceptancecriteria算例ncnsHHHA_V1HHHA_V2HHHAR1R2R3R1R2R3R1R2R3212_1212969.8971.2975.5969.8970.3975.5969.8969.8969.8212_22121149.21158.41167.61149.21158.01180.21149.21154.91166.7322_13221851.71893.21932.01836.01876.01911.81837.71864