A Multi-Start Biased-Randomized Algorithm for the Capacitated Dispersion Problem

Juan F. Gomez, Javier Panadero, Rafael D. Tordecilla, Juliana Castaneda and Angel A. Juan
Additional contact information
Juan F. Gomez: Computer Science Department, Universitat Oberta de Catalunya, 08018 Barcelona, Spain
Javier Panadero: Department of Management, Universitat Politècnica de Catalunya–BarcelonaTech, 08028 Barcelona, Spain
Rafael D. Tordecilla: School of Engineering, Universidad de La Sabana, Chia 250001, Colombia
Juliana Castaneda: Computer Science Department, Universitat Oberta de Catalunya, 08018 Barcelona, Spain
Angel A. Juan: Department of Applied Statistics and Operations Research, Universitat Politècnica de València, 03801 Alcoy, Spain

Mathematics, 2022, vol. 10, issue 14, 1-20

Abstract: The capacitated dispersion problem is a variant of the maximum diversity problem in which a set of elements in a network must be determined. These elements might represent, for instance, facilities in a logistics network or transmission devices in a telecommunication network. Usually, it is considered that each element is limited in its servicing capacity. Hence, given a set of possible locations, the capacitated dispersion problem consists of selecting a subset that maximizes the minimum distance between any pair of elements while reaching an aggregated servicing capacity. Since this servicing capacity is a highly usual constraint in real-world problems, the capacitated dispersion problem is often a more realistic approach than is the traditional maximum diversity problem. Given that the capacitated dispersion problem is an NP-hard problem, whenever large-sized instances are considered, we need to use heuristic-based algorithms to obtain high-quality solutions in reasonable computational times. Accordingly, this work proposes a multi-start biased-randomized algorithm to efficiently solve the capacitated dispersion problem. A series of computational experiments is conducted employing small-, medium-, and large-sized instances. Our results are compared with the best-known solutions reported in the literature, some of which have been proven to be optimal. Our proposed approach is proven to be highly competitive, as it achieves either optimal or near-optimal solutions and outperforms the non-optimal best-known solutions in many cases. Finally, a sensitive analysis considering different levels of the minimum aggregate capacity is performed as well to complete our study.

Keywords: capacitated dispersion problem; metaheuristics; biased-randomized algorithms; logistics networks; telecommunication networks (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/14/2405/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/14/2405/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:14:p:2405-:d:859067

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().