Procesos numéricos. Problema del viajero

Procesos numéricos

Problema del viajero

Integrantes:

Juan Pablo Acevedo Calderón - jpacevedoc@eafit.edu.co

Andrés Cano Agudelo - acanoa@eafit.edu.co

Laura Betancur Beltrán – lbetancurb@eafit.edu.co

Docente:

Carlos Alberto Álvarez Henao

Universidad EAFIT

23 de noviembre 2021

Tabla de contenido

1. Introducción
2. Historia
3. Marco teórico
4. Objetivos de la investigación
5. Ventajas y desventajas del tema a tratar
6. Aplicaciones
7. Conclusiones
8. Bibliografía

Introducción

El problema del viajero o Traveling Salesman Problem (TSP) es un problema de optimización que se caracteriza por la necesidad de hallar la mejor forma para encontrar la ruta adecuada y más corta para visitar todas las ciudades (únicamente una vez) y volver a la ciudad de partida.

En este trabajo se tratará el estudio de este problema considerado uno de los más conocidos en el tema de optimización y al mismo tiempo uno de los más complejos de resolver. El estudio de este problema tiene una gran importancia, ya que, varias problemáticas del mundo real se pueden formular a partir de este.

Se abordará la solución y la programación de este problema, al mismo tiempo se mostrará el paso a paso de la investigación y resultados obtenidos.

Palabras clave:

• TSP: Traveling Salesman Problem.
• Recorrido.
• Nodos.
• Ramificación.
• Heurístico.
• Algoritmo.

Historia

1800-1832: El problema del viajero es mencionado en un manual (realmente se desconoce el origen de este problema de optimización), donde mencionan una posible solución tomando como ejemplos recorridos por Alemania y Suiza.

los matemáticos W.R Hamilton y Thomas Kirkman fueron los pioneros en la investigación de este famoso problema.

1857: Hamilton propuso “el problema del ciclo hamiltoniano” en un determinado grafo de un dodecaedro. (Fig 1)

[pic 1]

Fig. 1. Grafo de un dodecaedro.

1930:  El TSP fue estudiado por el matemático Karl Menger junto con las universidades de Harvard y Viena, donde se descubrió que algunas lógicas no eran óptimas. Además, alrededor de estos tiempos se le otorgó el nombre de traveling salesman problem.

1950-1960: La contribución de los matemáticos George Dantzig, Delbert Ray Fulkerson y Selmer M. Johnson fue que lograron mostrar el problema como programación lineal en enteros y encontraron una solución partiendo del método de planos cortantes. (lograron resolver el problema con 49 ciudades e indicando que no existía un camino más corto).

1972: Richard M. Karp demostró que el famoso problema del ciclo de Hamilton realmente era un problema NP-completo y el problema del viajero un NP-duro.

1980: Se logró encontrar la solución de 2392 instancias usando el método de planos cortantes.

1990: Se desarrolla el programa Concorde, actualmente muy utilizado para la solución de este problema. Applegate, Bixby, Chvátal, y Cook fueron los desarrolladores.

2006: Cook y otros lograron un recorrido óptimo de 85.900 ciudades usando TSPLIB, siendo este la mayor instancia encontrada.

Marco teórico

Estamos ante uno de los problemas más estudiados a lo largo de los últimos años “el problema del viajero o Traveling Salesman Problem (TSP)” ha sido investigado desde diversas áreas del conocimiento, si bien ha sido analizado mayormente desde el área de la programación matemática, así como la programación lineal, optimización, incluso se volvió aún más famoso por su nivel de complejidad computacional; estás ramas del conocimiento se han dedicado a plantear diversas soluciones aparentemente absolutas al problema. Esto se debe a que al ser un problema abierto se aplica en la industria, mercados bursátiles, turismo, planificación, logística y distribución, entre otros.

Se plantea de la siguiente manera: Un comerciante planea trazar el camino más corto desde su lugar de trabajo, en la cual pueda visitar cada una de las ciudades de su lista únicamente una sola vez y regresar a su lugar de origen.

Para ello a lo largo de los años muchos investigadores, matemáticos, doctores y científicos han enfocado sus soluciones en:

El método más elemental para darle solución a este ejercicio consiste en explorar todos los recorridos posibles, sin necesidad de utilizar ningún tipo de algoritmo matemático. Luego de haber trazado todos los recorridos posibles lo siguiente sería definir diferentes rutas en las cuales se cumpla la condición de no repetir ciudades. Este método es el más simple para entender el concepto del problema, pero el menos práctico al momento de darle una solución práctica al problema.

Otra forma de solucionar este problema ha sido abordado desde la condición de que esta la solución depende de que las distancias entre un nodo y otro sean simétricas o no, es decir, de la ciudad A a la ciudad B la distancia a recorrer debe ser la misma que desde B hasta A, puesto que en la práctica es muy poco probable que así sea. Esta cantidad de rutas posibles está dada por   En caso de que las distancias no sean simétricas, de ser simétricas la fórmula estaría dada por . [pic 2][pic 3]

EJ: Es decir que en una red de 5 nodos la cantidad de rutas probables es igual a (5-1)! = 24.

Si se aplica la fórmula dada por simetría solo significa un ahorro significativo en el tiempo de procesamiento de rutas de gran tamaño.

Otro método muy analizado fue el heurístico, este consta de un diseño algoritmo el cual consiste en iniciar con establecer un punto de partida fijo; desde este punto se analizará quién es el vecino o la ciudad con la ruta más corta desde el punto de inicio. Una vez el viajero se haya desplazado a la siguiente ciudad se vuelve a hacer el mismo análisis, pero esta vez omitiremos la ciudad de la que el viajero acaba de salir. El método se seguirá desarrollando paulatinamente de la misma manera hasta llegar al último destino. Cabe aclarar que en muchas ocasiones este método no es el más efectivo, pero siempre sirve para obtener muy buenas conclusiones de los resultados.

...