The Prize Collecting Traveling Salesman Problem.

reportActive / Technical Report | Accession Number: ADA189418 | Open PDF

Abstract:

The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he visits and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and penalties, while visiting enough to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem PCTSP. This paper discusses structural, the convex hull of the solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimum. Keywords Traveling salesman problem Facets Polyhedral Combinations Convex polytopes.

Author(s):
Balas, Egon
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Descriptive Note:
Management science research rept.,
Supplementary Note:
Presented at the International Conference on Industrial and Applied Mathematics (1st) Paris, 19 Jun-3 Jul 87.
Pagination:
0028

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
MSRR-539, WP-11-87-88
Contract/Grant Number(s):
N00014-85-K-0198, $NSF-ECS86-01660
 Subject Terms
Joint Capability Areas:
JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_5_Command and Control
Communities of Interest:
Air Platforms
Descriptor(s):
*ROUTING, ALGORITHMS, COSTS, PENALTIES, SCHEDULING, TRAVEL, LAGRANGIAN FUNCTIONS
Field(s)/Group(s):
Operations Research
Keyword(s):
Traveling salesman problem, Convex polytopes
Report Date:
1987 Jul 01