Contador


jueves, 10 de enero de 2019

2.4 Problema de la ruta más corta


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