The Traveling Car Renter Problem (CaRS) is a generalization of the Traveling Salesman Problem. This paper presents a hybrid metaheuristic approach to deal with CaRS: an evolutionary algorithm (ScA) and the hybrid method Adaptive Local Search Procedure (ALSP), denoted by ScA+ALSP. A mixed integer programming model proposed for CaRS is corrected and used for ALSP. The results of various experimental studies using a suite of 21 instances taken from the literature have demonstrated the superiority of the hybrid ScA+ALSP over the best known algorithm in literature for non-Euclidean instances.
