OPTIMIZACIÓN DE RUTAS EN LA RED DEL
Sistema de Transporte Colectivo Metro CDMX
Algoritmo de Dijkstra · Arborescencia de Ruta Más Corta · Árbol de Expansión Mínima
Investigación de Operaciones Red modelada con 15 nodos y 30 arcos dirigidos Tiempo de traslado entre estaciones como costo de cada arco
Rodriguez Peña Atziri Alejandra · Albor Saucedo Dylan Gabriel
15 Nodos
30 Arcos
3 Métodos
2026
PLANTEAMIENTO DEL PROBLEMA
Problema central
Interpretación de la red
Determinar la ruta de menor tiempo entre la estación origen (S) y destino (t) de la red del Metro CDMX. • Nodos: cada estación de la red• Arcos: conexiones con costo en minutos• Nodo S: oferta = 1• Nodo t: demanda = 1• Sin restricciones de capacidad en arcos
Costos: Tiempo de traslado entre estaciones, indicado en cada arco.
Oferta y demanda: Se considera una unidad de flujo, donde S tiene oferta = 1 y t demanda = 1.
Capacidades: No se especifican capacidades, consistente con un problema de ruta más corta.
Técnicas aplicadas: Dijkstra · Arborescencia de ruta más corta · Árbol de expansión mínima (Kruskal)
PLANTEAMIENTO DEL PROBLEMA
Problema central
Interpretación de la red
Determinar la ruta de menor tiempo entre la estación origen (S) y destino (t) de la red del Metro CDMX. • Nodos: cada estación de la red• Arcos: conexiones con costo en minutos• Nodo S: oferta = 1• Nodo t: demanda = 1• Sin restricciones de capacidad en arcos
Costos: Tiempo de traslado entre estaciones, indicado en cada arco.
Oferta y demanda: Se considera una unidad de flujo, donde S tiene oferta = 1 y t demanda = 1.
Capacidades: No se especifican capacidades, consistente con un problema de ruta más corta.
Técnicas aplicadas: Dijkstra · Arborescencia de ruta más corta · Árbol de expansión mínima (Kruskal)
PROBLEMÁTICAS Y SOLUCIONES — 3 MÉTODOS
Algoritmo de Dijkstra
01
Encontrar la ruta de menor tiempo entre S y t mediante etiquetas (d(i), a(i)) donde d = distancia acumulada y a = predecesor. Inicialización con nodo S = (0,-). Actualización de nodos adyacentes. Selección del nodo con menor distancia temporal.
Arborescencia de Ruta Más Corta
02
Obtener el árbol de rutas óptimas desde S hacia todos los nodos alcanzables. Se selecciona en cada paso el nodo no permanente con menor etiqueta temporal hasta cubrir toda la red.
Árbol de Expansión Mínima (Kruskal)
03
Conectar todos los nodos de la red con el menor costo total posible, sin ciclos. Se ordenan los arcos de menor a mayor peso y se agregan si no forman ciclo, hasta conectar todos los nodos.
ANÁLISIS DE SENSIBILIDAD — CASOS WHAT-IF
* Agrega los botones interactivos de Problemática y Resolución en Genially sobre cada tarjeta
Se analiza cómo cambios en la red afectan la ruta óptima. Ruta base: S → 3 → 4 → 6 → t = 22 minutos
Caso 1 — Retraso en tramo (4,6) los viernes
Situación: Los viernes, el tramo (4,6) presenta retrasos por alta demanda.Cambio en el costo: El tiempo aumenta 6 minutos, pasando de 4 a 10.Resultado: La ruta S→3→4→6→t pasa de 22 a 28 min. Se recalcula Dijkstra buscando alternativa sin ese tramo.
Caso 2 — Falla en tramo (3,4) por mantenimiento
Situación: El tramo (3,4) queda fuera de servicio por mantenimiento programado.Cambio: Se elimina el arco (3,4) de la red. Costo original = 8 minutos.Resultado: La ruta se fuerza por caminos alternativos como 3→8→9→10→t, aumentando el tiempo total.
El análisis de sensibilidad valida la robustez de las rutas y la necesidad de rutas de contingencia en la red.
PLANTEAMIENTO DEL PROBLEMA
Problema central
Interpretación de la red
Determinar la ruta de menor tiempo entre la estación origen (S) y destino (t) de la red del Metro CDMX. • Nodos: cada estación de la red• Arcos: conexiones con costo en minutos• Nodo S: oferta = 1• Nodo t: demanda = 1• Sin restricciones de capacidad en arcos
Costos: Tiempo de traslado entre estaciones, indicado en cada arco.
Oferta y demanda: Se considera una unidad de flujo, donde S tiene oferta = 1 y t demanda = 1.
Capacidades: No se especifican capacidades, consistente con un problema de ruta más corta.
Técnicas aplicadas: Dijkstra · Arborescencia de ruta más corta · Árbol de expansión mínima (Kruskal)
PROBLEMÁTICAS Y SOLUCIONES — 3 MÉTODOS
Algoritmo de Dijkstra
01
Encontrar la ruta de menor tiempo entre S y t mediante etiquetas (d(i), a(i)) donde d = distancia acumulada y a = predecesor. Inicialización con nodo S = (0,-). Actualización de nodos adyacentes. Selección del nodo con menor distancia temporal.
Problemática
Resolución
Arborescencia de Ruta Más Corta
02
Obtener el árbol de rutas óptimas desde S hacia todos los nodos alcanzables. Se selecciona en cada paso el nodo no permanente con menor etiqueta temporal hasta cubrir toda la red.
Problemática
Resolución
Árbol de Expansión Mínima (Kruskal)
03
Conectar todos los nodos de la red con el menor costo total posible, sin ciclos. Se ordenan los arcos de menor a mayor peso y se agregan si no forman ciclo, hasta conectar todos los nodos.
Problemática
Resolución
* Agrega los botones interactivos de Problemática y Resolución en Genially sobre cada tarjeta
DESARROLLO — ALGORITMO DE DIJKSTRA
Etiquetas (d(i), a(i)): d = distancia acumulada desde S · a = nodo predecesor · [corchetes] = permanente
It. 1 — desde S
It. 2 — desde 3
It. 3 — desde 7
It. 4 — desde 1
(7,S) n1 · (4,S) n3 · (6,S) n7
(12,3) n4 · (9,3) n12
(9,7) n8 · (10,7) n12 NO mejora
(12,1) n2 · (17,1) n4 NO mejora
✓ [4,S] nodo 3
✓ [6,S] nodo 7
✓ [7,S] nodo 1
✓ [9,7] nodo 8
It. 5 — desde 8
It. 6 — desde 12
It. 7 — desde 2
It. 8-9 — 4 y 6
(15,8) n9 · (24,8) n4 NO mejora
(14,12) n9 mejora · (17,12) n13
(16,2) n5 · (12,3) n4 NO mejora
(16,4) n6 · (17,9) n10 → t
✓ [9,3] nodo 12
✓ [12,1] nodo 2
✓ [12,3] nodo 4
✓ [22,6] nodo t
RUTA ÓPTIMA: S → 3 → 4 → 6 → t | Costo total mínimo = 22 minutos
ARBORESCENCIA DE RUTA MÁS CORTA
Método
Se construye el árbol de rutas óptimas desde S hacia todos los nodos, seleccionando en cada paso el nodo no permanente con menor etiqueta temporal y actualizando los adyacentes. El resultado es un árbol dirigido (arborescencia) que contiene las rutas más cortas desde S a todos los demás nodos.
Etiquetas permanentes finales (arborescencia):
[0, -]
[4, S]
[6, S]
[7, S]
[9, 7]
12
[9, 3]
[12, 1]
[12, 3]
[14, 12]
[16, 2]
10
13
11
[16, 4]
[17, 9]
[17, 12]
[22, 10]
[22, 6]
ANÁLISIS DE SENSIBILIDAD — CASOS WHAT-IF
Se analiza cómo cambios en la red afectan la ruta óptima. Ruta base: S → 3 → 4 → 6 → t = 22 minutos
Caso 1 — Retraso en tramo (4,6) los viernes
Situación: Los viernes, el tramo (4,6) presenta retrasos por alta demanda.Cambio en el costo: El tiempo aumenta 6 minutos, pasando de 4 a 10.Resultado: La ruta S→3→4→6→t pasa de 22 a 28 min. Se recalcula Dijkstra buscando alternativa sin ese tramo.
Caso 2 — Falla en tramo (3,4) por mantenimiento
Situación: El tramo (3,4) queda fuera de servicio por mantenimiento programado.Cambio: Se elimina el arco (3,4) de la red. Costo original = 8 minutos.Resultado: La ruta se fuerza por caminos alternativos como 3→8→9→10→t, aumentando el tiempo total.
El análisis de sensibilidad valida la robustez de las rutas y la necesidad de rutas de contingencia en la red.
INTERPRETACIÓN Y CONCLUSIONES
Conclusión general
Las tres técnicas se complementan: Dijkstra resuelve emergencias en tiempo real; la arborescencia ofrece visión global de rutas óptimas desde cualquier origen; Kruskal apoya la planificación de infraestructura mínima. La solución más completa para la operación diaria es Dijkstra combinado con el análisis de sensibilidad, ya que permite adaptarse a cambios en los tiempos de traslado de la red.
Solución más completa: Dijkstra + Análisis de sensibilidad — permite adaptación en tiempo real a cambios en la red
REFERENCIAS
APA 7
[1] Hillier, F. S., & Lieberman, G. J. (2021). Introduction to Operations Research (11.ª ed.). McGraw-Hill Education.
[2] Taha, H. A. (2017). Operations Research: An Introduction (10.ª ed.). Pearson.
[3] Rodríguez Moreno, G. del C. (2026). Flor 2: Ruta Más Corta; Árbol de Peso Mínimo [Archivo PDF]. Material del curso de Investigación de Operaciones.
[4] Rodríguez Moreno, G. del C. (2026). Flor 2: Tipos de Modelos de Programación Entera [Archivo PDF]. Material del curso de Investigación de Operaciones.
Rodriguez Peña Atziri Alejandra · Albor Saucedo Dylan Gabriel · Investigación de Operaciones 2026
PROBLEMÁTICAS Y SOLUCIONES — 3 MÉTODOS
atziri Rodriguez
Created on June 9, 2026
Start designing with a free template
Discover more than 1500 professional designs like these:
View
Essential Business Proposal
View
Project Roadmap Timeline
View
Step-by-Step Timeline: How to Develop an Idea
View
Artificial Intelligence History Timeline
View
Microlearning: Design Learning Modules
View
Momentum: Onboarding Escape Game
View
Momentum: Manager Guide
Explore all templates
Transcript
OPTIMIZACIÓN DE RUTAS EN LA RED DEL
Sistema de Transporte Colectivo Metro CDMX
Algoritmo de Dijkstra · Arborescencia de Ruta Más Corta · Árbol de Expansión Mínima
Investigación de Operaciones Red modelada con 15 nodos y 30 arcos dirigidos Tiempo de traslado entre estaciones como costo de cada arco
Rodriguez Peña Atziri Alejandra · Albor Saucedo Dylan Gabriel
15 Nodos
30 Arcos
3 Métodos
2026
PLANTEAMIENTO DEL PROBLEMA
Problema central
Interpretación de la red
Determinar la ruta de menor tiempo entre la estación origen (S) y destino (t) de la red del Metro CDMX. • Nodos: cada estación de la red• Arcos: conexiones con costo en minutos• Nodo S: oferta = 1• Nodo t: demanda = 1• Sin restricciones de capacidad en arcos
Costos: Tiempo de traslado entre estaciones, indicado en cada arco. Oferta y demanda: Se considera una unidad de flujo, donde S tiene oferta = 1 y t demanda = 1. Capacidades: No se especifican capacidades, consistente con un problema de ruta más corta.
Técnicas aplicadas: Dijkstra · Arborescencia de ruta más corta · Árbol de expansión mínima (Kruskal)
PLANTEAMIENTO DEL PROBLEMA
Problema central
Interpretación de la red
Determinar la ruta de menor tiempo entre la estación origen (S) y destino (t) de la red del Metro CDMX. • Nodos: cada estación de la red• Arcos: conexiones con costo en minutos• Nodo S: oferta = 1• Nodo t: demanda = 1• Sin restricciones de capacidad en arcos
Costos: Tiempo de traslado entre estaciones, indicado en cada arco. Oferta y demanda: Se considera una unidad de flujo, donde S tiene oferta = 1 y t demanda = 1. Capacidades: No se especifican capacidades, consistente con un problema de ruta más corta.
Técnicas aplicadas: Dijkstra · Arborescencia de ruta más corta · Árbol de expansión mínima (Kruskal)
PROBLEMÁTICAS Y SOLUCIONES — 3 MÉTODOS
Algoritmo de Dijkstra
01
Encontrar la ruta de menor tiempo entre S y t mediante etiquetas (d(i), a(i)) donde d = distancia acumulada y a = predecesor. Inicialización con nodo S = (0,-). Actualización de nodos adyacentes. Selección del nodo con menor distancia temporal.
Arborescencia de Ruta Más Corta
02
Obtener el árbol de rutas óptimas desde S hacia todos los nodos alcanzables. Se selecciona en cada paso el nodo no permanente con menor etiqueta temporal hasta cubrir toda la red.
Árbol de Expansión Mínima (Kruskal)
03
Conectar todos los nodos de la red con el menor costo total posible, sin ciclos. Se ordenan los arcos de menor a mayor peso y se agregan si no forman ciclo, hasta conectar todos los nodos.
ANÁLISIS DE SENSIBILIDAD — CASOS WHAT-IF
* Agrega los botones interactivos de Problemática y Resolución en Genially sobre cada tarjeta
Se analiza cómo cambios en la red afectan la ruta óptima. Ruta base: S → 3 → 4 → 6 → t = 22 minutos
Caso 1 — Retraso en tramo (4,6) los viernes
Situación: Los viernes, el tramo (4,6) presenta retrasos por alta demanda.Cambio en el costo: El tiempo aumenta 6 minutos, pasando de 4 a 10.Resultado: La ruta S→3→4→6→t pasa de 22 a 28 min. Se recalcula Dijkstra buscando alternativa sin ese tramo.
Caso 2 — Falla en tramo (3,4) por mantenimiento
Situación: El tramo (3,4) queda fuera de servicio por mantenimiento programado.Cambio: Se elimina el arco (3,4) de la red. Costo original = 8 minutos.Resultado: La ruta se fuerza por caminos alternativos como 3→8→9→10→t, aumentando el tiempo total.
El análisis de sensibilidad valida la robustez de las rutas y la necesidad de rutas de contingencia en la red.
PLANTEAMIENTO DEL PROBLEMA
Problema central
Interpretación de la red
Determinar la ruta de menor tiempo entre la estación origen (S) y destino (t) de la red del Metro CDMX. • Nodos: cada estación de la red• Arcos: conexiones con costo en minutos• Nodo S: oferta = 1• Nodo t: demanda = 1• Sin restricciones de capacidad en arcos
Costos: Tiempo de traslado entre estaciones, indicado en cada arco. Oferta y demanda: Se considera una unidad de flujo, donde S tiene oferta = 1 y t demanda = 1. Capacidades: No se especifican capacidades, consistente con un problema de ruta más corta.
Técnicas aplicadas: Dijkstra · Arborescencia de ruta más corta · Árbol de expansión mínima (Kruskal)
PROBLEMÁTICAS Y SOLUCIONES — 3 MÉTODOS
Algoritmo de Dijkstra
01
Encontrar la ruta de menor tiempo entre S y t mediante etiquetas (d(i), a(i)) donde d = distancia acumulada y a = predecesor. Inicialización con nodo S = (0,-). Actualización de nodos adyacentes. Selección del nodo con menor distancia temporal.
Problemática
Resolución
Arborescencia de Ruta Más Corta
02
Obtener el árbol de rutas óptimas desde S hacia todos los nodos alcanzables. Se selecciona en cada paso el nodo no permanente con menor etiqueta temporal hasta cubrir toda la red.
Problemática
Resolución
Árbol de Expansión Mínima (Kruskal)
03
Conectar todos los nodos de la red con el menor costo total posible, sin ciclos. Se ordenan los arcos de menor a mayor peso y se agregan si no forman ciclo, hasta conectar todos los nodos.
Problemática
Resolución
* Agrega los botones interactivos de Problemática y Resolución en Genially sobre cada tarjeta
DESARROLLO — ALGORITMO DE DIJKSTRA
Etiquetas (d(i), a(i)): d = distancia acumulada desde S · a = nodo predecesor · [corchetes] = permanente
It. 1 — desde S
It. 2 — desde 3
It. 3 — desde 7
It. 4 — desde 1
(7,S) n1 · (4,S) n3 · (6,S) n7
(12,3) n4 · (9,3) n12
(9,7) n8 · (10,7) n12 NO mejora
(12,1) n2 · (17,1) n4 NO mejora
✓ [4,S] nodo 3
✓ [6,S] nodo 7
✓ [7,S] nodo 1
✓ [9,7] nodo 8
It. 5 — desde 8
It. 6 — desde 12
It. 7 — desde 2
It. 8-9 — 4 y 6
(15,8) n9 · (24,8) n4 NO mejora
(14,12) n9 mejora · (17,12) n13
(16,2) n5 · (12,3) n4 NO mejora
(16,4) n6 · (17,9) n10 → t
✓ [9,3] nodo 12
✓ [12,1] nodo 2
✓ [12,3] nodo 4
✓ [22,6] nodo t
RUTA ÓPTIMA: S → 3 → 4 → 6 → t | Costo total mínimo = 22 minutos
ARBORESCENCIA DE RUTA MÁS CORTA
Método
Se construye el árbol de rutas óptimas desde S hacia todos los nodos, seleccionando en cada paso el nodo no permanente con menor etiqueta temporal y actualizando los adyacentes. El resultado es un árbol dirigido (arborescencia) que contiene las rutas más cortas desde S a todos los demás nodos.
Etiquetas permanentes finales (arborescencia):
[0, -]
[4, S]
[6, S]
[7, S]
[9, 7]
12
[9, 3]
[12, 1]
[12, 3]
[14, 12]
[16, 2]
10
13
11
[16, 4]
[17, 9]
[17, 12]
[22, 10]
[22, 6]
ANÁLISIS DE SENSIBILIDAD — CASOS WHAT-IF
Se analiza cómo cambios en la red afectan la ruta óptima. Ruta base: S → 3 → 4 → 6 → t = 22 minutos
Caso 1 — Retraso en tramo (4,6) los viernes
Situación: Los viernes, el tramo (4,6) presenta retrasos por alta demanda.Cambio en el costo: El tiempo aumenta 6 minutos, pasando de 4 a 10.Resultado: La ruta S→3→4→6→t pasa de 22 a 28 min. Se recalcula Dijkstra buscando alternativa sin ese tramo.
Caso 2 — Falla en tramo (3,4) por mantenimiento
Situación: El tramo (3,4) queda fuera de servicio por mantenimiento programado.Cambio: Se elimina el arco (3,4) de la red. Costo original = 8 minutos.Resultado: La ruta se fuerza por caminos alternativos como 3→8→9→10→t, aumentando el tiempo total.
El análisis de sensibilidad valida la robustez de las rutas y la necesidad de rutas de contingencia en la red.
INTERPRETACIÓN Y CONCLUSIONES
Conclusión general
Las tres técnicas se complementan: Dijkstra resuelve emergencias en tiempo real; la arborescencia ofrece visión global de rutas óptimas desde cualquier origen; Kruskal apoya la planificación de infraestructura mínima. La solución más completa para la operación diaria es Dijkstra combinado con el análisis de sensibilidad, ya que permite adaptarse a cambios en los tiempos de traslado de la red.
Solución más completa: Dijkstra + Análisis de sensibilidad — permite adaptación en tiempo real a cambios en la red
REFERENCIAS
APA 7
[1] Hillier, F. S., & Lieberman, G. J. (2021). Introduction to Operations Research (11.ª ed.). McGraw-Hill Education.
[2] Taha, H. A. (2017). Operations Research: An Introduction (10.ª ed.). Pearson.
[3] Rodríguez Moreno, G. del C. (2026). Flor 2: Ruta Más Corta; Árbol de Peso Mínimo [Archivo PDF]. Material del curso de Investigación de Operaciones.
[4] Rodríguez Moreno, G. del C. (2026). Flor 2: Tipos de Modelos de Programación Entera [Archivo PDF]. Material del curso de Investigación de Operaciones.
Rodriguez Peña Atziri Alejandra · Albor Saucedo Dylan Gabriel · Investigación de Operaciones 2026