Problema del agente viajero tsp

TABLA DE CONTENIDO

Introducción 2
1. Problema del Vendedor Viajero (TSP) 3
1.1 Definición: 3
1.2 Breve Historia 3
Recors de TSP en el tiempo 3
2. Construcción Heurística 4
2.1 Algoritmo del vecino más cercano 4
2.2 Inserción Heurística 5
3. Soluciones de Mejora 5
3.1 2-opt Intercambios 6
Problema 7
Conclusión 9
Bibliografía 10



IntroductionIntroducción

A salesman has to visit N cities with given distances d ij between cities i and j , returning finally to his city of origin. Un vendedor tiene que visitar n ciudades con distancias indicadas d ij entre las ciudades i y j, regresando finalmente a su ciudad de origen. Each city is to be visited only once, and the route is to be made as short as possible. A popular special case is the EuclideanTSP, where the cities are given by their positions ( x i , y i ) in the plane and the distance matrix is given by the Euclidean distance, Cada ciudad debe ser visitado sólo una vez, y la ruta se hará lo más corto posible. Un caso especial es el popular TSP euclidiana, donde las ciudades están dadas por su posición (x i, y i) en el plano y el matriz de distancia está dada por la distanciaeuclídea,

The Travelling Salesman Problem (TSP) is the most prominent problem in combinatorial optimization [ 1 ]. It has attracted - and still attracts - researchers from various fields. El Problema del Vendedor Viajero (TSP) es el problema más importante en la optimización combinatoria. Ha atraído y atrae todavía - los investigadores de diversos campos.
Any known algorithm that claims to find thetrue optimum tour has a running time that grows exponentially with the number N of cities. Cualquier algoritmo conocido que pretende encontrar el recorrido óptimo de verdad tiene un tiempo de ejecución que crece exponencialmente con el número N de ciudades. Since TSP is NP-complete this will hold for any future algorithm - at least with high probability. Desde TSP es NP-completo esta llevará acabo por cualquier algoritmo de futuro - por lo menos con una probabilidad alta. Therefore efforts have concentrated on the development of heuristic algorithms, that do not aim to find the shortest tour but a tour that is reasonable short. Such approximate algorithms incorporate ideas that range from simple to highly sophisticated, and some of them give results that come very close to the optimumsolution [ 2 ]. Por lo tanto los esfuerzos se han concentrado en el desarrollo de algoritmos heurísticos, que no tienen por objeto encontrar el menor recorrido, sino una gira que sea razonablemente corta. Tales algoritmos de aproximación incorporan ideas que van de simples a muy sofisticados, y algunos de ellos dan resultados que resultan muy cerca de la solución óptima.
This is an introduction tosome these approximate TSP algorithms. Esta es una introducción a algunos algoritmos de aproximación de las TSP y la solución de un problema propuesto en clases. It contains animated, graphical implementations that allows you watch the algorithms in action and to play around with them.

1. Problema del Vendedor Viajero (TSP)

2.1 Definición:

Dado un conjunto finito de ciudades, ycostos de viaje entre todos los pares de ciudades, encontrar la forma más barata de visitar todas las ciudades exactamente una vez, y volver al punto de partida.
Más precisamente, los costos son simétricos en el sentido de que viajar desde la ciudad X a la ciudad Y tiene el mismo costo que viajar desde la ciudad Y a la ciudad X. La condición de visitar todas las ciudades implica que el problema sereduce a decidir en qué orden las ciudades van a ser visitadas.

2.2 Breve Historia

1. Primeras referencias datan del 1832, para vendedores viajeros.
2. Karl Menger, 1930, (Shortest Hamiltonian Path).
3. J.B. Robinson, “On the Hamiltonian game (a traveling-salesman problem)”, 1949. Esta es la primera referencia del problema como es conocido hoy en dia.
4. G. Dantzig,...