A Benders Decomposition Approach for a Capacitated Multi-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 collecting 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 Benders decomposition approach in which a set covering problem to select the collection points is solved in the master problem and a capacitated vehicle routing problem with intermediate facilities to determine the routes and price the set covering solution is solved in the subproblem. We show a way to derive valid Benders cuts when solving the Benders subproblem with column generation and propose a heuristic Benders approach that provides better solutions for larger instances and approximated lower bounds to assess the quality of the obtained solutions.