Meta-heuristic Algorithms For Several Variants Of The Traveling Salesman Problem

The traveling salesman problem is a classic NP-hard combinatorial optimization problem with important practical significance.This paper studies four variants of TSP,i.e.the traveling salesman problem with hotel selection(TSPHS),the pickup and delivery traveling salesman problem with FIFO loading(TSPPDF),the multi-commodity pickup-anddelivery traveling salesman problem(m-PDTSP),and clustered traveling salesman problem(CTSP).We propose four metaheuristic algorithms for them respectively and evaluate the performance of the proposed algorithm by means of extensive comparisons with the bestperforming state-of-art approaches from the literature.The main contribution of this paper includes:(1)A highly effective hybrid evolutionary search algorithm(denoted as HEA)is proposed for TSPHS,which integrates a number of distinguishing and novel ingredients:(i)a fast dynamic programming approach to optimally partition a given tour into a set of feasible trips,which is also incorporated into the local refinement procedure of HEA for further improvement of produced solutions;(ii)three dedicated crossover operators for generating high quality offspring solutions;(iii)an adaptive rule for crossover selection;and(iv)a local refinement procedure that alternates between a feasible and an infeasible search for an effective exploration of the search space.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 24 instances and matches the best known results for 104 instances.(2)A multi-restart iterative search approach(denoted as MIS)is proposed for TSPPDF.The basic idea behind MIS is to alternate between a threshold-based exploration phase,during which degrading solutions are considered as long as they satisfy a quality threshold,and a descent-based improvement phase that only accepts solutions that improve on the quality of the current solution.A dedicated restart strategy is applied to generate a new starting point for the next round of the iterative search as soon as the search is deemed trapped into a deep local optimum.Extensive experiments on a set of 42 benchmark instances from the literature show that the proposed approach competes very favorably with the existing methods from the literature.In particular,it reports new upper bounds(improved best-known solutions)for 20 instances,while matching the best-known result for the remaining instances.(3)A highly effective population based randomized tabu thresholding algorithm(denoted as PRTTA)is proposed for m-PDTSP.The basic idea behind PRTTA consists of a number of iterations of the basic randomized tabu thresholding approach to act as the local refinement procedure so as to improve the search intensification,and in each iteration a population of solutions is used to generate a new starting point for the current iterative search so as to improve the search diversification.Extensive experiments on the existing set of348 benchmark instances of different sizes show that the proposed approach competes very favorably with the existing methods from the literature.In particular,it reports new upper bound(improved best-known solution)for 97 out of the 108 medium and large instances.(4)We develop a solution approach for the CTSP by transforming the CTSP instance to the TSP one and solving the transformed problem with a highly effective hybrid evolutionary search algorithm.Extensive experiments on a set of benchmark instances show that the proposed approach outperforms all comparison methods with respect to both solution quality and run-time.In particular,it reports new upper bounds(improved best-known solutions)for almost all of the medium and large instances with unknown optima,while finding optimal solutions for the small cases.In most cases,the proposed algorithm is about 3 to 10 times faster than the other state-of-the-art heuristics.The above research results indicate that the proposed four heuristics are most efficient and effective heuristic algorithms,which compete favorably with these recent best performing approaches from the literature.In future research,we will try to employ these algorithms to solve other related traveling salesman problems or vehicle routing problems.