Back

G-94-27

An Algorithm for Weber's Problem on the Sphere

, , and

BibTeX reference

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

This cahier was revised in September 1995