Lim, Yai-Fung and Hong, Pei Yee and Ramli, Razamin and Khalid, Ruzelan and Baten, Md Azizul (2016) Performance evaluation of heuristic methods in solving symmetric travelling salesman problems. Journal of Artificial Intelligence, 9 (1). pp. 12-22. ISSN 1994-5450

PDF Restricted to Registered users only Download (219kB) | Request a copy

Abstract

Background and Objective: The Travelling Salesman Problem (TSP) is a challenging problem in combinatorial optimization whose main purpose is to find the shortest path reaching all interconnected cities by straight lines.In spite of many available heuristic methods for solving TSPs, no attempts have been made to evaluate and compare their performances. The purpose of this study is to carry out a comparative evaluation study on Simulated Annealing (SA) and several variation of Tabu Search (TS).Materials and Method: This study considers four heuristic methods, i.e., Simulated Annealing (SA), conventional Tabu Search (TS), Improved Tabu Search (ITS) and modified Reactive Tabu Search (RTS) to solve symmetric TSPs.The algorithms were tested on five chosen benchmark problems. Their performances were compared and the appropriate algorithm for solving TSPs was then identified. The solution quality was evaluated using empirical testing, benchmark solutions and probabilistic analyses. Results: The analysis of computational results showed that the modified RTS algorithm provided a better solution quality in terms of minimizing the objective function of TSPs, while the SA algorithm was useful for obtaining instant solutions for TSPs with a large number of cities. The modified RTS algorithm also performed better compared to the existing heuristic methods. Conclusion: This study has explored the most effective heuristic method for solving TSPs based on the intended solution quality. The algorithms proposed in this study should be considered in solving symmetric travelling salesman problems.

Item Type:	Article
Uncontrolled Keywords:	Traveling salesman problem, heuristic method, simulated annealing, tabu search, combinatorial optimization
Subjects:	Q Science > QA Mathematics
Divisions:	School of Quantitative Sciences
Depositing User:	Prof. Dr. Razamin Ramli
Date Deposited:	15 Nov 2016 07:45
Last Modified:	07 Dec 2016 02:11
URI:	https://repo.uum.edu.my/id/eprint/19622

Actions (login required)

View Item