Water flow-like algorithm with simulated annealing for travelling salesman problem

Nasser Hamed Al Dhawi (P65675)

Please use this identifier to cite or link to this item: https://ptsldigital.ukm.my/jspui/handle/123456789/476343

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Zulaiha Ali Othman, Assoc. Prof. Dr.
dc.contributor.author	Nasser Hamed Al Dhawi (P65675)
dc.date.accessioned	2023-10-06T09:16:45Z	-
dc.date.available	2023-10-06T09:16:45Z	-
dc.date.issued	2015-09-21
dc.identifier.other	ukmvital:82206
dc.identifier.uri	https://ptsldigital.ukm.my/jspui/handle/123456789/476343	-
dc.description	Search problems in industry or scientific domains are NP-hard, and thus require optimal solutions. The Travelling Salesman Problem (TSP) is a search problem that aims to find the shortest route to visit a collection of cities. The search conditions are that each city must be visited exactly once, and the visit ends at the starting point. Based on the literature review, metaheuristics algorithms such as the Water Flow like Algorithm (WFA), have been utilized for solving NP-hard problems. WFA is self-adaptive, and behaves dynamically in setting the population size and parameters. The algorithm has the potential to improve by enhancing the exploration of the problem search space and less search exploration capability using a local search algorithm. Simulated Annealing (SA) is a popular single-population technique that improves the solution search exploration with less trapping in local optima. This study aims to propose a water flow-like algorithm with Simulated Annealing for TSP (WFA-SA-TSP), which improves the basic WFA-TSP with SA. The implemented (WFA-SA-TSP) used four different neighbourhood structures (swap, 2-opt, 3 –opt and 4-opt). The experiments were conducted using the eighteen TSP data set benchmark with the number of cities ranging from 50 to 3795. The experimental results and statistical test (t-Test) demonstrate that embedding SA with the basic WFA has significantly improved the solution quality when using swap, 2-opt, 3-opt and 4-opt neighbourhood structures. The WFA-SA-TSP with 4-opt has shown the best obtained results, which has improved the solution quality of the basic WFA-TSP by 2.18% without any improvement in the computation time.,Certification of Master's/Doctoral Thesis" is not available
dc.language.iso	eng
dc.publisher	UKM, Bangi
dc.relation	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat
dc.rights	UKM
dc.subject	Travelling salesman problem
dc.subject	Water flow-like algorithm
dc.subject	Dissertations, Academic -- Malaysia
dc.title	Water flow-like algorithm with simulated annealing for travelling salesman problem
dc.type	theses
dc.format.pages	71
dc.identifier.barcode	002319(2016)
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Files in This Item:

File	Description	Size	Format
ukmvital_82206+SOURCE1+SOURCE1.0.PDF Restricted Access		568.48 kB	Adobe PDF	View/Open

Show simple item record Recommend this item