PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM
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 o...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kharkiv National University of Radio Electronics
2021-03-01
|
| Series: | Сучасний стан наукових досліджень та технологій в промисловості |
| Subjects: | |
| Online Access: | https://itssi-journal.com/index.php/ittsi/article/view/261 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849407762796118016 |
|---|---|
| author | Chandra Agung Natalia Christine |
| author_facet | Chandra Agung Natalia Christine |
| author_sort | Chandra Agung |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a92f4d1bdde24967838f45c8a7183a91 |
| institution | Kabale University |
| issn | 2522-9818 2524-2296 |
| language | English |
| publishDate | 2021-03-01 |
| publisher | Kharkiv National University of Radio Electronics |
| record_format | Article |
| series | Сучасний стан наукових досліджень та технологій в промисловості |
| spelling | doaj-art-a92f4d1bdde24967838f45c8a7183a912025-08-20T03:35:57ZengKharkiv National University of Radio ElectronicsСучасний стан наукових досліджень та технологій в промисловості2522-98182524-22962021-03-011 (15)10.30837/ITSSI.2021.15.069PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEMChandra Agung0Natalia Christine1Universitas Mercu BuanaUniversitas Katolik Indonesia Atma Jaya JakartaThe 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.https://itssi-journal.com/index.php/ittsi/article/view/261traveling salesman problemoptimization methodexact methodapproximate methodsgaps |
| spellingShingle | Chandra Agung Natalia Christine PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM Сучасний стан наукових досліджень та технологій в промисловості traveling salesman problem optimization method exact method approximate methods gaps |
| title | PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM |
| title_full | PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM |
| title_fullStr | PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM |
| title_full_unstemmed | PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM |
| title_short | PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM |
| title_sort | performance analysis of optimization methods for solving traveling salesman problem |
| topic | traveling salesman problem optimization method exact method approximate methods gaps |
| url | https://itssi-journal.com/index.php/ittsi/article/view/261 |
| work_keys_str_mv | AT chandraagung performanceanalysisofoptimizationmethodsforsolvingtravelingsalesmanproblem AT nataliachristine performanceanalysisofoptimizationmethodsforsolvingtravelingsalesmanproblem |