En 1964, Clark y Wright [4] desarrollaron un algoritmo heurístico eficaz que salva el algoritmo de Clark-Wright que mejora el método de Dantzig-Ramse.
Es precisamente debido a la publicación de los dos artículos innovadores anteriores que VRP se ha convertido en una frontera y un punto caliente en los campos de la investigación de operaciones y la optimización combinatoria.
En 1969, Christofides y Aron aplicaron 2-opt[5] y 3-opt[6] para resolver el problema de las rutas de vehículos.
En 1970, se propuso un enfoque de dos etapas para resolver el problema de generación de rutas de vehículos, que consistía en dos estrategias heurísticas: grupo primero-camino segundo y camino primero-grupo segundo.
En 1981, Fisher y Jaikumar propusieron un método de optimización basado en programación matemática para abordar problemas que involucraban alrededor de 50 puntos de clientes, y su eficiencia operativa también era un problema urgente a resolver. Ese mismo año, Gurren, Jarvis y Ratliff establecieron un enfoque heurístico para la interacción humano-computadora.
En 1981, Bodine y Golden resumieron muchas soluciones VRP. Se puede dividir en las siguientes siete categorías: programa exacto; método de optimización interactiva); primero en ruta; en segundo lugar, en ruta; guardar o insertar en grupo;
Desde 1990, los métodos de inteligencia artificial han demostrado potentes capacidades para resolver problemas de optimización combinatoria y se han aplicado plenamente en diversos campos. Muchos académicos también han introducido la inteligencia artificial en la resolución de problemas de rutas de vehículos y han construido una gran cantidad de algoritmos heurísticos basados en inteligencia artificial. La búsqueda tabú (TS) es básicamente un método de búsqueda local de inteligencia artificial (IA). Willard utilizó por primera vez este algoritmo para resolver VRP. Yuan Qingda [7] y otros diseñaron un algoritmo tabú que considera ventanas de tiempo y diferentes modelos de automóviles. Este algoritmo utiliza principalmente un algoritmo genético para generar la solución inicial y luego utiliza un algoritmo tabú para optimizar la solución inicial. El método de recocido simulado tiene las características de convergencia rápida y búsqueda global. Osman[8] estudió el algoritmo de recocido simulado de VRP. Los algoritmos genéticos tienen buenas propiedades para resolver problemas de optimización combinatoria. Holland utilizó por primera vez un algoritmo genético (GA) para resolver el problema VRPTW. Actualmente, la mayoría de los académicos adoptan una estrategia híbrida, utilizando dos métodos de inteligencia artificial para agrupar y optimizar rutas. Ombuki [9] propuso un algoritmo híbrido que utiliza GA para agrupar rutas y el método TS para optimizar rutas. Bent y Van Hentenryck [10] utilizaron por primera vez un algoritmo de recocido simulado para minimizar el número de rutas de vehículos y luego utilizaron una búsqueda de vecindarios grandes para minimizar los costos de transporte.
Basado en métodos anteriores para resolver VRP, se puede dividir en algoritmos precisos y algoritmos heurísticos. Los algoritmos precisos incluyen el método de rama y enlace, método de corte de rama, método de cobertura de conjuntos, etc. Los algoritmos heurísticos incluyen métodos parsimoniosos, métodos de recocido simulados, métodos de recocido deterministas, métodos de búsqueda tabú, algoritmos genéticos, redes neuronales, algoritmos de colonias de hormigas, etc.