Advances in Branch-and-Fix methods to solve the Hamiltonian cycle problem in manufacturing optimization

  1. Murua Etxeberria, Maialen
Dirigida por:
  1. Roberto Santana Hermida Director/a
  2. Diego Jesús Galar Pascual Director/a

Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 29 de marzo de 2022

Tribunal:
  1. Itziar Irigoien Garbizu Presidente/a
  2. Eneko Osaba Secretario/a
  3. Krishna C. Jha Vocal
Departamento:
  1. Ciencia de la Computación e Inteligencia Artificial

Tipo: Tesis

Resumen

Esta tesis parte del problema de la optimización de la ruta de la herramienta donde se contribuye con unsistema de soporte para la toma de decisiones que genera rutas óptimas en la tecnología de FabricaciónAditiva. Esta contribución sirve como punto de partida o inspiración para analizar el problema del cicloHamiltoniano (HCP). El HCP consiste en visitar todos los vértices de un grafo dado una única vez odeterminar que dicho ciclo no existe. Muchos de los métodos propuestos en la literatura sirven paragrafos no dirigidos y los que se enfocan en los grafos dirigidos no han sido implementados ni testeados.Uno de los métodos para resolver el problema es el Branch-and-Fix (BF), un método exacto que utiliza latranformación del HCP a un problema continuo. El BF es un algoritmo de ramificación que consiste enconstruir un árbol de decisión donde en cada vértice dos problemas lineales son resueltos. Este método hasido testeado en grafos de tamaño pequeño y por ello, no se ha estudiado en profundidad las limitacionesque puede presentar. Por ello, en esta tesis se proponen cuatro contribuciones metodológicasrelacionadas con el HCP y el BF: 1) mejorar la enficiencia del BF en diferentes aspectos, 2) proponer unmétodo de ramificación global, 3) proponer un método del BF colapsado, 4) extender el HCP a unescenario multi-objetivo y proponer un método para resolverlo.