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 [6], 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.
Tabu search versus GRASP for the maximum diversity problem / R. Aringhieri, R. Cordone, Y. Melzani. - In: 4OR. - ISSN 1619-4500. - 6:1(2008), pp. 45-60. [10.1007/s10288-007-0033-9]
Tabu search versus GRASP for the maximum diversity problem
R. AringhieriPrimo
;R. CordoneSecondo
;
2008
Abstract
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 [6], 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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.