针对客户不兼容的设施选址问题，提出改进的局部搜索算法，性能超越现有方法。
An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers
- 设计三种混合使用的破坏算子，结合精确求解器修复
- 在所有基准实例上均找到新最优解，优于现有元启发式方法
- 适合解决含冲突约束的实际设施选址问题
本文研究一种新型带容量限制的设施选址问题，考虑客户间存在的不相容关系——某些客户对不能由同一设施服务。该设定适用于存在危险品或竞争性客户的实际场景。为此，提出一种增强型大邻域搜索（LNS）算法：在框架内引入三种不同破坏算子并以混合方式组合，并在修复阶段使用精确求解器。通过实验分析验证了各组件的有效性。结果表明，所提方法在所有可用基准实例上均优于现有最先进元启发式算法，为全部实例提供了新的最优解。
原文摘要 · Abstract (English)
A new variant of the classic capacitated facility location problem, which considers incompatibilities between customers, has recently been introduced in the literature. This problem captures the situation where given pairs of customers cannot be served by the same facility. Such a feature is crucial for many practical cases of location problems, such as the presence of hazardous or polluting materials and contention between competing costumers. In this paper, we propose a Large Neighborhood Search (LNS) method to solve this problem. Within the framework of LNS, we introduce three different destroy operators, which are combined in a hybrid manner, and we use an exact solver in the repair phase. Different algorithmic components are investigated for the design of LNS. The experimental analysis shows that our new method outperforms existing state-of-the-art metaheuristics, providing new best solutions for all available benchmark instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。