Memetic algorithm for the Traveling Car Renter Problem: an experimental investigation

Research paper by Marco César Goldbarg, Paulo Henrique Asconavieta, Elizabeth Ferreira Gouvêa Goldbarg

Indexed on: 16 Sep '11Published on: 16 Sep '11Published in: Memetic Computing


The Traveling Car Renter Problem (CaRS) is a generalization of the Traveling Salesman Problem where the tour can be decomposed into contiguous paths that are travelled by different rented cars. When a car is rented in a city and delivered in another, the renter must pay a fee to return the car to its home city. Given a graph G and cost matrices associated to cars available for rent, the problem consists in determining the minimum cost Hamiltonian cycle in G, considering also the cost paid to deliver a car in a city different from the one it was rented. The latter cost is added to the cost of the edges in the cycle. This paper describes the general problem and some related variants. Two metaheuristic approaches are proposed to deal with CaRS: GRASP hybridized with Variable Neighborhood Descent and Memetic Algorithm. A set of benchmark instances is proposed for the new problem which is utilized on the computational experiments. The algorithms are tested on a set of 40 Euclidean and non-Euclidean instances.