Modelado de un problema de dispersión mediante Búsqueda en Vecindarios Variables (VNS) utilizando Octave
Barra lateral del artículo
Contenido principal del artículo
Resumen
Los problemas de dispersión y diversidad constituyen una clase relevante de la optimización combinatoria, con aplicaciones en diseño de redes, planificación territorial y análisis de datos. Estos problemas, generalmente NP-duros, buscan seleccionar subconjuntos que maximicen la diversidad según una medida definida, lo que dificulta su resolución exacta en instancias grandes. En este trabajo se propone la aplicación de la metaheurística Variable Neighborhood Search (VNS) para modelar y resolver un problema de dispersión, implementada en el entorno de programación libre Octave. Se presenta la formulación matemática del problema, la representación de soluciones, la definición de vecindarios y el pseudocódigo del algoritmo, junto con fragmentos de su implementación para garantizar la reproducibilidad. Los experimentos realizados sobre instancias de tamaño medio evidencian que VNS obtiene soluciones competitivas en tiempos razonables. Los resultados confirman la eficacia del enfoque propuesto y destacan a Octave como una plataforma accesible para la investigación en optimización combinatoria.
Detalles del artículo
Número
Sección
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Los autores conservan los derechos morales y patrimoniales de sus obras.
Se permite el autoarchivo de la versión final (maquetada tal como saldrá publicada en la revista).
Véase también "Derechos de autor y licencias".
Cómo citar
Referencias
Brimberg, J., Hansen, P., Mladenović, N., & Salhi, S. (2003). A survey of solution methods for the continuous location-allocation problem. International Journal of Operations Research, 1(2), 1–12.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Glover, F., & Kochenberger, G. A. (2003). Handbook of metaheuristics. Springer.
Hansen, P., & Mladenović, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130 (3), 449–467. https://doi.org/10.1016/S0377-2217(00)00100-1
Hansen, P., Mladenović, N., & Brimberg, J. (2004). Variable neighborhood search. In G. Laporte, J. A. T. & F. Glover (Eds.), Handbook of Metaheuristics (pp. 337–360). Springer.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighborhood search: Methods and applications. Annals of Operations Research, 175(1), 367–407. https://doi.org/10.1007/s10479-009-0657-6
Martí, R., & Moreno, L. (2002). Scatter search for the cut width minimization problem. INFORMS Journal on Computing, 14 (1), 43–52. https://doi.org/10.1287/ijoc.14.1.43.93
Martí, R., & Reinelt, G. (2011). The linear ordering problem: Exact and heuristic methods in combinatorial optimization. Springer.
Martí, R., & Laguna, M. (2003). Scatter search: Methodology and implementations in C. Springer.
Michalewicz, Z., & Fogel, D. B. (2004). How to solve it: Modern heuristics. Springer.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. *Computers & Operations Research, 24*(11), 1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2
Octave Community. (2023). GNU Octave: A high-level interactive language for numerical computations. https://www.gnu.org/software/octave/
Osman, I. H., & Laporte, G. (1996). Metaheuristics: A bibliography. Annals of Operations Research, 63 (5), 513–623. https://doi.org/10.1007/BF02601646
Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3 (4), 376–384. https://doi.org/10.1287/ijoc.3.4.376
Salhi, S., & Smith, G. (2015). Heuristic methods for the p-center problem. Journal of the Operational Research Society, 66(1), 1–12. https://doi.org/10.1057/jors.2014.20
Talbi, E. G. (2009). Metaheuristics: From design to implementation. Wiley.