Groupe d’études et de recherche en analyse des décisions

# An Algorithm for Weber's Problem on the Sphere

## Pierre Hansen, Brigitte Jaumard et Stéphane Krau

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, 1 000, and 10 000 demand points are solved in these three cases respectively. Furthermore, constrained problems with up to 1 000 demand points are also solved.

, 31 pages

Ce cahier a été révisé en septembre 1995