Hybrid Particle Swarm Optimization and Skewed Variable Neighborhood Search Techniques for the Generalized Max-Mean Dispersion Problem

When placing facilities such as warehouses, distribution centers, or public services (e.g., hospitals, fire stations), the objective is often to maximize the distance between selected facilities to ensure a wide service area and reduce redundancy. This is particularly important in areas where resource coverage must be spread evenly across a large geographical area. This paper focuses on this challenge by tackling the generalized max-mean dispersion problem with a novel hybrid optimization method. This method combines particle swarm optimization with skewed variable neighborhood search. It merges the global search capabilities of swarm-based optimization with the focused local search strengths of variable neighborhood search. The approach begins with a randomly generated population, refined through a greedy constructive procedure. A variable neighborhood descent strategy, employing diverse neighborhood operators and skewed local search techniques, is then applied to enhance the local search phase. This hybrid approach achieves a balance between global exploration and targeted local refinement, leading to improved solution quality and avoiding local optima. Experimental results illustrate that the proposed method significantly improves both solution quality and computational efficiency compared to existing techniques, achieving new lower bounds and matching the best-known solutions on other benchmark instances.