The selective travelling salesman problem (Q910347)

From MaRDI portal
Revision as of 13:52, 20 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    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

    Identifiers