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 vs. GRASP for the maximum diversity problem|
|Autori interni:||ARINGHIERI, ROBERTO (Primo)|
CORDONE, ROBERTO (Secondo)
|Data di pubblicazione:||dic-2005|
|Parole Chiave:||Maximum Diversity; GRASP; Tabu Search|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Citazione:||Tabu search vs. GRASP for the maximum diversity problem / R. Aringhieri, R. Cordone, Y. Melzani. - Crema : Università degli Studi di Milano, Polo Didattico e di Ricerca di Crema, 2005 Dec.|
|Appare nelle tipologie:||08 - Relazione interna o rapporto di ricerca|
- PubMed Central loading...