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

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.