A new Tabu Search heuristic algorithm for the Vehicle Routing Problem with Time Windows

摘要

This paper describes a new design of Tabu Search (TS) algorithm for solving the Vehicle Routing Problem with Time Windows (VRPTW). Since VRPTW is a well known NP-hard problem, heuristic algorithms such as Tabu Search are always used to get a good approach. The former published designs of TS usually focus on the neighbor structure, the relaxation to the objective function or the multi-period algorithms. This paper has two contributions. First, it designs an objective value-based Tabu List structure to help decreasing the tabu list size and escape from local optima. it still adopts some tactics like adaptive tabu size, randomly selected neighbor structure and so on. Second, from a problem oriented point of view, it shows that, with this self-adaptive Tabu List, even five kinds of simple neighbor structures and a single period algorithm with original objective function can get very good solutions. We tested this algorithm with Solomon’s VRPTW benchmark problems, and 7 of the best known solutions are updated. Another advantage of this algorithm is its efficiency. It runs on an average of 80 seconds on a normal personal computer for a solution of a problem with 100 customers.