Problema del Agente Viajero PDF

Preview

Summary

Modelos con ejemplos de Optimización y un Caso de Ejemplo...

Description

Problema del agente viajero TSP. Cristian David Sosa Aguirre. Modelos Matemáticos de Ingeniería – Programa Maestría en Ingeniería Eléctrica. Universidad Tecnológica de Pereira. [email protected].

Abstract- En el presente documento se encuentra información sobre la solución de un ejemplo del problema del agente viajero (TSP), el cual es un problema de programación lineal entera, para ello se utiliza la herramienta intlinprog de Matlab. Se muestran los resultados, código de programación y explicación general del problema. I.

INTRODUCCIÓN

A. Programación Lineal Entera. La programación lineal entera es un tipo de programación que tiene como fin resolver modelos matemáticos que son de carácter únicamente lineal y las variables son de carácter entero, a su vez el objetivo es poder optimizar alguna problemática ya sea encontrando el valor mínimo o el máximo de la función objetivo que se analiza. Un problema de programación matemática requiere de 4 componentes básicos:    

Conjunto de datos. Conjunto de variables involucradas y sus dominios. Conjunto de restricciones (región factible). Función objetivo.

B. El Problema del Agente Viajero TSP.

Fig 1. Modelo matemático del TSP.

Además se debe cumplir que el número de enlaces sea igual al número de nodos. El anterior modelo funciona correctamente en un sistema con pocos nodos sin embargo puede suceder lo siguiente:

El problema del TSP consiste en determinar la ruta más corta para visitar cada ciudad exactamente una vez, retornando al final al punto de partida. 1. Características del TSP:    

Es uno de los problemas más ampliamente estudiados en optimización computacional. Pertenece a la clase de problemas NP-difíciles. Aparece en variadas aplicaciones prácticas, bien sea solo o como subproblema de otros. Ha sido motor del desarrollo de teoría matemática, algoritmos e implementaciones.

2. Formulación: Datos de entrada: Un grafo completo (V,E) con N nodos, un vector de costos c E Q sobre las aristas  Objetivo: Seleccionar un conjunto de aristas, que formen un ciclo, que visiten todos los nodos y cuya suma sea la menor posible. 3. Modelo de optimización. 

Fig 2. Ejemplo de solución.

La anterior imagen, muestra una solución con subciclos que cumple con el modelo y las restricciones descritas en la figura 1, pero no corresponde a la solución general, para ello se le debe añadir una nueva restricción que no permita los subciclos. Varios modelos permiten solucionar este problema, el primero es el modelo DFJ. Es la siguiente restricción.

  Fig 3. Restricción para eliminar los subciclos, modelo DFJ.

Lo que indica la anterior ecuación, es que para un conjunto de nodos que pertenecen a un posible corte, la sumatoria de los posibles enlaces que pertenecen a los nodos seleccionados para el corte, debe ser menor o igual, al tamaño del conjunto de los nodos seleccionados al corte menos una unidad. De tal manera que el conjunto de nodos no puede ser el vacío y tampoco la totalidad de los nodos. El anterior modelo elimina los subciclos sin embargo de manera general se tienen las siguientes observaciones:   

El modelo tiene N(N-1)/2 ecuaciones. N restricciones de grado. 2^N-2 restricciones de eliminación de subciclos.

Para no evaluar todas las posibilidades de los cortes lo que se realiza es el siguiente proceso iterativo:  



   

Se tiene una restricción para cada enlace del modelo. Los enlaces que salgan del nodo número 1 o lleguen al enlace número 1 no se tienen en cuenta. Los enlaces i=j no se tienen en cuenta. Yij, es el enlace que va desde i hasta j. N: Es el número de nodos Se generan N variables U, debido a los N nodos que tengan el problema del TSP, estas variables son de carácter binario, por lo que al modelo original se le deben añadir pequeñas modificaciones por la creación de estas nuevas variables.

C. Modelo Implementado en Matlab. Para resolver este problema del TSP, se utiliza la herramienta intlinprog de Matlab, para ello se realiza la programación correspondiente para poder utilizar la función intlinprog.

Se plantea el modelo de la figura1, se resuelve y si la solución contiene subciclos, para cada subciclo se implementa la restricción de la figura3. Luego se vuelve a correr el modelo teniendo las restricciones de los ciclos, si aparecen nuevos subciclos se realiza lo mismo del paso anterior y este. Una vez se encuentre una solución donde no hayan subciclos se puede garantizar que se encuentra la solución óptima, ya que va a ser la única solución donde el número de enlaces es igual al numero de nodos, además que optimizador en cada iteración siempre esta buscando la ruta más corta, y que al ser un problema de programación lineal entera, siempre se encuentra el óptimo global.

