miércoles, 19 de noviembre de 2014

Grupo 4: Agente Viajero (TSP)




Problema de Agente Viajero
 ( Traveling Salesman Problem)

El problema del agente viajero o TSP por sus siglas en inglés (Travelling Salesmen 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 ratear 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 las ciencias informáticas como algoritmia y teoría de grafos.


 El TSP se describe como: un agente viajero desea programar visitas a sus clientes en diferentes ciudades, por lo que desea viajar lo mínimo posible. Así, se encuentra en el problema de determinar una ruta que minimice la distancia total (o bien tiempo o costo) necesaria para visitar todas las ciudades en su zona.

A las ciudades o a los puntos de partida y llegadas se les llama nodos y los caminos entre ellos se llama arcos. Existen arcos dirigido y no dirigidos los arcos dirigidos  solo pueden ir desde el arco inicial al arco terminal, es como una calle con un solo sentido, si el arco es no dirigido significa que se puede recorrer en doble sentido.

 En estos problemas se construye una ruta de costo mínimo en los cuales cada cliente, ciudades o nodos pasen por lo demás nodos exactamente una vez, es decir;

  • Dado n ciudades (o clientes).
  • Sea Ci j  el costo del viaje desde la ciudad i hasta la ciudad j.
  • Construir una ruta de costo mínimo que visite a cada ciudad                       exactamente una vez.
  • Si Ci j = Cj i  para todas la ciudades, entonces el problema es                 simétrico.
  • Si Ci  Cj i  para algún par de ciudades, entonces el problema es    asimétrico.



Existen numerosos métodos para la resolución de problemas de agente viajero el más exacto es el de la búsqueda exhaustiva o mejor conocido como “Método de fuerza bruta” pero solo es factibles con máximo seis nodos o ciudades debido al tiempo que se debe emplear para su resolución.

Por ejemplo, por exploración exhaustiva del conjunto de soluciones:


  •     Cada solución es una permutación del conjunto de vértices
          V= {1, 2, …, n}
  • En total se tendrían n! soluciones factibles posibles
  •  Con n = 20 ciudades por visitar se requiere evaluar 20! Posibles tours, imposible de realizar en un tiempo razonable.



N
Tiempo
5
1.2 ×10-6 segundos
10
1.2 ×10-6 segundos
15
3.63243 horas
18
741.015 días
20
771.468 años


  

Ejemplo del problema de vendedor viajero por el método de fuerza bruta:

El problema se sitúa dentro de un grafo, en este caso tenemos cinco ciudades y cada nodo es identificado con la primera letra de cada ciudad, además  se muestran los costos asociados para cada arco que representa el costo de traslado entre cada par de ciudades. El problema consiste en que el agente viajero tiene que vender sus productos en las distintas ciudades y debe volver a su lugar de partida u origen; esto debe hacerlo considerando el menor costo posible.


  En este caso se usa la intuición (método de fuerza bruta) para calcular la ruta óptima.

Grafo inicial:( contiene los datos del problema)


                                                                 





  • En el primer intento para conseguir la ruta óptima podemos decir, por ejemplo, que la ruta será partiendo de San Felipe  pasando por Los Teques, Zaraza, Caracas, Valencia, y volviendo a San Felipe, es decir, hacer la ruta por afuera  como muestra el siguiente gráfico en la cual  las suma de los costos asociados es 462.



                                                        





  • Segunda ruta, segundo intento.

                                                     



La suma de los costó de esta ruta es mayor que la primera por ello se descarta.

Así después de probar, podemos llegar a preguntarnos, ¿cuántas son las rutas posibles que se podría considerar  el agente viajero?

Después de analizar se puede concluir que si se tiene un conjunto finito de nodos entonces habrá una solución finita, es decir, N nodos = a una cantidad finita de rutas.

En este caso con cinco nodos y haciendo todas las combinaciones posibles podemos identificar que se pueden hacer veinticuatro combinaciones distintas; analizando en  términos matemáticos y pensando en alguna herramienta que permita agrupar de forma distinta una colección de elementos es posible concluir que cuando se tienen N nodos la cantidad de rutas posibles será de “N-1!”(N menos un factorial); es decir, N nodos = (N-1!) rutas posibles.
 En este caso como N vale cinco se determinan las rutas posibles calculando el factorial de 4. La factorial es una herramienta que permite realizar permutaciones; es decir; resolver el problema de cómo se agrupan una cantidad finita de elementos de forma distinta.

  • 5 nodos = (5-1!) rutas  (se le resta uno porque en la soluciones no se debe incluir el nodo de partida).
  •   = 4!
  •   =24

 Al calcular cada una de las rutas nos damos cuenta que cada una de ellas esta duplicadas, es decir, la solución de una también existe como solución en el sentido inverso.

Por ello la cantidad de rutas reales que se van a considerar corresponde a  (5-1!/2) = 12 rutas posibles. Debido a lo anterior se puede concluir que a medida que crece la cantidad de nodos se hará cada vez más complejo determinar el camino óptimo; sin embargo es el método más efectivo, cuando se resuelven problemas igual o menor a 6 nodos porque no da lugar a error.

A través del método de la “Fuerza Bruta” podremos descubrir que la ruta con el costo mínimo en este caso  es (s, z, c, l, v, s) el cual se muestra en el siguiente gráfico:


                                                         




El T.S.P. sería equivalente a encontrar el ciclo Hamiltoniano de
Costo mínimo: Partiendo de un depósito se debe recorrer todos los
Vértices y regresar al depósito con la menor distancia total
Recorrida.

 Un ejemplo del problema de agente viajero con ciclos Hamiltoniano  se puede resolver  de la siguiente manera:

 Un  agente viajero tiene que recorrer un conjunto de”ciudades unidas entre sí por carreteras. Si conoce el costo de transporte entre cada par de ellas se quiere.

  •   Recorrer todas las ciudades sin pasar 2 veces por alguna de ellas, volviendo a la ciudad de origen, y que el costo de dicho recorrido sea mínimo. (Circuito hamiltoniano).
  • Recorrer todas las ciudades sin pasar 2 veces por alguna de ellas, que el costo del recorrido sea mínimo comenzando por una ciudad dada, sin regresar a ella. (Camino hamiltoniano con origen).
  • Recorrer todas las ciudades, que el costo del recorrido sea mínimo y que la elección de la ciudad de origen sea óptima (Camino hamiltoniano).
Consideremos la matriz  {Cij } m x m donde m es el número de ciudades que hay que recorrer  y sea Ci j el costo de ir de la ciudad i a la ciudad j, además los Ci i son igual a infinito.

El problema del agente viajero equivale a encontrar un circuito hamiltoniano de valor mínimo que una las m ciudades. Es decir equivale a escoger una entrada de cada renglón y de cada columna en la matriz {Cij } tal que la suma de ellas sea mínima.


Se hace muy difícil aplicar técnicas exactas para encontrar la solución óptima, en su lugar se han desarrollado heurísticas para
determinar “buenas soluciones”

HEURÍSTICAS PARA RESOLVER EL TSP

 Las más sencillas están basadas en el sentido común, las
Principales son las heurísticas glotonas:

  • Heurística del vecino más cercano.
  • Heurística de Inserción más cercana.
  • Heurística del Método de ahorros. 


 Heurística del vecino más cercano: Se va construyendo el
Tour secuencialmente, a partir del depósito, eligiendo en
Cada paso como el nodo siguiente al nodo más cercano al
Nodo actual.

  • Paso 1. Seleccionar un nodo inicial


  • Paso 2. Identificar al nodo más cercano al último agregado,

        siempre que no haya sido agregado.

  •  Paso 3. Repetir el paso 2 hasta incluir todos los nodos.


La cota superior garantiza que la solución del TSP aplicando
este algoritmo es a lo más {½(log2 n) }+1/2.

El siguiente ejemplo muestra la resolución de un problema de agente viajero  utilizando el método de “el vecino más cercano”con el software “WinQSB”.

Alberto está  a punto de cumplir 10 años, por lo que su mamá le está organizando una fiesta a la cual podrá invitar a sus 4 amigos más cercanos, Beto, Carlos, Daniel y Ernesto.


Problema:
¿En qué orden debe repartir Alberto las tarjetas de cumpleaños para demorarse lo menos posible a fin de ir a escoger su regalo con su mamá?


 Datos:

                                                        




1 Paso: Cargamos en WinQSB  los datos presentados en el grafo, asumiremos que es distancia por el contexto del problema, por lo que la unidad será en (Km).

                                                  


2 Paso: Una vez cargados los datos del problema, procederemos a dar clic en (Solve and Analyze) señalado con la flecha roja.

                                                      


                                                        

3 Paso: Abrirá la ventana de color naranja y daremos clic nuevamente en «Nearest Neighbor Heuristic» que significa (Heurística del Vecino más cercano). Señalado con la flecha negra. Y luego en SOLVE.

 4 Paso: Se mostrará la solución final encontrada.
                                                               





Heurística de inserción más cercana:

  •             Ir a la ciudad más cercana y retornar.
  •           Insertar la ciudad más cercana a la ruta en la mejor secuencia.


Heurística  de método de ahorros:

  •            Adicionar a la ruta la ciudad o nodo que permite mayor ahorro, una y otra vez hasta volver al nodo de partida.




Algoritmo determinístico

La técnica búsqueda tabú:

La Búsqueda Tabú (BT) es un método metaheurístico que puede utilizarse para resolver problemas de optimización combinatoria, tales como el problema del agente viajero (TSP). La búsqueda tabú utiliza un procedimiento de búsqueda local o por vecindades para moverse iterativamente desde una solución x hacia una solución x* en la vecindad de x, hasta satisfacer algún criterio de parada. Para poder explorar regiones del espacio de búsqueda que serían dejadas de lado por el procedimiento de búsqueda local, la búsqueda tabú modifica la estructura de vecinos para cada solución a medida que la búsqueda progresa. Las soluciones admitidas para N*(x), el nuevo vecindario, son determinadas mediante el uso de estructuras de memoria. La búsqueda entonces progresa moviéndose iterativamente de una solución x hacia una solución x* en N*(x).

Quizás la estructura de memoria más importante usada para determinar las soluciones permitidas a un N*(x), sea la lista tabú. En su forma más simple, una lista tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos de n iteraciones atrás, donde n es el número de soluciones previas que van a ser almacenadas). La búsqueda tabú
Excluye las soluciones en la lista tabú de N*(x). Una variación de la lista tabú prohibe soluciones que tienen ciertos atributos.

