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.
Open Vehicle Routing Problem(OVRP),
nearest neighbor priority,
polar axis scan