An efficient hybrid algorithm for the Traveling Car Renter Problem

This paper tackles a Traveling Salesman Problem variant called Traveling Car Renter Problem, where one car renter desires to travel among cities using a rented vehicle. Basically, the car renter has two options when he/she arrives in a city: to return the vehicle and rent another one or to keep the same car until the next city. Every time a car is delivered in a city, a return fee must be paid. Travel cost between any pair of cities also depends on the chosen car. The objective is to establish a Hamiltonian cycle minimizing the travel costs and returning fees. An evolutionary algorithm (EA) and a hybrid method called Adaptive Local Search Procedure (ALSP) are proposed for this problem. Both were compared to the best known algorithm in literature and obtained better results for non-Euclidean instances. Such algorithms compose an efficient model for a better exploration of the problem solutions space. From the expert system point-of-view, we propose a novel inference engine with minimized results error.