A hybrid metaheuristic for the family capacitated vehicle routing problem

Full abstract

Read the full abstract

Abstract The Family Traveling Salesman Problem (FTSP) seeks a minimum-cost tour from a depot that visits a prescribed number of members of each customer family. This paper studies the Family Capacitated Vehicle Routing Problem (F-CVRP), a generalization of the FTSP in which customers carry demands and are served by a homogeneous fleet of capacitated vehicles, and proposes a hybrid metaheuristic for it. The method, named ILS+SP, couples an Iterated Local Search (ILS), which embeds a Random Variable Neighborhood Descent (RVND) over classical and problem-specific neighborhoods and accepts worsening moves through a Simulated-Annealing criterion, with a Set Partitioning (SP) post-optimization over the pool of routes collected during the search. On 144 large benchmark instances with more than 50 nodes, the metaheuristic wins or ties on every instance against the state-of-the-art heuristic of the literature, reducing the average gap to the best known solution from 1.84 to 0.01%. On a new benchmark of 120 larger instances with up to 142 customers, it attains an average gap of $$0.47\%$$ 0.47 % to the best solutions found across all our runs, within an average total running time of 37 s (a 20-second ILS budget plus the Set Partitioning post-optimization), showing that the method scales to these instance sizes in terms of running time.