求解车辆路径问题的改进离散差分进化算法  

Improved discrete differential evolution algorithm for solving vehicle routing problem

作　　者：于凯营 徐斌 YU Kaiying;XU Bin(School of Mechanical and Automotive Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)

机构地区：[1]上海工程技术大学机械与汽车工程学院,上海201620

出　　处：《上海工程技术大学学报》2024年第4期363-369,共7页Journal of Shanghai University of Engineering Science

基　　金：国家自然科学基金资助(61703268)。

摘　　要：针对带容量约束的车辆路径问题易受客户位置和需求等不确定因素影响,导致最优解不可行或非最优等问题,提出一种改进的离散差分进化算法。利用贪心法构建初始解,提高初始解质量;根据整数排列特征重新设计变异算子,并对问题模型改进交叉算子,提高了算法性能;设计融合局部重定位、条件交换及最大贡献度移除机制的局部搜索策略,提高了算法的探索能力。基准测试集仿真试验表明,在33个测试算例中,改进算法能找到31个算例的最优值,较对比算法有更好的求解能力,能有效解决带容量约束的车辆路径问题。Given that the vehicle routing problem with capacity constraints is easily influenced by uncertain factors such as customer location and demand,and leads to the infeasible or non-optimal solution,an improved discrete differential evolution algorithm was proposed.The greedy method was employed to construct the initial solution,thereby enhancing its quality of the initial solution.The mutation operator was redesigned according to the integer permutation characteristics,and the crossover operator was adapted for problem model,which improved the algorithm performance effectively.A local search strategy that incorporates local relocation,conditional exchange and a maximum contribution removal mechanism were designed,enhancing algorithm's exploration capabilities.Simulation experiments on the benchmark test set show that the improved algorithm can find the optimal value for 31 out of 33 test cases,indicating superior solution capabilities compared to other algorithms and effectively addressing the vehicle routing problem with capacity constraints.

关 键 词：车辆路径问题 差分进化算法 贪心法 离散优化 局部搜索 

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