Estudio de problemas de ubicación de instalaciones multi-nivel

Los problemas de ubicación de instalaciones (PUI) han sido amplia y profundamente estudiados en diversos campos [4]. Por ejemplo, en áreas como optimización discreta e investigación de operaciones se pueden encontrar numerosos estudios relacionados a los PUI. Tal vez una de las principales razones por la que estos problemas han recibido gran atención por parte de investigadores y practicantes es la fuerte relación que existe entre su amplia aplicabilidad a situaciones reales y la estructura matemática presente en los modelos de dichos problemas. Tal estructura ha demostrado ser muy importante al momento de desarrollar métodos de solución eficientes, los cuales en muchos casos han sido extendidos a todo el espectro en investigación de operaciones siendo hoy ampliamente utilizados para resolver diversos problemas de optimización. En este proyecto se pretende dar continuidad al trabajo publicado en [7-10] donde se estudió una clase general de PUI denotada “Problemas de Ubicación de Instalaciones Multi-Nivel” (PUIMN). En términos generales, en un PUIMN se tiene un conjunto de clientes con un requerimiento de producto o servicio y un conjunto de posibles sitios donde se pueden abrir las instalaciones para servir a los clientes. El conjunto de posibles sitios está particionado en k tipos diferentes de instalaciones. Por ejemplo, en el contexto de gestión y diseño de la cadena de suministro suponiendo que k=2, se debe determinar dónde ubicar plantas de producción y centros de almacenamiento para satisfacer los requerimientos de un conjunto de puntos de venta. En general, en un PUIMN, el objetivo es determinar cuáles instalaciones abrir simultáneamente en cada nivel (o tipo) de tal forma que los clientes sean asignados a una secuencia de instalaciones abiertas, mientras se optimiza una función objetivo. Así, los PUIMN generalizan PUI clásicos como el “Problema de Ubicación de Instalaciones no Capacitado” o el “Problema de la p-mediana” y surgen naturalmente de la misma manera en varias aplicaciones como por ejemplo en el diseño de la red de la cadena de suministro, redes de telecomunicación, transporte, sistemas de salud, entre otros [5]. El investigador principal de este proyecto desarrolló su reciente tesis doctoral alrededor del estudio de los PUIMN. En particular, uno de los resultados de dicha investigación se publicó en [10] donde se presenta un método de descomposición para resolver el caso de un PUIMN en el cual no se consideran capacidades en las instalaciones. En ese caso, se implementó exitosamente un algoritmo basado en una versión mejorada del método de descomposición de Benders [1] dando como resultado la solución óptima para instancias con hasta 3000 clientes, 300 sitios posibles para las instalaciones y cuatro tipos diferentes de instalaciones. Los tiempos de cómputo del método presentado sobre las instancias más grandes no superan unos cuantos minutos mientras que el software considerado como estado del arte en resolución de problemas de programación entera mixta no resolvió dichas instancias en más de un día de tiempo de computo. Esto es una muestra de que los PUIMN preservan de alguna manera la estructura encontrada en los PUI de un solo nivel donde los métodos de descomposición ya han sido probados exitosamente. Por otra parte, en [8] se extendieron resultados obtenidos para el caso de un solo nivel para un PUIMN de k niveles. En particular, basándose en una representación alternativa del problema se dieron condiciones suficientes para la extensión de los resultados presentados en el artículo de Cornuéjols et al. [2] el cual es de gran importancia en el área. En dicho artículo los autores usan la propiedad de submodularidad para obtener cotas del peor caso para un algoritmo codicioso y una heurística de búsqueda local. Unos años después un resultado de Feige [3] implicó que la mejor garantía de aproximación posible para el problema de la p-mediana estaba dada precisamente por el algoritmo codicioso, a menos que P=NP. Igualmente, en [8] se extendieron los resultados presentados en [6] para la obtención de una nueva formulación del problema basada en submodularidad. Es importante mencionar que estos resultados habían sido esquivos para la comunidad por cerca de 40 años. También, cabe recordar que aunque el Problema de Ubicación de Instalaciones de un solo nivel no Capacitado [2] es uno de los problemas más sencillos de presentar y de modelar en optimización discreta, éste es NP-duro. Es decir, no se sabe de la existencia de un algoritmo cuyo tiempo de computo del peor caso este acotado por un polinomio en los parámetros de la instancia. El PUIMN estudiado en [7,8] y [10] generaliza este problema y por lo tanto también hace parte de la clase de problemas NP-duros. Esto significa que aunque el modelo es simplificado en el sentido que se omiten algunas restricciones reales (como las capacidades), desde el punto de vista computacional se mantiene como un reto desafiante. La importancia de estos resultados teóricos y computacionales radica en el uso potencial de estos algoritmos y formulaciones en diversos problemas de optimización. Como se mencionó anteriormente, los PUI son problemas de optimización que suelen presentarse con frecuencia como subproblemas en muchos campos de estudio. Así pues, tener herramientas computacionales para resolver dichos problemas de manera eficiente tiene un impacto generalizado para resolver modelos de optimización discreta más sofisticados donde se modele más a detalle las variables y restricciones de un problema de decisión. De esta manera, aún es necesario realizar más investigación en el tema enfocándose principalmente en dos direcciones: (i) la utilización de los métodos desarrollados para resolver PUIMN en otros PUI que modelen más a detalle situaciones reales y (ii) la extensión de los resultados obtenidos recientemente hacia modelos matemáticos más generales. Un ejemplo de actualidad donde se involucren PUI en contextos reales es el problema de ubicación de estaciones de recarga para vehículos eléctricos. Aunque ya se pueden encontrar varios artículos relacionados, es un área relativamente joven debido el reciente crecimiento en la producción de dichos vehículos, en especial en el contexto colombiano. Por otra parte, un ejemplo sencillo donde se generaliza el PUIMN estudiado en [10], es el caso donde se incluyen capacidades en las instalaciones y los vínculos entre ellas además de decisiones de diseño de red. Así, resulta importante determinar bajo qué condiciones los resultados obtenidos en [8] y [10] se pueden extender a este problema más general. Finalmente, es importante mencionar que el presente proyecto cuenta con la participación de dos asesores internacionales quienes son ampliamente reconocidos por la comunidad académica en el área de la ciencia de localización (Location Science) y quienes fueron asesores de la tesis doctoral del investigador principal de este proyecto. De igual forma, son miembros activos de INFORMS (The Institute for Operations Research and Management Sciences) y han recibido importantes distinciones en el área. Esto garantiza un enfoque de internacionalización a la investigación realizada, además de generar vínculos con otras universidades, en especial en Canadá. REFERENCIAS [1]. J.F. Benders. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1):238-252, 1962. [2]. G. Cornuejols, M. L. Fisher, and G. L. Nemhauser. Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Management Science, 23(8):789-810, 1977. [3]. U. Feige. A threshold of ln n for approximating set cover. Journal of the Association of Computing Machinery, 45(4):634-652, 1998. [4]. G. Laporte, S. Nickel, and F. Saldanha da Gama, editors. Location Science. Springer International Publishing, Cham, Switzerland, 2015. [5]. M. T. Melo, S. Nickel, and F. Saldanha-da-Gama. Facility location and supply chain management - A review. European Journal of Operational Research, 196(2):401-412, July 2009. [6]. G. L. Nemhauser, L. A.Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14:265-294, 1978. [7]. C. Ortiz-Astorquiza, I. Contreras, G. Laporte. Multi-level facility location as the maximization of a submodular set function. European Journal of Operational Research. 247:1013-1016, 2015 [8]. C. Ortiz-Astorquiza, I. Contreras, G. Laporte. Formulations and approximation algorithms for Multi-level facility location problems. INFORMS Journal on Computing. 29(4):767-779, 2017. [9]. C. Ortiz-Astorquiza, I. Contreras, G. Laporte. Multi-level facility location problems. European Journal of Operational Research. 267 (3): 791-805. 2018. [10]. C. Ortiz-Astorquiza, I. Contreras, G. Laporte. An exact algorithm for Multi-level uncapacitaded facility location problems. Transportation Science. Aceptado. 2018.