Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorToulouse, Sophie
HAL ID: 177689
ORCID: 0000-0002-6689-1008
dc.date.accessioned2010-11-24T12:42:26Z
dc.date.available2010-11-24T12:42:26Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5161
dc.description.abstractfrLa 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 optimalen
dc.language.isofren
dc.subjectVoyageur de commerceen
dc.subjectOptimisation combinatoireen
dc.subject.ddc511en
dc.titleLe voyageur de commerce et ses variations : un tour d'horizon de ses résolutionsen
dc.typeChapitre d'ouvrage
dc.identifier.citationpages51-93en
dc.relation.ispartoftitleOptimisation Combinatoire 5 : problèmes paradigmatiques et nouvelles problématiquesen
dc.relation.ispartofeditorPaschos, Vangelis Th.
dc.relation.ispartofpublnameHermès science publ. Lavoisieren
dc.relation.ispartofpublcityParisen
dc.relation.ispartofdate2007
dc.relation.ispartofpages271-XI p.en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00152332/fr/en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-2-7462-1696-9en


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record