El problema de enrutamiento de vehículos (VRP) tiene muchas variantes, incluyendo los modelos más precisos de tareas de transporte en la vida real, lo que lo convierte en uno de los problemas matemáticos más importantes en el campo de la logística. Nuestro objetivo era diseñar un algoritmo que pueda competir contra las soluciones más recientes para VRP y VRP capacitado (CVRP), al mismo tiempo que sea aplicable a modelos de la vida real con simulaciones de transportes reales. Nuestro algoritmo es una variante del algoritmo memético bacteriano (BMA), que mejoramos con operadores novedosos y mejores métodos para la optimización manual de parámetros. La clave de nuestro rendimiento es una mezcla equilibrada de la búsqueda global de algoritmos evolutivos, la búsqueda local de variantes 2-OPT y la búsqueda pseudo-global de algoritmos de construcción probabilística. Nuestro algoritmo se beneficia de las ventajas de los tres métodos resultando en una convergencia rápida y evitando los mínimos globales. Esta es la primera vez que se aplica BMA para VRP, lo que significa que tuvimos que adaptar el método para el nuevo problema. Comparamos nuestro método con algunos de los métodos más utilizados para VRP en el conjunto de datos ABEFMP 1995. Proporcionamos resultados de comparación con el optimizador de inmunidad colectiva de coronavirus, algoritmo genético, hibridación de algoritmo genético con búsqueda de vecindario, algoritmo de luciérnagas, algoritmo de luciérnagas mejorado, optimización de colonia de hormigas y búsqueda de vecindario variable. Nuestro algoritmo tuvo un mejor rendimiento en todas las instancias de datos, obteniendo al menos una mejora. Presentamos nuestro mejor resultado en el conjunto de datos de Bélgica 2017 para futuras referencias. Finalmente, demostramos que nuestro algoritmo es capaz de manejar modelos de la vida real. Aquí también estamos ilustrando la importancia de los diferentes parámetros.