Medio ambiente en la UPTC
Páginas: 11 (2535 palabras)
Publicado: 5 de julio de 2014
PROBLEMA DEL AGENTE VIAJERO
Diego Parra
Victor Puerto
El problema del agente viajero es uno de los problemas más estudiados en Inteligencia artificial e investigación Operativa. Este se centra en estudiar problemas de la siguiente clase: un comercial debe visitar varios clientes y desea conocer cuál es el camino de mínima distancia que, partiendo de su lugar de trabajo, vaya a todas lasciudades y regrese.
Este problema de apariencia sencilla es famoso por su gran complejidad computacional. Puesto que encuadra dentro de la categoría NP-hard por lo que, al día de hoy, no se ha encontrado ningún algoritmo que logre resolverlo en un tiempo polinómico. No obstante, su importancia no se debe únicamente a la complejidad de su resolución, sino a la gran variedad de situacionesprácticas en las que puede ser aplicado. La mayor parte de estas se encuentran en el campo de la logística (reparto de mercancías, correo, rutas escolares), aunque también podemos encontrar aplicaciones de estos problemas en industria (producción de circuitos integrados) o en genética.
PROBLEMAS DE RUTAS (Clasificación del problema del agente viajero)
La importancia de esta clase de problemas sedebe al gran número de situaciones de logística y distribución reales en las que se puede aplicar. Debido al potencial ahorro de estas técnicas, las inversiones en investigación y software de las empresas relacionadas con el sector logístico han ido aumentando considerablemente en los últimos años.
En el siguiente cuadro se encuentran los tipos más importantes de problemas de rutas junto con losnombres que históricamente han recibido.
Como se puede observar en el cuadro, existen dos grandes tipos de problemas de rutas según los clientes se encuentren sobre los nodos o sobre los arcos. En el primero de los casos, la ruta óptima a determinar debe visitar todos los nodos, mientras que, en el segundo, se deben recorrer todos los arcos del grafo que define el problema.
Los problemasde rutas sobre nodos tienen su origen en el siglo XIX cuando el irlandés W.R. Hamilton y el británico T. Kirkman inventaron el denominado “Icosian Game". Este juego consistía en encontrar una ruta entre los 20 puntos del juego usando sólo los caminos permitidos y regresando al nodo origen.
Los problemas de rutas sobre arcos tienen su origen en el siglo XVIII cuando los habitantes deKonigsberg, un pequeño pueblo de la actual Rusia, empezaron a debatir si existía alguna ruta que pasase una única vez por los siete (7) puentes que atravesaban el río Pregel y volviese al punto de origen.
EL PROBLEMA DEL VIAJERO ANDANTE(Traveling Salesman Problem)
El problema del viajante (TSP) es uno de los problemas más famosos y mas estudiados en su área. A pesar de la aparente sencillez de suplanteamiento, el TSP es uno de los más complejos de resolver.
El problema del agente viajero (TSP), consiste en un agente de ventas que tiene que visitar, n ciudades, comenzando y terminando en la misma ciudad, visitando únicamente una vez cada ciudad, y haciendo el recorrido de costo mínimo, que puede estar expresado en términos de tiempo o distancia, es decir, recorrer el máximo de kilómetros ollevar a cabo un recorrido en el menor tiempo posible.
APLICACIONES DEL TSP
La mayor parte de las mejoras en TSP durante los primeros años estaban motivadas por aplicaciones directas del mismo. El TSP se ha aplicado sobre una gran variedad de problemas que van desde rutas de vendedores hasta la genética. A Continuación, se comentan brevemente algunas de las aplicaciones más importantes delproblema del viajante:
Logística:
Las aplicaciones más directas y más abundantes del TSP se centran en el campo de la logística. El flujo de personas, mercancías y vehículos en torno a una serie de ciudades o clientes se adapta perfectamente a la filosofía del TSP, como ya demostraron los primeros estudiosos del problema. Entre las múltiples aplicaciones logísticas del problema del...
PROBLEMA DEL AGENTE VIAJERO
Diego Parra
Victor Puerto
El problema del agente viajero es uno de los problemas más estudiados en Inteligencia artificial e investigación Operativa. Este se centra en estudiar problemas de la siguiente clase: un comercial debe visitar varios clientes y desea conocer cuál es el camino de mínima distancia que, partiendo de su lugar de trabajo, vaya a todas lasciudades y regrese.
Este problema de apariencia sencilla es famoso por su gran complejidad computacional. Puesto que encuadra dentro de la categoría NP-hard por lo que, al día de hoy, no se ha encontrado ningún algoritmo que logre resolverlo en un tiempo polinómico. No obstante, su importancia no se debe únicamente a la complejidad de su resolución, sino a la gran variedad de situacionesprácticas en las que puede ser aplicado. La mayor parte de estas se encuentran en el campo de la logística (reparto de mercancías, correo, rutas escolares), aunque también podemos encontrar aplicaciones de estos problemas en industria (producción de circuitos integrados) o en genética.
PROBLEMAS DE RUTAS (Clasificación del problema del agente viajero)
La importancia de esta clase de problemas sedebe al gran número de situaciones de logística y distribución reales en las que se puede aplicar. Debido al potencial ahorro de estas técnicas, las inversiones en investigación y software de las empresas relacionadas con el sector logístico han ido aumentando considerablemente en los últimos años.
En el siguiente cuadro se encuentran los tipos más importantes de problemas de rutas junto con losnombres que históricamente han recibido.
Como se puede observar en el cuadro, existen dos grandes tipos de problemas de rutas según los clientes se encuentren sobre los nodos o sobre los arcos. En el primero de los casos, la ruta óptima a determinar debe visitar todos los nodos, mientras que, en el segundo, se deben recorrer todos los arcos del grafo que define el problema.
Los problemasde rutas sobre nodos tienen su origen en el siglo XIX cuando el irlandés W.R. Hamilton y el británico T. Kirkman inventaron el denominado “Icosian Game". Este juego consistía en encontrar una ruta entre los 20 puntos del juego usando sólo los caminos permitidos y regresando al nodo origen.
Los problemas de rutas sobre arcos tienen su origen en el siglo XVIII cuando los habitantes deKonigsberg, un pequeño pueblo de la actual Rusia, empezaron a debatir si existía alguna ruta que pasase una única vez por los siete (7) puentes que atravesaban el río Pregel y volviese al punto de origen.
EL PROBLEMA DEL VIAJERO ANDANTE(Traveling Salesman Problem)
El problema del viajante (TSP) es uno de los problemas más famosos y mas estudiados en su área. A pesar de la aparente sencillez de suplanteamiento, el TSP es uno de los más complejos de resolver.
El problema del agente viajero (TSP), consiste en un agente de ventas que tiene que visitar, n ciudades, comenzando y terminando en la misma ciudad, visitando únicamente una vez cada ciudad, y haciendo el recorrido de costo mínimo, que puede estar expresado en términos de tiempo o distancia, es decir, recorrer el máximo de kilómetros ollevar a cabo un recorrido en el menor tiempo posible.
APLICACIONES DEL TSP
La mayor parte de las mejoras en TSP durante los primeros años estaban motivadas por aplicaciones directas del mismo. El TSP se ha aplicado sobre una gran variedad de problemas que van desde rutas de vendedores hasta la genética. A Continuación, se comentan brevemente algunas de las aplicaciones más importantes delproblema del viajante:
Logística:
Las aplicaciones más directas y más abundantes del TSP se centran en el campo de la logística. El flujo de personas, mercancías y vehículos en torno a una serie de ciudades o clientes se adapta perfectamente a la filosofía del TSP, como ya demostraron los primeros estudiosos del problema. Entre las múltiples aplicaciones logísticas del problema del...
Leer documento completo
Regístrate para leer el documento completo.