Diseño y evaluación de algoritmos de planificación de rutas eficientes para flotas de vehículos

Abstract

Los problemas VRP (Vehicle Routing Problems) son la generalización del problema del viajante (Travelling Salesman Problem), y consisten en encontrar un conjunto de rutas para K vehículos, tal que cada una de las ubicaciones sea visitada únicamente una vez, minimizando el coste total de las rutas. De este problema, ya de por sí computacionalmente complejo (NP-Hard), se han planteado diversas variantes. Entre ellas, algunas de las más comunes son el Capacitated VRP (CVRP), donde cada cliente demanda unas mercancías concretas y cada vehículo tiene una capacidad finita; el VRP con Time Windows (VRPTW).Además de ellas el proyecto intenta presentar una visión innovadora incorporando también restricciones de incompatibilidad de mercancías. Todo ello combinado con dataset reales de empresas del sector de la logística da lugar al también denominado R-VRP. Cada aplicación introduce características y parámetros específicos en la formulación del problema, dando lugar a nuevas restricciones, y requiriendo algoritmos desarrollados ad-hoc para cada caso. En concreto se va a utilizar un solver open source denominado Optaplanner, de cara a evaluar el rendimiento de la herramienta y comprobando su efectividad al resolver el problema en comparación con propuestas académicas concreta. Finalmente se observa como su rendimiento es realmente bueno aunque presenta ciertas restricciones a la hora de incorporar nuevas restricciones complejas al algoritmo como es el caso que nos atañe