dorsal/arxiv
View SchemaCharacterisation of the probabilistic travelling salesman problem
| Authors | Neill E. Bowler, Thomas M. Fink, Robin C. Ball |
|---|---|
| Categories | |
| ArXiv ID | physics/0011023 |
| URL | https://arxiv.org/abs/physics/0011023 |
| DOI | 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 (PTSP). 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(\bar{L}_{pruned}) = \sqrt{np} (0.872-0.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(L_{a priori}) =\sqrt{n/p}\beta (p) where \beta (p)=1/(1.25-0.82 ln(p)) is measured for 0.05 < p < 0.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 analogue 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.
{
"annotation_id": "6ec8e368-6a8d-4d05-afdb-f11e771202a4",
"date_created": "2026-03-02T18:00:32.797000Z",
"date_modified": "2026-03-02T18:00:32.797000Z",
"file_hash": "0fce8a9b9642802cd46b2d62af7c62607b98cb30d582a491f841f024953c4cdb",
"private": false,
"record": {
"abstract": "We show that Stochastic Annealing can be successfully applied to gain new\nresults on the Probabilistic Traveling Salesman Problem (PTSP). The\nprobabilistic \"traveling salesman\" must decide on an a priori order in which to\nvisit n cities (randomly distributed over a unit square) before learning that\nsome cities can be omitted. We find the optimized average length of the pruned\ntour follows E(\\bar{L}_{pruned}) = \\sqrt{np} (0.872-0.105p) f(np) where p is\nthe probability of a city needing to be visited, and f(np) -\u003e 1 as np -\u003e\ninfinity. The average length of the a priori tour (before omitting any cities)\nis found to follow E(L_{a priori}) =\\sqrt{n/p}\\beta (p) where \\beta\n(p)=1/(1.25-0.82 ln(p)) is measured for 0.05 \u003c p \u003c 0.6. Scaling arguments and\nindirect measurements suggest that \\beta (p) tends towards a constant for\np\u003c0.03. Our stochastic annealing algorithm is based on limited sampling of the\npruned tour lengths, exploiting the sampling error to provide the analogue of\nthermal fluctuations in simulated (thermal) annealing. The method has general\napplication to the optimization of functions whose cost to evaluate rises with\nthe precision required.",
"arxiv_id": "physics/0011023",
"authors": [
"Neill E. Bowler",
"Thomas M. Fink",
"Robin C. Ball"
],
"categories": [
"physics.comp-ph",
"physics.gen-ph"
],
"doi": "10.1103/PhysRevE.68.036703",
"title": "Characterisation of the probabilistic travelling salesman problem",
"url": "https://arxiv.org/abs/physics/0011023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "18cb2ba9-1277-449c-b1f6-9bfaa1e26048",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}