The selective travelling salesman problem (Q910347)

This paper deals with exact solutions for the Selective Traveling Salesman Problem - a TSP with profit at the nodes - by branch-and bound. The contribution is in the form of a new upper bound calculation as well as two node partitioning rules. The upper bound is a knapsack problem while the partitioning rules are (1) a single descendant node corresponding to the inclusion of each vertex that does not yield a dominated solution and (2) a two-descendant rule that has some vertices for which a decision is delayed until later on. Numerical results indicate that the first rule is generally best and that the upper bound calculation permits the resolution of problems with a few tens of nodes up to about 10 depending on the network and cost structure.