The symmetric clustered traveling salesman problem
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.
- A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
- An Algorithm for the Traveling Salesman Problem
- Nonoptimal Edges for the Symmetric Traveling Salesman Problem
- Procedures for travelling salesman problems with additional constraints
- The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
- An efficient composite heuristic for the symmetric generalized traveling salesman problem
- Metaheuristics for the tabu clustered traveling salesman problem
- Cluster based branching for the asymmetric traveling salesman problem
- The traveling salesman problem with backhauls
- The clustered team orienteering problem
- IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem
- An exact method for the double TSP with multiple stacks
- GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem
- scientific article; zbMATH DE number 4012343 (Why is no real title available?)
- Some applications of the clustered travelling salesman problem
- An exact algorithm for the clustered travelling salesman problem
- Picker routing in AGV-assisted order picking systems
- Symmetric weight constrained traveling salesman problem: Local search
- Cluster-level operations planning for the out-of-position robotic arc-welding
- An approximation algorithm for the clustered path travelling salesman problem
- Heuristics for a cash-collection routing problem with a cluster-first route-second approach
- An adaptive memory matheuristic for the set orienteering problem
- Traveling salesman problem with clustering
- An approximation algorithm for the clustered path travelling salesman problem
- A hybrid metaheuristic for the clustered travelling salesman problem
- An approximation algorithm for the (metric) clustered path traveling salesman problem
- An ALNS metaheuristic for the family multiple traveling salesman problem
- A survey on the traveling salesman problem and its variants in a warehousing context
- Self-organizing feature maps for the vehicle routing problem with backhauls
This page was built for publication: The symmetric clustered traveling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q759661)
