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.

No podemos dejar de lado el método de solución de ramificación. Este es un método matricial en el cual se tiene un algoritmo que funciona de manera tal en que analiza una matriz en la cual se ingresan todas las distancias entre ciudades; este algoritmo lo que hace es analizar cada una de estas distancias y después de X tiempo nos arroja un resultado óptimo al problema. El único defecto de este método es que, si se ingresa una matriz de datos muy grandes tanto en cantidad como en valores, este se toma un muy buen tiempo en arrojar una solución.

Objetivos

• Aplicar los conocimientos adquiridos a lo largo del curso para la formulación de un algoritmo adecuado que permita resolver el problema.
• Emplear diversos métodos aprendidos en la materia para realizar una comparación apropiada
• Elegir el método más apropiado para la resolución del problema.
• Encontrar la solución con el debido procedimiento teórico que garantice la resolución del problema en el menor número de operaciones posibles.

Ventajas y desventajas

Ventajas:

• Es un problema que tiene varias soluciones, dando así flexibilidad a la hora de resolverlo.
• Puede ser muy útil porque se puede aplicar a casos de la vida real para lograr la optimización adecuada, por ejemplo, en la logística, robótica, turismo, entre otros.
• El problema se puede adaptar a varias variables, es decir, se puede ajustar para encontrar particularmente soluciones que sirven a la hora de aplicar este método.
• Es un problema que siempre está abierto a que se encuentren más y más soluciones óptimas, es decir, a través del tiempo más personas encontrarán soluciones que ayudarán a mejorar continuamente sus aplicaciones.

Desventajas:

• Es considerado uno de los problemas de optimización más complejos de solucionar, la parte computacional es complicada y aún no se tiene una solución enteramente perfecta.
• No se puede garantizar que se encontrará una solución.

Aplicaciones

Situaciones de logística:

En un ambiente industrial en el cual se requiere la automatización de los procesos es de suma importancia buscar la manera más optima de realizar ciertas tareas. La optimización de variables como el consumo energético o el tiempo para realizar una tarea se traduce en dinero y productividad.

Planificación:

Todo se puede traducir en consumir los menores recursos posibles para optimizar la utilidad.  En una empresa de transporte de carga o de mensajería se aplica en la planeación de los recorridos de cada flota buscando reducir el consumo de combustible y la optimización de los tiempos de recogida o entrega.

...