Application of the guided local search method to a class of over-constrained vehicle routing problems

To solve the vehicle routing problem (VRP) with time windows, where over-constrained situation may exist that no feasible solution satisfying all constraints is found, a novel algorithm, guided local search (GLS), is provided to minimize the total cost of violated constraints. By dynamically modifying the original objective function, the algorithm can both keep the high efficiency of local search and overcome the limitation of local minimum, thus quickly returning a satisfactory solution. An example is also provided which shows that GLS is better than broadly used Tabu search for such kind of problems.