Diseño de una heurística de construcción y nuevos operadores de mejora para la resolución de problemas de asignación de rutas a vehículos con restricción de ventanas de tiempo

Resumen

El transporte es un sector que juega un papel muy importante en la sociedad de hoy en día. La distribución de mercancías, el movimiento de personas, o la provisión de servicios como la recogida de residuos, son actividades que impactan directamente en la calidad de vida, pero que también tienen una considerable repercusión en la economía y el medio ambiente. En el ámbito científico, el transporte tiene una relevancia igualmente crucial puesto que en torno a esta área de aplicación han surgido un sinfín de problemas difíciles de resolver debido a su complejidad computacional. Esto provoca que en muchas ocasiones sea prácticamente imposible la obtención de soluciones factibles, siendo necesario el uso de técnicas de aproximación que permitan obtener una buena solución en un tiempo limitado. En este sentido, surgen un amplio abanico de problemas de optimización y técnicas de resolución que tienen como objetivo principal la mejora continua para la obtención de soluciones cada vez más precisas, y con costes computacionales permisibles. La presente tesis doctoral se enmarca en el área de los problemas de generación de rutas para vehículos. Estos tipos de problemas han sido ampliamente estudiados durante los últimos 50 años, y siguen siendo foco de interés científico hoy en día, ya que aún no existe una técnica capaz de resolver de manera adecuada algunas tipologías de problemas. Es por esta razón que es posible encontrar y abordar puntos de mejora que contribuyan a la optimización de los procesos de resolución existentes. Con todo lo anterior, el trabajo de tesis doctoral presentado en este documento focaliza sus esfuerzos en la mejora del proceso de resolución de una de las variantes más ampliamente estudiadas del problema básico de asignación de rutas a vehículos: la variante con ventanas de tiempo (VRPTW). En concreto, se abordará el desarrollo de algoritmos para dos de las fases del proceso de resolución: la construcción de la solución inicial y la mejora iterativa de soluciones. La principal novedad del enfoque propuesto se encuentra en la definición de operadores de mejora basados en la reducción del número de rutas (que es uno de los criterios utilizados para medir la calidad de una solución). Tras una extensa experimentación comparando los métodos propuestos con las técnicas más representativas, y un exhaustivo y riguroso análisis de los resultados obtenidos, puede concluirse que los algoritmos generados representan un complemento idóneo para ser integrado en cualquiera de las técnicas heurísticas o metaheurísticas que atesoran los mejores resultados para los juegos de ensayo referentes en el contexto del VRPTW.