Modelo TSP
Enviado por Miguel Altamar • 14 de Julio de 2019 • Trabajo • 1.048 Palabras (5 Páginas) • 185 Visitas
RESUMEN
En el presente trabajo se describe la implementación de la metodología del TSP (Traveling Salesman Problem) o problema del agente viajero a unos centros comerciales de la ciudad de Barranquilla, con la finalidad de encontrar la ruta optima partiendo desde un sitio determinado, es decir, minimizar la distancia que se debe recorrer partiendo desde la casa sin dejar de visitar ningún centro comercial. El total de la distancia que se recorrería sin haber hecho un análisis detallado para minimizar la distancia a recorrer era de 47,95 km; una vez resuelto el problema del agente viajero en el sistema WinQSB se observó que se puede reducir la distancia recorrida a 5,9 km, lo que representa una disminución de 12,30% del total que se tenía. De igual forma se hizo el planteamiento de programación lineal aplicando el modelo matemático del TSP.
- OBJETIVO GENERAL
El objetivo de este trabajo es determinar la ruta optima a recorrer mediante el algoritmo del TSP para la minimización de la distancia recorrida entre 8 lugares.
1.1 OBJETIVOS ESPECÍFICOS
- Recolectar la información necesaria para obtener datos de ubicaciones de los centros comerciales y sus distancias.
- Diseñar un modelo de programación lineal representativo del caso de estudio.
- Resolver el modelo matemático mediante la herramienta Solver de Excel para obtener la solución.
- Resolver el problema de mediante la herramienta WinQSB utilizando la matriz de distancias de los 8 nodos.
- ASPECTOS TEÓRICOS
Problema del agente viajero
El problema del agente viajero o TSP por sus siglas en inglés (Travelling Salesman Problem) es uno de los problemas más famosos y complejos de las ciencias computacionales y ha sido abordado por varias ramas de la ingeniería y por distintas razones, su principal aplicación es la de rutear desde distintas perspectivas, ya sea un proceso que lleva una secuencia específica o una distribución de carácter logístico en la que intervienen elementos del transporte, buscando la mejor ruta posible con criterios de economía en distancia o en costo. Proveer soluciones contribuye a mejorar tareas y procesos en distintos ámbitos, científicos e industriales, proponiendo alternativas para el mejor uso de los recursos. Disciplinas que abordan este tema son la investigación de operaciones y la ciencia informática como algoritmia y teoría de grafos (López, 2008) [1]
El problema del agente viajero está dado por el siguiente modelo matemático:
[pic 2]
[pic 3]
[pic 4]
[pic 5]
(a)[pic 6]
(b)[pic 7]
(c)[pic 8][pic 9]
[pic 10]
[pic 11]
[pic 12]
Las restricciones (a) aseguran que se llegue solo una vez a cada sitio. Las restricciones (b) aseguran que se parta desde sitio. Las restricciones (c) son las fundamentales, ellas aseguran que:
- Cualquier conjunto de valores de x ij que conformen un subtour no sean soluciones factibles.
- Cualquier conjunto de valores de x ij que conformen un tour sea una solución factible.
Llamaremos tour a cualquier camino que satisfaga todas las condiciones del problema del vendedor viajero, es decir, pase por todos los puntos sin repetir, comience y termine en el mismo punto.
Un subtour es un camino cerrado, que comienza y termina en la misma ciudad, pero que no pasa por todas las ciudades.
Las variables representan la posición en el tour. [2][pic 13]
- Obtención y análisis de datos.
Para la realización del caso de estudio se tomaron en cuenta 8 sitios, 7 de ellos centros comerciales y una casa la cual fue tomada como el punto de partida. Para el cálculo de las distancias entre los diferentes sitios se utilizó la herramienta Google Maps y Google Earth.
Figura 1. Ubicación de los sitios
[pic 14]
Fuente. Google Earth
Se obtuvieron las siguientes distancias dadas en km:
Tabla 1. Matriz de distancias entre cada sitio.
[pic 15]
Fuente. Google Maps
- FORMULACIÓN DEL MODELO
[pic 16]
[pic 17]
[pic 18]
El objetivo es:
[pic 19]
[pic 20]
[pic 21]
[pic 22]
[pic 23]
[pic 24]
[pic 25]
[pic 26]
(Distancia recorrida)
Sujeto a:
[pic 27]
Esta restricción garantiza que desde cada lugar i, solo se puede llegar a un lugar j.
[pic 28]
Esta restricción asegura que a cada lugar j solo se podrá llegar desde un lugar i.
[pic 29]
Restricción de subtour
[pic 30]
...