The selective travelling salesman problem (Q910347)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The selective travelling salesman problem |
scientific article |
Statements
The selective travelling salesman problem (English)
0 references
1990
0 references
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.
0 references
Selective Traveling Salesman Problem
0 references
branch-and bound
0 references
upper bound calculation
0 references
node partitioning rules
0 references