The Maximum Diversity Problem (MDP) consists in determining a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise distances between the elements of M is maximum. This problem, introduced by Glover , has been deeply studied using GRASP methodologies [5, 1, 13, 2]. GRASP is often characterized by a strong design effort dedicated to build high quality randomized starting solutions, while the subsequent improvement phase is usually performed by a standard local search technique. The purpose of this paper is to explore a somewhat opposite approach, that is to refine the local search phase, by adopting Tabu Search methodologies, while keeping a very simple initialization procedure. Extensive computational results show that Tabu Search achieves both better results and much shorter computational times with respect to those reported for GRASP.
|Titolo:||Tabu search versus GRASP for the maximum diversity problem|
|Autori interni:||CORDONE, ROBERTO (Secondo)|
ARINGHIERI, ROBERTO (Primo)
|Parole Chiave:||GRASP; Maximum diversity; Tabu Search|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2008|
|Digital Object Identifier (DOI):||10.1007/s10288-007-0033-9|
|Appare nelle tipologie:||01 - Articolo su periodico|
File in questo prodotto:
- PubMed Central loading...