Vol. 2 No. 1 (2020): Memorias Institucionales UIS
III congreso Colombiano de Investigación de Operaciones

7- #1039 P-MEDIAN MODIFICADO CON RESTRICCIONES DE TIPO POR GENERACIÓN DE COLUMNAS

Ciro Alberto Amaya Guio
Profesor Asociado Departamento de Ingeniería Industrial, Universidad de los Andes, Colombia

Published 2019-01-01

Keywords

  • p-median,
  • generación de columnas,
  • localización.

How to Cite

Amaya Guio, C. A. (2019). 7- #1039 P-MEDIAN MODIFICADO CON RESTRICCIONES DE TIPO POR GENERACIÓN DE COLUMNAS. Memorias Institucionales UIS, 2(1), 22. Retrieved from https://revistas.uis.edu.co/index.php/memoriasuis/article/view/10383

Abstract

Uno de los problemas clásicos en logística es el problema de localización de instalaciones, en una de sus versiones se busca la selección, dentro de un grupo de candidatos, de p sitios, los cuales tendrán funciones especiales dentro del diseño de la cadena logística.
En la teoría de Localización Discreta, el problema de seleccionar dichas instalaciones para minimizar la distancia promedio ponderada de las demandas entre n clientes, o nodos de demanda, y la instalación más cercana seleccionada es más conocido como el problema p-median. Este problema está clasificado como NP-duro cuando se modela sobre un grafo general, cuando el grafo es un árbol, este puede ser solucionado en tiempo polinomial. (Mladenovic, Brimberg, Hansen, y Moreno-Pérez,2007) (Lorena y Senne,2003) (Kariv and Hakimi,1979)
En la versión clásica, todos los clientes, o puntos de demanda, tienen características similares, y se busca seleccionar p instalaciones, para atenderlos. Las instalaciones finalmente son ubicadas en nodos de demanda, dado el teorema de Hakimi (1965). Las restricciones del problema exigen que los puntos de demanda sean asignados a una sola instalación. El problema acá presentado tiene algunas variaciones, las cuales se resumen en:
1. Cada cliente puede asignarse a 1 o más instalaciones.
2. Cada cliente puede asignarse a un máximo número de instalaciones
Cada instalación debe cumplir con una demanda según el tipo de cliente La ponencia presenta un método de solución para el problema antes mencionada, el cual está basado en un modelo de optimización lineal. El problema presentado está inspirado en una situación industrial más compleja, pero que podría ser vista como un caso del problema modificado antes presentado.
La ponencia presenta con detenimiento la característica de los puntos de demanda, los cuales, en la situación industrial, son establecimientos que deben ser visitados, dada algunas condiciones particulares. Se presenta el modelo desarrollado y se hace un análisis de la capacidad de encontrar soluciones dadas diferentes situaciones. El análisis se realiza mediante la solución de diferentes instancias, que van en el rango de 9 a 230 establecimientos. El análisis incluye un método de generación de columnas, el cual será también presentado, y un análisis computacional realizado con el software comercial GUROBI y el software libre CBC. Se presenta los resultados encontrados, teniendo como base importante el tiempo de solución y la pertinencia en la implementación real en la empresa.

Downloads

Download data is not yet available.

References

Hakimi SL (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper Res 13:462–475.
Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. II: the p-medians. SIAM J Appl Math 37:539–560.
Lorena, Luis., Senne, Edson. (2003). A column generation approach to capacitated p-median problems. Computers & Operations Research, 31 (6), 863-876.https://doi.org/10.1016/S0305-0548(03)00039-X.
Mladenovic, N., Brimberg, J., Hansen, P., & Moreno-Pérez, J. A. (2007). The p-median problem: A survey of metaheuristic approaches. European Journal of Operational Research, 179(3), 927-939. https://doi.org/10.1016/j.ejor.2005.05.034.