Content deleted Content added
Combine information on TSP with NP-hardness for a more natural flow. Add {{Citation needed}} where needed in the description. |
m Dating maintenance tags: {{Citation needed}} |
||
Line 3:
[[File:Figure illustrating the vehicle routing problem.png|thumb|A figure illustrating the vehicle routing problem]]
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?" The problem first appeared, as ''the truck dispatching problem'', in a paper by [[George Dantzig]] and John Ramser in 1959,<ref name=DantzigRamser1959>{{cite journal|last=Dantzig|first=George Bernard|author2=Ramser, John Hubert |title=The Truck Dispatching Problem|journal=Management Science|date=October 1959|volume=6|issue=1|pages=80–91|url=http://andresjaquep.files.wordpress.com/2008/10/2627477-clasico-dantzig.pdf|doi=10.1287/mnsc.6.1.80}}</ref> in which it 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.{{Citation needed|date=July 2025}}
The VRP generalises the [[travelling salesman problem]] (TSP), which is equivalent to requiring a single route to visit all locations. As TSP is [[NP-hard]], the VRP is also NP-hard.<ref name=toth>{{cite book |editor=Toth, P. |editor2=Vigo, D. |title=The Vehicle Routing Problem |volume=9 |series=Monographs on Discrete Mathematics and Applications |year=2002 |publisher=Society for Industrial and Applied Mathematics |___location=Philadelphia |isbn=0-89871-579-2}}</ref>
VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.<ref name="Springer Verlag">{{cite book |url=https://books.google.com/books?id=UMI5GzcNd8wC&q=%22vendors+of+routing+tools%22 |title=Geometric Modelling, Numerical Simulation, and Optimization:: Applied Mathematics at SINTEF |date=2007 |publisher=Springer Verlag |isbn=978-3-540-68783-2 |editor=Geir Hasle |___location=Berlin |pages=397–398 |editor2=Knut-Andreas Lie |editor3=Ewald Quak}}</ref> Commercial solvers tend to use [[Heuristic|heuristics]] due to the size and frequency of real world VRPs they need to solve.{{Citation needed|date=July 2025}}
== Setting up the problem ==
| |||