Doctoral Dissertations
Date of Award
8-1991
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Major
Management Science
Major Professor
Charles E. Noon
Committee Members
Kenneth Gilbert, Lori Kaplan, Bruce Ralston
Abstract
The focus of this research is a mathematical model known as the Generalized Traveling Salesman Problem (GTSP). The GTSP is a generalization of a well known problem in the field of operations research known as the Traveling Salesman Problem (TSP). The GTSP can be simply described as follows. A salesman is given a list of cities that have been pregrouped into sets and a matrix of intercity distances. The salesman must decide a route of minimum total distance which begins at a home city, visits one city from each set, and then return to the home city. The GTSP is a difficult problem in the area of discrete optimization. The GTSP is useful for modeling real-world problems which involve simultaneous decisions of selection and sequence. One such problem is the vehicle routing problem. Other applications of the GTSP include order-picking and location/routing problems. The GTSP has received little attention in the literature perhaps due to the longstanding difficulty in solving its special case, the TSP. Our aim is to investigate a linear programming (LP) based cutting plane procedure for bounding the symmetric version of the GTSP. In the symmetric version of the problem, the distance associated with travel from city i to city j is the same as from city j to city i. The cutting plane procedure utilizes linear programming to solve a relaxed version of the problem and then uses specialized algorithms to identify violated constraints. When violated constraints are identified, they are added to the LP formulation and the problem is re-solved. This is repeated until either the LP yields an integer solution or until no more violated constraints can be found. In this dissertation, we analytically describe four classes of valid constraints for the symmetric GTSP. These constraints play a role in the development of the cutting plane procedure for computing lower and upper bounds on the total cost of the optimal solution. Our procedure includes algorithms for identifying violated constraints and heuristics for constructing feasible symmetric GTSP tours. We summarize the procedure's computational performance on 120 test problems. The results indicate that the cutting plane procedure is a viable method for producing optimal solutions or tight bounds on symmetric GTSP's of moderate size.
Recommended Citation
Sepehri, Mohammad Mehdi, "The symmetric generalized traveling salesman problem. " PhD diss., University of Tennessee, 1991.
https://trace.tennessee.edu/utk_graddiss/11217