Critical transition in the constrained traveling salesman problem

Area of Science:

• Computational mathematics
• Operations research
• Statistical physics

Background:

• The Traveling Salesman Problem (TSP) is a classic optimization challenge.
• Understanding TSP performance with environmental constraints is crucial.
• The Held-Karp lower bound provides a benchmark for TSP solutions.

Purpose of the Study:

• To investigate the finite size scaling of mean optimal tour length in a constrained TSP.
• To analyze the relationship between obstacle density and tour length deviations from the Held-Karp bound.

Main Methods:

• Computational analysis of a constrained TSP variant.
• Examining the mean optimal tour length.
• Assessing the excess over the Held-Karp lower bound as a function of obstacle density.

Main Results:

• A critical transition was identified in the TSP.
• This transition occurs at an obstacle density of approximately 85% (rho(c)).
• The excess of the mean optimal tour length over the Held-Karp lower bound shows a distinct dependence on obstacle density around this transition.

Conclusions:

• Obstacle density significantly influences TSP solution quality.
• A critical density threshold affects the relationship between optimal tour length and theoretical lower bounds.
• Findings provide insights into TSP behavior in constrained environments.