𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A tabu search heuristic for the Steiner Tree Problem

✍ Scribed by Gendreau, Michel; Larochelle, Jean-Francois; Sans�, Brunilde

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
342 KB
Volume
34
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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 search algorithm for the STP in graphs. The main feature of this algorithm is a sophisticated strategy for quickly obtaining a very good solution and powerful diversification mechanisms. Computational results on the benchmark problems of the OR-Library, for which optimal solutions are known, indicate that the proposed algorithm outperforms other recent heuristics.

📜 SIMILAR VOLUMES

Tabu search for the Steiner problem in g
Tabu search for the Steiner problem in graphs
✍ Celso C. Ribeiro; Maurício C. De Souza 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB 👁 2 views

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum-weighted subgraph spanning a given subset of nodes (terminals) of the original graph. In this paper, we describe a tabu search algorithm for the Steiner problem in graphs, based o

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
✍ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 2 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami

A tabu search heuristic for periodic and
A tabu search heuristic for periodic and multi-depot vehicle routing problems
✍ Cordeau, Jean-Fran�ois; Gendreau, Michel; Laporte, Gilbert 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB

We propose a tabu search heuristic capable of solving three well-known routing problems: the periodic vehicle routing problem, the periodic traveling salesman problem, and the multi-depot vehicle routing problem. Computational experiments carried out on instances taken from the literature indicate t

A new tabu search procedure for an audit
A new tabu search procedure for an audit-scheduling problem
✍ Peter Brucker; Doris Schumacher 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 141 KB 👁 1 views

We consider the following version of the auditing problem. A set of jobs must be processed by auditors A , . . . , A K . Each job consists of several tasks and there may be precedence constraints between these tasks. There is a due date associated with each job. Each auditor is available during disj

A strong lower bound for the Node Weight
A strong lower bound for the Node Weighted Steiner Tree Problem
✍ Engevall, Stefan; G�the-Lundgren, Maud; V�rbrand, Peter 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

In this paper, we study the Node Weighted Steiner Tree Problem (NSP). This problem is a generalization of the Steiner tree problem in the sense that vertex weights are considered. Given an undirected graph, the problem is to find a tree that spans a subset of the vertices and is such that the total