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

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. © 2022 by the authors.

El problema de dispersión capacitada es una variante del problema de máxima diversidad en el que se debe determinar un conjunto de elementos de una red. Estos elementos podrían representar, por ejemplo, instalaciones en una red logística o dispositivos de transmisión en una red de telecomunicaciones. Generalmente se considera que cada elemento tiene una capacidad de servicio limitada. Por lo tanto, dado un conjunto de ubicaciones posibles, el problema de dispersión capacitada consiste en seleccionar un subconjunto que maximice la distancia mínima entre cualquier par de elementos mientras alcanza una capacidad de servicio agregada. Dado que esta capacidad de servicio es una restricción muy habitual en los problemas del mundo real, el problema de dispersión capacitada es a menudo un enfoque más realista que el problema tradicional de máxima diversidad. Dado que el problema de dispersión capacitada es un problema NP-difícil, siempre que se consideren instancias de gran tamaño, debemos utilizar algoritmos basados ​​en heurísticas para obtener soluciones de alta calidad en tiempos computacionales razonables. En consecuencia, este trabajo propone un algoritmo aleatorio sesgado de múltiples inicios para resolver eficientemente el problema de dispersión capacitada. Se lleva a cabo una serie de experimentos computacionales empleando instancias de tamaño pequeño, mediano y grande. Nuestros resultados se comparan con las soluciones más conocidas publicadas en la literatura, algunas de las cuales han demostrado ser óptimas. Nuestro enfoque propuesto ha demostrado ser altamente competitivo, ya que logra soluciones óptimas o casi óptimas y supera a las soluciones más conocidas no óptimas en muchos casos. Finalmente, también se realiza un análisis sensible considerando diferentes niveles de capacidad agregada mínima para completar nuestro estudio. © 2022 por los autores.