EL PROBLEMA DE LA RUTA OPTIMA: UNA REVISIÓN DESDE LA TEORÍA DE GRAFOS

El análisis de red más común consiste en buscar la ruta más corta entre dos puntos, sin embargo antes de conocer cómo opera un algoritmo de ruta óptima se hace necesario conceptualizar la definición de red, de modo que una red es un sistema de elementos interconectados, como bordes (líneas) y cruces de conexión (puntos), que representa las posibles rutas desde una ubicación a otra. Las personas, recursos y bienes tienden a circular a través de redes: los carros y camiones circulan por carreteras, los aviones de transporte vuelan en rutas de vuelo predeterminadas, el petróleo circula por conducciones. Modelando las rutas de viaje potenciales con una red, es posible realizar análisis relacionados con el movimiento del petróleo, camiones u otros agentes en la red. Una red se compone de elementos puntuales (nodos) y lineales (arcos), pudiendo establecer un coste o impedancia que mide la dificultad del desplazamiento desde un origen a un destino en diferentes unidades: metros de recorrido, tiempo de recorrido, costes monetarios, etc. Dichos parámetros de fricción se emplean para definir impedancias de arcos (distancias, tiempo) o de arcos y nodos (giros y jerarquías de redes).

En la teoría de grafos o topología primitiva, el problema del camino más corto consiste en encontrar un camino entre dos vértices o nodos, de tal manera que la suma de los pesos de las aristas que lo constituyen sea mínima. Un ejemplo es encontrar el camino más rápido para ir desde un centro hospitalario a un punto de emergencia en un mapa. En este caso, los vértices representan el centro hospitalario y el punto que representa la ubicación de un accidente de tránsito y las aristas las carreteras que unen dichos puntos cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. 

Los algoritmos voraces más importantes para resolver este problema son: Algoritmo de Dijkstra, este resuelve el problema del camino mínimo entre dos vértices, desde un origen y un único destino. Este algoritmo consiste en ir explorando todos los caminos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino mínimo desde el vértice origen al vértice destino, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de coste uniforme y como tal no funciona en grafos con aristas dirigidas. Por su parte el algoritmo de Bellman-Ford resuelve el problema de del camino mínimo desde un origen si la ponderación de las aristas es negativa o dichas aristas poseen dirección. Los algoritmos de camino mínimo se usan para encontrar la solución de la ruta óptima que utiliza el mínimo número posible de movimientos, es decir, para encontrar una secuencia optima de opciones para llegar a un determinado destino.


REFERENCIAS


[1] "Social Network Analysis: A Handbook", John Scott Ed. Sage Publications Inc, 2000,ISBN 0-7619-6339-1

[2] "Network Analysis and Troubleshooting", J. Scott Haugdahl, Ed. Addison-Wesley, 1999, ISBN 0-201-43319-2

[3]https://investigaciondeoperaciones.wordpress.com/2010/04/01/problemas-de-transporte-del-analisis-de-redes/

[4]https://books.google.com.co/books?id=sA1dSQko3PAC&pg=PR12&lpg=PR12&dq=analisis+de+problemas+redes+de+transporte&source=bl&ots=YQ5gmI5Vkd&sig=HHsUVs8ei4Q60dCtAnjKAUxIZG8&hl=es&sa=X&ei=1PIiVYPHKcLvggTkhYS4BA&ved=0CFIQ6AEwCw#v=onepage&q=analisis%20de%20problemas%20redes%20de%20transporte&f=false

[5] Sánches, E. Una Mirada al análisis de Redes de Transporte en Cuba desde el punto de Vista de los Datos. 2013. Lampsakos. Medellín Colombia

[6] Ramirez, L. Determinación de área de influencia hospitalaria mediante el análisis espacial en SIG. Universidad Nacional del Nordeste.