• Generador de rutas óptimas para entregas en drone en la ciudad.

    Una herramienta de software para diseñar redes de distribución y calcular la mejor ruta desde tu origen hasta el destino seleccionado.

  • Utilizando teoría de grafos para ahorrar recursos.

    Impulsado por una implentación del algoritmo de Dijkstra, esta herramienta capaz de ofrecer la mejor solución personalizada a cada red de distribución establecida.

  • Para más información del proyecto revisa como usarlo o ve directo al funcionamiento , en donde se explica la metodología.

    Proyecto Final de Algoritmia

Más información

Descarga Drone Route Generator.

Se puede obtener el código fuente en GitHub. Dentro del repositorio también se puede consultar la licencia y más información al usuario.

Descargar

Documentación.

En este apartado se muestra una breve guía de uso para sacarle el máximo provecho a la funcionalidad implementada en la herramienta.

Objetivo y Metodología.

Esta herramienta fue creada con la idea de contar con procesamiento de gráfos para ser válida como proyecto final de la asignatura de Algoritmia.

¿Qué es?

Es una aplicación de escritorio programada en C#, que utiliza el conjunto de librerias de Windows Forms elaboradas por Microsoft para .NET Framework.

¿Para qué sirve?

Sirve para generar rutas de entrega locales optimizadas que ahorran tiempo empleando caminos mínimos en una red de entrega definida, asegurando la ruta más rápida de un punto a otro.

¿Cuál es el beneficio?

El principal beneficio de esta aplicación es el de generar redes y rutas de entrega de manera rápida y sencilla, además de optima apoyandose de la teoría de grafos.

Procesamiento.

Aplica el algoritmo de Dijkstra a un grafo previamente creado por el usuario, esta estructura de datos representa la red de distribución de un negocio que requiera entregas a través de la ciudad con un drone como medio de transporte.

Algoritmo de Dijkstra.

Desarrollado por el científico computacional Edsger Dijkstra, encuentra caminos mínimos en un grafo a partir de un vértice de origen, las características que requiere son: que el grafo sea conexo y ponderado con valores no negativos. Puedes consultar la implementación del algoritmo en este proyecto aquí.

Complejidad Algoritmica.

Expresando la complejidad en tiempo de ejecución del algoritmo de Dijkstra, la función dominante asíntotica sería representa por O(n2).

Resultados y Conclusiones.

Resultados obtenidos.

Después de varias pruebas en distintos casos de uso, la herramienta fue capaz de encontrar el resultado optimo cuando este estaba definido y podía ser calculado. En otras palabras, cuando el grafo cumplia con los requerimientos para ejecutar el algoritmo de Dijkstra. Ademas de exportar una imagen con el mapa con la ruta marcada y la distancia total de la misma.

Conclusión del proyecto.

Los principales puntos a remarcar al final de la implementación de este proyecto son, en primer lugar, la capacidad escalable de una aplicación cuya base es un algoritmo tan simple como el propuesto por Edsger Dijkstra para encontrar caminos mínimos, y como los grafos son una forma eficiente de representar la información relacionada.

Atribuciones.

Santiago Valle

Desarrollador

Estudiante de Ingeniería en Computación en la Universidad de Guadalajara.

Múltiples Contribuidores

Arte Dígital

Recursos visuales utilizados