𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A tabu search heuristic for the undirected selective travelling salesman problem

✍ Scribed by Michel Gendreau; Gilbert Laporte; Frédéric Semet

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
677 KB
Volume
106
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

✦ Synopsis

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 preset limit L. We describe a tabu search (TS) heuristic for this problem. The algorithm iteratively inserts clusters of vertices in the current tour or removes a chain of vertices. Tests performed on randomly generated instances with up to 300 vertices show that the algorithm consistently yields near-optimal solutions.

📜 SIMILAR VOLUMES

A branch-and-cut algorithm for the undir
A branch-and-cut algorithm for the undirected selective traveling salesman problem
✍ Gendreau, Michel; Laporte, Gilbert; Semet, Fr�d�ric 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 2 views

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a p

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