Esta  técnica de búsqueda tabú para la resolución de problemas de agente viajero es utilizado en su mayoría  cuando el número de nodos o ciudades a visitar es mayor a 15 o 20 debido a su complejidad, y se utilidad software de programación como el conocido “Matlab” usualmente por expertos en programación computacional.

Por último se puede agregar, que existen otros programas computacionales que se pueden utilizar para  la resolución de problemas complejos del agente viajero, como el programa estadístico Excel con su aplicación solver, WinQSB, java tabú; entre los mas usados.









                                                                


martes, 18 de noviembre de 2014

Árbol Mínimo Expandido


Grupo 2: Gleidimar Cuenca, Yiberlys Oliveros, Maira Pérez y Solmari Porras.



Cuando hablamos de Árbol Mínimo Expandido, nos referimos a la unión de nodos dentro de una red. Esta debe estar unida de tal manera que no se creen ciclos y así, los nodos se unan para las distancias mínimas o costos mínimos, sea el caso.
El Árbol Mínimo Expandido es apropiado para problemas, en los cuales, la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.


¿Para qué se utiliza?                    
Principalmente se utiliza para planificar y diseñar redes de cualquier tipo. Es una buena forma de establecer planes eficientes dentro de una comunidad; por ejemplo, en la planificación de servicios públicos, como el servicio de agua, de alumbrado, de transporte, entre otros.


