 | This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. (December 2021) |
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959,[1] in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.
Determining the optimal solution to VRP is NP-hard,[2] so the size of problems that can be optimally solved using mathematical programming or combinatorial optimization can be limited. Therefore, commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.
VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.[3]
- ^ Dantzig, George Bernard; Ramser, John Hubert (October 1959). "The Truck Dispatching Problem" (PDF). Management Science. 6 (1): 80–91. doi:10.1287/mnsc.6.1.80.
- ^ Toth, P.; Vigo, D., eds. (2002). The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. Vol. 9. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 0-89871-579-2.
- ^ Geir Hasle; Knut-Andreas Lie; Ewald Quak, eds. (2007). Geometric Modelling, Numerical Simulation, and Optimization:: Applied Mathematics at SINTEF. Berlin: Springer Verlag. pp. 397–398. ISBN 978-3-540-68783-2.