Néstor Elí Rodríguez Plascencia

Uno de los problemas más famosos y difíciles en la teoría de optimización, es del problema del agente viajero (TSP). El interés en el estudio de técnicas para su solución es motivado por la enorme cantidad de aplicaciones prácticas de problemas de toma de decisiones donde éste aparece como subestructura. En este artículo se hace una breve reseña de los métodos de aproximación (heurísticas) más relevantes que se han propuesto para intentar encontrar soluciones factibles de alta calidad.

El problema del Agente Viajero (mejor conocido por TSP, por sus siglas en inglés; Traveling Salesperson Problem), el cual es un problema clásico de optimización combinatoria, una de las subdisciplinas de la investigación de operaciones (IO). Señalamos cómo las aplicaciones de IO se encuentran en prácticamente todos los niveles y en todo tipo de industrias, y cómo una utilización adecuada de las técnicas de IO dándole soporte al complejo proceso de toma de decisiones que enfrentan las empresas, puede tener un impacto económico significativo.

el TSP se formula de la siguiente manera. Un agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar al punto de partida. Un recorrido con estas características, es llamado dentro de este contexto un tour

Se llaman de propósito especial, porque explotan la estructura y características particulares de cada problema. La primera familia de esta clase de heurísticas que describiremos pertencen a las heurísticas de tipo miope (greedy en inglés), son llamadas así porque sólo se preocupan por hacer lo mejor que pueden localmente, sin ver más allá de un cierto entorno muy cercano.

1. El vecino más cercano: Se trata de un procedimiento constructivo, se parte de elegir un vértice inicial
2. La inserción más cercana: Este procedimiento es también constructivo, pero en contraste con el anterior, en el cual se tiene un camino, y sólo al final se completa un tour, aquí tenemos subtours, los cuales van creciendo hasta completar un tour que abarque todos los vértices. Iniciemos con un subtour.

Garantías de Desempeño.
Hemos mencionado que no es posible garantizar que los dos métodos anteriormente descritos produzcan buenas soluciones.

Metaheurísticas
Las metaheurísticas 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 especial han fracasado en dar resultados efectivos y eficientes. Las metaheurísticas proporcionan marcos generales que permiten crear nuevos híbridos combinando diferentes conceptos derivados de las heurísticas clásicas, la inteligencia artificial, la evolución biológica, los sistemas neuronales, la mecánica estadística y el psicoanálisis freudiano.

Referencias:
http://yalma.fime.uanl.mx/~roger/work/Papers/article/article-inge-2000.pdf