Content deleted Content added
Update introduction with alternative applications. |
m Fix typo |
||
Line 5:
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. However, variants of the problem consider, e.g, the transport of the elderly or patient transport to and from health-care facilities.<ref>{{cite journal |last1=Cordeau |first1=Jean-François |last2=Laporte |first2=Gilbert |title=The dial-a-ride problem: models and algorithms |journal=Annals of Operations Research |date=July 2007 |volume=153 |issue=1 |pages=29-46 |doi=10.1007/s10479-007-0170-8}}</ref> The objective of the VRP is to minimise the total route cost.
The VRP generalises the [[travelling salesman problem]] (TSP), which is equivalent to requiring a single route to visit all locations. As the 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}}
| |||