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

Title:	Insertion based construction heuristic with cuckoo search metaheuristic for capacitated vehicle routing problem
Authors:	Mansour Alssager (P58730)
Supervisor:	Zulaiha Othman, Assoc. Prof. Dr.
Keywords:	Metaheuristic Cuckoo search Vehicle routing problem
Issue Date:	14-Feb-2017
Description:	Capacitated vehicle routing problem (CVRP) is a widely studied discrete heavily constraints combinatorial optimization problem with many applications and many operational challenges. Metaheuristics has been proven as the most effective solution methods for CVRP due to its ability to balance between exploration and exploitation, yet its performances attracted by premature convergence. Therefore none of these metaheuristic have been able to reach the optimal solution across all the instances. Two main stages affect the solving of CVRP as a whole methodology: initial solutions construction and iterative solution improvement. The constructive solution method aims to get fast quality solutions. This research aims to propose cheapest insertion heuristic (CIH) which is characterized as fast, simple to implement and easy to extend, by improving its initialisation criteria. Three initialisation criteria have been proposed by combining two criteria i.e., farthest with nearest, nearest with random, and farthest with random. On the other hand, various metaheuristics have been proposed as iterative methods. Recently, cuckoo search (CS) has obtained the best solution for travelling salesman problem, which motivates the study to propose the CS for CVRP. More importantly, CS categorized its abilities to balance for the exploration and exploitation capabilities for non-heavily constraints problems. However, various factors influence the performance of any metaheuristics which include the initial solution, metaheuristic parameter, neighbourhood structures, selection strategic and hybridization with other metaheuristic. Thus, this research aims to enhance the CS for solving CVRP by consider its (i) parameter setting using Taguchi method, (ii) Lévy flight associated with the twelve neighbourhood structures (ii) two acceptance criteria named as first and best (iv) three selection strategies which are tournament, rank and disruptive, which all attain to enhance the CS exploration capabilities. On other hand, the CS exploitation capabilities enhanced by (v) hybridizing with two single based methods known as simulated annealing and great deluge. The experiments are conducted using 16 standard benchmark instances of Chen. For the constructive methods, the experiment results show that the farthest and random initial criteria for the CIH shown as the best diversifying solution, with 70% faster with a bit less solution quality of 6.5% when compared to other constructive methods. While for the iterative method, the result shows 1% quality improvement of CS using Taguchi method, later enhanced by (best) sequence of neighbourhood structures and the (best) acceptance criteria named as neighbourhood enhanced CS (NE-CS), which is 15% faster when comparing to other basic start of the art methods with 3% less quality solution,. Later, the NE-CS is further improved using disruptive selection strategy named as (Dis-CS) with quality percentage improvements of 2.5%, with 14% slower in time. Furthermore, the Dis-CS is hybridized with simulated annealing metaheuristic named as (CS-SA), with 2.2% improvements in quality and 26% slower in time. The CS-SA is better in solutions quality for about 0.25% from the previous best state of art method; it is able to reach 12 out of 16 best known solutions with reasonable time. With such result that balanced between the exploration and the exportation of the proposed CS it can be concluded that the proposed CS-SA can be used as a good method for CVRP solution.,Certification of Master's/Doctoral Thesis" is not available
Pages:	188
Call Number:	T57.84.A399 2017 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.