Estudio de técnicas de Inteligencia Artificial aplicadas a una plataforma de planificación de servicios móviles.

Se trata de un nuevo proyecto  del cual la Unidad de Desarrollo Tecnológico en Inteligencia Artificial me ha hecho partícipe tomando un rol bastante principal. El proyecto está relacionado con la planificación de rutas de vehículo de transporte. 

Introducción 

Con la aparición y rápida evolución de las tecnologías de la información y de las comunicaciones, en la actualidad no se entiende un vehículo de transporte o turismo sin un control de localización remoto. Esto ha hecho que durante los últimos años hayan aparecido muchos sistemas de localización de vehículos.

Aunque en la actualidad exista un ingente número de empresas que se dedican al desarrollo de sistemas de navegación y localización, son muy pocas las que realizan sistemas completos de planificación y optimización, como las que demanda el mercado actual.

Este estudio se enmarca dentro de un proyecto d desarrollo de una suite de aplicaciones informáticas complementarias y necesarias para construir una Plataforma de Servicios Móviles para dar soporte a la

• planificación,
• control y
• gestión

de recursos móviles, así como las actividades diarias del sector empresarial. 

Nuestro objetivo

El objetivo de la Unidad de Desarrollo Tecnológico en Inteligencia Artificial es estudiar las tecnologías, basadas en inteligencia artificial, adecuadas para solcuionar el problema de la planifiación de las rutas de los servicios móviles. 

Es necesario investigar...

El problema del diseño de rutas de repartos es un problema bien conocido desde el punto de vista de la investigación. Se trata de un problema de cobertura de nodos. Estos nodos son unidos mediante rutas que parten y finalizan en nodos especiales llamados depósitos. A este problema se le conoce como VRP (Vehicle Routing Problems).

Por lo tanto, el problema se centra en encontrar la ruta de distancia mínima para cubrir un conjunto de nodos con ciertas restricciones. Se debe pasar una sola vez por cada nodo, desde un nodo origen que a su vez será destino generando así una ruta cerrada.

Dado que el problema de enrutamiento de vehículos VRP es de difiultad combinatoria (NP-complete), se deben explorar otras téncicas, basadas en inteligencia artificial, con la finalidad de obtener soluciones subótimas en tiempos aceptables. La realidad es que no existen en el mercado programas informáticos que puedan ofrecer una solución óptima en un tiempo viable. 

Solución VRP con algoritmo del vecino más próximo. Soft desarrollado en la UDT-IA

Los problemas de cobertura de nodos, a los que hacen referencia el presente estudio, se pueden clasificar en:

• TSP (Traveling Salesman Problem)
• m-TSP (Traveling Salesman Problem con m vehículos)
• VRP (Vehicle Routing Problem)
• CVRP (Capacited Vehicle Routing Problem)
• VRPTW (Vehicle Routing Problem with Time Window)
• CVRPTW (Capacited Vehicle Routing Problem with Time Window)

La clasificación anterior responde a diferentes evoluciones del problema de cobertura de nodos o diseño de rutas de reparto. En el futuro hablaré de cada una de ellas [Actualización

24/02/2008]. Estas evoluciones añaden complejidad al problema:

• Rutas para m vehículos, m>1.
• Rutas multi-depósito.
• Rutas con restricciones de tiempo o ventanas de tiempo.
• Rutas con restricciones de capacidad en los vehículos.

Otros datos

• Financiación: Ministerio de Industria Turismo y Comercio – Avanza I+D 2008
• Duración: Enero 2009 - Marzo 2009 (intervención de la UDT-IA).
• Coordinación:
  Unidad de Desarrollo Tecnológico en Inteligencia Artificial (UDT-IA, IIIA-CSIC) - Josep Puyol

Más información

Speed Telematics 

Vehicle Routing Problem