Browsing by Author "Turner, Wayne C."

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
    Development and application of multistep computational techniques for constrained and unconstrained mathematical functions
    Turner, Wayne C. (Virginia Tech, 1971)
    The application of incomplete relaxation and multistep concepts in the usage of steepest descent methods for the solution of simultaneous linear equations is recognized in the literature. There has been research in the area with very favorable results. Only recently, however, has there been any recognition of the fact that these concepts can be extended to unconstrained optimization problems, and by penalty formulations, also to constrained optimization problems. This holds true not only for steepest descent methods but also for any other "improving direction." In the discussion of the application of incomplete relaxation and multistep concepts to mathematical functions, very little has been accomplished in the mechanical applying of these ideas. The primary goal of this research, therefore, is to study these concepts and learn a significant amount about them. Algorithms are developed demonstrating the usage of incomplete relaxation and multistep concepts for unconstrained optimization on two directions - coordinate and gradient directions. Discussion of the performance of these methods follows in an attempt to choose some of the better ones. Ten such promising methods are selected and are applied to some complicated unconstrained functions to investigate the adaptability of these methods. Next, the application of these methods to constrained optimization is examined. Some well known constrained procedures are discussed to show how these applications can be made. A new algorithm for constrained optimization is then developed and used to solve a real world problem both to demonstrate the use of this algorithm and to show that nonlinear programming does have applications to the "real world." Finally, some areas that need further research are mentioned and discussed. The results, in general, are quite promising. For unconstrained optimization, underrelaxation yields faster convergence than did complete relaxation for all the problems examined. The difference is highly significant; but this is not startling as the same is true in the solution of simultaneous linear equations. Multistep methods are also quite efficient providing some way of efficiently determining or approximating the multistep multipliers can be obtained. In fact, an efficient multistep method is better than anyone step method for these problems. This research shows that out of the many algorithms tried only a few seem to offer the efficiency and adaptability that is needed. These methods are isolated so that their usage may be facilitated. Each of these requires its own development and to some extent stands alone. complicated unconstrained functions to investigate the adaptability of these methods. Next, the application of these methods to constrained optimization is examined. Some well known constrained procedures are discussed to show how these applications can be made. A new algorithm for constrained optimization is then developed and used to solve a real world problem both to demonstrate the use of this algorithm and to show that nonlinear programming does have applications to the "real world." Finally, some areas that need further research are mentioned and discussed. The results, in general, are quite promising. For unconstrained optimization, underrelaxation yields faster convergence than did complete relaxation for all the problems examined. The difference is highly significant; but this is not startling as the same is true in the solution of simultaneous linear equations. Multistep methods are also quite efficient providing some way of efficiently determining or approximating the multistep multipliers can be obtained. In fact, an efficient multistep method is better than anyone step method for these problems. This research shows that out of the many algorithms tried only a few seem to offer the efficiency and adaptability that is needed. These methods are isolated so that their usage may be facilitated. Each of these requires its own development and to some extent stands alone.
  • Thumbnail Image
    A manual inventory control system for small companies
    Craig, Robert J.; Turner, Wayne C. (Dept. of Industrial Engineering and Operations Research, Extension Division, Va. Tech, 1974)
    Finished goods and raw materials inventory frequently represent the greatest dollar investment made by small companies. Effective management of this inventory therefore may spell the difference between success and failure for the business. Because of the importance of the inventory function, this article explores a simplified manual control system suitable for use in small companies that do not have access to a computer and have only limited clerical resources.