求解带容量约束车辆路径问题的多模态差分进化算法  

Multimodal differential evolution algorithm for solving capacitated vehicle routing problem

作　　者：林剑[1] 叶璟轩 刘雯雯 邵晓雯 LIN Jian;YE Jingxuan;LIU Wenwen;SHAO Xiaowen(School of Information Management and Artificial Intelligence,Zhejiang University of Finance and Economics,Hangzhou Zhejiang 310018,China;School of Computer Science,Beijing University of Technology,Beijing 100124,China;Faculty of Electrical Engineering and Computer Science,Ningbo University,Ningbo Zhejiang 315211,China)

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

出　　处：《计算机应用》2023年第7期2248-2254,共7页journal of Computer Applications

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

摘　　要：针对带容量约束车辆路径问题(CVRP)中交通拥堵、资源供给、客户需求等不确定性因素的影响容易导致单一最优解不可行或非最优的问题,提出一种多模态差分进化(MDE)算法,以同时求解得到目标值相近的多个备选车辆路径方案。首先结合CVRP的特点,构建高效的解个体编解码策略,并基于修复机制提升解个体的质量;然后在差分进化(DE)算法框架下,基于多模态优化视角引入动态半径小生境生成方法,并采用杰卡德系数来度量解个体之间相似性,进而实现对于解个体之间距离的计算;最后,改进邻域搜索策略,采用精英存档和更新策略来得到多模态最优解集。基于典型数据集的仿真实验与分析结果表明,所提MDE算法寻优得到的平均最优解个数达到1.7434个,平均最优解与已知最优解的平均偏差为0.03%,而差分进化(DE)算法二者分别为0.8486和0.63%。可见,所提算法在求解CVRP上表现出较高的有效性和稳定性,能同时得到CVRP的多个近似最优解。In Capacitated Vehicle Routing Problem(CVRP),the influence of uncertain factors including traffic congestion,resource supply and customer demand will easily make the single optimal solution infeasible or non-optimal.To solve this problem,a Multimodal Differential Evolution(MDE)algorithm was proposed to obtain multiple alternative vehicle routing schemes with similar objective values.Firstly,combined with the characteristics of CVRP,an efficient solution individual coding and decoding strategy was constructed,and the solution individual quality was improved using a repair mechanism.Secondly,in the framework of Differential Evolution(DE)algorithm,a dynamic radius niche generation method was introduced from the perspective of multimodal optimization,and the Jaccard coefficient was used to measure the similarity between solution individuals,which realized the calculation of the distance between solution individuals.Finally,the neighborhood search strategy was modified,and a multimodal optimal solution set was obtained using elite archiving and updating strategy.Simulation and analysis results based on typical datasets show that the average number of optimal solutions obtained by the proposed MDE algorithm reaches 1.7434,and the deviation between the average optimal solution obtained by the proposed MDE algorithm and the known optimal solution is 0.03%,better than 0.8486 and 0.63% obtained by the DE algorithm.It can be seen that the proposed algorithm has high effectiveness and stability in solving CVRP,and can obtain multiple optimal solutions for CVRP simultaneously.

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

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]