La primera definición aparece en una artículo de George Dantzig y John Ramser en 1959, en donde plantea una aproximación algorítmica y fue aplicado para entregas de gasolina.[1] El problema, requiere la entrega de cierto producto, almacenado en un único local, a los clientes los cuales poseen cierta demanda; el objetivo fundamental es minimizar el coste total de las rutas trazadas.En 1964, Clarke y Wright mejoraron la aproximación de Dantzig y Ramser utilizando una aproximación “greedy” conocido como algoritmo de ahorros.Determinar la solución óptima es un problema NP-duro de optimización combinatoria.[2] Las implementaciones más utilizadas para resolver el problema se basan en heurísticas debido a que para grandes instancias del problema, que como sucede en ejemplos reales, producen buenos resultados.[3][4] Consiguientemente, cualesquier ahorros crearon por el VRP, incluso aún, de un 5%, es significativo.[3] Existen principalmente tres elementos involucrados en el VRP, que son los clientes, las bodegas o depósitos y la flota de vehículos.En los problemas reales de VRP aparecen muchas restricciones, entre las que cabe citar:Determina un conjunto de rutas, S, (una ruta para cada vehículo que inicia y termina en el depósito) tal que todas las demandas de los clientes son satisfechas y el coste de la transportación total está minimizado.Esto cuesto puede ser monetario, distancia, tiempo, etc.[2] La red de carretera puede ser descrita utilizando un grafo donde los arcos son las carreteras y los vértices representan la localización de los clientes y del depósito.Los arcos pueden ser dirigidos o no, debido a costes diferentes en cada dirección o alguna variante del problema.[7] Hay tres diferentes aproximaciones principales a la modelización el VRP La formulación del TSP por Dantzig, Fulkerson y Johnson fue extendido para crear el flujo de dos índices para el VRPLas restricciones 1 y 2 plantean que exactamente un arco entra y exactamente uno deja cada vértice asociado con un cliente, respectivamente.Finalmente, la restricción 6 define el dominio de las constantes.Las soluciones obtenidas con estos procedimientos pueden ser mejoradas utilizando métodos de búsqueda más complejos como las metaheurísticas, que conllevan mayores tiempos de cálculo.Para resolver este inconveniente se han desarrollado las denominadas "metaheurísticas", que son “estrategias maestras que permiten resolver de manera inteligente un problema”.[6] Las metaheurísticas modifican a otras heurísticas combinando diferentes conceptos para producir mejores soluciones que las encontradas por ellas.Con la utilización de las metaheurísticas no se asegura la exploración completa del espacio de soluciones; sin embargo, estos procedimientos exploran aquellas regiones en las que es factible encontrar buenas soluciones.Varios vendedores de software han construido productos de software para solucionar variantes del VRP.Numerosos artículos están disponibles para más detalles del contenido de la búsqueda y resultados de estas variantes.
Una figura que ilustra el problema de enrutamiento del vehículo
Un mapa que muestra la relación entre común VRP subproblems.
