On One Approach to TSP Structural Stability

Abstract EN

In this paper we study an inverse approach to the traveling salesman reoptimization problem.

Namely, we consider the case of the addition of a new vertex to the initial TSP data and fix the simple “adaptation” algorithm: the new vertex is inserted into an edge of the optimal tour.

In the paper we consider the conditions describing the vertexes that can be inserted by this algorithm without loss of optimality, study the properties of stability areas, and address several model applications.