A simple multi-wave algorithm for the uncapacitated facility location problem

作     者：Fred GLOVER Said HANAFI Oualid GUEMRI Igor CREVITS 

作者机构：Leeds School of BusinessUniversity of ColoradoBoulderCO 80309-0419USA LAMIHCNRS UMR 8201Université de ValenciennesFrance 

出 版 物：《Frontiers of Engineering Management》 (工程管理前沿（英文版）)

年 卷 期：2018年第5卷第4期

页      面：451-465页

学科分类：07[理学] 08[工学] 

基　　金：funded by ELSAT 2020 project which is cofinanced by the European Union with the European Regional Development Fund the France state and the Hauts de France Region Council 

主　　题：discrete optimization UFLP multi-wave optimization strategic oscillation tabu search 

摘      要：The multi-wave algorithm(Glover, 2016)integrates tabu search and strategic oscillation utilizing repeated waves(nested iterations) of constructive search or neighborhood search. We propose a simple multi-wave algorithm for solving the Uncapacitated Facility Location Problem(UFLP) to minimize the combined costs of selecting facilities to be opened and of assigning each customer to an opened facility in order to meet the customers demands. The objective is to minimize the overall cost including the costs of opening facilities and the costs of allocations. Our experimental tests on a standard set of benchmarks for this widely-studied class of problems show that our algorithm outperforms all previous methods.