ACOCaRS: Ant Colony Optimization Algorithm for Traveling Car Renter Problem

The Traveling Car Renter Salesman (CaRS) is a combinatorial optimization problem that is NP-hard and thus evolutionary and swarm computation metaheuristics are natural choices for designing a new practical algorithm. Considering that Ant Colony Optimization (ACO) is well suited for other routing type of problems - in this paper we propose ACOCaRS - an algorithm for solving CaRS based on ACO. The proposed algorithm was investigated experimentally and compared with other published algorithms for CaRS. The first results are encouraging since the proposed algorithm was significantly better for smaller problem instances than all the other published algorithms. However, for problem instances of size 100 and larger, ACOCaRS was the second best algorithm, and was outperformed significantly by a Transgenetic Algorithm. These results are based on the average performance of the algorithm and ranks, taking into account the number of wins and average ranks for the algorithms. A Friedman test confirmed that the results are statistically significant. In addition to average performance, data for assessing the peak performance of ACOCaRS are reported, along with a few new best known solutions for CaRS obtained in this research.