SCIENCE@home

Solution-based tabu search for the capacitated dispersion problem

Zhi Lu,A. Martínez-Gavara,Jin‐Kao Hao,Xiangjing Lai

Published 2023 in Expert systems with applications

ABSTRACT

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 N P -hard problem, developing a simple, effective, and parameter-free method based on the solution-based tabu search algorithm ( SBTS ). Specifically, we propose a greedy construction heuristic to obtain high-quality initial solutions, and the use of three specific hash functions to identify the tabu status of candidate solutions. Moreover, to enhance the search, we propose the combination of three neighborhoods, including a new one, in which we implemented a constrained swapping strategy. The combination of all these elements results in a very efficient strategy. Extensible computational experiments are performed to get insights into the influences of the algorithmic components of SBTS , and to show that our proposal outperforms the state-of-the-art results. Finally, our solution approach is applied to a realistic location problem.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-44 of 44 references · Page 1 of 1

CITED BY

Showing 1-21 of 21 citing papers · Page 1 of 1