Avtomat. i Telemekh., 2006, Issue 12, Pages 190–204
On the solution of the traveling salesman problem once again
P. P. Parkhomenko
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
The procedure is suggested for the construction of Hamiltonian cycles optimized along the length in weighted graphs by the method of the stagewise isolation and lengthening of the linear portions of paths of the minimized length. The procedure makes it possible to process both nonoriented and oriented graphs, i.e., to solve symmetric and nonsymmetric problems of the traveling salesman.
At each stage of the procedure (starting from the first stage), the subgraphs of the initial (original) graph of the problem are processed, the complexity of which decreases in the transitions from stage to stage. The isolation and the lengthening of linear portions of the paths are the simplest operations for the detection of vertices of degree 2 with the possible removal of some edges (arcs) of a subgraph.
These characteristics of the procedure (the stagewise decrease of the complexity of the processable subgraphs and the exceptional simplicity of operations for the isolation and lengthening of the linear portions of paths) permits us to hope for a high effectiveness of the use of the procedure for the solution of the traveling salesman problems of large dimensions.
PDF file (228 kB)
Automation and Remote Control, 2006, 67:12, 2036–2050
Presented by the member of Editorial Board: Â. Â. Êóëüáà
P. P. Parkhomenko, “On the solution of the traveling salesman problem once again”, Avtomat. i Telemekh., 2006, no. 12, 190–204; Autom. Remote Control, 67:12 (2006), 2036–2050
Citation in format AMSBIB
\paper On the solution of the traveling salesman problem once again
\jour Avtomat. i Telemekh.
\jour Autom. Remote Control
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|