计算机应用

作者：林剑, 叶璟轩, 刘雯雯, 邵晓雯

单位：1.浙江财经大学 信息管理与人工智能学院, 杭州 310018；2.北京工业大学 计算机学院, 北京 100124；3.宁波大学 信息科学与工程学院, 浙江 宁波 315211

关键词：车辆路径问题,多模态优化,差分进化,带容量约束,小生境

基金：国家自然科学基金资助项目(61973267)

针对带容量约束车辆路径问题（CVRP）中交通拥堵、资源供给、客户需求等不确定性因素的影响容易导致单一最优解不可行或非最优的问题，提出一种多模态差分进化（MDE）算法，以同时求解得到目标值相近的多个备选车辆路径方案。首先结合CVRP的特点，构建高效的解个体编解码策略，并基于修复机制提升解个体的质量；然后在差分进化（DE）算法框架下，基于多模态优化视角引入动态半径小生境生成方法，并采用杰卡德系数来度量解个体之间相似性，进而实现对于解个体之间距离的计算；最后，改进邻域搜索策略，采用精英存档和更新策略来得到多模态最优解集。基于典型数据集的仿真实验与分析结果表明，所提MDE算法寻优得到的平均最优解个数达到1.743 4个，平均最优解与已知最优解的平均偏差为0.03%，而差分进化（DE）算法二者分别为0.8486和0.63%。可见，所提算法在求解CVRP上表现出较高的有效性和稳定性，能同时得到CVRP的多个近似最优解。

来源：2023年第7期

《计算机应用》期刊编辑部

查看计算机应用杂志2023年第7期