摘要： 设计有数量限制的开放式车辆路径加速禁忌搜索算法，将所有点(包括客户和仓库)做Delaunay三角剖分后，限制问题的解的大多数边与Delaunay三角剖分的边重合。实验结果表明，该算法在保证寻求到相对较优解的前提下，执行速度得到大幅度的提升，解与上界关联紧密，可以应用到其他启发式搜索问题的求解中。

关键词: 开放式车辆路径问题, 禁忌搜索, Delaunay三角剖分, 最近邻居优先, 极坐标扫描

Abstract: This paper makes advantage of the Delaunay triangulation of all customers(including the depot), keeps most edges of the solution overlap the edges of Delaunay triangulation to accelerate an improved Tabu search algorithm. Experimental results show that the algorithm well solves the m-Open Vehicle Routing Problem(OVRP) problem with stable performance, and the solution keeps close with the upper bound. The search techniques proposed can be easily applied for other meta-heuristics for problem solving.

Key words: Open Vehicle Routing Problem(OVRP), Tabu search, Delaunay triangulation, nearest neighbor priority, polar axis scan

中图分类号: 

• TP301.6