Journal
EXPERT SYSTEMS WITH APPLICATIONS
Volume 223, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.eswa.2023.119856
Keywords
Combinatorial optimization; Diversity maximization; Dispersion; Metaheuristics; Tabu search
Ask authors/readers for more resources
This study addresses the capacitated dispersion problem in a weighted graph and proposes an effective and parameter-free heuristic algorithm based on solution-based tabu search. The algorithm employs a fast greedy construction heuristic and utilizes hash functions to identify eligible candidate solutions.
Given a weighted graph with a capacity associated to each node (element), the capacitated dispersion problem (CDP) consists in selecting a subset of elements satisfying a capacity constraint, in such a way that the minimum distance among them is maximized. The purpose of this work is to tackle this NP-hard problem, by developing an effective and parameter-free heuristic algorithm based on the solution-based tabu search. Specifically, we propose a fast greedy construction heuristic to obtain high-quality initial solutions. To ensure a high search efficiency, our algorithm exploits the combination of three neighborhoods, including a new neighborhood based on the constrained swap strategy, and uses hash functions to identify eligible candidate solutions. Extensive computational experiments on benchmark instances in the literature are performed to demonstrate the high performance of our algorithm and get insights into the influences of the algorithmic components. The application of our algorithm to a realistic location problem further shows the usefulness of our approach for practical problems.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available