Chapter One
Introduction
The objective of this investigation is to present and analyze alternative solution methodologies for the modified Weber problem on the surface of a sphere. The Weber problem consists of locating a single new facility that minimizes the sum of the weighted Euclidean distances to n existing facilities over a continuous planar area. It is typically solved using an optimal iterative algorithm by Weiszfeld (34 or 35). The Weber problem on the sphere is more complex than on the plane because the objective function is not convex over the entire surface.
Much of the work on these types of problems has been done in the last 25 years by a very few researchers. The majority of that work notes the difficulties and derives the limitations of the problem. Some of the literature has also presented solution algorithms and heuristics which attempt to solve for spherically global optima, and several procedures which approach providing a simple, direct, finite, optimal solution now exist. However, there is still no guarantor of an algorithm which works in all cases, and nothing which approaches the ease of the Weiszfeld algorithm has been suggested.
Shortest arc length distances, also known as great circle arcs, are the norm used for direct shortest path distances on the sphere surface; the distance using latitude (Φ) and longitude (Θ) measures is defined as
D = α * arccos(cos Φ1 * cos Φ2 * cos (Θ1-Θ2) + sin Φ1 * sin Φ2), [1]
where α is the radius of the sphere. For simplicity in calculation, the unit sphere (α=1) is used throughout this thesis. The conventions used for determining latitude (Φ) and longitude (Θ) are discussed in section 3.4 and shown in Figure 4.
The earth is a rough spheroid. The equatorial circumference is 1.003398 times the meridian (polar) circumference, due to rotational flattening (Gaus, 21). Distances over large areas of the earth's surface can be very closely approximated using great circles, particularly when surface variations are neglected. This allows utility especially when determining flight paths for aircraft or naval sailing paths (neglecting air and water currents and disturbances, and manmade constraints such as international borders). When working on relatively small surfaces of the earth's land surface (up to about one degree of arc), L2 Euclidean metrics can also be used with relatively small degrees of error. Over larger (continental) distances, the L2 metric yields severely non-optimal results when looking for true median or center locations.
Next Page
Back to Index