Tactical waste collection: column generation and mixed integer programming based heuristics

Environmental considerations and corresponding legislation cause a shift from waste management to materials management, requiring efficient collection of these flows. This paper develops a model for building tactical waste collection schemes in which a set of capacitated vehicles visits a set of customers during a given time period. Each vehicle must visit the disposal facility to discharge the waste after each customer visit. This is motivated by the fact that the waste of each customer has to be weighed at the disposal facility. The goal is to find a set of routes for each vehicle that satisfy both the demand and the frequency constraints and minimize the total cost. Since a state-of-the-art solver could not find a solution with a reasonable gap within an acceptable time limit, a column generation and a mixed integer programming-based heuristic are proposed. While the mixed integer programming-based heuristic outperforms the column generation heuristic in terms of solution quality, the lower bound provided by column generation allows to prove the small optimality gaps of the solutions obtained. Moreover, by applying both heuristics on instances derived from real-life data, they proved to be capable of finding good quality solutions in small computation times.