Metodología para resolver el problema de ruteo de vehículos con entregas y recogidas simultáneas - VRPSPD utilizando el algoritmo genético de Chu – Beasley combinado con técnicas exactas

Resumen

En este artículo se presenta una metodología para resolver el problema de ruteo de vehículos homogéneos con entregas y recogidas simultáneas (VRPSPD) utilizando una matheurística, conformada por el algoritmo genético especializado de Chu-Beasley  y técnicas exactas de programación lineal entera mixta, basadas en el procedimiento de Branch-and-Cut,  aplicadas a la mejor configuración obtenida del algoritmo genético,  con el apoyo de métodos heurísticos constructivos en la determinación de los subproblemas, que hacen parte de la generación de la población inicial y son necesarios en la etapa de mejoría local.

              El problema considera un conjunto de clientes, cuyas demandas de recogida y entrega de productos o personas son conocidas y su objetivo es obtener el conjunto de rutas de costo mínimo, que permita satisfacer la demanda de los clientes, considerando las respectivas restricciones del sistema y los vehículos necesarios para la realización de las mismas.

La metodología desarrollada se implementa en C++, GAMS (lenguaje de modelado algebraico) y Java. Para encontrar la solución se dispone del software solver CPLEX (paquete de software de optimización que ayuda a resolver el problema codificado en GAMS). La eficiencia de la implementación del algoritmo se verifica con la utilización de instancias de prueba disponibles en la literatura especializada, obteniendo buenos resultados en tiempos de cómputo relativamente cortos.