Segunda entrega del proyecto

Resumen del proyecto

Nuestro proyecto consiste red de entregas de logística (como DHL, por ejemplo) para encontrar la ruta más óptima para entregar un objeto desde la central de la empresa hasta su destino.

Nota: Se cambió la definición del proyecto, ya que la anterior idea era muy ambigua y no pegaba con un sistema adaptativo.


Avances

Se ha identificado el problema a resolver, que consiste en una instancia del problema del camino más corto. Este problema busca encontrar el camino que minimice el costo de algo, ya sea distancia, tiempo o cualquier otro parámetro que se tome en cuenta.

Una grafo, todavía sin ponderar, que representa una red de calles/ciudades.

El algoritmo debería ser capas de resolver cuál ruta es mejor, por ejemplo, desde el nodo J hasta el nodo V

Para resolver este problema se diseñará un algoritmo que pueda resolverlo mediante metaheurísticas (propias y de terceros), pero también se tendrá que implementar un algoritmo que permita introducir la información de los nodos, cuáles están conectadas y cuáles no, de manera sencilla, esto con el fin de poder brindar un sistema que pueda resolver cualquier configuración de nodos que se le dé, siempre y cuando la información esté bien “diseñada” primero.

Para resolver este problema he introducido un concepto de un "nodo fantasma", cuya ubicación puede ser cualquiera (aunque de preferencia independiente de otro nodo), el cual esté "conectado" con todos los nodos. El propósito de este nodo es brindar una "ayuda" al algoritmo, pues con dicha información relacionado a este nodo será posible conocer cuál es la distancia entre dos nodos, aun si no estén conectados directamente.

Por ejemplo, si estoy en el nodo A y quiero saber que tan lejos estoy del nodo T sólo se tendría que triangular las distancias, aunque hay que investigar cómo implementarlo en un algoritmo...

Lista de recursos y herramientas

• Lenguaje de programación JAVA: No es el lenguaje más óptimo cuando se requiere conservar recursos, pero por su facilidad de uso y la robustez que constituye el paradigma de la programación orientada a objetos nos ayudará mucho en la elaboración de nuestro proyecto.

• IDE Eclipse: Es fácil de utilizar y ayuda muchísimo cuando se escribe el código.

• Meta heurística del algoritmo de colonización de hormigas: A pesar de que nuestro proyecto no tiene que ver con el problema del viajero, es muy parecido en cuanto su estructura, por lo que ayudará en la elección de nodos cuando se quiere encontrar el más óptimo. No obstante, es claro que se necesitará implementar nuevos algoritmos, que para efectos de conveniencia tendrá que crearse nuevas estructuras de información.

Bosquejo de solución

1 - Inicializar grafo
2 - Pedir nodo de inicio
3 - Pedir nodo a encontrar
4 - Criterio de terminación (iteraciones, tiempo, etcétera...)
5 - Mientras Criterio de terminación no se cumpla
6- Algoritmo de búsqueda de nodos (meta heurístico propio basado en ACO)
7 - Fin Mientras
8 - Mostrar los resultados