Sufficient stability conditions in the traveling salesman problem

Uniform sufficient conditions for the stability of optimal routes in the traveling salesman problem under various distortions of initial data are formulated and proved. The distortions include addition and removal of vertices and changes in the travel cost matrix. Polynomial-time algorithms are presented, which use the obtained sufficient conditions to construct stability domains on finite sets. Results of experiments in metric traveling salesman problems on the integer lattice are demonstrated.