Optimización de enjambre de partículas (pso) aplicada al problema de la p-mediana

Abstract

El problema de la P-mediana consiste en ubicar un conjunto de facilidades entre un grupo de cliente distribuidos en un área, de tal manera que las suma de las distancias entre cada cliente y la facilidad más cercana sea minimizada. El estudio de este problema ha despertado un gran interés en el área de la Investigación de Operaciones debido a su aplicación en campos como las telecomunicaciones, y la logística de transporte y distribución de la industria. Sin embargo, el problema planteado desde la teoría de Optimización Combinatoria, ha sido difícil de resolver debido al creciente tamaño de problemas prácticos que se tienen que abordar actualmente y a la característica de tiempo exponencial para resolver óptimamente el problema con los algoritmos disponibles en el momento. En este estudio, se propone y describe una representación de una solución y un método de decodificación para aplicar la metaheurística Enjambre de Partículas Discreto (DPSO) al problema de la P-mediana estándar (PMP). Aunque este método no garantiza la prueba de optimalidad en la solución resultante, puede ser utilizado como un método aproximado para obtener cotas superiores de calidad para problemas prácticos de gran tamaño en un tiempo computacional razonable. El algoritmo propuesto es probado utilizando problemas de la librería OR-Library, y el código es implementado en el software MATLAB. Los resultados de los experimentos numéricos muestran desviaciones mínimas respecto a la solución óptima de cada problema, incluso en los casos más difíciles que es cuando la proporción de medianas y vértices es alta.