A central facilities location problem involving traveling salesman tours and expected distances

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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Industrial Engineering and Operations Research

Department dc:contributor.department

Industrial Engineering and Operations Research

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1974

Author dc:creator

• Burness, Robert Currie

Chair dc:contributor.committeechair

• White, John A.

Committee members dc:contributor.committeemember

• Schmidt, J. William
• Turner, Wayne C.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-07072010-020153

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/43550