De esta manera se evita evaluar todos los ciclos posibles, esta manera se le denomina eliminación por Dantzing Fulkerson-Johnson Constraints. Otra forma de eliminar los subciclos es implementando la ecuación de Tucker-Zemlin Constraints.

Fig 5. Herramienta intlinprog.

II.

Fig 4. Ecuación MTZ para eliminar los subciclos.

Con esta ecuación, se evita evaluar todos los posibles cortes y el proceso iterativo, encontrando la solución óptima global de manera más rápida computacionalmente. Sin embargo de la ecuación anterior se obtiene las siguientes interpretaciones:

EJERCICIO DE APLICACIÓN

Para entender el problema del TSP, se presenta los siguientes ejemplos aplicativos, con su respectiva solución programado en Matlab. La solución se presenta utilizando el método DFJ, MTZ y utilizando el software Condor especializado para resolver este problema del TSP, para un ejemplo de 20, 50, 100, 200 y 300 nodos. Cada uno resuelto por las 3 metodologías respectivas.

 Número de cortes utilizados: 7.  Tiempo de computo: 1.6222 s.  Función Objetivo: 397,8875 unidades. 2. Ejemplo de 50 nodos.

Nota:   

El modelo DFJ fue programado por el profesor granada. El software Condor, es un programa especializado para este problema de libre uso. El modelo MTZ, se reutiliza cierto código programado por el profesor para resolver el DFJ y a partir de este se construye el modelo MTZ.

Los archivos de Matlab se anexan junto este informe y el documento en Excel que contiene las coordenadas de los puntos para cada caso. A. Modelo DFJ 1. Ejemplo de 20 nodos.

Fig 8. Ejemplo sin implementar DFJ.

Fig 6. Ejemplo sin implementar DFJ.

Fig 9. Ejemplo implementando DFJ.

  

Fig 7. Ejemplo implementando DFJ.

Número de cortes utilizados: 20. Tiempo de computo: 2.05 s. Función Objetivo: 558.9376 unidades.

3. Ejemplo de 100 nodos. 4. Ejemplo de 200 nodos.

Fig 10. Ejemplo sin implementar DFJ.

Fig 12. Ejemplo sin implementar DFJ.

Fig 11. Ejemplo implementando DFJ.

  

Número de cortes utilizados: 33. Tiempo de computo: 9.7 s. Función Objetivo:777.6121 unidades.

Fig 13. Ejemplo implementando DFJ.

  

Número de cortes utilizados: 69. Tiempo de computo: 610.22 s. Función Objetivo: 1079.1 unidades.

Fig 16. Ejemplo implementando con Concorde.

 

5. Ejemplo de 300 nodos.

Tiempo de computo: 0.31 s. Función Objetivo: 560 unidades.

3. Ejemplo de 100 nodos.

Fig 17. Ejemplo implementando con Concorde.

 

Tiempo de computo: 0.37 s. Función Objetivo: 773 unidades.

4. Ejemplo de 200 nodos.

Fig 14. Ejemplo sin implementar DFJ.

Para 300 nodos el computador resolviendo el modelo del TSP con el DFJ no fue capaz de realizarlo. B. Modelo con Concorde. 1. Ejemplo de 20 nodos.

Fig 18. Ejemplo implementando con Concorde.

 

Tiempo de computo: 0.61 s. Función Objetivo: 1074 unidades.

5. Ejemplo de 300 nodos.

Fig 15. Ejemplo implementando con Concorde.

 

Tiempo de computo: 0.14 s. Función Objetivo: 397 unidades.

2. Ejemplo de 50 nodos.

 

Tiempo de computo: 1.95 s. Función Objetivo: 1295 unidades.

C. Modelo con MTZ 1. Ejemplo de 20 nodos. 2. Ejemplo de 50 nodos. 3. Ejemplo de 100 nodos. 4. Ejemplo de 200 nodos. 5. Ejemplo de 300 nodos.

III.

CONCLUSIONES REFERENCIAS

[ CITATION Mau19 \l 9226 ] M. Granada, Curso Modelos Matematicos de Ingenieria, Pereira, 2019. Universidad Tecnológica de Pereira....