1. UKM Learning and Research Repository
2. Master Thesis / Tesis Master
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Decision support tool based on improved water flow-like algorithm for the travelling salesman problem
Authors:	Wu Diyi (P68508)
Supervisor:	Suhaila Zainudin, Dr.
Keywords:	Problem solving -- Data processing Decision support systems Computer programming Universiti Kebangsaan Malaysia -- Dissertations Dissertations, Academic -- Malaysia
Issue Date:	28-May-2015
Description:	Decision Support Tools (DST) have been applied to solve complex problems using metaheuristic algorithms. The Travelling Salesman Problem (TSP) aims to find the shortest route for travelling, where all cities must be visited once. TSP is a well know complex problem categorized as a combinatorial optimization problem (COP). TSP is one of the issues that occur in areas such as business, transportation, medical, engineering, computer and networking. The current trend is towards rich TSP or related models that can be used in commercial Decision Support Tools (DST) in order to reduce transport costs and optimize the route. Metaheuristics are well-known techniques that produce good TSP solutions. Recently, many metaheuristics and its improvements such as 3-opt and 4-opt achieved success in COP. However, there is still room for improvement to get the best solution within a reasonable period of time, especially for large-size of data. On the other hand, the Water flow-like algorithm (WFA) is a relatively new algorithm that has shown good solutions for TSP (WFA-TSP) and is comparable to the state of the art results. A previous research using 2-opt for WFA-TSP (WFA-TSP-2opt) has shown promising performance. Therefore, this research aims to improve WFA-TSP with 3-opt (WFA-TSP-3opt) and 4-opt (WFA-TSP-4opt) respectively. A TSP decision support tool has been developed that allows the user to visualize their TSP solution and its performance using the proposed algorithm. The experiments were conducted using the standard TSP dataset (TSPLIB) containing up to 3795 cities. The experimental results show that WFA-TSP-3opt has improved accuracy in comparison with WFA-TSP-2opt by up to 0.61%. On the other hand, WFA-TSP-4opt improved the accuracy of WFA-TSP-3opt by up to 1.06%. The computation time and relations between city size reveal WFA-TSP-3opt and WFA-TSP-4opt represents as time=k*n. The DST for TSP evaluations through usability test was indicate that proposed system was usable. In conclusion, the TSP decision support tool is able to suggest the shortest solution and enable users to visualize the proposed route.,Master of Management Information System
Pages:	102
Call Number:	QA63.W835 2015 3 tesis
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.