Technical Summary: A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem

Problem Definition

The paper addresses the Family Capacitated Vehicle Routing Problem (F-CVRP), a generalization of the Family Traveling Salesman Problem (FTSP) and the classic Capacitated Vehicle Routing Problem (CVRP). In the F-CVRP, a homogeneous fleet of $K$ vehicles with capacity $Q$ departs from a single depot to serve a set of customers partitioned into families. Unlike the standard CVRP where every customer must be visited, the F-CVRP requires that a specific number of members ($v_l$) from each family $l$ be visited, while the remaining members of that family may be left unvisited. The objective is to minimize the total routing cost while respecting vehicle capacity constraints and fulfilling the exact visit requirements for each family.

As problem instances scale, exact methods become computationally prohibitive. Consequently, the paper focuses on developing a fast, high-quality heuristic capable of delivering solutions within tight time budgets, serving both as a standalone solver and as a provider of primal bounds for exact frameworks.

Methodology: The ILS+SP Hybrid Metaheuristic

The authors propose ILS+SP, a hybrid metaheuristic that combines an Iterated Local Search (ILS) framework with a Set Partitioning (SP) post-optimization phase. The algorithm operates as follows:

1. Iterated Local Search (ILS) Core

The search is driven by an ILS framework that maintains a pool of routes ($P$) and tracks the best feasible solution found ($s^*$).

• Initial Solution: Generated via a Best Parallel Insertion (BPI) heuristic, constructing $K$ routes by iteratively inserting customers to minimize cost increases, ensuring family visit counts are met.
• Local Search (RVND): The local search employs a Random Variable Neighborhood Descent (RVND) strategy. It explores a portfolio of nine neighborhoods:
  • Inter-route (5): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
  • Intra-route (3): Exchange, Reinsertion, Or-opt2.
  • Specialized (1): MemberRelocate, a problem-specific operator that removes a visited customer and inserts a non-visited member of the same family at the best position across all routes.
  • All neighborhoods preserve the structural constraints of family visit counts and the number of active routes ($K$).
• Acceptance Criterion: Unlike standard local search, the algorithm accepts worsening moves based on a Simulated Annealing (SA) criterion with a time-driven cooling schedule. This allows the search to escape local minima.
• Perturbation: To diversify the search, the algorithm applies one of three random perturbations (RandomSwap, RandomShift, or RandomMemberRelocate) to the current solution before re-entering the local search.
• Penalty Handling: Capacity violations are handled via a dynamic penalty coefficient ($\theta$) in the objective function, which is adjusted based on the feasibility of the current solution to guide the search toward feasible regions.

2. Set Partitioning (SP) Post-Optimization

Upon exhausting the time budget, the algorithm performs a final optimization step. It formulates a Set Partitioning problem over the pool of capacity-feasible routes ($P$) collected during the entire search process.

• The SP model selects a subset of routes to minimize total cost while satisfying family visit requirements and using exactly $K$ routes.
• Since the pool $P$ contains the routes composing the best solution found so far ($s^*$), the optimal solution to the SP is guaranteed to be at least as good as $s^*$.

Key Contributions

The paper highlights four primary contributions distinguishing this work from the existing state-of-the-art (specifically the ILS by Bernardino and Paias, 2024):

1. Hybridization with Set Partitioning: The introduction of an SP post-optimization phase to re-optimize the route pool, a matheuristic component absent in previous approaches.
2. Enhanced Local Search: The implementation of the MemberRelocate neighborhood, which optimally inserts non-visited family members into the best position across all routes, rather than simply swapping them in place.
3. Randomized Neighborhood Exploration: The use of RVND to randomize the order of neighborhood exploration, contrasting with the fixed order used in prior literature.
4. Simulated Annealing Acceptance: The adoption of an SA criterion to accept worsening solutions, replacing the strict improvement-only acceptance of previous methods, thereby improving the balance between intensification and diversification.

Computational Results

The authors evaluated ILS+SP on two benchmark sets:

1. Standard Benchmark (144 instances): Derived from the Augerat et al. (1995) set, containing instances with more than 50 customers.
   • Performance: The method won or tied on every instance against the state-of-the-art heuristic of Bernardino and Paias (2024).
   • Gap Reduction: The average gap to the Best Known Solution (BKS) was reduced from 1.84% (previous best) to 0.01%.
2. Scalability Benchmark (120 instances): A new set of larger instances (up to 142 customers) derived from the CVRP Set X (Uchoa et al., 2017).
   • Performance: The algorithm achieved an average gap of 0.47% with an average running time of 37 seconds, demonstrating scalability to larger problem sizes.

Significance and Claims

The paper positions ILS+SP as a robust and scalable solution for the F-CVRP. The authors claim that by integrating a matheuristic post-optimization (SP) with a sophisticated ILS framework featuring problem-specific neighborhoods and SA acceptance, the method significantly outperforms existing heuristics. The results suggest that the approach is not only capable of matching or improving upon the best-known solutions for established benchmarks but also scales effectively to larger, more complex instances, making it a valuable tool for both standalone application and integration into exact solution frameworks.