ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 22/2 - 2008  - pp.209-235  - doi:10.3166/ria.22.209-235
TITLE
Combining metaheuristics and ILP for solving the car sequencing problem

RÉSUMÉ
Dans cet article, nous proposons deux formes d'hybridation entre une métaheuristique (Optimisation par Colonie de Fourmis ou Algorithme Génétique) et une méthode exacte (Programmation Linéaire en Nombres Entiers) pour la résolution du problème d'ordonnancement de voitures. Nous examinons dans quelles mesures ce type d'hybridation peut améliorer la qualité des solutions obtenues par rapport à ce que l'on pourrait obtenir avec une métaheuristique utilisant une procédure de recherche locale. Les expérimentations numériques présentées ont été effectuées en utilisant des benchmarks classiques de la littérature. Les résultats obtenus montrent que l'utilisation d'approches hybrides apporte une amélioration significative de la performance et que l'efficacité de l'heuristique ou de la métaheuristique sur laquelle se base l'hybridation influence aussi grandement la qualité des solutions. Toutefois, on note également une augmentation importante des temps d'exécution. Nous concluons que les mécanismes de diversification d'une métaheuristique à base de populations jouent un rôle important dans l'hybridation.


ABSTRACT
In this paper we propose two forms of hybridization between a metaheuristic (Ant Colony Optimization or Genetic Algorithm) and an exact method (ILP) for the solution of the car sequencing problem. We examine whether such hybridizations can improve solution quality over what can be obtained from the alternative approach of using local search within one of these metaheuristics. We present a computational experiment based on the CSPLib benchmarks. The results presented show that the use of hybrid approaches provides a significant improvement and that the performance of the heuristic or metaheuristic that the hybridization is based on greatly influences the quality of the results, however, computations time are long. We conclude that diversification in a population-based metaheuristic plays an important role in the hybridization.


AUTEUR(S)
Marc GRAVEL, Caroline GAGNÉ, S. NOËL, A. ZINFLOU

MOTS-CLÉS
hybridation, métaheuristiques, optimisation par colonie de fourmis, algorithme génétique, programmation linéaire en nombres entiers, ordonnancement, problème d'ordonnancement de voitures.

KEYWORDS
hybridization, metaheuristics, ant colony optimization, genetic algorithm, ILP, scheduling, car sequencing problem.

CITATIONS
ria.revuesonline.com/revues/30/citation/11538.html

LANGUE DE L'ARTICLE
Anglais

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (988 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier