INVESTIGACION DE OPERACIONES EN ACCION: HEURISTICAS PARA LA SOLUCION DEL TSP

INVESTIGACION DE OPERACIONES EN ACCION: HEURISTICAS PARA LA SOLUCION DEL TSP
Objetivo: dar a conocer los tipos de algoritmos utilizados para resolver problemas del agente del viajero (TSP).
Introducción:
El TSP es conocido como el problema del agente viajero este es un problema clásico de optimización combinatoria. El TSP tiene aplicaciones a problemas reales: como el problema deprogramación de tareas que se presenta en la manufactura de bienes y el del ruteo de vehículos en el ramo de la logística, una de las características del TSP es el de pertenecer a una clase de problemas muy difíciles de resolver , es decir , hallar la solución optima, en la practica es muy común utilizar algoritmos de aproximación par obtener soluciones factibles de alta calidad. El TSP esun agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas y retornar al punto de partida (hacer un tour). El problema consiste en encontrar el tour par el cual la distancia total recorrida sea mínima. Considerando que se conoce la distancia entre cada ciudad.
RESUMEN:
Este tipo de problemas son difíciles de resolver y suimplicación directa de un problema difícil de resolver es que cualquier algoritmo empleado para encontrar la solución optima emplea un tiempo de computo que crece exponencialmente con el tamaño de los datos del problema. Es por eso que se emplean heurísticas: son procedimientos que no garantizan una solución óptima al problema, pero obtienen soluciones factibles de alta calidad en un tiempo deejecución razonable. Unos de los algoritmos utilizados son las heurísticas de propósito especial estas explotan la estructura y características particulares de cada problema.
Un tipo de heurísticas son la miopes esta aplican lo del vecino mas cercano el cual se trata de un procedimiento constructivo y se parte de elegir un vértice inicial después se elige la distancia mas pequeña yasí, el problema de esto es que probablemente al final se pueden elegir aristas de longitud muy grande. Otra heurística es la inserción más cercana. Este procedimiento es también constructivo pero este hace varios subtours los cuales van creciendo hasta completar un tour que abarque todos los vértices. Y se inicia con un subtour.
Todos estos métodos se analizan con el elemento degarantía si c* que consiste en identificar si se encuentra mas cerca de 1, tenemos que el algoritmo de aproximación, obtendrá soluciones que no se encuentran muy lejos de del valor optimo, y si este valor es muy grande, esto indica que se pueden producir soluciones muy alejadas del valor optimo en el caso del TSP es posible encontrar garantías de desempeño, pero con la condición de quelas instancias examinadas posean un propiedad adicional: la desigualdad del triangulo.
Metahuristicas son una clase de métodos de aproximación que se diseñan para atacar problemas difíciles para los cuales las heurísticas de propósito. El método utilizado es iterativo el cual da inicio desde una solución arbitraria, el procedimiento consiste en explorar una vecindad previamente definidapara cada punto del espacio de soluciones y elige una nueva solución dentro de tal vecindad predefinida, a esta solución se le llama un mínimo local. Pero en el TSP es llamado 2 opt. El cual consiste en eliminar del tour un par de aristas que no sean adyacentes y reemplazarlas con el único par de aristas con el cual se puede formar nuevamente un tour. Esta tiene sus desventajas ya queva buscando soluciones mejores pero así como busca la óptima después se puede ir alejando empeorando la solución, para impedir esto se emplea una estrategia que modifica las vecindades a medida que la búsqueda avanza.
CONCLUSION:
El problema del agente del viajero es muy común, pero no parece ser muy difícil, sin embargo debido a que así es considerado existen muchas empresas gastan...