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%.

 


Refbacks

  • There are currently no refbacks.


Copyright 2020 by the Mathematical Association of Thailand.

All rights reserve. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission of the Mathematical Association of Thailand.

|ISSN 1686-0209|