Back to search

Universidad de la Laguna

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

Abstract

dc:description.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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Centeno Romero, Manuel Vicente
Advisor dc:contributor.advisor
  • Salazar González, Juan José

Rights

dc:rights.accessrights
Statement dc:rights.accessrights
  • info:eu-repo/semantics/openAccess
  • Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Language dc:language.iso
es

Identifiers

dc:identifier.*
Repository record dc:identifier.uri
http://riull.ull.es/xmlui/handle/915/21163

Chain of custody

source
Harvested from
Universidad de la Laguna
Base URL
riull.ull.es/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Centeno Romero, Manuel Vicente. Un estudio metodológico y computacional del problema de asignación multidimensional. 2012. http://riull.ull.es/xmlui/handle/915/21163