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

Title:	An enhanced firework algorithm for solving capacitated vehicle routing problem
Authors:	Noora Hani AbdulMajeed (P62468)
Supervisor:	Masri Ayob, Assoc. Prof. Dr.
Keywords:	Enhanced firework algorithm Firework algorithm Capacitated vehicle Capacitated vehicle routing problem Transportation problems (Programming)
Issue Date:	29-Jan-2014
Description:	The capacitated vehicle routing (CVRP) is a challenging and an important optimization problem in the fields of transportation, distribution and logistics. CVRP is an NP-hard problem, which is difficult to find an optimal solution. Thus, many exact, heuristic and meta-heuristic approaches have been proposed to solve CVRP. However, for large instances, exact algorithms require considerable CPU time. Therefore, this thesis focuses on solving CVRP using a new meta-heuristic algorithm known as the firework algorithm (FA). Our aim is to investigate the capability of FA in solving CVRP by utilizing its advantages and addressing its shortcoming by integrating it with other mechanism. We select FA in this thesis due to its ability in dealing with many difficult optimization problems such as mathematical function, engineering and design problems. Furthermore, there is no existing work have utilized FA for solving CVRP. Firework algorithm mimics the explosion phenomenon in searching nearby the space of the solutions by generating a sparks around the solutions. Firstly, we apply the standard FA on CVRP using the suitable representation for CVRP. Although promising results have been obtained, FA faces the problem of fast convergence because most of the individual in the population is identical which will make the population of solutions converged too early which resulting in suboptimal solution. To address this weakness, we enhanced FA by incorporating a mutation operator with standard FA for the purpose of improving the exploration process. The proposed approaches are applied to solve 14 benchmark CVRP instances. The results show that the enhanced FA outperformed standard FA on seven instances, matched the best known results on seven instances and obtained new best for one instance out of 14. This reveals that adding the mutation operator in FA can improve the exploration process and subsequently enhance the performance of FA.,Master
Pages:	94
Call Number:	QA402.6 .N645 2014 3
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.