Optimización de la red de transporte urbano de los compactadores utilizando algoritmos genéticos en la ciudad de Puno

Abstract

En el presente trabaio titulado "OPTIMIZACIÓN DE LA RED DE TRANSPORTE URBANA DE LOS COMPACTADORES UTILIZANDO ALGORITMOS GENETICOS EN LA CIUDAD DE PUNO", problema típico del Agente Viajero, nos permite hallar la ruta óptima en los diferentes planos divididos a los cuales denominamos zonas de trabajo El objetivo general es el establecer el itinerario para la optimización de los tiempos y distancias utilizado por los compactadores en la ciudad de Puno mediante la teoría de los algoritmos genéticos. Para buscar el camino óptimo se ha considerado el plano de la ciudad de Puno realizado en Autocad que nos permite hallar sus respectivas coordenadas de las manzanas y caminos posibles para ello se realizó una interacción con el visual Basic basados en la teoría de los grafos. Se diseñó los algoritmos en UML (Unified Modeling Languaje) basado en el software Rational Rose e implementaron los algoritmos de solución para hallar el camino óptimo en el transporte de los compactadores de la ciudad de Puno en sus respectivas zonas de trabajo en Java y se hizo un estudio comparativo de las mismas. Dentro de las técnicas seleccionadas para su implementación se encuentran tres métodos exactos como son: "Búsqueda Exhaustiva Ingenua -(Naive Search Exhaustiva)", "Ramificación y Acotamiento Ingenuo (Naive Branch and Bound)" y el de "Una Mejor Ramificación y Acotamiento (A Better Branch and Bound)". El método aproximado seleccionado fue: "Dos Optimal", Se realizaron diversas pruebas de evaluación cuya medición lo realiza el Factor de Garantía y el cociente de Aproximación en un determinado número Instancias (3,5,8, ... ,10) puntos de atención en donde se obtuvo excelentes resultados en velocidad de respuesta del algoritmo aproximado "Dos Optimal" cuyo factor de garantía posee un valor de 0.720 que se considera aceptable con cociente de aproximación de 0.889 donde muestra la confiabilidad relativamente buena. El algoritmo del método exacto: "Ramificación y acotamiento ingenuo" ("Naive Branch and bound ingenuo") tiene un mejor comportamiento debido a la rapidez en dar una solución optima que el método exacto: "Búsqueda Exhaustiva Ingenua" ( "Naive Search Exhaustive").