RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Avtomat. i Telemekh.: Year: Volume: Issue: Page: Find

 Avtomat. i Telemekh., 2006, Issue 12, Pages 190–204 (Mi at1262)

Technical Diagnostics

On the solution of the traveling salesman problem once again

P. P. Parkhomenko

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia

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

Full text: PDF file (228 kB)
References: PDF file   HTML file

English version:
Automation and Remote Control, 2006, 67:12, 2036–2050

Bibliographic databases:

PACS: 02.10.Îõ
Presented by the member of Editorial Board: Â. Â. Êóëüáà

Citation: 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
\Bibitem{Par06} \by P.~P.~Parkhomenko \paper On the solution of the traveling salesman problem once again \jour Avtomat. i Telemekh. \yr 2006 \issue 12 \pages 190--204 \mathnet{http://mi.mathnet.ru/at1262} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2283327} \zmath{https://zbmath.org/?q=an:1194.90110} \transl \jour Autom. Remote Control \yr 2006 \vol 67 \issue 12 \pages 2036--2050 \crossref{https://doi.org/10.1134/S0005117906120150} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33845619444}