Un algorithme de branch-and-cut pour la résolution du Problème de Tournées Sélectives

摘要: Cet article decrit un algorithme de branch-and-cut pour resoudre le probleme tournees selectives (Team Orienteering Problem - TOP). Il s'agit d'une variante du vehicules dont but est maximiser la somme des profits collectes tout en respectant temps trajet limite chaque vehicule. Notre base sur une formulation lineaire avec nombre polynomial variables. Un ensemble proprietes dominance et d'inegalites valides propose renforcer cette formulation. Elles sont basees l'elimination symetrie sous-tours ainsi que l'introduction bornes profit/nombre clients coupes exploitant graphes d'incompatibilite. Les experimentations realisees benchmark TOP montrent l'efficacite notre methode. L'algorithme capable traiter grand d'instances permet a l'optimalite plusieurs instances ouvertes.