Un estudio metodológico y computacional del problema de asignación multidimensional

Abstract

Entre los problemas que estudia la optimización combinatoria están el problema de transporte y el problema de asignación (AP). El AP es un caso particular del problema de transporte, donde las ofertas y demandas son iguales a uno; y ambos conjuntos son de igual tamaño. El AP es un problema polinomial, ya que existen algoritmos exactos ejecutables en tiempo polinomial que lo resuelven hasta la optimalidad. Sin embargo, y debido a la extensa aplicabilidad del AP, se han planteado problemas más complejos. Este trabajo trata una extensión de AP conocida como el problema de asignación multi-dimensional (mAP), el cual aparece en diversas situaciones de la vida real y es el objeto de estudio, junto a sus métodos de resolución, de esta memoria. El 3AP existe desde hace bastante tiempo en la literatura (véase, Pierskalla, 1968), presentándose en las últimas décadas novedades sobre su estudio y resolución, tales como: Balas y Saltzman (1989 y 1991), Crama y Spieksma (1992), Burkard y Rudolf (1993), Magos y Miliotis (1994), Burkard et al. (1996a y 1996b), Magos (1996), Aiex et al. (2001) y Huang y Lim (2006). El mAP es un problema con complejidad algorítmica de tipo NP-difícil, en el sentido fuerte, cuando m >= 3 [Frieze, 1983]. Este hecho, junto con su importancia en operaciones prácticas, justifica la necesidad de un estudio profundo que conduzca a la propuesta y desarrollo de nuevos algoritmos para su resolución. Otros trabajos tales como: Robertson (2001), Pasiliao (2003), Oliveira y Pardalos (2004), Gutin y Karapetyan (2009a y 2009b) y Karapetyan y Gutin (2010), presentan metaheurísticos que resuelven el mAP, para m >= 3. Existen en la literatura otras investigaciones relacionadas con el mAP, las cuales desarrollan otros tipos de algoritmos, estudios y métodos, tales como: Poore y Robertson (1997) que presentan un algoritmo basado en relajación lagrangiana para una clase del mAP. Grundel et al. (2004) muestran propiedades asintóticas de mAP aleatorios, probando dos conjeturas. Grundel y Pardalos (2005) presentan un método de generación de un mAP-axial de tamaño controlable. Grundel et al. (2007) realizan un estudio sobre el número de mínimos locales para el mAP y Krokhmal et al. (2007) responden la pregunta de la conducta asintótica del valor óptimo esperado del mAP de gran escala. Dentro del caso tridimensional existen dos variantes, en la primera se debe elegir cada valor de una dimensión una única vez, y crear así n ternas disjuntas, con n el tamaño de la dimensión (3AP-axial). En otra versión, se elige un valor de cada dimensión para cada pareja de valores de las otras dos dimensiones (3AP-planar). En esta memoria hemos desarrollado, con el fin de buscar soluciones a ambas versiones, algoritmos heurísticos y metaheurísticos en búsqueda de buenas cotas superiores y por que no del óptimo, sobre los problemas tratados. En esta investigación también se abordó el problema de asignación para m > 3, específicamente m = 4. Se desarrolla un algoritmo metaheurístico para el 4AP, haciendo uso del sistema hormiga. Luego del trabajo realizado llegamos, entre otras, a las siguientes conclusiones: los algoritmos metaheurísticos son buenos para la resolución de problemas NP-difíciles, como este caso, problemas de mAP, para m = 3 y 4. Las metaheurísticas algoritmo genético y búsqueda tabú, produjeron buenos resultados para el 3AP-axial, y esta última para el 3AP- planar, para los problemas tratados en esta memoria. Los algoritmos desarrollados mejoran, en varios casos, los resultados existentes en la literatura. Aunque el 3AP-axial y el 3AP-planar son del tipo NP-difíciles, se puede considerar al 3AP-planar de mayor complejidad para su resolución, ya que tiene un espacio de soluciones mucho mayor al espacio de soluciones del 3AP-axial, lo cual complica la búsqueda. La metaheurística sistema hormiga produjo buenos resultados, para el 4AP, para los problemas tratados en estas memorias