Access by Xinjiang University

Traveling salesman problem with a center

¹Faculty of Physics, Adam Mickiewicz University, 61-614 Poznań, Poland
²Institute of Linguistics, Adam Mickiewicz University, 60-371 Poznań, Poland

Phys. Rev. E 71, 067701 – Published 10 June, 2005

DOI: https://doi.org/10.1103/PhysRevE.71.067701

Abstract

We study a traveling salesman problem where the path is optimized with a cost function that includes its length $L$ as well as a certain measure $C$ of its distance from the geometrical center of the graph. Using simulated annealing (SA) we show that such a problem has a transition point that separates two phases differing in the scaling behavior of $L$ and $C$ , in efficiency of SA, and in the shape of minimal paths.

Article Text

References (17)

D. S. Johnson, in Procedings of the 17th Colloquium on Automata, Languages and Programming, edited by M. S. Paterson, Lecture Notes in Computer Science, Vol. 443 (Springer-Verlag, Berlin, 1990).
M. Garey and D. S. Johnson, Computers and Intractability (Freeman, San Francisco, 1979).
J. R. Koza, Genetic Programming (MIT Press, Cambridge, MA, 1992).
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671 (1983).
S. Boettcher and A. Percus, Artif. Intell. 119, 275 (2000).
B. Hayes, Am. Sci. 85, 108 (1996).
T. Hogg, B. A. Huberman, and C. P. Williams, Artif. Intell. 81, 1 (1996).
W. Zhang and R. E. Korf, Artif. Intell. 81, 223 (1996).
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature (London) 400, 133 (1999).
S. Mertens, Phys. Rev. Lett. 84, 1347 (2000); G. Korniss, Z. Toroczkai, M. A. Novotny, and P. A. Rikvold, ibid. 84, 1351 (2000).
S. Lin and B. W. Kernighan, Oper. Res. 21, 498 (1973).
P. F. Stadler and W. Schnabl, Phys. Lett. A 161, 337 (1992).
J. Beardwood, J. H. Halton, and J. M. Hammersley, Proc. Cambridge Philos. Soc. 55, 299 (1959).
Assuming that distribution of the central points of links is uniform in the unit square we obtain that their average distance from $(1 ∕ 2, 1 ∕ 2)$ equals $\bar{c} = \int_{0}^{1} \int_{0}^{1} \sqrt{{(x - 0.5)}^{2} + {(y - 0.5)}^{2}} d x d y \sim 0.384$ . For $r = 0$ and $N = 100$ our numerical calculations give $C \sim 37.3$ which is in a relatively good agreement with the approximation $C = \bar{c} N$ . (As might be expected, it is slightly smaller.)
J. Lee and M. Y. Choi, Phys. Rev. E 50, R651 (1994).
G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, J. Comput. Phys. 159, 139 (2000).
J. Bentner, G. Bauer, G. M. Obermair, I. Morgenstern, and J. Schneider, Phys. Rev. E 64, 036701 (2001).

Physical Review E

Export citation

Export citation

Traveling salesman problem with a center

Abstract

Article Text

References (17)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation