一种毗邻信息改进的车辆路径问题禁忌搜索算法

An Improved Tabu Search Algorithm with Adjacent Information for Capacitated Vehicle Routing Problem

提高求解大规模车辆路径问题的算法效率,已经成为物流配送的现实需要。针对一种典型的车辆路径问题禁忌搜索算法,提出用毗邻信息指导的动态候选集规模改进禁忌搜索算法,以提高禁忌搜索算法求解大规模车辆路径问题的自适应能力和鲁棒性。算例测试证明,改进的算法在求解问题规模较大时,可以带来超过50%的搜索时间节省。

Efficiently solving large scale Vehicle Routing Problem （VRP） has become the practical needs of the logistics. In order to improve the self-adaptive capacity and robustness of Tabu Search （TS） in solving large scale VRP, an approach directed by adjacent information is proposed, and a dynamics of the neighbor candidate set is designed. The simulation shows that the improved algorithm has higher time-efficiency than the old one in solving larger scale VRP, bring more than half savings of searching time.