车辆路径问题的捕食搜索算法研究

Predatory search algorithm for vehicle routing problem

针对车辆路径问题存在的NP难题,设计了一种模仿动物捕食策略的捕食搜索算法进行求解。该算法利用搜索空间限制的大小,定义算法的局域搜索和全局搜索,并通过调节搜索空间的限制,以实现局域搜索和全局搜索之间的转换,它具有较好的局部集中搜索和跳出局部最优的能力。通过测试实例的计算,并与已有相关算法进行比较,结果表明该算法简洁而行之有效,是求解车辆路径问题的一个较好方法。

With respect to the inherent NP-hard complexity of vehicle routing problem, a predatory search algorithm simulating animal predatory strategies was designed. This algorithm defined local and global search by the restriction value of search space, and realized the conversion between local and global search by adjusting the restriction value of search space. It had better ability to conduct local search and jump out of local optimal solution simultaneously. Computation results of application examples showed that the designed algorithm was more feasible and effective than other relevant algorithms, and it was a good solution to vehicle routing problem.