A multi-exchange heuristic for the single-source capacitated facility location problem

• 成果类型: Article
• 署名作者: Ahuja, RK; Orlin, JB; Pallottino, S; Scaparra, MP; Scutellà, MG
• 署名单位: State University System of Florida; University of Florida; Massachusetts Institute of Technology (MIT); University of Pisa
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1030.0193
• 发表日期: 2004
• 页码: 749-760
• 关键词: location problems; large-scale optimization; neighborhood search; negative cycles

摘要

We present a very large-scale neighborhood (VLSN) search algorithm for the capacitated facility location problem with single-source constraints. The neighborhood structures are induced by customer multiexchanges and by facility moves. We consider both traditional single-customer multi-exchanges, detected on a suitably defined customer improvement graph, and more innovative multicustomer multi-exchanges, detected on a facility improvement graph dynamically built through the use of a greedy scheme. Computational results for some benchmark instances are reported that demonstrate the effectiveness of the approach for solving large-scale problems. A further test on real data involving an Italian factory is also presented.