• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Le voyageur de commerce et ses variations : un tour d'horizon de ses résolutions

Monnot, Jérôme; Toulouse, Sophie (2007), Le voyageur de commerce et ses variations : un tour d'horizon de ses résolutions, in Paschos, Vangelis Th., Optimisation Combinatoire 5 : problèmes paradigmatiques et nouvelles problématiques, Hermès science publ. Lavoisier : Paris, p. 51-93

Type
Chapitre d'ouvrage
External document link
http://hal.archives-ouvertes.fr/hal-00152332/fr/
Date
2007
Book title
Optimisation Combinatoire 5 : problèmes paradigmatiques et nouvelles problématiques
Book author
Paschos, Vangelis Th.
Publisher
Hermès science publ. Lavoisier
Published in
Paris
ISBN
978-2-7462-1696-9
Number of pages
271-XI p.
Pages
51-93
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Toulouse, Sophie cc
Abstract (FR)
La difficulté de résolution du TSP a d'autant plus porté sur lui l'attention des chercheurs. Aussi a-t-il été étudié et retourné sous tous les angles~: théorie des graphes, programmation linéaire, programmation dynamique, optima locaux, etc. Les premières formalisations de la recherche exhaustive par la stratégie d'évaluation et séparation seraient même nées de recherches sur le voyageur de commerce. Ce chapitre retrace, certainement pas de façon exhaustive, l'histoire conjointe de la recherche opérationnelle et du voyageur de commerce. Après avoir présenté le problème, nous proposons des algorithmes, exacts puis approchés, pour différentes versions du problème~: minimisation ou maximisation, instances métriques, distances binaires, etc. Certains de ces algorithmes mettent en oeuvre des modèles généraux de résolution tels que la stratégie par séparation et évaluation, la programmation dynamique ou la recherche locale. Certains encore utilisent des heuristiques, qui ne sont autres que des idées de bon sens quant à la constitution d'une solution pour le problème étudié~: nous pensons par exemple aux heuristiques du regret et du plus proche voisin. D'autres enfin, exploitant la relative facilité de sous-problèmes du TSP, partent d'une solution de ces sous-problèmes et construisent à partir de celle-ci un cycle hamiltonien~; c'est le parti pris par l'algorithme de Christofides avec l'arbre couvrant, mais de nombreux résultats sont également obtenus par le biais d'un 2-couplage optimal
Subjects / Keywords
Voyageur de commerce; Optimisation combinatoire

Related items

Showing items related by title and author.

  • Thumbnail
    Algorithmes approchés pour le problème du voyageur de commerce multicritère 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent; Monnot, Jérôme (2005) Communication / Conférence
  • Thumbnail
    Un tour d'horizon sur quelques classes de jeux combinatoires 
    Giannakos, Aristotelis; Paschos, Vangelis (2006) Document de travail / Working paper
  • Thumbnail
    Tour d'horizon de l'actualité fiscale en matière d'acte anormal de gestion 
    Massard, Thibaut; Megdoud, Leïla (2012-06) Article accepté pour publication ou publié
  • Thumbnail
    Convergence des revenus par tête : un tour d'horizon 
    Le Pen, Yannick (1997) Article accepté pour publication ou publié
  • Thumbnail
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo