Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Theses >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/5254

Title: Metaheuristics for the waste collection vehicle routing problem with time windows
Authors: Benjamin, Aida Mauziah
Advisors: Beasley, JE
Keywords: Disposal facilities
Driver rest period
Tabu search
Variable neighbourhood search
Variable neighbourhood Tabu search
Publication Date: 2011
Publisher: Brunel University, School of Information Systems, Computing and Mathematics
Abstract: In this thesis there is a set of waste disposal facilities, a set of customers at which waste is collected and an unlimited number of homogeneous vehicles based at a single depot. Empty vehicles leave the depot and collect waste from customers, emptying themselves at the waste disposal facilities as and when necessary. Vehicles return to the depot empty. We take into consideration time windows associated with customers, disposal facilities and the depot. We also have a driver rest period. The problem is solved heuristically. A neighbour set is defined for each customer as the set of customers that are close, but with compatible time windows. This thesis uses six different procedures to obtain initial solutions for the problem. Then, the initial solutions from these procedures are improved in terms of the distance travelled using our phase 1 and phase 2 procedures, whereas we reduce the number of vehicles used using our vehicle reduction (VR) procedure. In a further attempt to improve the solutions three metaheuristic algorithms are presented, namely tabu search (TS), variable neighbourhood search (VNS) and variable neighbourhood tabu search (VNTS). Moreover, we present a modified disposal facility positioning (DFP), reverse order and change tracking procedures. Using all these procedures presented in the thesis, four solution procedures are reported for the two benchmark problem sets, namely waste collection vehicle routing problems with time windows (VRPTW) and multi-depot vehicle routing problem with inter-depot routes (MDVRPI). Our solutions for the waste collection VRPTW problems are compared with the solutions from Kim et al (2006), and our solutions for the MDVRPI problems are compared with Crevier et al (2007). Computational results for the waste collection VRPTW problems indicate that our algorithms produce better quality solutions than Kim et al (2006) in terms of both distance travelled and number of vehicles used. However for the MDVRPI problems, solutions from Crevier et al (2007) outperform our solutions.
Description: This thesis was submitted for the degree of Doctor of Philosophy and awarded by Brunel University.
Sponsorship: Ministry of Higher Education, Malaysia
URI: http://bura.brunel.ac.uk/handle/2438/5254
Appears in Collections:Mathematical Science
Dept of Mathematics Theses

Files in This Item:

File Description SizeFormat
FulltextThesis.pdf1.04 MBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.