An efficient hybrid genetic algorithm for the traveling salesman problem with release dates

This paper deals with a generalization of the classic traveling salesman problem where each customer is associated with a release date, defined as the time at which the desired product becomes available at the depot. In this problem, a single uncapacitated vehicle is allowed to perform multiple trips in order to satisfy all demands. However, the vehicle cannot start a route unless all the products associated with the demands in the route are released. As a consequence, there might be a waiting time before starting the next route. The objective of the problem is to minimize the completion time of the service, defined as the time at which the vehicle returns to the depot after satisfying all demands. We propose a hybrid genetic algorithm that incorporates more advanced mechanisms to evaluate individuals and to ensure population diversity. We also introduce a novel dynamic programming splitting algorithm that converts a sequence of visits to customers, the so-called giant-tour, into the best set of routes that respects the sequence. Computational experiments performed on 522 benchmark instances show that our approach is able to find all 154 known optimal solutions from the literature. In addition, we were able to improve the best-known upper bounds for 364 instances in significantly shorter computational times when compared to the state-of-the-art.