A vehicle routing problem (VRP) is the task of finding a set of routes for a fleet of vehicles, based at one or more depots, to deliver goods to a given set of customers while satisfying a set of conditions and minimising the overall transportation cost.1
Origin and classical form
Dantzig and Ramser’s 1959 paper “The Truck Dispatching Problem” concerns the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations. The aim is to assign stations to trucks so that station demands are satisfied and the total mileage of the fleet is a minimum. Their abstract gives a procedure based on a linear programming formulation for a near-optimal solution and says that no practical applications had been made as yet.2
Petropoulos, Laporte and colleagues describe the capacitated vehicle routing problem (CVRP) as first proposed by Dantzig and Ramser. In it, identical trucks leave a central depot, each returns to the depot after visiting an ordered subset of the customers, every customer is visited once, and the objective is to minimise the sum of the travelling distances of every truck.1 The review presents the VRP as a generalisation of the travelling salesman problem, and says that introducing a capacitated fleet makes the CVRP a much harder generalisation.1
Variants and solution methods
A 2024 survey describes the VRP as a “crucial component” within any logistics framework, concerned with the administration and strategising of distribution networks for vehicle fleets, and sets out its variants, formulations and algorithms from the previous two decades.3 The review adds that the CVRP definition has been enriched over the decades to take into account the delivery requirements of customers and transportation providers and the characteristics of the available fleet.1
On the exact side, the review names branch-cut-and-price as the most successful framework. Metaheuristics can solve very large instances in limited computing time but give no proof of optimality. The popular CVRP frameworks it lists include tabu search, adaptive large neighbourhood search, iterated local search and the hybrid genetic algorithm; a competition launched in 2022 aimed at developing and comparing machine learning techniques for the problem.1 The corpus links this page to Genetic Algorithm and Reinforcement Learning; in the passages used here the review names the hybrid genetic algorithm and machine learning in general, and does not mention reinforcement learning.1
Scope
The VRP sits within Logistics Optimisation. The sources used here describe the delivery case.13
Footnotes
-
Fotios Petropoulos, Gilbert Laporte and colleagues, “Operational Research: Methods and Applications”, arXiv:2303.14217. https://arxiv.org/pdf/2303.14217 ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7
-
G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem”, Management Science 6(1), abstract record on IDEAS/RePEc. https://ideas.repec.org/a/inm/ormnsc/v6y1959i1p80-91.html ↩
-
E. Khayya, I. Medarhri and R. Zine, “A survey of the vehicle routing problem and its variants: formulations and solutions”, Mathematical Modeling and Computing 11(1), abstract record. https://science.lpnu.ua/node/34084 ↩ ↩2