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

Title:	Bee colony optimisation algorithms for vehicle routing problems with time windows
Authors:	Sana Ibrahim Ali Jawarneh (P67833)
Supervisor:	Salwani Abdullah, Prof. Dr.
Keywords:	Vehicle routing Bee colony optimisation Algorithms Dissertations, Academic -- Malaysia
Issue Date:	Aug-2016
Description:	The vehicle routing problems with time windows (VRPTW) is an NP-hard problem. Both types of VRPTW, namely, static (S-VRPTW) and dynamic (D-VRPTW), aim to determine the optimal route used by a group of vehicles when serving a group of customers within a predefined time interval, called time window. The objective in VRPTW is to minimise overall transportation cost. Various heuristic and metaheuristic approaches have been developed in literature to produce high-quality solutions for this problem because of its high complication rate and extensive implementation in real-life applications. This research investigates the use of bee colony optimisation (BCO) as a population-based algorithm in S-VRPTW and D-VRPTW. To date, most approaches presented in literature use off-line parameter initialisation (i.e., parameters are initialised with fixed values), wherein the optimal values of parameters depend on various instances to be solved. The effectiveness of a parameter setting may change during optimisation. Thus, an online (self-adaptive) parameter tuning strategy is proposed in this research to adaptively tune a parameter during optimisation. The literature review also indicates that only a few researchers have focused on generating the initial population. This process considers diversification and is essential in the performance of population-based algorithms. Consequently, this research adopts the sequential insertion heuristic (SIH) to generate diverse initial populations to prevent premature convergence. Population-based algorithms have several limitations, such as being more concerned with exploration than with exploitation. Therefore, this research presents the hybridisation of the BCO algorithm with two local search algorithms, namely, simulated annealing (SA) and late acceptance hill climbing (LAHC), to achieve a balance between exploration and exploitation. This balance leads the hybrid algorithms to generate solutions with improved quality. Solving D-VRPTW has received limited attention in literature, although this problem is essential in real-life applications that require new techniques. The explicit memory (EM) mechanism has been used to track new changes dynamically and to reuse information from previous searches to adapt to changes in the problem instead of solving the problem from scratch. Experimental results demonstrate that the self-adaptive parameter tuning strategy integrated into the BCO algorithm (Self-Adaptive BCO) helps improve the quality of the solutions. Integrating SIH into the Self-Adaptive BCO (Self-Adaptive BCO-SIH) further enhances the solutions by generating diverse initial populations. The comparison between the proposed hybridisation approaches shows that the Self-Adaptive BCO-SIH with LAHC outperforms the Self-Adaptive BCO-SIH with SA. In D-VRPTW, using EM mechanism addresses the issue of changing information during optimisation. Integrating EM mechanism into the hybrid approach provides new best results compared with the established best results in literature.,Certification of Master's/Doctoral Thesis" is not available
Pages:	200
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.