Planificación de rutas de transporte en sistemas de distribución multinivelel problema de VRPTW
- Alejandro García del Valle Director
- Eduardo Guillén Solórzano Director
Defence university: Universidade da Coruña
Fecha de defensa: 28 September 2009
- Francisco Javier Faulín Fajardo Chair
- Susana Barbeito Roibal Secretary
- Pedro Figueroa Dorrego Committee member
- Ángel Alejandro Juan Pérez Committee member
- Manuel Martínez Carballo Committee member
Type: Thesis
Abstract
La presente tesis se ha enfocado al análisis del problema de planificación de rutas de transporte en la pequeña y mediana empresa. Este problema no sólo afecta a las Pymes del sector de distribución y reparto, sino que afecta a todas aquellas empresas en las que sus costes de distribución tienen un peso significativo en sus cuentas de explotación. Cada día es mayor la importancia que tiene la obtención de ahorros significativos en el reparto de mercancías y el mantenimiento de altos niveles de calidad en lo que se refiere al cumplimiento de los requerimientos del cliente. En los últimos años, en base a los desarrollos de los Sistemas de Información Geográfica y a la disponibilidad de hardware cada vez más potente, se han desarrollado también aplicaciones de gestión logística y Sistemas Integrados de Información Logística, si bien la inmensa mayoría se dirigen hacia grandes empresas. Este problema es bien conocido en la literatura como el Problema de Rutas de Vehículos, cuyas siglas en inglés son VRP (Vehicle Routing Problem), una generalización del problema del viajante, cuyas siglas en inglés son TSP (Travelling Salesman Problem), en el que se debe encontrar la ruta de distancia mínima entre un conjunto de puntos geográficamente dispersos, visitándolos todos una sola vez, volviendo al finalizar la ruta a su origen. Si generalizamos el problema del TSP, admitiendo un número NV de vehículos limitados por tiempo de utilización y por carga máxima, y asignamos demandas en cada uno de los nodos a visitar, nos encontramos con el problema del VRP. Si al VRP le añadimos restricciones temporales de servicio en los nodos, nos encontramos con el Problema de Rutas de Vehículos con Ventanas de Tiempo, o VRPTW (Vehicle Routing Problem with Time Windows). En la última década del siglo pasado se obtienen los avances más importantes en los sistemas de resolución del VRPTW mediante metaheurísticos: algoritmos genéticos, búsqueda tabú y recocido simulado. Más cerca en el tiempo se plantean métodos tipo colonias de hormigas, redes neuronales y metaheurísticos híbridos que combinan distintos métodos en varias fases. En los últimos tiempos se identifica por parte de varios autores, la correlación existente entre las soluciones de partida de los metaheurísticos y los resultados finales de los mismos, de ahí que sea muy importante, para la resolución del problema, partir de un buen método de construcción de rutas. De igual forma, una solución inicial buena reducirá las necesidades de cálculo de los métodos de post-optimización. Si nos centramos en el entorno de las Pymes en las que las rutas tienden a ser cortas y las capacidades financieras, organizativas y de gestión tienden a ser muy reducidas, se hace patente que lo que éstas necesitan es un método muy rápido y que no necesite usar grandes recursos de ningún tipo. Por ello y siguiendo los trabajos previos de Guillén y del Valle, circunscribimos este trabajo a las técnicas de construcción de rutas y el desarrollo de un método eficiente de construcción de rutas.