A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem

A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem

0.00 Avg rating0 Votes
Article ID: iaor20072559
Country: United Kingdom
Volume: 33
Issue: 9
Start Page Number: 2526
End Page Number: 2546
Publication Date: Sep 2006
Journal: Computers and Operations Research
Authors:
Keywords: graphs
Abstract:

An efficient and effective tabu search implementation for the weighted maximal planar graph problem is proposed. The search incorporates a number of novel features including: the introduction of a new set of two-move operators; a move-cache-memory structure for efficiently searching the neighbourhood space; and a random roulette selection from a ranked list of best moves for diversification. The effects of these and other features on solution quality are investigated. Computational results are reported on a set of 100 benchmark instances of sizes varying from 20 to 100 vertices. The results demonstrate that the new probabilistic tabu search algorithm is very competitive with state of the art algorithms in the literature in terms of both solution quality and computational effort.

Reviews

Required fields are marked *. Your email address will not be published.