An ILS-RVND-SP Metaheuristic for the Capacitated Vehicle Routing Problem with Family Constraints

This work addresses the Capacitated Vehicle Routing Problem with Family Constraints (F-CVRP), an extension of the Traveling Salesman Problem with Families (FTSP) in which a homogeneous fleet of capacitated vehicles must serve a set of customers partitioned into families, each with a minimum quota of visits to be fulfilled. To address this problem, a metaheuristic called ILS-RVND-SP is proposed, structured around an Iterated Local Search with Randomized Variable Neighborhood Descent and refinement by Set Partitioning. An acceptance criterion using Simulated Annealing is adopted to broaden the search diversification. Computational experiments demonstrate that the proposed method consistently outperforms previously published heuristics, reducing the total cost of solutions by up to 4.73% on average and by up to 4.30% in the best solution, with significantly shorter execution times than those reported in the literature.