Une nouvelle méthode hybride AUGMECON2-BC pour la résolution du problème de voyageur de commerce avec gains

Session : LTSS5-1 / LTSS5 : Problèmes de transport riches
Mercredi 10 février 11:00 - 12:20 Salle : GI041
Soumaya Ait Bouziaren et Brahim Aghezzaf

Le problème du voyageur de commerce avec gains (Traveling Salesman Problem with Profit TSPP) est une variante du problème de voyageur de commerce (TSP). Dans cette généralisation, un profit est associé à chaque sommet. L’objectif est de déterminer un itinéraire à travers un sous-ensemble de villes qui minimise simultanément le coût de voyage et maximise le profit récolté. Dans cet article, nous proposons une nouvelle méthode hybride AUGMECON2-BC incorporant une version améliorée de l'ε-contrainte augmentée et un algorithme Branch and Cut. Cette approche transforme un problème bi-objectif en problème monoobjectif. Ensuite, chaque sous problème atteint est résolu en utilisant l’algorithme Branch & Cut. Les expérimentations réalisées sur l’ensemble des instances de TSPLIB montrent que notre algorithme est capable de résoudre un grand nombre d’instances de tailles variées et converge dans un temps de calcul raisonnable.

Mots clés : Optimisation combinatoire bi-objective, Ɛ-contrainte, voyageur de commerce avec gains, exact Pareto, Branch and Cut, hybridation, AUGMECON2