A transgenetic algorithm applied to the Traveling Car Renter Problem

• The Traveling Car Renter, a generalization of the TSP is considered.
• An integer quadratic programming model is presented.
• Eighteen instances are optimally solved.
• A transgenetic algorithm is applied to sixty large instances.
• The proposed algorithm is highly effective in solving instances of up to 300 nodes.

The Traveling Car Renter is a new problem and constitutes a generalization of the Traveling Salesman. Several applications arise from it, mainly in the scheduling optimization of rental cars and in other problems concerning transport systems. In this paper, an integer quadratic programming model is presented for the Traveling Car Renter. It is linearized and implemented on a solver providing optimal solutions to a set of eighteen small instances. Large instances are tackled with a transgenetic algorithm proposed here. A computational experiment is reported on sixty instances and the proposed algorithm is compared to a memetic algorithm presented previously. The computational experiment aimed at focusing on the differences of performance between the two heuristic algorithms due to the search strategy used by each of them. Therefore, the implementation of both methods shared several elements. The results show that the transgenetic algorithm presents the best performance, indicating that its cooperative evolutionary process was more effective on the investigated problem than the competitive scheme of the memetic algorithm.