A branch-and-cut algorithm for the undirected selective traveling salesman problem
A branch-and-cut algorithm for the undirected selective traveling salesman problem
复制标题
DOI：
10.1002/(sici)1097-0037(199812)32:4
复制
发表时间：
1998-12
期刊：
影响因子：
2.1
通讯作者：
M. Gendreau;G. Laporte;F. Semet
中科院分区：
文献类型：
--
作者：
M. Gendreau;G. Laporte;F. Semet
选择性旅行商问题（STSP）定义在图中，利润与顶点相关联，成本与边相关联。某些顶点是强制性的。其目标是构造一个包含所有强制顶点且费用不超过一个预定常数的利润最大的旅游。我们开发了几类有效的不等式的对称STSP和使用它们的分支和切割算法。根据问题的参数，该算法可以解决涉及多达300个顶点的实例。q 1998 John Wiley & Sons，Inc.网络32：263-273，1998年
The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a preset constant. We developed several classes of valid inequalities for the symmetric STSP and used them in a branch-and-cut algorithm. Depending on problem parameters, the proposed algorithm can solve instances involving up to 300 vertices. q 1998 John Wiley & Sons, Inc. Networks 32: 263-273, 1998