Repository logo
Log In(current)
  1. Home
  2. Colleges & Schools
  3. Graduate School
  4. Doctoral Dissertations
  5. The Traveling Salesman Subset-tour Problem with one additional constraint (TSSP+1)
Details

The Traveling Salesman Subset-tour Problem with one additional constraint (TSSP+1)

Date Issued
December 1992
Author(s)
Pillai, Rekha Sukumar
Advisor(s)
Charles E. Noon
Additional Advisor(s)
Kennth Gilbert
Melissa Bowers
Bruce Ralston
Permanent URI
https://trace.tennessee.edu/handle/20.500.14382/59337
Abstract

The Traveling Salesman Problem (TSP) is a well known problem in the field of operations research/management science. Given a list of customers and a matrix of intercustomer distances, the TSP problem requires the decision maker to construct a minimum length tour which visits all customers in the list. The Traveling Salesman Subset-tour Problem (TSSP) is a variant of the TSP in that the decision maker is not required to visit all the customers. The TSSP problem requires the salesman to select a subset of customers from the list and construct a minimum length tour over the selected customers. The TSSP problem is thus one of selection and sequencing whereas a TSP involves only sequencing. When an additional restriction is imposed on the minimum length tour, the problem is called a TSSP with one additional constraint, (TSSP+1). The focus of this research is the development of an optimal solution approach for the TSSP+1 class of problems.

The TSSP+1 is useful for modeling real-world routing problems which involve simultaneous decisions of selection and sequencing. Previously studied problems such as the Orienteering Problem (OTP), the Prize Collecting TSP (PCTSP), and the Time Constrained TSP (TCTSP) are special cases of the TSSP+1. An optimal solution approach developed for the general TSSP+1 can be immediately applied to solve these special cases. Another important application of the TSSP+1 problem is to the Vehicle Routing Problem (VRP).Given a set of customers, a matrix of intercustomer distances, and a demand value associated with each customer, the basic capacity-constrained VRP is to determine a set of capacity-feasible vehicle routes with minimum total travel distance such that each customer demand is met by exactly one vehicle. A decomposition approach which relies on solving TSSP+1 subproblems can be used to develop bounds for the VRP problem. In spite of its applicability, the generalized form of the TSSP+1 has received little attention from researchers.

In this dissertation, we investigate a branch-and-cut approach for solving the symmetric TSSP+1. In the symmetric version of the TSSP+1, the distance associated with travel from customer i to customer j is the same as from customer j to customer i. We employ a Linear Programming (LP)-based cutting plane method for bounding within the branch-and-cut algorithm. The cutting plane method utilizes linear programming to solve a relaxed version of the problem and uses specialized algorithms to identify violated constraints. The violated constraints are added to the current LP formulation and the problem is re-solved. The steps of constraint identification, constraint addition, and LP solution are repeated until no more violated constraints can be found or the LP relaxation yields an integer solution. If the LP solution at the end of the cutting plane procedure is non-integer, branching on variables with non-integer values is carried out. The procedure terminates with a confirmed optimal solution when all the branches have been explicitly or implicitly investigated.

We analytically describe two classes of valid constraints for the symmetric TSSP+1. These constraints greatly impact the bound quality within the cutting plane method and ultimately influence the speed of problem resolution in the branch-and-cut procedure. Our branch-and-cut procedure includes a heuristic for constructing feasible TSSP+1 tours from non-integer LP solutions and incorporates variable elimination and constraint management for controlling problem size.

The branch-and-cut procedure is tested on 169 test problems from the literature. The results indicate that the branch-and-cut procedure is a viable method for producing optimal solutions or tight bounds for the symmetric TSSP+1.

We also examine how the branch-and-cut procedure can be used to bound the capacity-constrained VRP via decomposition. Initial test results suggest that the TSSP+1 can be used to develop tight bounds for the capacity-constrained VRP.

 
Degree
Doctor of Philosophy
Major
Management Science
File(s)
Thumbnail Image
Name

Thesis92b.P544.pdf

Size

4.49 MB

Format

Adobe PDF

Checksum (MD5)

fb256fb4561741aabfc5c0d7d1ebba8a


University Libraries

1015 Volunteer Boulevard
Knoxville, TN 37996
865-974-4351

Map & Directions
Donate to the Libraries
  • About
  • John C. Hodges Society
  • Speaking Volumes magazine
  • Outreach
  • Directory
  • Employment
  • Policies
  • Library Intranet
University of Tennessee power T logo

The University of Tennessee, Knoxville
Knoxville, Tennessee 37996
865-974-1000

Events
A-Z
Apply
Privacy
Map
Directory
Give to UT
Accessibility

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science