Please use this identifier to cite or link to this item:
https://ptsldigital.ukm.my/jspui/handle/123456789/513249Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.advisor | Masri Ayob, Prof. Dr. | |
| dc.contributor.author | Hamzah Ali Khalaf Alkhazaleh (P58723) | |
| dc.date.accessioned | 2023-10-16T04:34:59Z | - |
| dc.date.available | 2023-10-16T04:34:59Z | - |
| dc.date.issued | 2016-02-22 | |
| dc.identifier.other | ukmvital:83276 | |
| dc.identifier.uri | https://ptsldigital.ukm.my/jspui/handle/123456789/513249 | - |
| dc.description | This work focuses on Team Orienteering Problem (TOP) that is difficult to tackle for optimality. The TOP deals with maximizing the total score collected by all paths. Each path is constructed based on the number of selected locations that can be visited within time limit, where each location has different score. Scatter Search (SS) is one of the methods that is commonly used to solve complex problems. SS explores a search space of solutions systematically by evolving a small set of reference solutions. It has strategies for diversification (in diversification generation and subset generation methods); and intensification (in the improvement and updating method). However, all these methods are very time consuming. Therefore, this research aims to apply and enhance SS algorithm for solving TOP by reduce processing time and maintaining a good set of references solutions in terms of diversity and quality. TOP problem is chosen to test the performance of SS due to huge dataset that has variety of instances. The research begins with applying classical SS algorithm in solving TOP. Results show that classical SS algorithm is capable to solve the TOP but struggle with slow convergence and stuck in the local optima (no more updating on the reference set). To overcome this weakness, we improved SS algorithm (called ISS) by increasing the diversity of the initial solutions in the population pool by employing five common constructive heuristics in TOP. To speed up the search process, ISS utilizes four selection strategies in subset generation method: (1) randomly select two-parents, (2) randomly select multi-parents, (3) greedy selected two-parents, (4) roulette wheel selection. Moreover, ISS utilizes two strategies to update the references set pool in order to overcome the issues of slow convergence and local optima. These two strategies are: References set of quality solution-method, and Reference set queen bee-method. ISS algorithm obtained better results than classical SS algorithm in terms of solutions quality and computational time. For further enhancement of the intensification process in ISS, we hybridize ISS (called HISS) with four local search algorithms: steepest descent (SD), first improvement (FI), simulated annealing (SA), and great deluge (GD). Results demonstrate that the HISS-SD outperformed ISS, HISS-FI, HISS-SA, and HISS-GD. The proposed HISS-SD gained a competitive results in TOP, when compared to the best known methods in the scientific literature. This indicates that the modifications and the hybridization within SS to balance between intensification and diversification, end up with an effective HISS-SD framework that presents a promising approach for TOP as optimization problem in term of quality and 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 | Scatter search | |
| dc.subject | Algorithm | |
| dc.subject | Team Orienteering Problem | |
| dc.subject | Dissertations, Academic -- Malaysia | |
| dc.title | Enhanced scatter search algorithm for Team Orienteering Problem | |
| dc.type | Theses | |
| dc.format.pages | 239 | |
| Appears in Collections: | Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| ukmvital_83276+SOURCE1+SOURCE1.0.PDF Restricted Access | 210.58 kB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.