基于交替方向法的韦伯问题求解方法

韦伯问题(Weber problem)是设施选址领域中的重要问题,Weiszfeld算法则是求解韦伯问题最常用的数值方法.应用Weiszfeld算法求解韦伯问题需考虑如下两方面:1)当出现迭代点和顾客点重合(称为奇异情形)时,Weiszfeld算法的全局收敛性无法保证;2)韦伯问题经常需要快速求解,但Weiszfeld算法作为最速下降法其求解效率并不高.本文对lp-范数下的韦伯问题建立基于交替方向法的统一算法框架,并提出求解l1,l2,l∞-范数下韦伯问题新的数值算法.新算法在算法的收敛性和收敛效率两方面都有着显著的优势:即使在奇异情形下新算法仍能保证全局收敛性,且具有比Weiszfeld算法更快的收敛效率.数值实验验证了基于交替方向法的新算法求解韦伯问题的有效性.