Objetivo
Tal y como se señala el principal objetivo del Árbol Mínimo Expandido es minimizar las distancias o los costos, bien sea el caso que deseamos resolver.

Problema

A continuación, presentamos un ejemplo sencillo y fácil de entender para la ejecución de este método:
   La operadora de acueductos HidroCapital, requiere suministrar agua a varios sectores del este de la ciudad de Caracas. En el siguiente gráfico se presentan los diferentes puntos donde se debe abastecer el servicio de agua:

Gráfico #1
Determinar la forma más económica de suministrar agua a todos los sectores a través de un Árbol Mínimo Expandido.

Solución
 
Para resolver este problema, utilizamos como herramienta el programa TORA
El procedimiento se realizó de la siguiente manera:
Abrimos el programa y damos "Click Here"


Luego, damos click a "Network models" y siguiente a "Minimal Spanning Tree"


Le colocamos nombre al problema en "Problem Title" y seguidamente el número de nodos "No. of Nodes"; en este caso, son 8 nodos que serían los sectores. Agregamos todos los datos que nos muestra el Gráfico #1 con respecto a los nodos A, B, C, D, E, F, G y H. En la tabla se muestra, respectivamente, los costos (miles de Bs.) que hay entre un nodo y otro. Después de llenar la tabla, damos click a "SOLVE Menu"


Nos pide para "salvar" el documento. Damos click a "Si" y lo guardamos en cualquier parte de nuestro disco duro.



Luego damos click a "Solve Problem" y después a "Go To Output Screen"

Seguidamente, en "Starting Node" seleccionamos cualquier nodo que representaría el "nodo de partida o inicio" como tal, y damos click a "All Iterations" y "Aceptamos" lo que nos pide.
Se observa entonces una lista de las conexiones de los nodos que serían los más económicos con respecto a la construcción de tuberías para suministrar agua hacia los sectores.


Y el nuevo gráfico, de acuerdo a los resultados de TORA, queda de la siguiente manera:

Gráfico #2



En conclusión, se reduce a 25 mil Bs., el costo total de la construcción de tuberías para el suministro de agua hacia los diversos sectores del este de Caracas.


Conceptos básicos
  • Árbol: una serie de nodos que no contienen ciclos
  • Árbol Expandido: es un árbol que conecta todo los nodos de la red  (contiene n-1 arcos).
  • Arcos: líneas, ligaduras o ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales.
  • Nodos: puntos o vértices.