Trabajo Fin de Grado
Estudio experimental de diferentes modelos matemáticos para resolver el problema TSP
Autor/es | Corral Sánchez, Ana |
Director | García Sánchez, Jose Manuel |
Departamento | Universidad de Sevilla. Departamento de Organización Industrial y Gestión de Empresas I |
Fecha de publicación | 2020 |
Fecha de depósito | 2021-03-05 |
Titulación | Universidad de Sevilla. Grado en Ingeniería de las Tecnologías Industriales |
Resumen | Actualmente, existen diversos métodos y estrategias para la resolución del Problema del
Viajante de Comercio (TSP), es decir, “The Travelling Salesman Problem” como sus iniciales
indican, ya que quizás es el problema de ... Actualmente, existen diversos métodos y estrategias para la resolución del Problema del Viajante de Comercio (TSP), es decir, “The Travelling Salesman Problem” como sus iniciales indican, ya que quizás es el problema de optimización combinatoria más ampliamente investigado. Para la solución de este problema existen diferentes estrategias, tanto métodos aproximados, donde entrarían las heurísticas y las metaheurísticas, como el uso de métodos exactos, donde se sitúa este trabajo. El objetivo principal de este trabajo será analizar y comparar cuatro modelos matemáticos diferentes que permitan la resolución óptima de los diferentes problemas TSP o una solución factible pasado un tiempo razonable. Se utilizará una batería de problemas que contemplará tanto escenarios simétricos como asimétricos respecto a la distancia entre nodos. Los modelos matemáticos se implementarán en una herramienta informática de optimización llamada Lingo, en la cual se formularán los modelos con su propio lenguaje, y los enlazaremos con los problemas situados en ficheros de texto (“.txt”) que contendrán todos los datos necesarios para su resolución. En cuanto a los modelos, tendremos tres versiones principales. Por un lado, el modelo propuesto por Miller, Tucker y Zemlin (1960) [5], por otro lado, el modelo propuesto por Desrochers y Laporte (1988) [9], que es muy similar al modelo MTZ, y como tercer modelo el propuesto por Sarin (1992) [2]. Finalmente, el último modelo de estudio será un modelo intermedio entre el propuesto por Miller, Tucker y Zemlin y el propuesto por Desrochers y Laporte, el cual recibirá el nombre del Modelo Intermedio. La finalidad del trabajo es obtener datos concluyentes y reales, que sirvan de ayuda a la hora de escoger uno de los cuatros métodos dependiendo del tipo de problema al que nos estemos enfrentando. (Extraído del Objetivo del Trabajo) |
Cita | Corral Sánchez, A. (2020). Estudio experimental de diferentes modelos matemáticos para resolver el problema TSP. (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
TFG-3222-CORRAL SANCHEZ.pdf | 1.798Mb | [PDF] | Ver/ | |