Metodología de algoritmos meméticos para el problema de ruteo de vehículos con entregas parciales y tiempos de viaje dependientes con ventanas de tiempo

El problema de ruteo de vehículos VRP es uno de los problemas más estudiados en investigación de operaciones, dada su relevancia en los campos del transporte y la logística. En los últimos años ha aumentado el interés en minimizar la contaminación por la emisión de gases efecto invernadero a causa del consumo de combustibles fósiles. El sector transporte representa una parte importante en esas emisiones. En el transporte, situaciones como los embotellamientos en las horas pico, por ejemplo, conducen a una red vial dinámica en la que varían los tiempos de viaje y consecuentemente el consumo de combustible. Por lo anterior el problema de enrutamiento de vehículos con tiempos dependientes TDVRP es una representación más cercana la vida real que los modelos tradicionales de enrutamientos de vehículos, VRP. Por otro lado, el problema de enrutamiento de vehículos con partición de entregas, SDVRP permite asignar múltiples rutas a un mismo cliente, propiciando ahorros en las mismas. El objetivo de esta tesis es desarrollar un método para el uso de los recursos de transporte, con el fin de atender a los clientes de manera eficiente respecto al costo total de la distancia recorrida y al tiempo total de viaje requerido. El problema consiste en programar un recorrido durante un día dividido en intervalos o zonas horarias, con ventanas de tiempo para atender a cada cliente, vehículos homogéneos con capacidad fija Q y un depósito único. Para ello se propone en este trabajo un Algoritmo Memético (MA) capaz de encontrar soluciones que respetan las restricciones del problema, teniendo en cuenta la posibilidad de hacer particiones en las entregas. Mediante el Diseño de Experimentos se evaluó la calidad de las soluciones generadas respecto a un Algoritmo Genético (GA) desarrollado también para el propósito, teniendo como criterio de evaluación el porcentaje de mejores soluciones alcanzado por cada algoritmo. Los experimentos permiten afirmar que el Algoritmo Memético propuesto supera el Algoritmo Genético, resultando más robusto ante cambios en los parámetros de ambos métodos. La solución propuesta representa un modelo más cercano a la realidad de las redes viales y genera rutas tendientes a disminuir la cantidad, recorrido y tiempo de permanencia de los vehículos en la red vial, conllevando a la disminución de las emisiones de gases efecto invernadero.

• Autores: Cadavid Jaramillo, Jhoan Sebastián
• Fecha de publicación: 2019
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/76923
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/76923; http://bdigital.unal.edu.co/73941/
• Palabra clave: Problema de ruteo de vehículos; Estudio de tiempos y movimientos; Metaheurístico; Algoritmo Memético; Split Delivery; Memetic Algorithm
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional