A beam search based algorithm for the capacitated vehicle routing problem with time windows

In this paper the capacitated vehicle routing problem with time windows is tackled with a beam-search based approximate algorithm. An instance of this problem is defined by a set of customers and a fleet of identical vehicles. A time window is associated with each customer and a maximum capacity characterizes a vehicle. The aim is then to serve all the customers by minimizing the number of vehicles used as well as the total distance and by respecting the time windows. The proposed method follows three complementary phases: (i) dividing the set of customers into disjunctive clusters, (ii) determining a feasible solution in each cluster by using beam search, and (iii) applying a local search in order to improve the quality of the solutions. The proposed method is analyzed computationally on a set of benchmarks due to Solomon. Encouraging results have been obtained.