PDF
HTML
Publicado
2025-12-19
Número
Sección
Artículos Originales
Licencia
Derechos de autor 2025 Maria T. Ortega O., Daniel Sánchez Díaz
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
Modelado de un problema de dispersión mediante Búsqueda en Vecindarios Variables (VNS) utilizando Octave
Maria T. Ortega O.
Universidad de Panamá, Facultad de Informática, Electrónica y Comunicación, Departamento de Informática. Panamá
https://orcid.org/0009-0000-3629-9751
Daniel Sánchez Díaz
Universidad de Panamá, Facultad de Ciencias Naturales, Exactas y Tecnología, Departamento de Matemática, Panamá
https://orcid.org/0009-0008-4326-5734
DOI: https://doi.org/10.55204/trj.v4i2.e108
Palabras clave: Optimización combinatoria; problemas de dispersión y diversidad; búsqueda en vecindarios variables (VNS); metaheurísticas; Octave; modelado matemático; algoritmos de optimización.
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.
Descargas
Citas
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.
