On one approach to TSP structural stability

DOI10.1155/2014/397025MaRDI QIDQ2248701zbMATH OpenOpenAlexDBLPWikidataFDO

Authors E. E. Ivanko

Publication date 27 June 2014

Published in Advances in Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2014/397025

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Review text

Summary: 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.

Recommendations

• Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
• Stability of a routing optimization algorithm
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of minimum and maximum traveling salesman's tours
• Reoptimizing the traveling salesman problem

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A general approach to the study of the stability of solutions in discrete optimization problems
• Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Knowing all optimal solutions does not help for TSP reoptimization
• Measure of quasistability of a vector integer linear programming problem with generalized principle of optimality in the Helder metric
• On five types of stability of the lexicographic variant of the combinatorial bottleneck problem
• On the stability of some integer programming algorithms
• Reoptimizing the traveling salesman problem
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Sometimes Travelling is Easy: The Master Tour Problem
• Stability and accuracy functions in multicriteria linear combinatorial optimization problems
• Stability, parametric, and postoptimality analysis of discrete optimization problems
• The analysis of the stability of some integer programming algorithms with respect to the objective function

Cited in

(5)

• Stability of a routing optimization algorithm
• On inverse traveling salesman problems
• Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
• Some Inverse Traveling Salesman Problems
• Study on the stability of Steiner tree structure of explosion-proof textiles

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: On one approach to TSP structural stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248701)