Análisis de los métodos de construcción de rutas en los sistemas de planificación para el problema del VRPTW

Resumen

Este trabajo analiza el problema de la planificación de rutas de transporte con restricciones temporales, algo que en la literatura se conoce con el nombre de Vehicle Routing Problem with Time Windows, o simplemente VRPTW. Para ello se contemplan tres campos complementarios: en primer lugar se ha realizado un estudio de la problemática empresarial, atendiendo a las necesidades puntuales de las empresas en el sector, así como de las soluciones informática existentes para resolver dichos problemas. En segundo lugar, se plantea un análisis de la evolución de los métodos de solución recogidos en la literatura para la resolución del problema a través de múltiples algoritmos, y que fundamentan en los problemas del Traveling Salesman Problem y del Vehicle Routing Problem, como antecedentes del VRPTW. A partir de estos estudios se presena un modelo propio centrado en los procesos de construcción de rutas, más que en los algoritmos de postoptimización. Para ello se persiguen una serie de reglas fundamentadas en los principios de asignación, inserción (simple y doble), y adición, previamente contemplados por otros autores. Este algoritmo se basa en una aplicación informática para su implementación en diferentes problemas, aunque en este trabajo se ha validado a través de su aplicación a los problemas estándar de la literatura, y que mayormente hacen referencia a los ejemplos de Solomon (1987). En la última parte del trabajo se detallan los resultados del propio algoritmo, así como se establece la comparativa con otros planteamientos recogidos en la literatura. Como conclusión final, cabe destacar el mejor comportamiento del método en algunos grupos de ejemplos, en particular aquellos similares a los problemas estudiados, aunque en otros casos la eficacia del método ha de ser mejorada.