Empreu aquest identificador per citar o enllaçar aquest ítem: http://hdl.handle.net/10609/147032
Títol: A multi-start biased-randomized algorithm for the capacitated dispersion problem
Autoria: Gómez González, Juan Francisco  
Panadero, Javier  
Tordecilla, Rafael D.  
Castaneda, Juliana  
Juan, Angel A.  
Altres: Universitat Oberta de Catalunya (UOC)
Universitat Politècnica de Catalunya (UPC)
Universidad de La Sabana
Universitat Politècnica de València
Citació: Gómez, J.F., Panadero, J., Tordecilla, R., Castañeda, J. & Juan Perez, A.A. (2022). A Multi-Start Biased-Randomized Algorithm for the Capacitated Dispersion Problem. Mathematics, 10(14), 1-20. doi: 10.3390/math10142405
Resum: 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.
Paraules clau: problema de dispersió capacitat
metaheurística
algorismes esbiaixats i aleatoris
xarxes logístiques
xarxes de telecomunicacions
DOI: https://doi.org/10.3390/math10142405
Tipus de document: info:eu-repo/semantics/article
Versió del document: info:eu-repo/semantics/publishedVersion
Data de publicació: 7-set-2022
Llicència de publicació: http://creativecommons.org/licenses/by/4.0  
Apareix a les col·leccions:Articles cientÍfics
Articles

Arxius per aquest ítem:
Arxiu Descripció MidaFormat 
A multi-start biased-randomized algorithm for the capacitated dispersion problem.pdf576,72 kBAdobe PDFThumbnail
Veure/Obrir
Comparteix:
Exporta:
Consulta les estadístiques

Els ítems del Repositori es troben protegits per copyright, amb tots els drets reservats, sempre i quan no s’indiqui el contrari.