Content deleted Content added
Brief introduction to approximate solutions for the VRP |
Update introduction with alternative applications. |
||
Line 3:
[[File:Illustration of the Vehicle Routing Problem.svg|thumb|An illustration of an instance of the vehicle routing problem in a road network, containing routes for three vehicles to deliver goods from a central depot (D) to 11 locations.]]
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 '''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>
| |||