Algoritmo PSO-Híbrido para solucionar el problema de ruteo de vehículos con entrega y recolección simultáneas

PSO-Hybrid algorithm for solving the vehicle routing problem with simultaneous pickup and delivery

Se presenta la metaheurística de Optimización de Enjambre de Partículas (PSO) para la solución del Problema de Ruteo de Vehículos con Entrega y Recolección Simultáneas (VRPSPD). Se aplica una representación de la solución y un método de decodificación para implementar el PSO al VRPSPD. El método de decodificación inicia transformando una partícula en una lista de prioridades de clientes para entrar a las rutas y en una matriz de prioridades de vehículos para servir cada cliente. Las rutas de los vehículos son construidas con base en la lista de prioridad de clientes y en la matriz de prioridad de vehículos. El algoritmo es validado usando 18 instancias disponibles en la literatura para problemas de 100, 200 y 400 clientes.

I. INTRODUCCIÓN

El Problema Ruteo de Vehículos (VRP, su sigla en inglés) consiste en la construcción de rutas desde un depósito hasta un número determinado de clientes ubicados en un espacio geográfico, con el fin de ofrecerles algún tipo de servicio con una flota de vehículos, siendo la entrega de bienes el más común. El diseño de sistemas de distribución efectivos puede representar un significativo ahorro de costos a las empresas [1].

Dada su vigencia en la gestión empresarial del ambiente económico actual, el cual exige la nivelación adecuada de flujos de bienes entre los diferentes agentes de la cadena de suministros para alcanzar mejores indicadores de competitividad, han surgido variaciones del problema, relacionadas con el tipo de actividad logística llevada a cabo en la asignación de rutas de transporte. Algunas de las mayores exigencias a los sistemas de distribución están dadas por las crecientes preocupaciones medioambientales, que han dirigido esfuerzos hacia la protección del ambiente tanto en la industria como en la legislación. Un mejor manejo de desperdicios y de energía consumida, que permita directamente una reducción de costos, ha generado que el desensamble, el reciclaje parcial y completo, la remanufactura y la reutilización de bienes formen parte de los nuevos enfoques de producción y administración de la cadena de suministros [2].

Una de las variaciones del VRP que encuentra gran aplicación en las operaciones logísticas de las empresas en la actualidad es el Problema de Ruteo de Vehículos con Entrega y Recolección Simultáneas (VRPSPD, su sigla en inglés), propuesta por Min [3] , quien se interesó por un transporte de libros en una biblioteca. En el VRPSPD, además de entregar bienes a los clientes, la flota de vehículos debe recoger otros bienes desde la ubicación de los clientes de manera simultánea, considerando restricciones de capacidad y tiempo, con el objetivo de minimizar costos, distancias o tiempos de viaje.