Resumen

El problema que aquí se aborda es un problema de programación combinatoria de dos niveles denominado problema de localización de instalaciones no capacitadas con preferencias del cliente. Se desarrolla un algoritmo híbrido para resolver una batería de instancias de referencia. El algoritmo hibrida un algoritmo evolutivo con la revinculación de trayectorias; este último procedimiento se añade en la fase de cruce para explorar la trayectoria entre ambos padres. El algoritmo propuesto supera a los algoritmos evolutivos existentes en la literatura. Los resultados muestran que la inclusión de un procedimiento más sofisticado para mejorar la población a lo largo de las generaciones acelera la convergencia del algoritmo. En apoyo de esta última afirmación, se obtiene una reducción de alrededor de la mitad del tiempo computacional utilizando el algoritmo híbrido. Además, debido a la naturaleza de los problemas de dos niveles, si se desean soluciones factibles, el nivel inferior debe resolverse para cada cambio en la solución actual del nivel superior. Se realiza un estudio para ilustrar el impacto en el rendimiento del algoritmo al resolver el nivel inferior mediante tres enfoques exactos o heurísticos diferentes.

• Materias:Análisis Matemático Matemáticas Algebra Ingeniería Lógica matemática
• Subjects:Mathematical Analysis mathematics Algebra Engineering Mathematical logic
• Palabras claves:Problema de programación combinatoria a dos niveles; problema de localización de instalaciones no pacificadas; algoritmo híbrido; algoritmo evolutivo; reconexión de caminos; tiempo computacional.
• Keywords:Combinatorial bilevel programming problem; uncapacitated facility location problem; hybrid algorithm; evolutionary algorithm; path relinking; computational time