Captura de objetos móviles sobre una recta

Abstract

En este trabajo se comenzó estudiando el problema de captura de objetos sobre una recta de una generalización como una variante del agente viajero con objetivos móviles. A pesar de ser abordado mediante programación lineal, el poder de esta herramienta sólo sirvió en los problemas que implicaban orden, es así como se recurrió a la programación dinámica mediante la discretización del plano, ello bastó para demostrar que dicho mecanismo es suficiente para encontrar una solución óptima en un espacio finito de soluciones. La complejidad del problema no pudo ser disminuida siguiendo este camino. Es aquí donde el problema del reparador juega un papel importarte al ser éste último un caso especial del problema de este trabajo y al estar demostrado que este problema está en el conjunto de problemas NP-Completos. Se tuvo una contribución en lo que respecta a este problema con ventanas de tiempo unitarias, ya que se mejoraron dos algoritmos del estado del avance del conocimiento, en cuanto a su factor de aproximación y se encontró una mejora en cuanto a tiempo de ejecución con respecto a otros 2 algoritmos. En cuanto al trabajo futuro en esta línea de investigación se podrían contemplar las siguientes propuestas: Mejorar el factor de aproximación para Line-TRP con ventanas de tiempo unitarias. Usar el algoritmo de Line-TRP con ventanas unitarias para CTOMSR y sus variantes. Modelar mediante programación entera Line-TRP y CTOMSR. Encontrar la complejidad para Line-TRP con ventanas unitarias.