1. ¹Université du Québec à Chicoutimi, Québec, Canada
2. ²Université Laval Ste-Foy, Québec, Canada

Correspondence: M Gravel, Département d'Informatique et de Mathématique, Université du Québec á Chicoutimi, 555 Boul. de l'Université, Chicoutimi, Québec, CanadaG7H 2B1. E-mail: marc_gravel@uqac.ca

Received November 2005; Accepted October 2006; Published online 19 March 2008.

Abstract

This paper compares different ant colony optimization algorithms for solving the NP-hard car-sequencing problem, which is of great practical interest. The five algorithms that are compared are the Ant System (AS), the Elitist AS, the Rank-Based AS, the Max–Min AS and the Ant Colony System. These algorithms, which are well known in the literature, differ in the way in which the pheromone trail is managed. The comparative analysis seeks to identify which algorithm best manages the learning process in solving the car-sequencing problem. Moreover, we propose a new structure for the pheromone trail specifically designed to take advantage of the type of constraints found in the car-sequencing problem. The quality of the results obtained with this new form of learning for three problem sets drawn from the literature is superior to that of the best results published and demonstrates the efficiency of this new trail structure.