Chapter Four
Proposed Methodology
4.1 Development of Stand-Alone Solutions for Testing
The software for this problem was coded in FORTRAN95. The first step was to properly code (and check versus known solutions) the general two-dimensional Weber problem. Checks were made versus on-hand calculations of the accepted solutions to verify the coding correctness. This code is included in this text as an appendix and the executable in the online version of this thesis.
A second code was written to find the Euclidean three-dimensional minimum for demand points located on a unit sphere, and to project that point from the origin to the surface of said sphere. This program was used to analyze 53 problems both from the literature and specially developed to test the usefulness of the method. The third code 3d solutions (using colatitude and latitude) were viewed on an actual, physical globe model of the earth to verify that the solutions and projected points were consistent with physical geometry, as well as verified through exhaustive gradient descent viewing (step-by-step through iterations). For each problem the objective function value was calculated over the entire sphere at 2-degree steps for comparison. This code is included in this text as an appendix and the executable in the online version of this thesis.
A third and final code attempts to use the great circle distance metric in the Weber problem on the sphere, and compares test information with the known information from the previous codes. This code is included in this text as an appendix and the executable in the online version of this thesis.
The problems tested in these programs will range from 3 to 50 demand points, with both equal and random weights, over small areas of the sphere, over areas close to a Π/4 spherical circle radius, over hemispheres, and over the entire sphere. Each type of problem will tell us how the algorithms perform over the range of demand point characteristics.
4.2 Description of Methodology for Geometric Method
Given a set of demand points S, find the 3-dimensional L2 spatial median to the desired degree of accuracy (up to eight decimal places, per the REAL type convention of FORTRAN95) using Weiszfeld's algorithm. Construct a ray extending from the spherical center to the surface through the 3-D spatial median. This is equivalent to computing the projected latitude and longitude of the 3-space spatial median. Define the projected point as P. Determine the goodness of P for a direct solution to the Weber problem on the sphere.
Figure 5. Proposed Methodology for Geometric Projection Method
4.3 Proposal for Extension of Possible Solution Bounds
The possibility of the existence of a geometric loophole of the hemispherical convexity limit, as noted in section 3.4, might be proven or disproven based on the relative success of the methods used. In the event the geometric spatial median projection is effective to some determined degree, we may be able to extend the spherical covering circle radius for point P to a point just over Π/2 (the limit of hull convexity for a set). This will however disallow any methods of checking for continuation of optimality (or the relative degree of optimality we achieve with the projection method) except for direct computation (enumeration) of all points' objective function values.
4.4 Surface Coordinate Transformations for Spherical Geometry
Two basic coordinate systems are appropriate for use in this type of problem. The first is a standard 3-dimensional Cartesian system, utilizing the L2 Euclidean metric for measuring distances. The second is a surface-based latitude and longitude system, with an origin based at a point on the equator and along a specific longitude (for Earth models the Greenwich Meridian is used); the conventions used in this paper are discussed in Section 3.4. This system is basically equivalent to a right ascension-declination system with a unit length segment projected from the center to a surface point. The Cartesian system is space-based, while the latitude/longitude system is surface-based.
Technically the right ascension-declination system is an infinite space system with a fundamental plane described by a 'celestial equator' and with the prime right ascension direction of the vernal equinox (the first point in Aries); therefore, on a rotating oblate ellipsoid (or other earth-model) the starting longitude would always be calculated with additional factors for greenwich sidereal time and any spherical distortions (this is known as the geocentric-equatorial coordinate system). For simplicity this thesis uses a non-rotational model sphere which allows direct transformations between our surface latitude and longitude system and the right ascension-declination system. The appropriate transformations (using longitude (theta) and colatitude (phi)) for these two systems follow:
x = r sin Θ cos Φ [9]
y = r sin Θ sin Φ [10]
z = r cos Θ [11]
r = (x**2 + y**2 + z**2)**0.5 [12]
Θ = arctan ( (x**2 + y**2) / z) [13]
Φ = arctan (y / x) [14]
All transformations must use colatitude, not latitude, as their phi term; these make intuitive sense geometrically (numerically) as well as physically.
4.5 Criteria for Relative Success of Proposed Methodology
Direct comparison of the objective function values for the projected point versus other the values for other points in the problem spherical circle will yield the success/failure data for this method.
Next Page
Back to Index