Arbol Expansion Minima

ANÁLISIS DE LA RUTA MAS CORTA A SEGUIR CON MODELOS DE REDES (ARBOL DE EXTENSION MINIMA).

¿QUÉ COMBINACIÓN DE CAMINOS HACE EL TIEMPO Y LA DISTANCIA MÁS CORTO Y EFECTIVO?

OMAR DE JESÚS JIMÉNEZ PRIETO

INTRODUCCIÓN

El primer día hábil de cada mes, se tiene por costumbre hacer un recorrido por distintos puntos de la ciudad, los cuales se lleva recorriendo por más de un año. Cada uno de los 5 puntos a visitar tiene distintos caminos, con kilómetros y tiempos distintos.

Una vez hecho el recorrido, siempre surge la misma pregunta, ¿en realidad se tomo el camino más corto?

A continuación, se responde a esta pregunta mediante el modelo de árbol de extensión mínima de modelos de redes.

OBJETIVOS

Analizar los caminos que conectan los 5 destinos a visitar cada primer día hábil de cada mes, tomando en cuenta la información obtenida en google maps, como la distancia en kilómetros, así como también el tiempo aproximado de arribo. El orden de visita no afecta en lo absoluto.

MODELO TEÓRICO Y METODOLOGÍA

Un modelo es una representación o abstracción de un fenómeno u objeto reales, que muestra las relaciones (directas e indirectas) y las interrelaciones de la acción y la reacción en términos de causa y efecto.

ÁRBOL DE EXTENSIÓN MÍNIMA

Dado un conjunto de nodos y un conjunto de arcos, el problema consiste en encontrar los arcos que se deben utilizar para que todos los nodos se conecten de manera que se minimice la longitud total de los arcos utilizados.

ALGORITMO PARA EL ÁRBOL DE EXTENSIÓN MÍNIMA

El algoritmo de red que puede utilizarse para resolver el problema del árbol de expansión mínima es muy sencillo. Los pasos del algoritmo son los siguientes:

Paso 1: Comenzar en forma arbitraria en cualquier nodo y conectarlo con el nodo más próximo. A estos dos nodos se les denomina nodos conectados o conexos y a los nodos restantes se les denomina nodos no conectados o inconvexos.

Paso 2: Identificar al nodo no conectado que esté más cerca de uno de los conectados. Deshacer los empates en forma arbitraria si son dos o más los nodos que califican como nodo más cercano. Agregar este nodo al conjunto de nodos conectados. Repetir este paso hasta que se hayan conectado todos los nodos.

Como ya se explicó anteriormente, cada primer día hábil del mes se tiene un recorrido acostumbrado visitando 4 puntos, se parte del fraccionamiento Lic. Manuel Gómez Morín con rumbo a fraccionamiento Olinda, Universidad Autónoma de Aguascalientes, Av. Héroe de Nacozari 126-A y fraccionamiento Ojocaliente I, no necesariamente con ese orden.

Se inicio buscando en google maps las rutas disponibles de cada punto A a punto B, vaciando los datos en WinQSB y descartando las rutas menos eficientes. Como objetos de estudio tomamos las distancias en kilómetros y en tiempo (minutos aproximados). Este procedimiento se realizo con los 5 puntos disponibles que llamaremos nodos.

Los datos más eficientes en distancia (kilómetros) se vaciaron en el software WinQSB nuevamente para la búsqueda de la solución. Ésta fue la tabla capturada:

Al igual que en distancia, se investigaron las caminos mas óptimos en términos de tiempo (minutos), y se capturaron nuevamente en el software WinQSB. Los datos quedaron de la siguiente manera:

SOLUCIÓN

Aplicando lo aprendido en el tema árbol de expansión mínima se procedió a dar salida a los datos obtenidos en el software utilizado arrojando

...