Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities

• Describes and motivates a generalized and practically inspired recyclable waste collection problem.
• Develops an MILP with valid inequalities as well as a multiple neighborhood search heuristic.
• Confirms the significant added value of the valid inequalities in the MILP formulation.
• Evaluates the heuristic and its components against the solutions of the MILP, benchmark instances, and real-world data.
• Highlights and analyzes the potential cost savings from the flexible assignment of destination depots.

We consider a complex recyclable waste collection problem that extends the class of vehicle routing problems with intermediate facilities by integrating a heterogeneous fixed fleet and a flexible assignment of destination depots. Several additional side constraints, such as a mandated break period contingent on tour start time, multiple vehicle capacities, and site dependencies are also included. This specific problem was inspired by a real-world application and does not appear in the literature. It is modeled as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, state-of-the-art solvers are only able to tackle instances of small to medium size. To solve realistic instances, we propose a multiple neighborhood search heuristic capable of systematically treating all problem features and general enough to respond to the varying characteristics of the case study regions for which it is intended. The results show that the heuristic achieves optimality on small instances, exhibits competitive performance in comparison to state-of-the-art solution methods for special cases of our problem, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing a flexible depot assignment. The data from the state of practice comes from a company in the waste collection industry in Geneva, Switzerland.