Redirigiendo al acceso original de articulo en 21 segundos...
ARTÍCULO
TITULO

PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM

Chandra Agung    
Natalia Christine    

Resumen

The subject of this research is distance and time of several city tour problems which known as traveling salesman problem (tsp). The goal is to find out the gaps of distance and time between two types of optimization methods in traveling salesman problem: exact and approximate. Exact method yields optimal solution but spends more time when the number of cities is increasing and approximate method yields near optimal solution even optimal but spends less time than exact methods. The task in this study is to identify and formulate each algorithm for each method, then to run each algorithm with the same input and to get the research output: total distance, and the last to compare both methods: advantage and limitation.  Methods used are Brute Force (BF) and Branch and Bound (B&B) algorithms which are categorized as exact methods are compared with Artificial Bee Colony (ABC), Tabu Search (TS) and Simulated Annealing (SA) algorithms which are categorized as approximate methods or known as a heuristics method. These three approximate methods are chosen because they are effective algorithms, easy to implement and provide good solutions for combinatorial optimization problems. Exact and approximate algorithms are tested in several sizes of city tour problems: 6, 9, 10, 16, 17, 25, 42, and 58 cities. 17, 42 and 58 cities are derived from tsplib: a library of sample instances for tsp; and others are taken from big cities in Java (West, Central, East) island. All of the algorithms are run by MATLAB program. The results show that exact method is better in time performance for problem size less than 25 cities and both exact and approximate methods yield optimal solution. For problem sizes that have more than 25 cities, approximate method ? Artificial Bee Colony (ABC) yields better time which is approximately 37% less than exact and deviates 0.0197% for distance from exact method. The conclusion is to apply exact method for problem size that is less than 25 cities and approximate method for problem size that is more than 25 cities. The gap of time will be increasing between two methods when sample size becomes larger.

 Artículos similares

       
 
Abhijit Bhowmik, Noorhuzaimi Mohd Noor, Md. Saef Ullah Miah, Md. Mazid-Ul-Haque, Debajyoti Karmaker     Pág. 200 - 213

 
Abba Mahmud, Stephen O. Ogunlana, W.T. Hong, Ibrahim Wuni Yahaya, Sani Rueben Akoh    
Qualitative data plays an important role in system dynamics (SD) modelling, particularly in model conceptualization. Among the various forms of data, information from the mental database of stakeholders is considered the most important which can be acces... ver más

 
Bamidele Michael Efuwape,Oluwabunmi Asake Efuwape     Pág. 24 - 34
Technology-enriched learning was integrated into the teaching of abstract concepts in electrical/electronic technology with investigation of its effects on students? academic performance and learning retention. A quasi-experimental design was adopted for... ver más
Revista: Invotec

 
Kesavan Manoharan, Pujitha Dissanayake, Chintha Pathirana, Dharsana Deegahawature, Renuka Silva    
This study primarily identifies the knowledge gaps that must be filled to apply conceptualised methods for rising and benchmarking productivity levels of various construction operational tasks. Accordingly, this study intended to evaluate labour producti... ver más

 
Jugal Pancholi, Dr. Ganesh Devkar    
The use of lean tools and techniques to reduce waste from the workflow has been prominently gaining popularity in the construction industry worldwide. Last Planner System (LPS) is one of such distinguished tools used by construction majors. Many research... ver más