Traveling salesman problem with a center
A. Lipowski1 , D. Lipowska1
1 Faculty of Physics, A. Mickiewicz University, 61-614 Poznań, Poland
1 Institute of Linguistics, Adam Mickiewicz University, 60-371 Poznan, Poland
Phys. Rev. E, 71, 067701 (2005)
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.