FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMATICA Y
SISTEMAS
Optimización del trayecto entre el puente Pachachaca y el Mirador de Abancay
utilizando el algoritmo Djkistra
ASIGNATURA: Investigación de Operaciones
DOCENTE: Ing. Jezzy Pinto Espinoza
INTEGRANTES:
Hans Andre Perez Sequeiros 222184
Jose Eduardo De La Cuba Zambrano 222167
ABANCAY-APURIMAC
2025
Contenido
Introducción.........................................................................................................................3
Planteamiento del problema................................................................................................5
Problema general.............................................................................................................5
.........................................................................................................................................6
Objetivo general...............................................................................................................7
Marco Teórico......................................................................................................................8
Representación de caminos como grafos.........................................................................9
Georreferenciación y análisis espacial básico.................................................................9
Metodología.......................................................................................................................11
Ruta más corta:..............................................................................................................12
Segunda ruta más corta:.................................................................................................13
Resultados esperados.........................................................................................................14
Determinación precisa del trayecto óptimo...................................................................14
Visualización del camino más corto en un mapa...........................................................14
Análisis comparativo entre rutas óptimas y alternativas...............................................15
Conclusiones......................................................................................................................15
Introducción
En la ciudad de Abancay, como en muchas otras ciudades en crecimiento, el
desplazamiento eficiente dentro del entorno urbano se ha vuelto cada vez más importante.
Existen diversos puntos de interés que, a pesar de estar relativamente cerca, pueden presentar
trayectos complejos debido a la falta de señalización clara, rutas poco conocidas o simplemente
por la ausencia de herramientas que permitan identificar cuál es el camino más corto. Uno de
esos casos es el trayecto que va desde el Puente Pachachaca, un lugar simbólico y con un alto
valor cultural, hasta el Mirador de Abancay, un punto turístico muy visitado por su hermosa vista
panorámica de la ciudad.
La motivación principal de este trabajo nace de la curiosidad por encontrar una solución
sencilla pero efectiva a este problema cotidiano: ¿cómo encontrar la mejor ruta entre estos dos
lugares? A partir de esta pregunta, se plantea el uso de una herramienta matemática y
computacional conocida como algoritmo de Dijkstra, que permite identificar el camino más corto
entre dos puntos dentro de una red de caminos. Aunque este algoritmo fue creado hace muchos
años, su utilidad sigue vigente y se aplica hoy en día en programas de navegación, redes de
transporte, y otros sistemas inteligentes.
El objetivo de esta monografía es aplicar dicho algoritmo al caso específico del trayecto
mencionado, representando las posibles rutas como un grafo, es decir, un conjunto de puntos
conectados por líneas, donde cada línea tendrá un valor asignado (en este caso, la distancia). A
través de este modelo, se podrá analizar cuál es la opción más eficiente para llegar desde el
Puente Pachachaca hasta el Mirador de Abancay, considerando las diferentes alternativas que
existen en el camino.
Este trabajo también busca mostrar que no es necesario recurrir a tecnologías demasiado
avanzadas para encontrar soluciones útiles. Con conocimientos básicos de programación,
matemáticas discretas y un enfoque práctico, es posible desarrollar herramientas que aporten a la
vida diaria de los ciudadanos, especialmente en ciudades como la nuestra, donde aún hay mucho
por explorar en términos de tecnología aplicada al entorno.
Planteamiento del problema
En la actualidad, encontrar rutas óptimas dentro de una ciudad se ha vuelto una necesidad
cada vez más común, especialmente en zonas donde la geografía presenta desafíos y la
infraestructura vial no siempre está bien señalizada o estructurada. Abancay, con sus calles
irregulares y su ubicación geográfica entre montañas, representa uno de estos escenarios. Dos
puntos emblemáticos de la ciudad, como el Puente Pachachaca y el Mirador de Abancay, están
conectados por varias rutas posibles, pero no siempre es evidente cuál de ellas es la más corta o
eficiente para transitar.
Desde una perspectiva académica y técnica, este tipo de situación puede abordarse
utilizando herramientas de teoría de grafos, donde los caminos y cruces se representan como
nodos y conexiones. En este contexto, surge el siguiente problema:
Problema general
¿Cuál es la ruta más corta y eficiente desde el Puente Pachachaca hasta el Mirador de
Abancay?
Ilustración 1
La siguiente ilustración muestra la imagen del puente Pachachaca
Ilustración 2
La siguiente ilustración muestra la imagen del Centro Ecológico Recreacional Taraccasa
Objetivo general
Modelar el trayecto como un grafo con nodos y aristas.
Representar las distintas rutas disponibles entre ambos puntos utilizando un grafo, donde
cada intersección o punto clave será un nodo, y los tramos de camino entre ellos serán las
aristas con un valor asignado que represente la distancia o dificultad del trayecto.
Aplicar el algoritmo de Dijkstra para determinar el camino más corto.
Implementar el algoritmo sobre el grafo creado, procesando los datos para identificar cuál
es la ruta óptima desde el punto de inicio (Puente Pachachaca) hasta el punto de llegada (Mirador
de Abancay).
Evaluar la eficiencia del resultado obtenido.
Comparar la ruta sugerida por el algoritmo con otras rutas posibles, validando su eficacia
mediante estimaciones de tiempo o distancia, y analizando si la solución propuesta puede ser útil
para su aplicación en contextos reales, como guías turísticas o sistemas de movilidad urbana.
Marco Teórico
En el campo de la teoría de grafos, uno de los algoritmos más destacados para resolver el
problema de encontrar la ruta más corta entre dos puntos es el algoritmo de Dijkstra. Este
método, propuesto por Edsger Dijkstra en 1959, se ha convertido en una herramienta
fundamental para el análisis de redes y caminos debido a su simplicidad, eficiencia y
aplicabilidad a una gran variedad de situaciones reales.
El algoritmo de Dijkstra trabaja sobre grafos ponderados, es decir, redes donde las
conexiones entre nodos (aristas) tienen un valor numérico asignado, conocido como peso. Este
peso puede representar diferentes aspectos dependiendo del contexto, como la distancia entre dos
puntos, el tiempo estimado de recorrido o el nivel de dificultad del trayecto. Su principal
característica es que solo funciona correctamente si todos los pesos son positivos.
El funcionamiento del algoritmo se basa en recorrer progresivamente el grafo, siempre
eligiendo el camino con el menor costo acumulado desde el nodo inicial hasta el siguiente. A
medida que avanza, va actualizando las distancias mínimas hacia los demás nodos, hasta
encontrar el camino más corto hacia el destino. Este enfoque sistemático lo hace especialmente
útil para sistemas que requieren precisión y fiabilidad.
En la vida cotidiana, el algoritmo de Dijkstra es utilizado en diversas aplicaciones:
sistemas de navegación GPS, planificación de rutas en logística, optimización de redes de
telecomunicaciones, entre otros. Gracias a su eficiencia y solidez, sigue siendo uno de los
métodos más empleados cuando se busca optimizar trayectos en mapas urbanos o rurales, como
en el caso del análisis entre el Puente Pachachaca y el Mirador de Abancay.
Representación de caminos como grafos
Para aplicar algoritmos como Dijkstra, primero es necesario transformar el mapa de rutas
en un grafo. En este contexto, el grafo puede ser dirigido (cuando hay sentido único en una calle)
o no dirigido (cuando se puede circular en ambos sentidos). Cada punto de interés o intersección
será un nodo, y cada camino entre ellos será una arista.
Es fundamental asignar correctamente los pesos a estas aristas, ya que de ellos depende la
precisión del resultado. El peso puede ser la distancia real en metros, el tiempo estimado de
recorrido, el estado del camino (por ejemplo, asfaltado o trocha), o una combinación de estos
factores. Esta representación permite analizar rutas de forma matemática y sistemática, haciendo
posible la automatización del proceso de búsqueda de caminos óptimos.
Georreferenciación y análisis espacial básico
Para obtener un modelo más realista del entorno, es importante considerar herramientas
de georreferenciación. Estas permiten ubicar puntos exactos en el espacio mediante coordenadas
(latitud y longitud), lo cual facilita el diseño del grafo sobre un mapa real.
Herramientas como Google Maps, Google Earth o QGIS (Sistema de Información
Geográfica de Código Abierto) pueden ser muy útiles para este fin. Google Maps permite medir
distancias entre puntos, identificar rutas posibles y obtener datos aproximados de tiempo de
viaje. QGIS, por otro lado, ofrece funcionalidades más avanzadas para quienes buscan trabajar
con capas de información geográfica, análisis topológico, o incluso integrar bases de datos
espaciales.
Estos recursos permiten no solo construir un modelo más preciso del trayecto, sino
también validar los resultados obtenidos por los algoritmos, contrastándolos con datos reales del
Ilustración 3
terreno.
La siguiente ilustración muestra la imagen de los nodos trasados hacia la ruta.
Metodología
Para el análisis y cálculo de las rutas más eficientes dentro del sistema de nodos
propuesto, se implementó el algoritmo de Dijkstra, una de las técnicas más utilizadas en teoría de
grafos para encontrar el camino más corto entre dos puntos en una red ponderada. Este algoritmo
garantiza la obtención de la ruta óptima desde un nodo origen hacia todos los demás nodos del
grafo, siempre y cuando las ponderaciones (en este caso, las distancias en metros) sean no
negativas.
El algoritmo de Dijkstra funciona evaluando de manera iterativa todos los caminos
posibles desde el nodo inicial, seleccionando en cada paso el nodo no visitado con la distancia
acumulada más corta. A medida que avanza, actualiza las distancias tentativas hacia los nodos
vecinos hasta completar todo el recorrido o alcanzar el nodo destino. Este proceso asegura que la
ruta obtenida sea la más eficiente en términos de distancia total recorrida.
En este estudio, se estableció el Nodo 1 como punto de partida y el Nodo 32 como
destino final, evaluando todas las conexiones posibles dentro de la red definida. Como resultado
del análisis, se determinó que existe una única ruta más corta, la cual tiene una distancia total
aproximada de 19,191.41 metros y sigue la siguiente secuencia de nodos:
Ruta más corta:
1 → 2 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12 → 13 → 14 → 15 → 16 → 17 →
18 → 19 → 20 → 4d → 5d → a20 → a21 → a22 → a23 → a24 → a25 → a26 → 32
Ilustración 4
La siguiente ilustración muestra la imagen de la ruta mas corta.
Ilustración 5
La siguiente ilustración muestra la imagen de la ruta mas corta de forma limpia.
Adicionalmente, se identificó una segunda ruta más corta, la cual si bien no es la más
eficiente, resulta útil para estudios comparativos o situaciones en las que la ruta principal se vea
comprometida. Esta segunda opción presenta un recorrido ligeramente distinto:
Segunda ruta más corta:
1 → 2 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → z1 → 11 → 12 → 13 → 14 → 15 → 16 →
17 → 18 → 19 → 20 → 4d → 5d → a20 → a21 → a22 → a23 → a24 → a25 → a26 → 32
Resultados esperados
Este proceso de identificación y evaluación de rutas permitió no solo determinar la
eficiencia del sistema actual, sino también plantear posibles mejoras en la conectividad general
de la red.
Al aplicar el algoritmo de Dijkstra al trayecto entre el Puente Pachachaca y el Mirador de
Abancay, se esperan diversos resultados concretos que permitan validar la eficacia del modelo
propuesto, así como su aplicabilidad en contextos reales relacionados con el transporte, la
planificación urbana y el turismo local.
Determinación precisa del trayecto óptimo
El resultado principal esperado es la identificación de la ruta más corta y eficiente entre
los puntos analizados, considerando una red de caminos representada mediante nodos y aristas
con pesos asignados. Gracias a la implementación del algoritmo de Dijkstra, se ha obtenido un
trayecto óptimo que parte desde el Nodo 1 y llega al Nodo 32, con una distancia total
aproximada de 19,191.41 metros. Esta ruta representa la opción más adecuada en cuanto a
distancia total, minimizando el esfuerzo físico, el tiempo de desplazamiento y posibles desvíos
innecesarios.
Visualización del camino más corto en un mapa
Otro resultado esperado y de gran valor es la representación gráfica de las rutas mediante
herramientas de georreferenciación como Google Maps, Google Earth o software especializado
como QGIS. Esta visualización permitirá mostrar de forma clara y comprensible las rutas
propuestas, facilitando el análisis, la validación de los resultados obtenidos y su interpretación
tanto para especialistas como para usuarios comunes. La visualización también servirá como
recurso didáctico o base para futuras implementaciones tecnológicas.
Análisis comparativo entre rutas óptimas y alternativas
Además del trayecto más corto, se identificó una segunda ruta viable, que aunque
presenta una mayor distancia, puede ser útil como alternativa en casos de congestión o bloqueo
de caminos. Se espera realizar un análisis comparativo entre ambas rutas y otras opciones
comúnmente utilizadas, evaluando diferencias en términos de tiempo estimado de recorrido,
condiciones del terreno y facilidad de acceso. Este análisis contribuirá a determinar si la solución
propuesta mediante Dijkstra representa una mejora significativa frente a las rutas habituales.
Finalmente, se contempla que este estudio pueda servir como base para el desarrollo de
aplicaciones móviles o sistemas de información geográfica enfocados en mejorar la movilidad en
Abancay. Al tratarse de una zona con alto valor cultural y turístico, contar con rutas optimizadas
hacia puntos como el Mirador de Abancay puede significar una mejora notable en la experiencia
de los visitantes, así como un apoyo estratégico en la planificación del transporte local y la toma
de decisiones urbanísticas.
Conclusiones
La implementación del algoritmo de Dijkstra para determinar el trayecto más corto entre
el Puente Pachachaca y el Mirador de Abancay ha demostrado ser una herramienta eficaz y
confiable para resolver problemas de optimización de rutas urbanas. A través del modelado del
entorno como un grafo ponderado, donde cada nodo representa un punto clave del recorrido y
cada arista representa un tramo con una distancia asociada, fue posible identificar con precisión
el camino óptimo y otras rutas alternativas.
Uno de los hallazgos más relevantes es la determinación exacta de la ruta más corta, con
una distancia total aproximada de 19,191.41 metros, validada mediante datos recolectados y
simulaciones computacionales. Esta ruta no solo cumple con el criterio de menor distancia, sino
que también se adapta a las condiciones reales del entorno, lo que resalta el valor práctico del
modelo desarrollado.
Asimismo, se identificó una segunda ruta alternativa, que aunque menos eficiente en
términos de distancia, constituye una opción viable en caso de contingencias. Este tipo de
análisis comparativo refuerza la utilidad del enfoque no solo desde el punto de vista académico,
sino también como herramienta para la toma de decisiones en ámbitos como el transporte, el
turismo o la planificación territorial.
Es importante destacar que el éxito de este tipo de trabajos depende no solo del algoritmo
utilizado, sino también de la calidad de los datos. La correcta georreferenciación, la
identificación precisa de los nodos, y la asignación adecuada de pesos a cada tramo fueron
determinantes para lograr resultados coherentes con la realidad geográfica de Abancay. Esto
evidencia la necesidad de una fase rigurosa de recolección y análisis de datos como base del
proceso.
Finalmente, esta investigación demuestra que el uso de algoritmos clásicos como Dijkstra
sigue teniendo una vigencia y aplicabilidad significativa en contextos reales. La metodología
desarrollada puede ser extendida a otros trayectos dentro de la región, sentando las bases para el
diseño de aplicaciones móviles de orientación turística, sistemas inteligentes de rutas, o
herramientas de planificación urbana. De esta manera, se fortalece el vínculo entre la
computación, la ingeniería y las necesidades cotidianas de la sociedad.
