Desarrollo de un algoritmo hibrido para la resolución del problema de ruteo de vehículos con entrega y recogida simultaneas (vrpspd)

Abstract

El problema de ruteo de vehículos con entrega y recolección simultánea es una variación del VRP que ha generado gran interés en la comunidad académica y en los sectores productivos debido a que considera la posibilidad de entregar y recoger bienes de forma simultánea. Por lo tanto, es un problema de gran aplicabilidad en una variedad de campos de la logística y la logística inversa. Particularmente, la complejidad de este problema está en la necesidad de servir un conjunto de clientes localizados en un espacio geográfico considerando la carga fluctuante de los vehículos en cada uno de los trayectos de las rutas. Matemáticamente, el VRPSPD es un problema de optimización combinatoria de tipo NP-hard para el cual encontrar buenas soluciones implica consumo de recurso computacional de tipo exponencial. Por esta razón, es común el uso de métodos aproximados como metaheurísticas y heurísticas, que permitan obtener buenas soluciones en tiempo computacional razonable. En este proyecto de investigación se propone el uso de un algoritmo aplicado al problema siglas en inglés), una heurística de construcción de rutas cheapest insertion heuristic y una heurística para mejoramiento de rutas de búsqueda local 2-opt. El método propuesto arroja buenos resultados y fue comparado con otros métodos propuestos para resolver 18 instancias disponibles en la literatura del problema VRPSPD.