Optimization Online


The Quadratic Selective Travelling Saleman Problem

Tommy Thomadsen (tt***at***imm.dtu.dk)
Thomas Stidsen (tks***at***imm.dtu.dk)

Abstract: A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an associated profit which can be gained only if both nodes are visited. The QSTSP is a subproblem when constructing hierarchical ring networks. We describe an integer linear programming model for the QSTSP. The QSTSP is solved by two construction heuristics and by a branch-and-cut algorithm. Computational results are presented for two budget constraints limiting the length of the ring and the number of nodes in the ring respectively. It is investigated how the tightness of the budgets affect the running time of the branch-and-cut algorithm and correspondingly how this affect the solution quality of the construction heuristics. The construction heuristics have difficulties in finding good solutions. One heuristic is best when tight budgets are considered, the other heuristic is best when loose budgets are considered. The branch-and-cut algorithm finds the optimal solutions at a cost of much higher running time. All problems with up to 50 nodes are solved within one hour.

Keywords: Ring Networks, (Selective) Traveling Salesman Problem, Branch-and-Cut, Integer Programming

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming (0-1 Programming )

Category 3: Network Optimization

Citation: Technical Report 17, Informatics and Mathematical Modelling, Technical University of Denmark, August 2003

Download: [Postscript][PDF]

Entry Submitted: 09/01/2003
Entry Accepted: 09/01/2003
Entry Last Modified: 09/01/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society