Menu
Algoritmo de Dijkstra con WinQSB
En la optimización de recursos, uno de los aspectos que se deben de tomar en consideración es la reducción de costos.
En el caso de transporte de mercancías o personas de un sitio a otro se tiene un costo asociado a la distancia de transporte, por lo que se debe de buscar la ruta más corta desde el origen hasta el destino.
El procedimiento usado para encontrar esa distancia más corta es el algoritmo de Dijkstra, es un método analítico de la red que analiza las diferentes rutas y selecciona la más óptima.
Una red, representa las rutas del origen hacia el destino y los puntos intermedios, ambos representados por nodos, en el caso que se ilustra, se proporcionan las distancias entre cada uno de los nodos, las direcciones de las flechas indican el sentido en que se puede recorrer de un nodo a otro
La red de la figura representa el nodo de origen (1) y el nodo de destino (7), se trata de transportar material para formación de terraplén con camión del volteo, el banco de material se encuentra en el nodo (1) y el lugar donde se está formando el terraplén es el nodo (7), las flechas indican la dirección en que se pueden recorrer las distancias, cuando la flecha se muestra en dos sentidos, significa que hay bidireccionalidad.
Las distancias están indicadas en Kilómetros.
El problema consiste en determinar la ruta más corta entre los nodos (1) y (7) para minimizar los costos de transporte de material. Se usará el algoritmo de Dijkstra que se encuentra programado en el software WinQSB.
Se selecciona el módulo Network Modeling que es el indicado para el modelado de estas redes para solucionarlas con el algoritmo de Dijkstra que tiene programado.
Toda vez que se accesa al módulo, se da de alta un nuevo problema y de las opciones que aparecen se elige. Shortest Path Problem, se asigna el número de nodos que en este caso son 7, así como se asigna un nombre al problema
Se despliega un grid donde se deben de colocar las distancias entre nodos, teniendo en cuenta lo siguiente:
a).- Cuando no hay conexión entre nodos se deja vacío
b).- Por ejemplo, si por la direccionalidad si hay conexión del nodo 2 al 3, pero no del 3 al 2, entonces solamente se coloca la distancia de 2 a 3 y de 3 a 2 se deja vacío.
Del menú Solve and Analyze, se elige la opción Solve the Problem
Aparece un cuadro de diálogo donde se pide que se indique la menor distancia que se quiere conocer (de qué nodo de orígen a qué nodo de destino)
Para este problema, se requiere conocer la distancia más corta (y la ruta) para llegar al nodo (7) desde el nodo (1), la cual se muestra en la siguiente figura.
De acuerdo a la figura anterior, la menor distancia del nodo (1) al nodo (7) es de 7.50 Kilómetros, y la ruta que se debe de seguir es del nodo(1) al nodo(3), luego del nodo(3) al nodo(4) y finalmente del nodo(4) al nodo(7).
José Manuel Carrillo Hernández
Ingeniero Civil, Maestro en Ciencias en Ingeniería de la Construcción, Doctor en Ingeniería con especialidad en sistemas de planeación y construcción