A hybrid dynamic programming and memetic algorithm to the Traveling Salesman Problem with Hotel Selection

The Traveling Salesman Problem with Hotel Selection (TSPHS) is a variant of the classic Traveling Salesman Problem. It arises from a number of real-life applications where the maximum travel time for each “day trip” is limited. In this paper, we present a highly effective hybrid between dynamic programming and memetic algorithm for TSPHS. The main features of the proposed method include a dynamic programming approach to find an optimal hotel sequence for a given tour, three dedicated crossover operators for solution recombination, an adaptive rule for crossover selection, and a two-phase local refinement procedure that alternates between feasible and infeasible searches. Experiments on four sets of 131 benchmark instances from the literature show a remarkable performance of the proposed approach. In particular, it finds improved best solutions for 22 instances and matches the best known results for 103 instances. Additional analyses highlight the contribution of the dynamic programming approach, the joint use of crossovers and the two local search phases to the performance of the proposed algorithm.