A Tabu Search Heuristic for the Vehicle Routing Problem
提出一种新的禁忌搜索启发式算法TABUROUTE，用于解决带容量和路线长度限制的车辆路径问题，通过移除和重新插入顶点生成邻域解，允许不可行解，数值测试表明其优于现有启发式算法。
The purpose of this paper is to describe TABUROUTE, a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algorithm considers a sequence of adjacent solutions obtained by repeatedly removing a vertex from its current route and reinserting it into another route. This is done by means of a generalized insertion procedure previously developed by the authors. During the course of the algorithm, infeasible solutions are allowed. Numerical tests on a set of benchmark problems indicate that tabu search out performs the best existing heuristics, and TABUROUTE often produces the best known solutions.