Approche Sous-gradient pour le problème du TSP " Travelling Salesman Problem "

Abstract

Un nouvel algorithme de sous-gradient dévié est présenté pour calculer une borne inférieure du problème dual. Ces bornes peuvent être utiles, dans l’évaluation des nœuds dans un l’algorithme ’Branch and Bound’, pour trouver la solution optimale des problèmes de programmation linéaire en nombre entier à grande taille. La direction de recherche déviée utilisée dans cette thèse est une combinaison convexe de la technique de gradient modifié et de la stratégie de direction moyenne. Dans ce contexte, nous identifions le paramètre de combinaison convexe optimal permettant à la direction du vecteur sous-gradient dévié de former un angle plus aigu avec la meilleure direction vers une solution optimale. L’algorithme modifié donne des résultats encourageants pour des instances de problèmes de voyageur de commerce symétrique (TSPs) sélectionnés depuis la base de données TSPLIB.