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.
Citation
Technical Report 17, Informatics and Mathematical Modelling, Technical University of Denmark, August 2003