An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

Technical Summary: An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

Problem Definition
This paper addresses the Multi-Source Capacitated Facility Location Problem with Customer Incompatibilities (MS-CFLP-CI). This variant extends the classic MS-CFLP by introducing a set of incompatible customer pairs ($I$) that cannot be served by the same facility. The problem involves determining which facilities to open (incurring opening costs $f_j$) and how to distribute customer demand ($d_i$) among open facilities (incurring shipping costs $c_{ij}$) to minimize total cost. The solution must satisfy facility capacity constraints ($s_j$), fully meet customer demand, and ensure that no two incompatible customers share a facility. The presence of incompatibility constraints renders the subproblem of finding optimal supply from open facilities NP-hard, even when the set of open facilities is fixed.

Methodology
The authors propose a Large Neighborhood Search (LNS) framework to solve MS-CFLP-CI. The core of the approach involves iteratively destroying a portion of the current solution and repairing it using an exact Mixed Integer Programming (MIP) solver (Gurobi).

• Solution Representation: Solutions are represented as matrices of shipped quantities, supported by auxiliary data structures tracking open/closed facilities and assigned customers.
• Initial Solution: A heuristic constructs a starting solution by sorting facilities by opening cost, selecting enough to meet total demand, and adding a specific number of extra facilities ($k=5$) to handle incompatibility constraints. Customers are assigned based on a uniform strategy.
• Destroy Operators: The paper introduces three novel destroy operators designed specifically for the incompatibility constraints:
  1. Cheapest Facilities (CF): Selects a random facility and its customers, then identifies other open facilities that offer the lowest average shipping cost for that specific customer group.
  2. Hybrid Customers (HC): A recombination of two strategies. It selects a random facility and its customers, then identifies "cheapest customers" (those with low shipping costs to the facility) and "expensive customers" (those with high shipping costs). It then selects additional facilities that offer the best service for these specific customer subsets.
  3. Closed Facilities: Both random closed facilities and those with the minimum cost measure ($Q_g$) are included in the sub-problem to explore opening new facilities.
• Repair Operator: The sub-problem defined by the destroyed elements is solved exactly using Gurobi. To manage computational time, the repair phase includes a constraint limiting the number of newly opened facilities to at most two more than currently involved in the sub-problem. A cutoff value (the current sub-problem cost) is provided to the solver to accelerate convergence.
• Configuration and Tuning: The authors employ the irace tool for feature-based parameter tuning, adjusting parameters such as sub-problem size ($\nu$) based on instance scale (specifically distinguishing between instances with $\le 700$ and $> 700$ facilities). The final algorithm, termed $LNS_{init,accept}$, combines the proposed destroy operators with an improved initial solution heuristic and an acceptance criterion that allows solutions with equal cost to be accepted, facilitating escape from local optima.

Key Contributions

• Novel Algorithmic Framework: This is the first application of Large Neighborhood Search to the MS-CFLP-CI problem.
• Specialized Operators: The design of destroy operators (CF and HC) that explicitly account for incompatibility constraints, moving beyond standard facility location heuristics.
• Hybrid Exact/Heuristic Repair: The integration of an exact MIP solver within the repair phase, optimized with specific constraints to balance solution quality and runtime.
• Rigorous Analysis: A comprehensive ablation study and statistical analysis (using Friedman and Nemenyi tests) to evaluate the impact of individual components (initialization, acceptance criteria, adaptive weights).
• Extensive Benchmarking: Evaluation on two large-scale datasets (wlp and cflp-ci) containing up to 3,000 facilities and 8,000 customers.

Experimental Results
The proposed $LNS_{init,accept}$ method was tested against state-of-the-art metaheuristics, including MineReduce-based Multi-Start Iterated Local Search (MR-MS-ILS), GRASP, Permutation-coded Evolutionary Algorithm (PcEA), Multi-start Greedy (MG), and Simulated Annealing (SA).

• Performance: The proposed method significantly outperformed all existing methods on both datasets under two different time limits ($10\sqrt{m}$ and $m$ seconds).
• New Best Solutions: The approach found new best solutions for all 80 instances across both datasets.
• Statistical Significance: Statistical tests confirmed that the improvements over the previous best method (SA) are statistically significant.
• Scalability: While exact solvers (Gurobi/CPLEX) could only solve instances up to 150 facilities to optimality within reasonable time, the LNS approach effectively handled instances with up to 3,000 facilities.
• Gap Reduction: For the wlp dataset, the method achieved gap improvements ranging from -0.68% to -1.84% over the best-known solutions. For the cflp-ci dataset, improvements ranged from -0.46% to -2.09%.

Significance and Claims
The authors claim that their method represents the current state-of-the-art for the MS-CFLP-CI problem. The significance of the work lies in its ability to handle the computational complexity introduced by customer incompatibilities, which previous metaheuristics struggled to optimize fully, particularly for larger instances. The paper asserts that the combination of novel destroy operators, an exact repair phase, and specific algorithmic tuning allows the method to explore mid-sized neighborhoods effectively, finding superior solutions where SA and other methods stagnate. The authors modestly note that while their method is currently the best, future work could involve Instance Space Analysis to better understand instance hardness and extending the approach to other facility location variants.