Date
2010
Lien vers un document non conservé dans cette base
http://hal.inria.fr/inria-00494762/en/
Indexation documentaire
Recherche opérationnelle
Subject
Voyageur de commerce; Statistiques mathématiques; Processus
Titre du colloque
42èmes Journées de Statistique
Date du colloque
05-2010
Ville du colloque
Marseille
Pays du colloque
France
Année
2010
Auteur
Bellalouna, Monia
Paschos, Vangelis
Khaznaji, Walid
Type
Communication / Conférence
Résumé en français
Le problème du voyageur de commerce est généralement NP-Hard. Notre but est de chercher des cas qui sont "Faciles", c'est à dire résolubles en temps polynomial. Le Problème du Voyageur de Commerce Petit illustre bien ces cas, notre étude comporte deux volets, d'abord nous donnons la relation entre le problème déterministe et son homologue probabiliste, ensuite nous montrons un résultat remarquable, à savoir : ce problème est stable : la perturbation par l'absence de certaines données n'influe pas l'optimalité de la solution.
Résumé en anglais
The Probabilistic Traveling Salesman Problem is in general NP-Hard, the
objective of this paper is to look for particular cases which can be solved in an
easy way. First we give the relation between the two problems deterministic and
probabilistic. Second, we study the stability of the deterministic problem. We
prove that in the small traveling salesman problem, several tours were optimal,
but there is only one stable among them : The absence of certain cities does
not disturb the tour induced by the method of modi cation of the optimal tour
a priori.
