Agente viajero

PROBLEMA DEL AGENTE VIAJERO (PAV) Y UNA SOLUCION CON SOLVER DE EXCEL ANDRES MAURICIO CAMACHO SANCHEZ COD. 1032408541 acamachos@ucentral.edu.co RESUMEN Este documento presenta la solución a un caso logístico, un problema de ruteo para un recorrido a nivel nacional. Este caso es modelado como un problema del agente viajero resuelto con la hoja de calculo de Excel. El problema usa informacion actualde las distancias existentes entre una ciudad y otra. Para nuestro caso, manejamos 12 ciudades. OBJETIVO • Obtener el resultado de ruteo mas óptimo posible. Para lograr un recorrido mínimo de todas las ciudades partiendo desde una origen y regresando de nuevo a esta.

INTRODUCCIÓN El problema del viajante es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos deproblemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema. La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado (problema de tipo NP-hard). El problema del viajante(también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otrosproblemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos. Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante.

La solución más directa es la que aplica la fuerza bruta: evaluar todas lasposibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si unordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades. Por ejemplo las rutas posibles entre 12 ciudades son 479.001.600 combinaciones y los caminos individuales entre ciudades sonel sumatorio de las 12-1 ciudades es decir 66. PLANTEAMIENTO DEL PROBLEMA El problema consiste en determinar la mejor ruta o mínimo recorrido, que se realice entre las 12 ciudades, partiendo desde un punto de partida y regresando a este (ciclo Hamiltoniano), además se tiene que visitar todas las ciudades 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

DESARROLLO DEL PROBLEMA Matemáticamente el modelo se puede expresar así: • Función objetivo:

MIN

•

Sujeto a:

•

Se puede necesitar romper un subciclo, por tanto:

Donde,

Distancia de ir de un lugar i a un lugar j. Variables binarias de decisión. Toma valor de 1 cuandose selecciona el modo de ir de i a j, o toma 0 cuando ese modo no es seleccionado. Un subciclo es un circuito formado por un subconjunto del ciclo Hamiltoniano, es decir del ciclo en general. Ejemplo:

Fig 1. Subciclos de 3 y de 9 ciudades Para dar inicio al desarrollo del problema, partimos de la tabla de datos, con sus respectivas distancias dadas en KM, esta es desarrollada en la hoja de...