车辆路径问题的水波算法

作者：张春苗; 赵燕伟; 冷龙龙

来源：数值计算与计算机应用, 2018, 39(03): 231-242.

• 水波算法
• 车辆路径问题
• 传播
• 折射
• 碎浪

水波算法(Water Wave Optimization WWO)是郑宇军于2014年基于浅水波理论提出的一种新颖的元启发式算法,用于全局优化问题.通过水波的传播、折射和碎浪操作,可以用来导出在高维解决方案空间中搜索的有效机制.算法WWO的框架简单,易于实现,并且只需要少量的控制参数.本文应用WWO求解车辆路径问题(the Capacitated Vehicle Routing Problem CVRP),算法采用0-1矩阵编码方式,通过传播操作进行全局搜索,反射操作实现进化,碎浪操作防止陷入局部最优.利用构建的算法求解64个benchmark算例,求解的结果中有65%的算例获得已知最优解,有6个算例更新了已知最好解,验证水波算法求解车辆路径问题的可行性,为水波算法应用于其他优化问题提供参考.

• 单位
  浙江工业大学; 嘉兴职业技术学院