Este artículo presenta algoritmos para resolver un caso especial del problema de enrutamiento de vehículos (VRP). Definimos nuestro problema propuesto de un caso especial de VRP como una combinación de dos problemas difíciles: la asignación generalizada y el problema de enrutamiento de vehículos. Se utiliza el algoritmo de evolución diferencial (DE) para resolver el problema. El proceso de recombinación del DE original se modifica añadiendo dos conjuntos más de vectores: el vector mejor y el vector aleatorio, y utilizando otros dos conjuntos: el vector objetivo y el vector de prueba. Se propone la fórmula de probabilidad lineal para utilizar potencialmente uno de los cuatro conjuntos de vectores. Esto se llama el algoritmo DE modificado (MDE). Se integran dos búsquedas locales en el algoritmo MDE: intercambio e inserción. Estos procedimientos crean un DE y un MDE que utilizan (1) ninguna técnica de búsqueda local, (2) dos técnicas de búsqueda local, (3) solo el procedimiento de intercambio, y (4) solo el procedimiento de inserción. Esto genera cuatro algoritmos DE y cuatro algoritmos MDE. Los métodos propuestos se prueban con 15 instancias de prueba y un estudio de caso. El procedimiento actual se compara con todas las heurísticas propuestas. El resultado computacional muestra que, en el estudio de caso, el mejor algoritmo DE (DE-4) tiene una solución un 1.6% mejor que la de la práctica actual, mientras que el algoritmo MDE es un 8.2% mejor. El algoritmo MDE que utiliza la misma búsqueda local que los algoritmos DE genera una solución un 5.814% mejor que la de los algoritmos DE.