Application of Element Decomposing Method for Solving Traveling Salesman Problems

Ekkaphon Jaiyen, Komgrit Leksakul

Abstract

The objective of this research study was to solve the traveling salesman problem (TSP) in order to provide a traveling sequence for the minimum total traveling time. This paper highlights the significance of creating and developing the element decomposition method (EDCM) as a part of the finite element method for solving TSP. There are two phase of research methodology. The first phase involves simplex method. The second phase is about creating and developing the algorithm through the application of the EDCM. The results obtained using the algorithm employing the EDCM were then compared with branch and bound method (B&B) and ant colony optimization (ACO) in terms of accuracy and time consumption, Regarding the problem, it can be solved with the number of cities, that is 6 to 343. The B&B method has the capability of resolving problems with the limitation of 22 stations. However, between ACO and EDCM, which can resolve problems for 343 stations. It found that the EDCM provides better value than ACO with an average of 1.31% and the time consumption of 55.00%.