Abstract: This paper proposed an iterated local search (ILS) algorithm with a new perturbation mechanism for vehicle routing problem.The perturbation mechanism is based on ruin and recreating principle,which includes destroying and repair procedures.The best local neighborhood solution is firstly destroyed by a method which takes randomness and correlation into account.In the destroying process,a perturbation factor is also introduced into the perturbation mechanism to control the strength of destroying.And then the destroyed solution is repaired by randomly selecting basic greedy insertion and regret greedy insertion algorithms.The experiments on the benchmark instances prove that the developed algorithm is more effective when compared with quantum evolutionary algorithm and artificial bee colony.

Key words: Vehicle routing problem,Iterated local search,Ruin and recreate,Metaheuristic