InvOp - RutaCorta

RUTA MAS CORTA

iNVESTIGACION DE OPERACIONES

INSTITUTO TECNOLOGICO SUPERIOR DE SAN MARTIN TEXMELUCAN

DIVISION DE INGENIERIA EN SISTEMAS COMPUTACIONALES

PRESENTA: Anayeli Rivera Sanchez 23240011 Miguel Castillo Resendiz 23240043 Gabriela Avila Escamilla 23240068 Cristina Tejada Sandoval 23240041 IMPARTE: Mtra. Fani Rodriguez Flores

Í N D I C E

Introduccion

Algoritmos

Conceptos

Aplicaciones

conclusion

ejemplo

Introduccion

El problema de la ruta más corta es uno de los problemas clásicos en la investigación de operaciones. Se trata de encontrar el camino más eficiente entre dos puntos en una red, minimizando el costo, la distancia o el tiempo necesario para recorrerlo.

01

Conceptos clave

Conceptos clave

Redes y grafos

Variables de Decisión

Costos

Una red se representa mediante un grafo, donde los nodos representan puntos (como ciudades o intersecciones) y las aristas representan las conexiones entre ellos (como carreteras o rutas).

Cada arista tiene un costo asociado, que puede ser la distancia, el tiempo de viaje, o cualquier otro factor relevante.

En este problema, las variables de decisión son binarias y representan si se recorre o no un tramo específico.

02

Algoritmos comunes

Algoritmo de Dijkstra

Algoritmos Comunes

Este algoritmo encuentra la ruta más corta desde un nodo origen a todos los demás nodos en una red con costos no negativos. Es eficiente y ampliamente utilizado en aplicaciones prácticas.

Algoritmo de Bellman - Ford

Similar al de Dijkstra, pero puede manejar redes con costos negativos. Es útil en situaciones donde los costos pueden variar.

Algoritmo A

Utiliza una heurística para mejorar la eficiencia en la búsqueda de la ruta más corta. Es especialmente útil en aplicaciones de inteligencia artificial y videojuegos.

04

Aplicaciones

Logistica y transporte

Redes de Comunicacion

Planificacion Urbana

Diseño de infraestructuras eficientes para el tráfico vehicular y peatonal.

Optimización de rutas de entrega para minimizar costos y tiempos de viaje.

Determinación de rutas óptimas para la transmisión de datos.

04

Ejemplo practico

(A)----6----(B) | \ / | 3 5 2 1 | \ / | (C)-7-(D)-3-(E)

Ejemplo Practico

Supongamos que tienes el siguiente grafo, donde los nodos representan ciudades y los números asociados a las aristas representan distancias en kilómetros

Paso 1: Definir el problemaNodos: A, B, C, D, E Aristas con distancias: A-B: 6 A-C: 3 A-D: 5 B-D: 2 B-E: 1 C-D: 7 D-E: 3 El objetivo es encontrar la ruta más corta desde A hacia todos los demás nodos. Paso 2: Inicializar distancias y nodos Nodo de inicio: A Distancias iniciales desde A: A: 0 (distancia a sí mismo) B: ∞ C: ∞ D: ∞ E: ∞ Conjunto de nodos no visitados: {A, B, C, D, E} Paso 3: Aplicar el algoritmo de Dijkstra Inicio en A: Desde A, las distancias iniciales son: A-B = 6 A-C = 3 A-D = 5 Actualizo las distancias: B: 6 C: 3 D: 5 Nodo más cercano no visitado: C (distancia 3)

Visitar C: Desde C, solo podemos ir a D (C-D = 7). Verificamos si mejoramos la distancia a D: Distancia actual A-D = 5, distancia a través de C: 3 + 7 = 10 → No mejoramos. Nodos no visitados: {B, D, E}. Nodo más cercano: D (distancia 5). Visitar D: Desde D podemos ir a B y E: Para B: A-D-B = 5 + 2 = 7 (B tenía 6, no mejora). Para E: A-D-E = 5 + 3 = 8 → Actualizo la distancia a E. E = 8 Nodos no visitados: {B, E}. Nodo más cercano: B (distancia 6). Visitar B: Desde B podemos ir a E: Para E: A-B-E = 6 + 1 = 7 → Mejoramos la distancia a E. E = 7 Nodo no visitado: E (distancia 7). Visitar E: No hay más nodos que mejorar. Termina el algoritmo. Paso 4: Resultado final Las distancias más cortas desde A son: A → A: 0 A → B: 6 A → C: 3 A → D: 5 A → E: 7 Paso 5: Ruta más corta hacia E La ruta más corta desde A hacia E es A → B → E con una distancia total de 7.

El problema de la ruta más corta es fundamental en la investigación de operaciones y tiene numerosas aplicaciones prácticas. Los algoritmos desarrollados para resolver este problema ayudan a optimizar procesos y mejorar la eficiencia en diversas industrias.

Conclusión

¡Gracias!

Referencias Bibliograficas

Blog de Leo. (n.d.). El problema de la ruta más corta. Recuperado de https://blog.nekomath.com/investigacion-de-operaciones-el-problema-de-la-ruta-mas-corta/ CCFProsario. (n.d.). Ruta más corta: optimiza tus procesos con Investigación de Operaciones. Recuperado de https://ccfprosario.com.ar/ruta-mas-corta-investigacion-de-operaciones/ Ingeniería Industrial. (n.d.). Algoritmo de la ruta más corta. Recuperado de https://ingenierosindustriales.jimdoweb.com/herramientas-para-el-ingeniero-industrial/investigacion-de-operaciones/algoritmo-de-la-ruta-mas-corta/ Ingeniería Industrial Online. (2019). Algoritmo de la ruta más corta. Recuperado de https://www.ingenieriaindustrialonline.com/investigacion-de-operaciones/algoritmo-de-la-ruta-mas-corta/