THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM
THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM
复制标题
DOI：
10.1002/net.3230190602
复制
发表时间：
1989-10-01
期刊：
影响因子：
2.1
通讯作者：
BALAS, E
中科院分区：
文献类型：
--
作者：
BALAS, E
下面是一类重要的调度和路由问题的有效模型。一名推销员在两个城市之间旅行，费用只取决于这两个城市，在他访问的每个城市都会得到一份奖金，并对他没有访问的每个城市支付罚款，他希望将旅行成本和净罚款降到最低，同时访问足够多的城市来领取规定数量的奖金。我们把这个问题称为领奖旅行商问题(PCTSP)。本文讨论了PCTS多面体的结构性质，即PCTSP解的凸包。具体地说，它确定了定义这个多面体的几个小平面家族。其中一些与普通TS多面体的面有关，另一些与背包多面体的面有关。它们可以用在PCTSP的算法中，既可以作为割面，也可以作为拉格朗日最优的成分。
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 vitis and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and net penalties, while visiting enough cities to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural properties of the PCTS polytope, the convex hull of 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 optimand.