Comparación de los Algoritmos de Ramificación y Acotamiento y Evolucionario Para Resolver el Problema Clásico de Ruteo De Vehículos Conocido Como VRP

Abstract

– La solución del modelo de enrutamiento es un desafío algorítmico que busca optimizar las rutas de entrega para minimizar los costos asociados. La programación lineal es un método clásico propuesto para encontrar las rutas de costo mínimo. Alternativamente, se han propuesto metodologías heurísticas y metaheurísticas para resolver el problema de enrutamiento. El objetivo de este trabajo es comparar tanto el tiempo medio para encontrar una solución como la distancia total media recorrida obtenida mediante el uso de un algoritmo genético evolutivo y un modelo de programación lineal. Se estudiaron cinco configuraciones de rutas con diez, veinte, treinta, cuarenta y cincuenta clientes o nodos a visitar. Los resultados señalaron que a medida que se duplica el número de clientes a visitar de diez a veinte, el tiempo promedio para encontrar la mejor solución es aproximadamente diez veces mayor cuando se utiliza un modelo de programación lineal. Además, cuando el número de clientes se duplica de veinte a cuarenta, el tiempo medio para encontrar la solución aumenta sesenta y ocho veces el tiempo anterior. Por el contrario, el algoritmo genético evolutivo mostró que el tiempo promedio de respuesta para encontrar una solución disminuyó significativamente a medida que aumentaba el número de clientes incluidos en el modelo. Con respecto a la distancia total recorrida en la ruta, el modelo de programación lineal encontró una solución 96,26% menor que la encontrada con el método evolutivo para una ruta con diez clientes, y 48,48% menor en una ruta con 50 clientes. Las recomendaciones basadas en los resultados encontrados indican que es conveniente encontrar una solución a través del modelo de programación lineal cuando se incluyen cincuenta o menos clientes en el modelo. Por el contrario, para más de cincuenta clientes es conveniente resolver el problema de enrutamiento mediante algoritmos genéticos evolutivos que necesitan significativamente menos tiempo para encontrar una solución al problema y también encuentran soluciones cada vez más cercanas que las encontradas por el modelo de programación lineal a medida que aumenta el número de clientes.