An algorithm for Weber’s problem on the sphere

Weber’s problem is to locate a facility in order to minimize the sum of its weighted distances to n fixed demand points. On a sphere, this problem is nonlinear and nonconvex. Within a branch-and-bound scheme, four ways to compute lower bounds are proposed and compared. Computational results are given with demand points generated uniformly over the whole sphere, two thirds of the sphere and a hemisphere. Problems with up to 500, 1000, and 10000 demand points are solved in these three cases respectively. Furthermore, constrained problems with up to 1000 demand points are also solved.