The vehicle routing problem with backhauls integrates decisions on product delivery with decisions on the collection of returnable items. In this paper, we analyze a scenario in which collection of items is optional—but subject to a penalty cost. Both transportation costs and penalties associated with non-collecting decisions are considered. A mixed-integer linear model is proposed and solved for small instances. Also, a metaheuristic algorithm combining biased randomization techniques with iterated local search is introduced for larger instances. Our approach yields cost savings and is competitive when compared to other state-of-the-art approaches. © 2020, Sociedad de Estadística e Investigación Operativa.