A hybrid dynamic programming and memetic algorithm to the Traveling Salesman Problem with Hotel Selection. (February 2018)

• Record Type: Journal Article
• Authors: Lu, Yongliang; Benlic, Una; Wu, Qinghua
• Is Part Of: Computers & operations research. Volume 90(2018)
• Page Start: 193
• Page End: 207
• Publication Date: 2018-02
• Subjects: Dynamic programming -- The traveling salesman problem -- Infeasible local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.008
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We present a hybrid dynamic programming and memetic algorithm for solving the traveling salesman problem with hotel selection. We present a dynamic programming approach to find an optimal hotel sequence for a given tour. Memetic search uses three dedicated crossover operators for solution recombination and an adaptive rule for crossover selection. Memetic search yields new best solutions for 22 of test problems. Abstract: 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.