DocumentCode
729519
Title
A branch and bound algorithm for the porbabilistic traveling salesman problem
Author
Mahfoudh, Soumaya Sassi ; Khaznaji, Walid ; Bellalouna, Monia
Author_Institution
ENSI(Ecole Nat. des Sci. Inf.), Tunisia
fYear
2015
fDate
1-3 June 2015
Firstpage
1
Lastpage
6
Abstract
The Probabilistic Traveling Salesman Problem (PTSP) is a generalization of the well-known Traveling Salesman Problem (TSP), the main difference is the cities are present with a probability. PTSP is NP-Hard, researches are rather directed towards heuristics for having acceptable solutions. In this paper, we propose an branch and bound algorithm for exact resolution for the PTSP .Estimating the evaluation represents the originality of our paper.
Keywords
computational complexity; graph theory; probability; set theory; travelling salesman problems; tree searching; NP-hard problem; PTSP; branch-and-bound algorithm; exact resolution; probabilistic traveling salesman problem; probability; Binary trees; Cities and towns; Probabilistic logic; Random variables; Traveling salesman problems;
fLanguage
English
Publisher
ieee
Conference_Titel
Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD), 2015 16th IEEE/ACIS International Conference on
Conference_Location
Takamatsu
Type
conf
DOI
10.1109/SNPD.2015.7176284
Filename
7176284
Link To Document