大规模多设施Weber问题的改进Cooper算法

A MODIFIED COOPER ALGORITHM FOR LARGE-SCALE MULTI-SOURCE WEBER PROBLEM

多设施Weber问题（multi-source Weber problem，MWP）是设施选址中的重要模型之一，而Cooper算法是求解MWP最为常用的数值方法．Cooper算法包含选址步和分配步，两步交替进行直至达到局部最优解．本文对Cooper算法的选址步和分配步分别引入改进策略，提出改进Cooper算法：选址步中将Weiszfeld算法和adaptive Barzilai-Borwein（ABB）算法结合，提出收敛速度更快的ABB—Weiszfeld算法求解选址子问题；分配步中提出贪婪簇分割策略来处理退化设施，由此进一步提出具有更好性质的贪婪混合策略．数值实验表明本文提出的改进策略有效地提高了Cooper算法的计算效率，改进算法有着更好的数值表现．

The multi-source Weber problem （MWP） is a very important model in facility location and Cooper algorithm is the most well-used method to solve MWP. Cooper algorithm con- sists of two steps： location step and allocation step. By doing such two steps alternately, the local optimal solution can be obtained. In this paper, we propose a modified Cooper algorithm by introducing improved strategy for both steps. For location step, we combine the Weiszfeld method with the adaptive Barzilai-Borwein （ABB） method to propose ABB- Weiszfeld method, which has a faster convergence rate in solving location subproblems. For allocation step~ we propose a greedy cluster splitting strategy to deal with out-of-use fa- cilities, and then we propose a mixed greedy strategy which has better properties. Some preliminary numerical experiments are reported which have shown that the proposed strate- gies improve the computational efficiency of Cooper algorithm and thus result in a modified algorithm which has better performance.