Well solved cases of probabilistic traveling salesman problem

Bellalouna, Monia; Paschos, Vangelis; Khaznaji, Walid

Bellalouna, Monia; Paschos, Vangelis; Khaznaji, Walid (2010), Well solved cases of probabilistic traveling salesman problem, 42èmes Journées de Statistique, 2010-05, Marseille, France

Type

Communication / Conférence

External document link

http://hal.inria.fr/inria-00494762/en/

Date

2010

Conference title

42èmes Journées de Statistique

Conference date

2010-05

Conference city

Marseille

Conference country

France

Metadata

Show full item record

Author(s)

Bellalouna, Monia
Paschos, Vangelis
Khaznaji, Walid

Abstract (FR)

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.

Abstract (EN)

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.

Subjects / Keywords

Voyageur de commerce; Statistiques mathématiques; Processus