We propose GenericILS, a general-purpose heuristic framework for generating high-quality upper bounds for Vehicle Routing Problems whose pricing subproblems are modeled, in column-generation-based exact algorithms, as resource-constrained shortest path problems described through Resource Extension Functions (REFs), the standard device for encoding constraints in branch-and-price algorithms. GenericILS reuses REFs implemented for the exact method, without a problem-specific heuristic, illustrated on risk-constrained, simultaneous pickup and delivery, multi-depot, and heterogeneous-fleet variants. The search engine, a Nested Iterated Local Search, handles infeasibility via a lightweight, problem-agnostic penalty estimated from the number of infeasible arcs, evaluated in constant time using forward and backward label structures built in linear time and space, improving on prior quadratic schemes. Experiments on four VRP variants and twelve benchmark sets show best-solution gaps below 0.9% on Branch-Cut-and-Price-relevant instances under a matched time budget, falling to at or below 0.12\% under a tenfold larger budget. An open-source implementation is available at https://github.com/brunomattos1/GenericILS