DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2016-07-05 - Colloque/Présentation - poster - Anglais - 1 page(s)

Tuyttens Daniel , Mezmaz Mohand , Vaillant Gautier, Melab Nouredine, "Exploring GRASP-based Metaheuristics to solve the Traveling Salesman Problem" in 28th European Conference on Operational Research, Poznan, Pologne, 2016

  • Codes CREF : Recherche opérationnelle (DI1150)
  • Unités de recherche UMONS : Mathématique et Recherche opérationnelle (F151)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech)
Texte intégral :

Abstract(s) :

(Anglais) Exploring GRASP-based Metaheuristics to solve the Traveling Salesman Problem. Daniel Tuyttens, Mohand Mezmaz, Gautier Vaillant, Nouredine Melab In this work we consider the GRASP metaheuristic and the classical Traveling Salesman Problem. The paper proposes three variants of the GRASP method. These variants can be seen as a generalization of the construction phase used in GRASP. A first variant adds elements at the beginning and at the end of a partial solution unlike GRASP’s construction phase which adds elements only at the beginning. The second variant builds group of partial solutions simultaneously unlike GRASP’s construction phase which builds them separately. In a the third variant, a bound evaluates a partial solution like in a Branch-and-Bound procedure. Experiments on standard instances of the TSP show that some combinations of the variants improve, on average, the obtained results compared with the classical GRASP method. As a future work, we plan to test these variants on other optimization problems.