Decomposition method for a capacitated single-vehicle covering tour problem with intermediate facilities

We consider a waste collection problem with intermediate disposal facilities to accommodate the usage of smaller, but more sustainable vehicles, with less capacity than the traditional waste collection trucks. The optimization problem consists in determining the locations to place the collection points and the routes of a capacitated collection vehicle that visits these locations. We first present a mixed-integer linear programming formulation that exploits the sparsity of the road network. To efficiently solve practical instances, we propose a solution method that decomposes the problem into a set covering problem to select the locations and a capacitated vehicle routing problem with intermediate facilities to determine the routes and price the set covering solution. We apply column generation to solve this routing problem and present a novel approach for the set covering problem that exploits the properties of the problem to efficiently find a set cover by using a graph theoretical approach. We compare our method with the set construction method presented in a previous work and the direct resolution of the MILP formulation by a state-of-the-art commercial solver. Computational experiments on instances derived from real-life data confirm the difficulty of our problem and show the superior performance of the developed decomposition method with respect to the number of best solutions and the average gaps to the best solution.