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

  1. Murua Etxeberria, Maialen
Supervised by:
  1. Roberto Santana Hermida Director
  2. Diego Jesús Galar Pascual Director

Defence university: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 29 March 2022

Committee:
  1. Itziar Irigoien Garbizu Chair
  2. Eneko Osaba Secretary
  3. Krishna C. Jha Committee member
Department:
  1. Ciencia de la Computación e Inteligencia Artificial

Type: Thesis

Teseo: 157753 DIALNET lock_openADDI editor

Abstract

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.