A Hybrid Metaheuristic for the Traveling Car Renter Salesman Problem

摘要

The Traveling Car Renter Salesman Problem (CaRS) is a generalization of the Traveling Salesman Problem. To deal with CaRS, a hybrid metaheuristic approach is presented: an evolutionary algorithm (EA) and the hybrid method called Iterated Adaptive Local Search Procedure (IALSP), denoted by EA+IALSP. The IALSP proposed is a new variant of the framework Adaptive Local Search Procedure (ALSP). The results of various experimental studies using a suite of 19 non-Euclidean instances taken from the literature show that the EA+IALSP is a promising optimization method. EA+IALSP was compared to the best known algorithm in literature. Non-parametric test (Wilcoxon signed-ranks test) was used. Level of significance 5%. Significant improvements were found in instances with more than 100 vertices. A new approach is suggested to improve IALSP's performance near the optima, such as using a Scientific Algorithm.