mailto:uumlib@uum.edu.my 24x7 Service; AnyTime; AnyWhere

A comparative study of heuristic methods to solve Traveling Salesman Problem (TPS)

Lim, Yai Fung and Hong, Pei Yee and Ramli, Razamin and Khalid, Ruzelan (2011) A comparative study of heuristic methods to solve Traveling Salesman Problem (TPS). Project Report. Universiti Utara Malaysia. (Unpublished)

[thumbnail of Lim.pdf] PDF
Restricted to Registered users only

Download (1MB)
[thumbnail of 1.LIM YAI FUNG.pdf]
Preview
PDF
Download (1MB) | Preview

Abstract

Traveling Salesman Problem (TSP) is a famous problem in combinatorial optimization. The objective of the TSP is to find the shortest path that reaches all the cities which are interconnected with each other by straight lines.The symmetric TSP is used and the distance between two cities is calculated by using Euclidean equation.In this study, three heuristic methods, namely simulated annealing (SA), tabu search (TS) and reactive tabu search (RTS) are used to solve TSP.SA is a generic probabilistic meta-algorithm for the global optimization problem and TS is a meta-heuristic search technique that guides a local search procedure to explore the solution space beyond local optimality. RTS is an improved method of TS and it dynamically adjusts tabu list size based on how the search is performed.The performance of SA, TS and RTS algorithms in solving TSP with different size of problems are evaluated by using empirical testing, benchmarking solution and simple probabilistic analysis. The implementations of the three methods to solve TSP show that the RTS algorithm provides a better solution in terms of minimizing the objective function while SA algorithm is less time consuming in solving problem with large number of cities.In conclusion, RTS is more effective in producing good quality solution and on the other hand, SA may be used to obtain instant results.

Item Type: Monograph (Project Report)
Uncontrolled Keywords: Traveling salesman problem; Simulated annealing; Tabu search; Reactive tabu search; Combinatorial optimization
Subjects: Q Science > QA Mathematics > QA76 Computer software
Divisions: College of Arts and Sciences
Depositing User: Mdm. Yai Fung Lim
Date Deposited: 13 Mar 2013 06:30
Last Modified: 06 Jul 2014 04:42
URI: https://repo.uum.edu.my/id/eprint/7345

Actions (login required)

View Item View Item