  


The Quadratic Selective Travelling Saleman Problem
Tommy Thomadsen (ttimm.dtu.dk) 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 Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Integer Programming (01 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  