The Quadratic Selective Travelling Salesman Problem  Tommy Thomadsen, Thomas Stidsen
 Abstract  A wellknown 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 branchandcut 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 branchandcut 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 branchandcut 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, BranchandCut, Integer Programming  Type  Technical report  Year  2003  Publisher  Informatics and Mathematical Modelling, Technical University of Denmark, DTU  Address  Richard Petersens Plads, Building 305, DK2800 Kgs. Lyngby  Series  IMMTechnical Report200317  Electronic version(s)  [pdf] [ps]  BibTeX data  [bibtex]  IMM Group(s)  Operations Research 
Back :: IMM Publications
