Problema de la ruta más corta
El problema de la ruta más corta es uno
de los problemas más importantes de optimización combinatoria con muchas
aplicaciones, tanto directas como subrutinas en otros algoritmos de
optimización combinatoria. Los algoritmos para este tipo de problemas han sido
estudiados desde la década de los 50’s y continúan siendo un área activa de
investigación. De hecho, ha sido el objetivo de una investigación extensiva
durante muchos años y ha dado como resultado la publicación de un gran número
de documentos científicos.
Encontrar la ruta más corta entre dos
nodos de una red, en la cual cada arco tiene un costo (o longitud) no negativo
es un problema que a menudo se presenta en cierto tipo de actividades. El
objetivo es minimizar el costo (tiempo o longitud) total.
El problema de la Ruta más Corta es
fundamental en muchas áreas, como son: investigación de operaciones, ciencia de
la computación e ingeniería. Algunas de las razones son:
1.- La amplia variedad de aplicaciones
prácticas como es el envío de algún material entre dos puntos específicos de la
forma más eficiente, económica o rápida.
2.- Existen métodos de solución
eficientes, los cuales al ser aplicados a una red con características
específicas (acíclica y con costos no negativos), proveen una solución exacta a
un tiempo y costo razonables.
3.- Se puede utilizar como inicio en el
estudio de modelos complejos de redes, esto es, cuando no se conoce la
estructura de la red se pueden aplicar algoritmos para conocer algunas
características de la red (presencia de ciclos negativos).
4.- Se utiliza frecuentemente como
subproblemas (subrutinas) en la solución de problemas combinatorios y redes,
así en el caso de problemas para los cuales no existe un algoritmo de solución
exacto (p. e. problemas NP-completos), la aplicación de algoritmos de ruta más
corta, resultan auxiliares para encontrar una buena solución.
Aplicaciones
El problema de ruta más corta tiene
muchas aplicaciones prácticas, algunas son: encontrar la ruta más corta o más
rápida entre dos puntos en un mapa, redes eléctricas, telecomunicaciones,
transporte, planeación de tráfico urbano, trasbordo, diseño de rutas de
vehículos, planeación de inventarios, administración de proyectos, planeación
de producción, horarios de operadores telefónicos, diseño de movimiento en
robótica, redes de colaboración entre científicos, reemplazo de equipo, etc.
Además, como se mencionó anteriormente los algoritmos de solución pueden
adaptarse en la búsqueda inicial de una solución aproximada de problemas
complejos, esto significa que la aplicación consiste precisamente en proveer
estructura para varios problemas de optimización combinatoria como: el problema
de la mochila, secuencia de alineación en biología molecular (secuenciación del
ADN), el problema del agente viajero, etc.
Ejemplo
•Determine la ruta más corta entre
Seattle y El Paso para la siguiente red de carreteras.
•Solución- Analogía de un problema
de programación lineal.
– Variables de Decisión
•Solución- Analogía de un problema
de programación lineal.
-Variables de decisión
Conclusión
El método de la ruta más corta es
uno de mucha importancia dentro del área de la investigación de operaciones,
debido a que, gracias a esto, las empresas pueden minimizar costos de envió
principalmente, además de conocer cuál es la menor distancia posible entre
varios puntos, entre varias otras funciones que este método conlleva.
Solo hay que imaginar que hoy en
día casi la un tercio de las compras se hacen en línea, las compras online
conllevan un gran peso para las empresas más grandes de paquetería, Y los
problemas de la ruta más corta, hacen que el producto llegue más rápido y con
un costo de envió más barato.
Pero olvidemos ahora lo de las
compras online, pongámonos en el caso de una gran empresa de barcos con
productos de importación, El costo se elevaría por las nubes, Ya que aquí
estamos hablando de viajes continentales y de miles de kilómetros de distancia,
donde también por obvias razones se tienen que reducir al tiempo los tiempos y
los gastos.
No hay comentarios:
Publicar un comentario