•We introduce an RVRP where the last-mile delivery of some demands can be outsourced.•We propose construction and improvement heuristics handling outsourcing decisions.•The routes include the driving and rest periods according to European regulations.•We solve 60 artificial instances using our algorithms in classic metaheuristics.•The impact of the construction procedure and the outsourcing decisions are evaluated. This paper addresses a Rich Vehicle Routing Problem (RVRP) characterized by the following attributes: long-haul transport, driver hours regulation, incompatibility among goods, multiple depots and pickup locations, heterogeneous vehicles, time windows, and outsourcing decisions for last-mile delivery. Addressing the latter aspect is especially challenging, since it requires substantial changes in the algorithms for generating initial feasible solutions (construction heuristic) and for modifying existing solutions (improvement heuristics). Our work develops new heuristics adapted to the above attributes, and evaluates their performance in combination with common solving metaheuristics. We also assess the impact and the cost-effectiveness of the outsourcing attribute.