The symmetric clustered traveling salesman problem
type: Item
instance of: scholarly article
title: The symmetric clustered traveling salesman problem
zbMATH Open document ID: 0553.90100
DOI: 10.1016/0377-2217(85)90309-1
author: Kees Jongens
author: Ton Volgenant
published in: European Journal of Operational Research
publication date: 1985-01-01T00:00:00Z
review text: A travelling salesman problem (TSP) with n cities and symmetric cost matrix C is considered. The cities are partitioned into m groups called clusters and there is an additional constraint that all cities in each cluster must be visited contiguously. This constrained problem is called the clustered TSP (CTSP). Let C' be the matrix obtained by adding a large positive number H to \(C_{ij}\) whenever cities i and j are not in the same cluster. Any optimal tour for TSP with C' as the cost matrix is an optimal tour for CTSP with C as the cost matrix. However, the usual branch and bound algorithm performs poorly with the cost matrix C'. A bounding approach based on an adaptation of the Lagrangean relaxation approach with the 1-tree relaxation for the CTSP, and by introducting a new multiplier corresponding to the constraint that every feasible tour for the CTSP must have m edges (i,j) with cities i and j belonding to different clusters, is described. Heuristics are developed for finding upper bounds, and some techniques are discussed to detect and eliminate nonoptimal edges. With these changes, the branch and bound approach turns out to be satisfactory for the CTSP, as illustrated by computational results on problems involving up to 150 cities.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3882229
zbMATH Keywords: grouped cities
zbMATH Keywords: travelling salesman
zbMATH Keywords: symmetric cost matrix
zbMATH Keywords: clusters
zbMATH Keywords: bounding approach
zbMATH Keywords: Heuristics
zbMATH Keywords: branch and bound
MaRDI profile type: Publication
full work available at URL: 0377-2217(85)90309-1
OpenAlex ID: W2080894457
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: Nonoptimal Edges for the Symmetric Traveling Salesman Problem
cites work: An Algorithm for the Traveling Salesman Problem
cites work: Procedures for travelling salesman problems with additional constraints
cites work: A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
cites work: The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
description: scientific article; zbMATH DE number 3882229