Les problèmes d'optimisation combinatoire sont omniprésents, aussi bien dans le

monde académique que dans l'univers industriel, dans les cas d'école comme dans les

décisions liées à des enjeux financiers importants (logistique de production et de

transport, télécommunications, design).

Comment ordonnancer un atelier ? Combien de tournées de véhicules sont

nécessaires pour servir les clients à partir des fournisseurs ? Dans quel ordre acheminer

les paquets de données dans un réseau internet ? Etc. Des questions qui obligent à

effectuer un choix de valeurs pour un ensemble de variables de décision sujettes à des

contraintes et ce, en optimisant des critères et/ou des préférences.

Deux grandes familles de méthodes de résolution existent. La première englobe les

méthodes dites exactes, qui ont l'avantage de garantir l'optimalité des solutions si elles

existent, mais souffrent de l'explosion combinatoire. La seconde famille de méthodes,

dites approchées, permet de réduire cette explosion sans toutefois garantir l'optimalité.

C'est dans le cadre de cette seconde famille que nous présentons ici les

métaheuristiques les plus célèbres à savoir : le recuit simulé, la recherche Tabou, les

méthodes de pénalité, l'optimisation par colonies de fourmis et les algorithmes

génétiques. Les origines, les principes et éléments de base, les algorithmes standards ainsi

que leurs extensions sont ainsi développés, avec des exemples de problèmes

complexes.

Cet ouvrage s'adresse : à l'ingénieur, en lui faisant découvrir et/ou maîtriser des

méthodes d'optimisation génériques et pratiques à mettre en oeuvre pour une aide à la

décision efficace ; au chercheur, débutant ou confirmé, en lui apportant une bibliographie

étendue ; à l'enseignant et à l'étudiant en lui fournissant un support de cours.