Resumen

El presente trabajo propone el uso de metaheurísticas y computación paralela para resolver un problema real de enrutamiento de vehículos con flota heterogénea, ventanas de tiempo y entregas fraccionadas, en el que la demanda de los clientes puede ser mayor que la capacidad de los vehículos. El problema consiste en determinar un conjunto de rutas económicas que deben satisfacer las necesidades de cada cliente respetando todas las restricciones. La estrategia adoptada para resolver el problema consiste en utilizar una adaptación de la heurística constructiva propuesta por Clarke y Wright (1964) como solución inicial. Posteriormente, se implementa un algoritmo genético paralelo que se resuelve con la ayuda de un cluster de ordenadores, con el objetivo de explorar nuevos espacios de solución. Los resultados obtenidos muestran que la heurística constructiva básica presenta resultados satisfactorios para el problema, pero puede mejorarse sustancialmente con el uso de técnicas más sofisticadas. La aplicación del algoritmo genético paralelo de múltiples poblaciones con solución inicial, que presentó los mejores resultados, proporciona una reducción del coste total de la operación del orden del 10%, en relación con la heurística constructiva, y del 13%, cuando se compara con las soluciones utilizadas originalmente por la empresa.

1. INTRODUCCIÓN

Dror y Trudeau (1989, 1990) introdujeron recientemente en la bibliografía el problema de las rutas vehiculares con entregas divididas (SDVRP), presentando la formulación matemática del problema y analizando el ahorro que puede generarse al permitir que un cliente sea atendido por más de un vehículo, tanto en relación con el número de vehículos como con la distancia total recorrida.

Según Dror y Trudeau, el SDVRP es una relajación del problema clásico de enrutamiento de vehículos, pero sigue siendo NP-completo. Los autores demostraron que cuando las distancias satisfacen la desigualdad del triángulo, existe una solución óptima al problema tal que ningún par de rutas tiene dos o más vértices en común.

El SDVRPTW es una generalización del problema de enrutamiento de vehículos con entrega dividida (SDVRP) mediante la adición de restricciones de ventana temporal. Ho y Haugland (2004) demostraron que la propiedad de desigualdad triangular de Dror y Trudeau (1989, 1990) también es válida para el SDVRPTW.

El objetivo de este trabajo fue desarrollar heurísticas y metaheurísticas para un problema real de enrutamiento de vehículos con ventanas de tiempo y entregas divididas (Split Deliveries Vehicle Routing Problem with Time Windows SDVRPTW), con el fin de optimizar el sistema de transporte. En primer lugar, se implementa una adaptación de la heurística de Clarke y Wright (1964).

• Materias:Logística Algoritmo genético Algoritmos metaheurísticos Operación logística Transporte por carretera
• Subjects:Logistics Genetic algorithm Metaheuristic algorithms Logistics operation Road transport
• Palabras claves:Problema de enrutamiento de vehículos; Ventanas de tiempo; Entregas divididas; Metaheurísticas
• Keywords:Vehicle routing problem; Time windows; Split deliveries; Metaheuristics