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 origin and destination depot. 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 commercial solvers are only able to tackle instances of small to medium size. To solve realistic instances, we propose a local 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 random 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 assignment of origin and destination depot. The data from the state of practice comes from a recyclable waste collection company in Geneva, Switzerland.