Abstract

This work proposes a new algorithm that combines Iterated Local Search (ILS), Variable Neighborhood Search (VNS), Random Variable Neighborhood Descent (RVND) and a constructive initial search to solve the Traveling Car Renter Problem (CaRS). The CaRS a variation of the Traveling Salesman Problem where a customer wants to visit a set of cities using a rental car. The customer has a fixed amount of car options available to choose and when he returns the car, he will not be able to use it again. The traveling cost varies according to the car used, being the same value in the opposite direction. In addition to this cost, the customer also pays for a vehicle return. The objective is to minimize costs and fees. The results were compared to the state of the art and showed better performances.