Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows

Abstract The problem studied in this paper is the open vehicle routing problem with time windows. This problem is different from the better known vehicle routing problem with time windows because in the former the vehicles do not return to the distribution depot after delivering the goods to the customers. For solving this problem an iterated local search algorithm was used, whose good results are mainly due to the kind of perturbations applied, in particular, ejection chains, and also to the use of elite solutions. The performance of this algorithm is tested using a large set of benchmark problems, containing 418 instances in total. The solutions obtained show that it is competitive with the best algorithms existing in the literature.