Chapter Five
Results and Sample Solutions
5.1 Sample Problem Data Sets
In order to compare the solution data fairly with another set of 'known' answers, the same 19 data sets from Litwhiler (25) were initially solved. These data sets are included in Appendix E. They vary in number of demand points and weights, and include three 'real world' problems. Set D17 presents nine bases/research stations (circa 1977) and their coordinates (to the nearest arc-degree). Set D18 consists of 24 cities in the former Ukrainian SSR, their coordinates to the nearest arc-degree, and their proportional weight to the population of the 100 largest Russian cities in 1961. Litwhiler notes that "the latitude of Kharkov is in error by about nine degrees, but since Kuhn and Kuenne (23) evidently used the published coordinates to solve the problem, they were also used for this example" (p127). The original data is used in this trial as well. Set D19 is also a continuing problem; Chapelle (9) used the weight in pounds of first class letter mail for 1965 from each state, assumed to originate from each state capital, to find a planar median facility location. Litwhiler used this data and presented results; this example will compare all three location methods for the problems in which other results have been published.
Problems 20-53 were developed randomly (generated using the RAND function in MS Excel, yielding pseudo-random numbers on the normal distribution) to test the method over very small areas (5 degrees of arc), moderate areas (up to 90 degrees of arc - within the spherical Π/4 circle constraint), hemispherical areas (up to 180 degrees of arc and out of the Π/4 constraint area), and entire spherical areas (all points on the sphere are fair game). The small, moderate, and hemispherical area cases were calculated with both equally-weighted (w=1 for all demand points) and randomly-weighted (w varies from .01 to 5 or 15, on the author's whim) demand points to show differences in the problem types.
Each problem was sorted into one of several different cases, based on the problem characteristics. The cases are as follows:
Case A1 Covered area less than p/4 radius, equal weights
Case A2 Covered area less than p /4 radius, differing weights
Case B1 Covered area >p /4 radius, <p/2 radius, equal weights
Case B2 Covered area >p /4 radius, <p/2 radius, differing weights
Case C1 Covered area greater than p /2 radius, equal weights
Case C2 Covered area greater than p /2 radius, differing weights
Case D Problem has symmetry not fitting into one of the other cases
By analyzing problems from each of these cases we can draw additional inferences on when the method is or is not effective.
5.2 Results of the Spheresolver Code
All case A1 and A2 problems yielded superior results for matching the projected point to the best-found points, except for data set 17 (Antarctic station data). Based on the method herein of calculating the surface objective function data map at a 2 degree spread, any results for the projected point within approximately .025 radians (around 100 miles on the earth's surface, over spherical circles of up to 6300 miles diameter) verify the method for these case problems. Additional searches within the identified areas for each problem should determine exactly how good the projection method is for very small areas.
It did not appear to matter whether the demand points were equally weighted or not in cases A1 and A2. It is not surprising that the method obtained good results for these cases; the very small areas of the covering spherical circles at a relatively large distance from the sphere center ensure that the projected point would be close to the center of the covering circles.
Case B1 and B2 problems showed a large amount of variability in how well the projection predicted a good solution point. Problems 4, 7, 8, 9, and 11 showed reasonable results (distances of between .082 and .156 radians from the best grid solutions), while problems 1, 2, 10, 13, and 14 were not even close. The other six problems in the B1 case were excellent solutions. Data set 1 globally minimized at a demand point instead of at the projected point, showing that we still need to check the objective function values at demand points as well. Data set 2, a collinear set of points on the equator, should minimize at a demand point or along a linear segment between other data points.
Seven problems in the (or very close to, as exact spherical circle centers were not found) C1 and C2 cases yielded generally poor projection point results, unsurprisingly. The D case problems were also found to be unsuitable for this type of geometric projection method.
The following table details the findings of the spheresolver code, sorted by case and problem number. The table lists the data set index (problem number), minimum spherical covering circle radius, the projected longitude and latitude, the objective function value at that point, the best grid longitude and latitude, objective function at that point, case, and the distance in radians from the projected point to the best-found grid point.
Table 1
Table 1. Results of Spheresolver Runs for 53 Problem Data Sets
5.3 Comparison of Results to Projected Centroid Method
The results herein compared favorably with the problem sets for which Litwhiler (25) presented results.
Table 2
Table 2. Comparison of Final Points and Objective Function Values for 14 Problems
Table 2 compares the results from this research to results provided in the 14 problems for which results were provided in Litwhiler's research. For each presented problem set, Litwhiler's projected centroid location and objective function value can be directly compared with locations and objective function values from a Weber 3d projected point and the 2-degree grid enumeration analyses conducted for this research. Where Litwhiler presented solutions using his algorithmic approaches, the 'optimum' location and objective function values are also stated. Note that some of our results were better than his stated optima, perhaps resulting from computational or algorithmic errors in one or both research projects.
In general, the projected 3d Weber solution provided a better (in objective function terms) starting point for analysis. It did not do so in problems 10, 13, 14, and 15; note that in these cases the covering circle was larger than that guaranteeing a global minima. The only other problem in this set not meeting that condition was 11. Based on these data problems in the A case (all points contained in a covering circle of less than Π/4 radius), the 3d Weber solution will probably provide a better initial starting point, but for larger problem sets that is not the general case. It would have been interesting to see more direct comparisons of results from Litwhiler's projected centroid method (or those from one of his developed algorithms) for more A1/A2 cases to those of the proposed geometric method (only problem 3 was reported in the earlier research), but results were not published in the original paper and reconstruction of his algorithms and results was not in the purview of this research.
Note that in case 15, all surface points' objective function values are the same. Some inconsistency in the global optimum objective function values and better values found in this experiment may indicate the difficulty of accurate computations at the time the earlier research was carried out (25). The current codes used were debugged as much as possible (though certainly not thoroughly) and seem only to have problems in polar regions at this time. Note that our results for the real world problems (17, 18, & 19) are both good and simple, excepting potential computational errors in both this experiment and the earlier work. Good is relative in the real world.
Also, note that by a fast search of a 2-degree grid around the sphere, we still (for these sparsely-populated problems) find good or excellent solutions with a minimum of computational effort. In denser problems or those exhibiting strong local minima, this would not necessarily be the case. The question again pops up: How much effort should we expend to find a more exact solution over finding a very good one? An extremely simple search escalates in computations required to find a solution at a rate of n**2 as we decrease the search grid spread, but this might prove acceptable for a real-world problem where absolute global minimization is not as important as finding a good solution quickly; or where other problem externalities exist (geo- and political factors, for example).
5.4 Results of the Great Circle Arc Norm substitution into the Weiszfeld Algorithm
Direct substitution of the great circle arc distance function for the Euclidean distance function for the 19 problems tested unsurprisingly failed wholly. Dataset 3 was the only problem tested to yield a good answer (close to the same point predicted through other methods), even though several other problems were very similar in problem characteristics. We expect that the cause of the test was due directly to the non-differentiability of the objective function, a key in the development of the Weiszfeld algorithm (the Euclidean metric in integer n-space is always differentiable). The results of the tests are noted in Table 3. Note that the only A1/A2 cases tested did not converge at all.
Table 3
Table 3. Results of Greatcircle Runs for 19 Problem Data Sets
Next Page
Back to Index