Back to Search
Start Over
TETRAHEURÍSTICA SISTÉMICA (THS) PARA EL TSP.
- Source :
-
INGENIARE - Revista Chilena de Ingeniería . may-ago2010, Vol. 18 Issue 2, p187-202. 6p. 4 Diagrams, 4 Charts. - Publication Year :
- 2010
-
Abstract
- This paper presents a novel method to solve instances of the TSP. This method is comparable in effectiveness and efficiency with "nearest neighbour", "cheapest insertion", "two-way exchange improvement" and "branch and bound". The first section provides a literature review of the combinatorial optimization, the second provides a reference frame, the third the methodology used and the fourth contains, inter alia, system thinking, A×B factorial design and management tool CAP-DO. The fourth section presents the design "new" method called systemic tetraheuristic, followed by ANOVA and Duncan ranges for each factor: method and number of cities; this section concludes with an analysis of the proportion of "failures" of the proposed algorithm with increasing complexity of the TSP. As a result of this study a method is presented for solving the TSP. This method consists of: 1. "nearest neighbour", 2. "short-term sacrifice" 3. "LIFO transfer" and a support heuristic "right search 4P4 ". For the design of the "sacrifice short-term" procedure, it was necessary to analyze the "nearest neighbour" heuristic from a systems perspective. This heuristic is related to the "quick solutions that fail" archetype, which can be applied to day-to-day. The proposed method has proved to be more efficient than others, in what concerns quality of the solution and the computation time, especially when the complexity of the TSP increases. [ABSTRACT FROM AUTHOR]
Details
- Language :
- Spanish
- ISSN :
- 07183291
- Volume :
- 18
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- INGENIARE - Revista Chilena de Ingeniería
- Publication Type :
- Academic Journal
- Accession number :
- 57155231