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

Title:	Hybrid water flow-like algorithm for capacitated vehicle routing problem
Authors:	Mokhtar Massoud Mohammed Kerwad (P68219)
Supervisor:	Suhaila Zainudin, Dr.
Keywords:	Algorithm Vehicle routing problem
Issue Date:	24-Jan-2018
Description:	Capacitated Vehicle Routing Problem (CVRP) is widely studied with many applications in different domains. Nevertheless, CVRP still faced ongoing operational challenges. Population-based etaheuristics such as Genetic Algorithm (GA) and Ant Colony Optimization (ACO) have been proven as the most effective solution for CVRP due to its ability in solution diversification but still lacking on solution intensification. GA and ACO rely on a fixed number of solutions which restricts the solution search for a large data set. Therefore, these algorithms have been improved using appropriate searching strategies. Water Flow-like Algorithm (WFA) is a dynamic population-based metaheuristic that was successfully used to solve complex problems such as Bin- Packing Problem, Nurse Scheduling Problems, and Travelling Salesman Problem. WFA demonstrates self-adaptive and dynamic behavior in determining its population size and parameter settings during problem solving. WFA is able to balance between diversification and intensification capabilities for non-heavily constrained problems. It is made up of four components; flow splitting and moving, flow merging, water evaporation, and water precipitation. This research aims to propose WFA for solving CVRP by following three objectives. First, to propose a basic WFA for CVRP (WFACVRP), which consider suitable design strategy for solution representation, objective function calculation and iteration number parameter tuning. Second, to enhance WFA for CVRP by three constructive heuristics (random method, nearest neighbor and greedy randomized adaptive search procedure) embedded within precipitation operation to improve WFA exploration capabilities (IWFA-CVRP). Third, to enhance IWFA by hybridizing it with four single based methods (best improvement, first improvement, great deluge, and simulated annealing) to improve IWFA exploitation capability (HIWFA-CVRP). Hybridization between WFA and S-metaheuristics is determined to be effective and efficient in balancing solution diversification and ntensification to utilize the superiority of both categories and improve their weaknesses. The experiments were conducted using 55 CVRP benchmark datasets. Basic WFA achieved two best results out of 55 datasets with improved up to 74.5% compared with the stateof-the-art. IWFA obtained two best results out of 55 datasets, with improved up to 76.36% compared with the state-of-the-art. IWFA also scored 34 best results from 55 datasets compared to WFA. Furthermore, HIWFA with great deluge metaheuristic outperformed basic WFA and IWFA in 33 out of 55 datasets, and better than the state of the art in 15 out of 55 datasets, with improvement of 27.27% in term of solutions quality. This indicates that the modifications and the hybridization capabilities of WFA can achieve a balance between intensification and diversification. The result is an effective HIWFA that can be used as a good method for CVRP solution. The results indicate that the proposed algorithm provides competitive results compared with state of the art.,Certification of Master's/Doctoral Thesis" is not a available
Pages:	191
Call Number:	TL250.K437 2018 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.