混合超启发式算法求解复杂两级车辆路径问题尹丹1,2，胡蓉1,2**，钱斌1,2，郭宁1,2(1.昆明理工大学信息工程与自动化学院,云南昆明650500；2.云南省计算机技术应用重点实验室,云南昆明650500)摘要：针对模糊需求下的绿色两级车辆路径问题，以最小化车辆运营成本和油耗成本之和为优化目标，提出一种混合超启发式算法进行求解.首先，考虑两级问题解空间庞大且相互耦合，设计一种聚类分解策略将该问题分解为多个子问题，以合理缩小问题搜索空间；然后，提出增强超启发式分布估计算法（enhancedhyper-heuristicestimationofdistributionalgorithm，EHHEDA）对各个子问题进行求解，进而获得原问题的解.EHHEDA基于超启发式算法框架，在高层策略域设计一种基于三维概率模型的分布估计算法，动态确定由底层操作域中各搜索算子所组成的排列（即高层个体），可有效控制和引导整个算法的搜索行为；同时，在底层操作域设计10种有效邻域搜索算子，并加入重升温操作的模拟退火机制作为问题解（即底层个体）的接受准则，有利于在问题解空间中执行深入搜索.仿真实验结果表明,所提出的算法在大多数测试集上优于近年来用于求解类似问题的算法,验证了所提出算法的有效性.关键词：绿色两级车辆路径问题；模糊需求；聚类分解；超启发式算法；分布估计算法；模拟退火中图分类号：TP18文献标志码：A文章编号：0258−7971(2024)01−0023−15随着电子商务的快速发展，物流调度的重要性日趋显著.传统的车辆路径问题(vehicleroutingproblem,VRP)即仓库直接服务客户的运输方式，难以满足日益增长的需求量；并且多数城市对大型车辆采取限行措施，由此形成两级车辆路径问题(two-echelonvehicleroutingproblem,2E-VRP)[1].2E-VRP增加了中间设施中转站，中心仓库通过中转站间接服务客户的方式可将大型车辆限制在城市中心之外，在改善城市交通的同时，提高了服务效率[2].同时，全球气候变暖愈加严重，物流调度中的交通运输已成为碳排放的主要来源之一，考虑运输车辆的燃油消耗或碳排放量受到重视[3].此外，在实际情况中，客户的需求往往存在不确定性.譬如，快递公司提供揽收服务时，难以明确客户的需求[4].在上述背景下，本文针对揽收货物的情况，研究模糊需求下的绿色两级车辆路径问题(greentwo-echelonvehicleroutingproblemwithfuzzydemand,G2E-VRPFD).由于G2E-VRPFD属于NP-hard问题.故研究G2E-VRPFD的建模及其求解算法具有理论价值和现实意义.2E-VRP在快递服务、杂货店和电子商务等...
