A capacitated multi-vehicle covering tour problem with intermediate facilities for waste collection

We consider a waste collection problem which consists in identifying locations of collection sites that cover all residential buildings (set cover) and creating collection routes with intermediate facilities for a vehicle at minimum total cost. We propose a mixed-integer linear programming (MILP) formulation that exploits the sparsity of the road network. To efficiently solve practical instances, we decompose the problem as follows: we solve a minimum clique covering problem on chordal graphs to identify the set covers and propose a column generation approach to build the routes for a given set cover.