Metaheuristics with disposal facility positioning for the waste collection VRP with time windows

This paper improves heuristic algorithms presented in Benjamin and Beasley (Comput Oper Res 37(12):2270-2280, 2010) for solving the waste collection vehicle routing problem with time windows, particularly the real life waste collection benchmark problems from Kim et al. (Comput Oper Res 33(12):3624-3642, 2006). These consist of ten test problems, involving up to 2,092 customers and 19 waste disposal facilities. The main difference between this paper and Benjamin and Beasley (Comput Oper Res 37(12):2270-2280, 2010) is that here we use a disposal facility positioning (DFP) procedure to evaluate routes for our algorithms. Since the problem involves multiple disposal facilities, the objective of DFP is to choose the best disposal facilities to go on the vehicle route. Computational results indicate that our algorithms with DFP produce substantially better quality routes than previous approaches in the literature.