UNIVERSIDAD NACIONAL DE SAN AGUSTÍN
FACULTAD DE INGENIERÍA DE PRODUCCIÓN Y SERVICIOS
ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS
CURSO
ANÁLISIS Y DISEÑO DE ALGORITMOS
DOCENTE:
DRA. AUREA SORIANO VARGAS
ALUMNOS:
ALFRED MARVIN CASANOVA VARGAYA/ CUI:20142708
FRANK LENY CCAPA USCA / CUI:20180562
PATRIK RENEE QUENTA NINA: CUI:20181702
2020
“Recorrido TSP de las principales ciudades de
las provincias de Arequipa”
Frank Leny Ccapa Usca Patrik Renee Quenta Nina,
Escuela Profesional de Ing. De Sistemas Escuela Profesional de Ing. De Sistemas
Universidad Nacional de San Agustín de Arequipa Universidad Nacional de San Agustín de Arequipa
[email protected] [email protected]
Alfred Marvin Casanova
Escuela Profesional de Ing. De Sistemas
Universidad Nacional de San Agustín de Arequipa
[email protected]Resumen distancia mínima. Dando a conocer a las personas
(Turistas), la ruta más eficiente para continuar su
En este proyecto se verá un recorrido de las
viaje
principales ciudades de las provincias de la ciudad de
arequipa que será trabajado bajo 2 algoritmos dijkstra y
Para todo ello se ha trabajado con los algoritmos
algoritmo de colonia de hormigas donde se compararon su
complejidad y tiempo computacional , al final se obtendrá dijkstra y colonia de hormigas verificando así la ruta
el camino mas corto para recorrer las principales ciudades más óptima y con mejor eficiencia.
de las provincias de la región arequipa
II. MARCO TEÓRICO
I. INTRODUCCIÓN A) Q
ue es un problema de TSP
En la actualidad el departamento de Arequipa se El problema del agente viajero o TSP por sus siglas
basa en su potencial turístico [4], en la herencia de la en inglés (Travelling Salesmen Problem)[1], Se
cultura prehispánica y en sus riquezas naturales. El emplea para es la de encaminar (rutear) desde
turismo se concentra en la ciudad, por lo que es distintas perspectivas, buscando la mejor
necesario tener un mapa completo de las rutas que ruta(camino) posible con criterios de economía en
conectan con las principales ciudades, para así de distancia o en costo [1].
esta manera poder ofrecer un recorrido completo a
todos los visitantes (turistas) B) A
lgoritmo de rutas más cortas
El trabajo consiste en plantear la ruta más corta que El algoritmo de la ruta más corta [2], es una
conecta con las principales ciudades de cada distritos particularidad de los problemas de redes, en los
del departamento de Arequipa. Para este propósito cuales se determinan un plan de rutas, donde se
ha sido necesario crear un grafo que hará un genera el camino con la mínima distancia total, que
recorrido completo uniendo de esta manera las una nuestro nodo origen con un nodo destino, sin
principales ciudades. El proyecto tiene como importar el número de nodos que existan entre estos
principal objetivo dar a conocer todos los caminos y [2].
distancias que existen entre las principales ciudades
de la región Arequipa, de tal manera que con esta C) Algoritmo de dijkstra
información expresar el proyecto como un TSP El algoritmo de Dijkstra [3], es un algoritmo que
(Travelling Salesman Problem)[1], hallando así la tiene como complejidad O(n^2) lo cual lo hace muy
eficiente, tiene como utilidad encontrar el camino de A) Representación del Grafo
coste mínimo desde un nodo origen a todos los
demás nodos del grafo[3] Al representar la ciudad de Arequipa por medio de
un grafo, las principales ciudades de cada distrito
El algoritmo funciona de la siguiente manera: si el conforman los vértices (nodos) y las aristas los
camino más corto entre los vértices u y v pasa por el caminos (las carreras) que los unen, cabe recalcar
vértice w, entonces la parte del camino que va de w que estas vías tienen doble sentido por ello
a v debe ser el camino más corto entre todos los podremos decir que este grafo es un no dirigido,
caminos que van de w a v. Y de esta forma, se irán debido a ello, no será necesario colocarles un sentido
construyendo sucesivamente los caminos de coste a nuestras aristas
mínimo desde un nodo inicial hasta cada uno de los
nodos del grafo, y se van a utilizar los caminos Construyendo nuestro grafo: Para ello será necesario
conseguidos como parte de los nuevos caminos [3]. ver si existe un camino para llegar de un destino a
otro:
III. METODOLOGÍA (EL PROBLEMA
PADRÓN Y LOS ALGORITMOS QUE ● Caraveli: cotahuasi (357 km, 7h 39min),
SERÁN USADAS). Camaná (210 km, 3h 36 min)
● Cotahuasi: caraveli (357 km, 7h 39min),
El problema del agente viajero consiste en obtener Chuquibamba (142 km 2h 35 min)
las distancia entre un nodo y otro, planteando ● Chuquibamba: Camaná (173km 2h 59min),
obtener la ruta más corta que conecta dichos nodos. Cotahuasi (142k m 2h 35 min), aplao
(49.5 km, 1h 3 min)
Para resolver dicho problema estructuramos dos ● Camaná: Caraveli (210 km, 3h 36 min),
soluciones, siendo estas el Algoritmo para la chuquibamba (173 km 2h 59min), aplao (124
determinación del camino más corto, dado un vértice km 2h), Chivay (296 km, 4 h 50 min),
origen, hacia el resto de los vértices en un grafo que Arequipa (177 km, 3h), Mollendo (111 km,
tiene pesos en cada arista y el algoritmo 1h 46 min)
ACO(Algoritmo de la Colonia de Hormigas) que es ● Aplao: Camaná (124 km, 2h), Chuquibamba
una red interconectada de nodos con un principio y (49.5 km, 1h 3 min), Chivay (299km 5h 1m)
fin, nos mostrará la probabilidad de tomar x ruta ● Chivay: aplao (299km, 5h 1m), Arequipa
desde un punto de partida hasta el destino final que (162 km, 2h 56 min), Camaná (296 km, 4h
se escogido. 50min)
● Arequipa: Chivay (162 km, 2h 56 min),
IV. DESCRIPCIÓN DE LOS DATOS.
Camaná (177 km, 3h), Mollendo (124 km, 2h
Provincias de Arequipa y sus principales ciudades 12 min)
● Mollendo: Arequipa (124 km, 2h 12 min)
● Arequipa - Arequipa
Camaná (111 km, 1h 46min)
● Camaná - Camaná
● Islay - Mollendo B) Matriz de incidencia con el peso del Arco
● Caylloma - Chivay
● Castilla - Aplao Esta matriz representa la distancia entre los vértices
● Condesuyos - Chuquibamba (Ciudades principales de cada Provincia de
● La Unión - Cotahuasi Arequipa), y el sentido como se lee es fila-columna,
● Carabalí - Carabalí donde el cero (0) representa la distancia de un nodo
con el mismo, 1E significa que los nodos no están
conectados por ningún arco (no existe un camino sin
directo hacia el destino), y valores diferentes a estos
que indican el peso del arco que los conecta. Ver V. EXPERIMENTOS Y RESULTADOS
cuadro siguiente: A) Herramientas
1.Caraveli 5.Aplao Dijkstra
2.Cotahuasi 6.Chivay
3.Chuquibamba 7.Mollendo Para realizar la implementación de de dicho
algoritmo utilizamos herramientas como google
4.Camana 8. Arequipa
Colab, dicha plataforma fue utilizada más
que todo para poder editar al mismo tiempo y
aprovechar las librerías de esta.
Algoritmo de la Colonia de Hormigas
Para la implementación del código usamos
el IDE de visual studio code y el lenguaje de
programación C++.
B) Comparación de complejidad
computacional de los algoritmos descritos
en la metodología.
Imagen 1. Matriz de pesos de arcos
Los algoritmos utilizados para resolver dicho
problema fueron Dijkstra con un de
Finalmente obtendremos nuestro grafo como se
complejidad O(V+E log2E) y
muestra a continuación:
ACO(Algoritmo de la Colonia de Hormigas).
C) Resultados
La implementación del algoritmo Dijkstra,
funciona de tal manera que nosotros elegimos un
nodo raíz del cual partir, y mediante de una serie de
procesos este irá comparado nodos eligiendo el
menor valor de estos, de esta forma nos retorna la
suma del path desde el nodo inicio hasta el nodo
destino.
Imagen 2. Grafo de las principales ciudades de la
región Arequipa por km
Al implementar el ACO necesitamos de una clase BÚSQUEDA TABÚ. Revista de Matemática: Teoría y
Node que permita enlazar no sólo con un nodo sino Aplicaciones, 21(1), pp.127-144.
con los que sean necesarios para satisfacer el
[2] Salazar López, B., 2019. Algoritmo De La Ruta Más
problema, además de ser dinámico. La evolución de
Corta | Ingeniería Industrial Online. [online] Ingeniería
las rutas para llegar a una óptima (ruta más corta o Industrial Online. Available at:
más segura) se realiza combinando las efecto de <https://www.ingenieriaindustrialonline.com/investigacio
agregar feromonas cuando las hormigas exitosas n-de-operaciones/algoritmo-de-la-ruta-mas-corta/#:~:text
regresan al nido. El número de feromonas utilizadas =El%20algoritmo%20de%20la%20ruta,nodos%20que%2
en nuestro problema es 11 para indicar los recorridos 0existan%20entre%20estos.> [Accessed 6 December
que une a las ciudades. 2020].
Las hormigas al usar caminos previamente visitados [3] Sánchez Torrubia, G. and Lozano Terrazas, V., 2001.
hacia la comida, hacen que las feromonas que dejan Algoritmo de Dijkstra. Un Tutorial Interactivo. In: VII
vaya aumentando en la ruta anteriormente tomada. Jornadas de Enseñanza Universitaria de la Informática
(JENUI). Madrid.
La caminata aleatoria impuesta para aumentar la
[4] AREQUIPA: PRINCIPALES ATRACTIVOS
probabilidad de encontrar comida junto con el
TURÍSTICOS. [ebook] Arequipa. Available at:
equilibrio entre la descomposición de las feromonas <https://www.bcrp.gob.pe/docs/Sucursales/Arequipa/Are
y la mejora en varias rutas permite a la colonia quipa-Atractivos.pdf> [Accessed 8 December 2020].
cambiar de camino hasta obtener la convergencia.
En nuestro caso es hallar la ruta más óptima de una
ciudad hacia otra.
VI. CONCLUSIONES
A diferencia de Dijkstra, ACO no analiza todas las
rutas posibles y, por lo tanto, puede converger a una
solución subóptima. Sin embargo, para problemas a
gran escala, ACO podría ser una mejor opción que
Dijkstra, considerando que no es un método
exhaustivo y no necesita evaluar todos los caminos
posibles.
En el caso concreto del TSP la entrada es el número
de nodos (o ciudades) del grafo. Cuanto mayor sea el
número de nodos, mayor será el número de rutas
posibles, y por lo tanto mayor será el esfuerzo
requerido para calcular todas ellas.
VII. REFERENCIAS
[1] LÓPEZ, E., MURILLO, Á. and SALAS, O., 2020. EL
PROBLEMA DEL AGENTE VIAJERO: UN
ALGORITMO DETERMINÍSTICO USANDO
