A special VRP arising in the optimization of waste disposal: a real case

We address a particular pick-up and delivery vehicle routing problem arising in the collection and disposal of bulky recyclable waste. Containers of different types, used to collect different waste materials, once full, must be picked-up to be emptied at suitable disposal plants and replaced by empty containers alike. All requests must be served and routes are subject to a maximum duration constraint. Minimizing the number of vehicles is the main objective, while minimizing the total route duration is a secondary objective. The problem belongs to the class of Rollon-Rolloff Vehicle Routing Problems (RR-VRPs) though some characteristics of the case study as the free circulation of containers and the limited availability of spare containers, allow us to exploit them in the solution approach. We formalize the problem as a special VRP on a bipartite graph, we analyze its structure and we compare it to similar problems emphasizing the impact of limited spare containers. Moreover we propose a neighborhood based metaheuristic which alternatively switches from one objective to the other along the search path, and periodically destroys and rebuilds parts of the solution. The main algorithm components are experimentally evaluated on real and realistic instances, the largest of which fail to be solved by a MILP solver. We are increasingly competitive with the solver as the instance size increases, especially regarding fleet size. In addition the algorithm is applied to the benchmark instances for the RR-VRP.