𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A tabu search heuristic using genetic diversification for the clustered traveling salesman problem

✍ Scribed by Gilbert Laporte; Jean-Yves Potvin; Florence Quilleret

Publisher
Springer US
Year
1997
Tongue
English
Weight
736 KB
Volume
2
Category
Article
ISSN
1381-1231

No coin nor oath required. For personal study only.

✦ Synopsis

The clustered traveling salesman problem is an extension of the classical traveling salesman problem where the set of vertices is partitioned into clusters. The objective is to find a least cost Hamiltonian Cycle such that the vertices of each cluster are visited contiguously and the clusters are visited in a prespecified order. A tabu search heuristic is proposed to solve this problem. This algorithm periodically restarts its search by merging two elite solutions to form a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics.

πŸ“œ SIMILAR VOLUMES

A tabu search heuristic for the undirect
A tabu search heuristic for the undirected selective travelling salesman problem
✍ Michel Gendreau; Gilbert Laporte; FrΓ©dΓ©ric Semet πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 677 KB

The undirected Selective Travelling Salesman Problem (STSP) is defined on a graph G= ( V, E) with positive profits associated with vertices, and distances associated with edges. The STSP consists of determining a maximal profit Hamiltonian cycle over a subset of V whose length does not exceed a pres

A tabu search heuristic for the Steiner
A tabu search heuristic for the Steiner Tree Problem
✍ Gendreau, Michel; Larochelle, Jean-Francois; SansοΏ½, Brunilde πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 342 KB πŸ‘ 2 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se