Browsing by Author "White, John A."

Now showing 1 - 3 of 3
  • Thumbnail Image
    A central facilities location problem involving traveling salesman tours and expected distances
    Burness, Robert Currie (Virginia Tech, 1974-05-06)
    The objectives of this research were to present an original formulation of a significant facilities location problem, the traveling salesman location problem, and to develop several heuristic solution procedures for determining minimum distance locations. Despite the wide applicability of the traveling salesman location problem, a survey of the facilities location literature revealed that this research effort apparently was the first to address the problem. After mathematically formulating the problem, several rather simple example problems were investigated in order to gain some insight regarding the behavior of the function under a variety of different conditions. Many of the results stemming from the study of the simple examples were counter-intuitive. Additionally, it was demonstrated that even for problems involving only a few existing facilities the resulting objective function is non-convex. Due to the non-convexity of the objective function and the overwhelming combinatorics involved with just one functional evaluation, it was desired that the solution procedures developed be capable of obtaining near optimal solutions in the shortest time possible. One of the solution techniques proposed, Procedure 2, was based on the Successive Quadratic Approximation Procedure. This procedure was selected for two reasons: 1) It was expected that the procedure would yield minimum solutions to large problems rather quickly, and 2) It was hoped that by approximating the function over the entire solution space, the procedure would tend to overlook local minimum points, and instead, find a global minimum point. It was demonstrated that while Procedure 2 is capable of obtaining optimal solutions, it does not immediately recognize a particular solution as being optimal. The other procedure proposed, Procedure 1, based on a relationship between the Steiner-Weber problem and the traveling salesman location problem, was selected because of its ability to immediately recognize a particular solution as being a local minimum point. At each iteration Procedure 1 required the solution of a Steiner-Weber problem as well as solutions to the "string" of traveling salesman problems. The Steiner-Weber problems were solved through the use of the Hyperbolic Approximation Procedure. It was verified that both procedures are capable of obtaining optimal solutions by applying each procedure to several of the example problems. The effectiveness of each procedure in finding minimum distance solutions was determined by applying each procedure to a number of randomly generated problems, and then comparing the resulting execution times and minimum distance solutions. A difference of two percent or more between the minimum distance solutions obtained for a given problem was considered to be significant. Problems involving 4, 6, 8, 10, and 11 existing facilities were solved. No attempts were made to solve larger problems due to the excessively long execution times required. On the basis of the computational results obtained, it was concluded that 1) There is no significant difference between Procedures 1 and 2 for problems involving four existing facilities. 2) For about 15 to 20 percent of the problems involving 6, 8, 10, or 11 existing facilities, Procedure 1 performs better than Procedure 2. By examining the mean execution times for each procedure, it was found that there was little significant difference between the two procedures until rather large problems were solved. Procedure 2 required relatively shorter execution times than Procedure 1 for problems involving 10 or 11 existing facilities. However, the reduction in execution time for Procedure 2 occurred at a point where it was considered economically infeasible to continue to examine larger problems. The length of execution times for larger problems can probably be reduced by: 1) Eliminating the need to evaluate all traveling salesman problems by setting many of the PhiS, the subset probabilities, equal to zero, and 2) Replacing the branch and bound algorithm for solving traveling salesman problems with one of the more effective heuristic procedures that have been developed.
  • Thumbnail Image
    Probabilistic formulations of some facility location problems
    Aly, Adel Ahmed (Virginia Tech, 1975-01-07)
    The area of facilities location covers a wide variety of problems involving both public and private sector applications. To date, the study of location problems has been restricted primarily to deterministic formulations of the problem. The present research effort investigates the effect of random variation on the location decision. Three location problems are considered: the single facility location problem, the multifacility location problem, and the emergency service location problem. The first two problems treated are defined as the generalized Weber problem, where the concern is to locate one or more new facilities in the plane relative to several existing facilities such that the expected total cost of item movements is minimized. The total cost function is considered to be a linear function of either the expected rectilinear or the Euclidean distance, as well as a quadratic function of the expected Euclidean distance. In the generalized Weber problem the locations of the existing facilities and the item movement between facilities are considered to be random variables. Two expected total cost formulations are presented; the first involves the product of the random variables, weight and distance; the second involves the random sum of each individual distance traveled. For each formulation, possible applications are discussed, theoretical properties are developed, and a solution procedure is provided. Each algorithm is programmed and optimal solutions are obtained for several example problems. A comparison between the probabilistic and deterministic solutions is provided. Both discretely and continuously distributed random variables are treated; however, for the case of continuously distributed random variables, the normal distribution is emphasized. Both constrained and unconstrained formulations are considered. In formulating the emergency service facilities location problems which are studied, random variation is assumed to be present due to the assumption that the location of an incident is a random variable occurring uniformly over a given region. Both discrete space and continuous space formulations are considered. For the discrete case, a covering criterion is employed and the deterministic equivalent problem is solved as a set cover problem. For the continuous case, the problem is solved as a location-allocation problem. In all formulations, the rectilinear norm is used to measure the distance traveled. An example is solved for each case to illustrate the impact of probabilistic aspects on the location decision.
  • Thumbnail Image
    Probabilistic formulations of some facility location problems in discrete space
    Chapman, Stephen Clay (Virginia Tech, 1975-05-04)
    The first formulation to be examined is a probabilistic version of the set covering problem. The problem can be stated as follows: determine the locations of the minimum number of facilities among a discrete set of feasible location sites in order to assure that the probability each customer is covered by some facility is no less than a specified value. The second problem treated involves the location of a given number of facilities among a discrete set of feasible location sites in order to maximize the minimum probability that a customer is covered by some facility. This problem is a probabilistic formulation of a special case of the discrete space, minimax location problem known as the p-center problem. Thus, the first and second problems can be considered to be complementary problems. Frequently, several measures of overall system effectiveness must be considered simultaneously. This is particularly the case in many public sector location problems. Thus, the third problem treated in the dissertation considers the case in which several objectives are to be optimized collectively. The problem is formulated as a goal programming problem in which the objectives are ranked ordinally. The problems discussed above are formulated probabilistically under the assumption of a discrete solution space. This approach was taken in order to account explicitly for the random variation inherent in the systems of inte~est. Example problems are employed throughout the research to assist in the explanation of each formulation. The emphasis in the research is placed upon a sound formulation of each problem, reduction of the problem to an equivalent but computationally more efficient formulation, and the application of an appropriate procedure in solving each problem. Sensitivity analyses are conducted in order to provide further insight into the specific cause-effect relationships.