Algorithmes génétiques pour le CARP

International audienceLe CARP (Capacitated Arc Routing Problem) est un problème NP-difficile, utile pour modéliser par exemple le ramassage des ordures ménagères ou le déneigement des routes. Les méthodes exactes de résolution ne résolvent que de petites instances et les problèmes de grande taille sont traitables uniquement par des heuristiques ou des métaheuristiques. Nous présentons les premiers algorithmes génétiques de la littérature pour résoudre le CARP. Le modèle de données étendu permet de prendre en compte efficacement plusieurs extensions telles que les rues à sens unique ou à double sens et les interdictions de tourner. Notre meilleur algorithme génétique, de type hybride, a été testé sur des instances de la littérature et se montre compétitif avec les métaheuristiques déjà publiées