Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

PROBLEMA DEL AGENTE VIAJERO

expo IDO
by

Silvia Malavar

on 14 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PROBLEMA DEL AGENTE VIAJERO

Problema del Agente Viajero (TSP) ¿En qué consiste? Aplicaciones Historia Modelo El Problema del Agente Viajero puede resolverse de diferentes maneras: Ejemplo • Reparto de productos.
• Transporte.
• Robótica.
• Turismo y agencias de viajes.
• Horarios de transportes laborales y/o escolares.
• Inspecciones a sitios remotos.
• Secuencias. Inicia em 1850. William Rowan Hamilton, y Thomas Penyngton Kirkman . Y es justamente a Hamilton a quien se le debe el término de circuitos hamiltonianos. solución del problema del agente viajero desde un punto de vista gráfico,originado en un juego inventado por este matemático en 1859. • Enumeración de todas las soluciones factibles. •Métodos exactos. También llamados algoritmos óptimos, intentan descartar familias enteras de posibles soluciones, tratando así de acelerar la búsqueda y llegar a una óptima.
• Heurísticas. Son métodos obtienen buenas soluciones en tiempos de cómputo muy cortos. las rutas posibles entre 12 ciudades son 479.001.600combinaciones y los caminos individuales entre ciudades son el sumatorio delas 12-1 ciudades es decir 66.
PLANTEAMIENTO DEL PROBLEMA
El problema consiste en determinar la mejor ruta o mínimo recorrido, que serealice entre las 12 ciudades, partiendo desde un punto de partida yregresando a este (ciclo Hamiltoniano), además se tiene que visitar todas lasciudades una sola vez. A continuación se mencionan las ciudades de trabajo:
Bogotá
Cali
Medellín
Pasto
Bucaramanga
Villavicencio
Armenia
Valledupar
Leticia
Yopal
Florencia
Puerto Inírida el PAV iba ganando notoriedad como un problema prototipo de problemas duros en optimización combinatoria
Este problema se abrió camino cuando George Dantzig, Ray Fulkerson, y Selmer Johnson (1954) publicaron una descripción de un método de solución del PAV titulado “Solutions of a large scale traveling salesman problem“, “Soluciones de gran escala para el problema del agente viajero”. para resolver una instancia de 49 ciudades, un agente viajero o bien una persona que desea visitar un conjunto n de ciudades y que se le dan los costos, las distancias o el tiempo de viajar de una ciudad que le podemos llamar i a una ciudad que le podemos llamar j.
Y tiene dos condiciones:regresar a la misma ciudad de la cual partió y no repetir ciudades, es decir, si ya visitó laciudad 3 una vez ya no se puede volver a pasar por esa ciudad. Con el objetivo de encontrar una ruta o un camino que sea el más corto posible. Algunas heurísticas para el Problema del Agente Viajero Asimétrico El vecino más cercano (heurística constructiva).

Moverse de una ciudad a la siguiente, de tal forma que, de todas las opciones, la ciudad elegida sea la más cercana a donde se encuentra ubicado el agente viajero Inserción aleatorizada (heurística constructiva)

consiste en crear una ruta inicial de la forma más económica posible, después elegir una trayectoria de forma aleatoria, y eliminar los vértices que pertenecen a ella Búsqueda local (2-opt).

El movimiento 2-Opt consiste en eliminar dos aristas rompiendo una ruta inicial en dos caminos, y reconectándolos de una manera diferente para obtener un nuevo ciclo Conclusiones
• En general, los dos algoritmos constructivos son capaces
de llegar al óptimo en instancias pequeñas, todos con un
tiempo de cómputo pequeño.
• En instancias grandes, la miopía del vecino más cercano se hace evidente, sin embargo, es el algoritmo con el mejor tiempo de cómputo, esto es, el más rápido.
• La inserción aleatorizada ofrece soluciones de buena calidad aun en instancias grandes, pero es más tardada que el vecino más cercano.
• La búsqueda local unida al vecino más cercano genera una mejora significativa sin comprometer el tiempo. Unida a la inserción aleatorizada, sigue obteniendo muy buenas soluciones, sin embargo, el tiempo aumenta considerablemente.
• Para decidir qué algoritmo utilizar se debe ponderar tanto el tiempo que se tiene para dar una solución, así como qué tan estricta es la exigencia de la calidad de la solución.
Full transcript