Hybridization of Metaheuristics with Exact Methods for the Traveling Car Renter Salesman Problem
Hybrid metaheuristics, Traveling Car Renter Salesman Problem, Scientic Algorithms, Evolutionary Computation, Exact methods, Integer programming, Adaptive
Local Search Procedure, Iterated Adaptive Local Search Procedure
The Traveling Car Renter Salesman Problem or simply Traveling Car Renter Problem (CaRS), is a generalization of the Traveling Salesman Problem (TSP) where the tour can be decomposed into contiguous sub-tours that are travelled by dierent rented cars. The objective is to construct a minimal cost Hamiltonian circuit, considering the penalty paid for changing cars for another on the tour, this penalty is the cost of returning a car to the city where it was rented. CaRS is classied as a NP-hard problem. This work studies the CaRS version classied as: complete, total, unrestricted, with no repetition, free and symmetric. This research is focused on hybrid procedures that combine metaheuristics and linear programming (LP) based on the branch-and-bound algorithm. Metaheuristics and procedures based on exact methods are hybridized, such as: Scientic algorithms (ScA), Evolutionary algorithms (EA), Adaptive Local Search Procedure (ASLP) and a new variant of ALSP called Iterated Adaptive Local Search Procedure (IALSP). The following techniques are proposed to deal with CaRS: ScA+ALSP, EA+IALSP e ScA+IALSP. A mixed integer programming model proposed for CaRS is corrected and then used by ALSP and IALSP. Non-parametric tests are used to compare the algorithms within a set
of instances from the literature.