Simulated Annealing Algorithm for TSP Problem with Two-Point Exchange Operation

Simulated Annealing is a heuristic optimization algorithm inspired by the metallurgical process of annealing, widely used for solving combinatorial optimization problems. The Traveling Salesman Problem (TSP) serves as a classic application scenario, aiming to find the shortest possible route that visits each city exactly once and returns to the origin city.

The two-point exchange operation is a common neighborhood search mechanism in simulated annealing, where two cities are randomly selected from the current path and their positions are swapped to generate new solutions. In code implementation, this can be achieved through a simple array element swap function. The algorithm initially accepts a higher proportion of inferior solutions to escape local optima, gradually converging as the temperature decreases according to a cooling schedule.

The core algorithm framework includes: initial solution generation (often using random permutation or greedy methods), temperature cooling strategy (typically geometric cooling with α=0.95), neighborhood search (two-point swap operation), acceptance criterion (Metropolis criterion using probability exp(-ΔE/T)), and termination conditions. The method's key advantage lies in its ability to escape local optima, though parameter tuning significantly impacts final results.

Practical implementation requires balancing exploration and exploitation. The simplicity of two-point exchange makes it easy to code (requiring only O(1) operation time), but may need combination with other neighborhood operations like inversion or insertion to improve solution quality. Code should include temperature logging and solution tracking for performance analysis.