The Library
Characterization of the probabilistic traveling salesman problem
Tools
Bowler, Neill E., Fink, Thomas M. A. and Ball, Robin. (2003) Characterization of the probabilistic traveling salesman problem. Physical Review E, Vol.68 (No.3). ISSN 1063651X

PDF
WRAP_Ball_Characterization_probabilistic_travelling.pdf  Accepted Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (267Kb) 
Official URL: http://dx.doi.org/10.1103/PhysRevE.68.036703
Abstract
We show that stochastic annealing can be successfully applied to gain new results on the probabilistic traveling salesman problem. The probabilistic "traveling salesman" must decide on an a priori order in which to visit n cities (randomly distributed over a unit square) before learning that some cities can be omitted. We find the optimized average length of the pruned tour follows E((L) over bar (pruned))=rootnp(0.8720.105p)f(np), where p is the probability of a city needing to be visited, and f(np)>1 as np>infinity. The average length of the a priori tour (before omitting any cities) is found to follow E(La priori)=rootn/pbeta(p), where beta(p)=1/[1.250.82 ln(p)] is measured for 0.05less than or equal topless than or equal to0.6. Scaling arguments and indirect measurements suggest that beta(p) tends towards a constant for p<0.03. Our stochastic annealing algorithm is based on limited sampling of the pruned tour lengths, exploiting the sampling error to provide the analog of thermal fluctuations in simulated (thermal) annealing. The method has general application to the optimization of functions whose cost to evaluate rises with the precision required.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Physics  
Library of Congress Subject Headings (LCSH):  Simulated annealing (Mathematics), Travelingsalesman problem  
Journal or Publication Title:  Physical Review E  
Publisher:  American Physical Society  
ISSN:  1063651X  
Official Date:  9 September 2003  
Dates: 


Volume:  Vol.68  
Number:  No.3  
Number of Pages:  7  
Identification Number:  10.1103/PhysRevE.68.036703  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Open Access  
Funder:  BP Amoco, Engineering and Physical Sciences Research Council (EPSRC)  
References:  [1] R. C. Ball, T. M. Fink, and N. E. Bowler, submitted 

URI:  http://wrap.warwick.ac.uk/id/eprint/9242 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year