Vehicle routing problems with different service constraints: A branch-and-cut-and-price algorithm

In this article, we consider a variation of the vehicle routing problem arising in the optimization of waste management systems. Constraints imposing adequate level of service to the citizens and even workload among the drivers make the problem challenging and ask for the design of specialized algorithmic approaches. We propose an exact optimization algorithm, in which dynamic generation of rows and columns is done in a branchand-bound framework; exact and heuristic algorithms are proposed for the pricing problem. Experimental tests on data-sets from the literature show that our algorithm outperforms previous ones and it is able to solve instances of realistic size to proven optimality in reasonable computing time.