Laboratoire de Génie Informatique et d’Automatique de l’Artois

Séminaire

Les algorithmes d’approximation avec garantie (ρ-approximation)

Le 2 avril 2019 à 15h00 Salle des séminaires du LGI2A, FSA, Béthune
Hamid ALLAOUI Professeur, Directeur du laboratoire LGI2A

Souvent trois champs sont investigués pour l’optimisation des systèmes logistiques. Le premier est l’analyse de la complexité des problèmes. Le deuxième est la formulation des algorithmes donnant la solution optimale. Si le temps de calcul est exorbitant, dans ce cas le troisième champ s’impose pour donner des solutions approximatives. Il consiste à utiliser des heuristiques, des méta-heuristiques ou des schémas d’intégration de différentes méthodes de résolution. Dans cette présentation nous nous focalisons sur les algorithmes d’approximation avec garantie (ρ-approximation). Nous illustrons le principe de ces algorithmes avec des exemples en ordonnancement, tournées de véhicules et localisation.