Algoritmo del problema del agente viajero

Introducción

En esta monografía se hablará de el Problema del Agente Viajero o Traveling Salesperson Problem en ingles.

El cual debe resolver el problema de una persona que debe recorrer varios puntos de una ciudad, pero debe hacer el recorrido de cada punto en una distancia mínima.

Este problema sirve de mucho en la vida real ya que facilita el trabajo de vendedores en recorrer rutas de sus clientes a cortas distancias y a bajo costo.

Resumen

En la historia se desarrollará quienes plantearon este problema y la fecha en la que se hizo.

Se mencionarán tres definiciones de diferentes autores.

Se dará a conocer tipos de aplicaciones de este problema.

Se desarrollarán varios ejemplos del problema del agente viajero.

Historia

La primera fecha de referencia del problema data del año: 1832.

"Shortest Hamiltonian Path" ("Camino Hamiltoniano corto" en espan˜ ol) de Karl Menger en 1930.

"On the Hamiltonian game (a traveling-salesman problem)" de J.B. Robinson en 1949 Este es el primer ejemplo del problema como se conoce actualmente.

Pero luego este problema se volvió mas notorio cuando George Dantzik, Ray Fulkerson y Selmer Johnson publicaron un metodo de solucion de problema del agente viajero en 49 ciudades de Estados Unidos. "Soluciones de gran escala para el P.A.V" – 1954.

"A Dynamic Programming Approach to Sequencing Problems" de M.Held y R.M. Karp en 1962.

Definición

Primera definición:

El peso total de un circuito es la suma de los pesos de las aristas que lo conforman.[1]M icha, Elias (p.57)

Segunda definición:

El PAV tiene que ver con la determinacion del viaje mas corto con n ciudades, la cual se visita solo una vez.[2]H amdy, T aha (p.390) El caso se define:

Si dij es la distancia de la ciudad i a la ciudad j, entonces el modelo del agente viajero sera:

Tercera definición:

Sea G un grafo ponderado completo donde cada vértice es una ciudad y cada arista una distancia entre ellas. El P.A.V. busca encontrar un circuito hamiltoniano de peso mínimo para G. El número de permutaciones P que se pueden encontrar es: P = (n – 1)!/2. donde n es el número de vértices.[3]Lipson, M arc & Lipschutz, Seymour (p.176)

Tipos

El P.A.V. tiene aplicaciones en los siguientes ejemplos:

Ruta de vehiculos.

Bus escolar.

Atención de llamadas de emergencia.

Servicio de correo expreso. Secuencia de genes.

Ordenamiento de observaciones en telescopios (NASA).

Diseño de chips.

Tour mundial.

Ejemplos

El grafo completo Kn con n = 3 vértices tiene H=(n-1)!/2 circuitos hamilonianos(donde no se distingue entre un circuito y su opuesto)

Con cuatro vértices este grafo tiene H=3 circuitos hamiltonianos, los circuitos empiezan desde A y se muestran sus circuitos y sus pesos.

|ABCDA| = 3 + 5 + 6 + 7 = 21

|ACDBA| = 2 + 6 + 9 + 3 = 20

|ACBDA| = 2 + 5 + 9 + 7 = 23

En conclusion el recorrido es |ACDBA| con un peso mínimo de 20.[1]Lipson, M arc & Lipschutz, Seymour (p.177)

Conclusión

El algoritmo del Problema del Agente Viajero se utiliza más que todo para acortar las distancias que hay entre ciudades, por lugares a los cuales se debe llegar por medio de un transporte cualquiera, pero que este mismo viaje debe requerir la mínima cantidad de dinero gastado posible.

Como se ve en un ejemplo el número de permutaciones siempre dependerá del número de vértices, esto quiere decir que si existen pocos vértices menor será el número pero mientras más vertices existan en el grafo será mayor el número de permutaciones al punto de que un supercomputador podría demorarse de minutos hasta an˜ os en la resolución de este problema solo dependiendo de su número de vértices.

Este tema me parece muy interesante sobre todo si se trata de personas que su trabajo es salir a diferentes puntos de una ciudad o país pero viendo la forma de gastar lo mínimo en dinero.

Recomendación

Mi recomendación sería simplemente que cada persona que quiera iniciar un negocio que tenga que ver con el recorrido de distancias para el servicio que ofrezcan, una de las soluciones pueden ser aplicar este algoritmo a las distancias que recorran así no gastarían mucho presupuesto o combustible.

Me dirijo específicamente a las pequen˜ as empresas que ofrecen el servicio de tour en Puno para los turistas que llegan y quieren conocer más de nuestra cultura.

Bibliografía

[1]Micha, Elias (2003). Matemá ticas Discretas. México: LIMUSA.

[2]Hamdy, Taha (2004). Investigación De Operaciones. México: Pearson Educación.

[3]Lipson, Marc & Lipschutz, Seymour (2007). Matemá ticas Discretas. México: McGraw-Hill Companies.

Anexos

Desarrollo del P.A.V. en el paso de los años:

Dedicatoria

Dedico esta monografía a: mi familia quien influyó en mi para que yo continue en su elaboración…

Agradecimiento

Agradezco a mi familia quienes persisten en mi formación como estudiante y a mi docente quien influye en el trajin diario de mi formación profesional…

Autor:

Andree Montes de Oca Vallenas

UNIVERSIDAD NACIONAL DEL ALTIPLANO

Facultad de Ingeniería Mecánica-Elétrica, Electrónica y Sistémas

Escuela Profesional de Ingeniería de Sistémas

2013