Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities

In this problem 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. A procedure that attempts to fully utilise a vehicle is used to obtain an initial solution, with this initial solution being improved using an interchange procedure. We present two metaheuristic algorithms using tabu search and variable neighbourhood search that are based around the neighbour sets. We also present a metaheuristic based on variable neighbourhood tabu search, where the variable neighbourhood is searched via tabu search. Computational results are presented for publicly available waste collection problems involving up to 2092 customers and 19 waste disposal facilities, which indicate that our algorithms produce better quality solutions than previous work presented in the literature. (C) 2010 Elsevier Ltd. All rights reserved.