Tecnologías Específicas

Computación

Descripcion y Objetivos

Una empresa de la región está interesada en incorporar a su sistema una nueva funcionalidad que le permita diseñar de forma eficiente las visitas de sus comerciales y transportistas. Mediante la incorporación de un algoritmo de rutas.

El problema de rutas es un problema clásico en la literatura, donde hay una serie de destinos a visitar y hay que encontrar la mejor ruta minimizando la distancia recorrida, (problema del viajante).

El objetivo del proyecto es diseñar un algoritmo que encuentre una buena ruta en función de una serie de parámetros configurables en los destinos a visitar, como son: hora a la que se quiere llegar, tiempo de parada en cada destino, congestión en la ruta, etc.

El algoritmo a diseñar debe de tener en cuenta estos parámetros para el diseño de la ruta y ofrecer una solución con la ruta donde se cumpla las restricciones impuestas por el usuario o en caso de que no se pueda, porque las restricciones impuestas hacen imposible seguir una ruta, que devuelva una ruta alternativa indicando que destinos no pueden visitarse y por qué motivo.

El algoritmo debe incorporar la siguiente funcionalidad:

• Posibilidad de incorporar múltiples destinos.
• Lugar de salida, donde comience y termine la ruta.
• Hora de salida, se puede incorporar como dato inicial o el algoritmo debe estimarlo en función de a la hora que se quiera llegar al primer destino.
• Tiempo estimado de cada parada, el usuario incorporará cuanto tiempo estima demorarse en cada destino, para que el algoritmo a parte de la ruta indique tiempos estimados de llagada a cada destino.
• Hora destino, incorporar la hora a la que se quiere estar en un destino determinado, por ejemplo hora a la que se tiene una reunión. En función de esta se determinará la hora de salida y la llegada y salida a los destinos previos.
• Poder incorporar información de los destinos, información útil para el usuario, como dato del contacto a visitar, lugar de la reunión, etc.
• Poder incorporar información de la persona que hace la ruta, teléfono mail, nombre.
• Campo de anotaciones con información. Se pretende poder hacer anotaciones a la persona que viaja (por ejemplo para conductores de camiones indicar la anchura de la calle).
• Campo de anotaciones para el usuario. Se quiere que si la herramienta es usada por comerciales, estos puedan guardar anotaciones, ofertas o cualquier dato que consideren interesante para futuras reuniones.

 

Con toda esta información se debe diseñar un algoritmo que devuelva el orden en que debe visitar los destinos y tiempo estimado de llagada a cada destino.

Otras opciones a estudiar:

• Incorporación de la variable de tráfico y cortes de tráfico.
• Incorporación de la ubicación de las gasolineras y su precio.
• Incorporación de datos meteorológicos con alertas.
• Guardar toda la información y mantenerla como histórico en una Base de Datos.

 

Lenguaje de desarrollo

El sistema será implantado en una plataforma web realizada en php, por lo que el proyecto debe de ser desarrollado en algún lenguaje compatible con la plataforma.

 

Metodología y Competencias

Metodoligía:

1. Estudio del problema para entender los principales elemento y la utilidad del algoritmo.
2. Estudio del estado del arte, qué algoritmos hay, cómo abordan el problema, qué resuelven, qué técnicas utilizan y cómo lo hacen.
3. Implementación del algoritmo.
4. Testeo y pruebas del algoritmo implementado.
5. Integración del algoritmo en la plataforma.

Copetencias:

• Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

• Capacidad para conocer los fundamentos, paradigmas y técnicas propias de los sistemas inteligentes y analizar, diseñar y construir sistemas, servicios y aplicaciones informáticas que utilicen dichas técnicas en cualquier ámbito de aplicación.

• Capacidad para adquirir, obtener, formalizar y representar el conocimiento humano en una forma computable para la resolución de problemas mediante un sistema informático en cualquier ámbito de aplicación, particularmente los relacionados con aspectos de computación, percepción y actuación en ambientes entornos inteligentes.

 

Medios a utilizar

La empresa colaboradora dará acceso a sus bases de datos y a su plataforma para que el estudiante pueda desarrollar con mayor facilidad el trabajo.

 

Bibliografía

• “Metaheuristics for Vehicle Routing Problems”, Nacima Labadie, Christian Prins, Caroline Prodhon
• “Vehicle Routing: Problems, Methods, and Applications”, Paolo Toth and Daniele Vigo