Content deleted Content added
Information on alternative objectives. |
m Change "trucks" to "vehicles". |
||
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.<ref>{{cite journal |last1=Fisher |first1=Marshall L. |last2=Jaikumar |first2=Ramchandran |title=A generalized assignment heuristic for vehicle routing |journal=Networks |date=June 1981 |volume=11 |issue=2 |pages=109–124 |doi=10.1002/net.3230110205}}</ref> However, variants of the problem consider, e.g, collection of [[Municipal solid waste|solid waste]]<ref>{{cite book |last1=Shuster |first1=Kenneth A. |last2=Schur |first2=Dennis A. |title=Heuristic Routing for Solid Waste Collection Vehicles |date=1974 |publisher=U.S. Environmental Protection Agency}}</ref> and the transport of the elderly and the sick 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><ref>{{cite journal |last1=Cappart |first1=Quentin |last2=Thomas |first2=Charles |last3=Schaus |first3=Pierre |last4=Rousseau |first4=Louis-Martin |title=A Constraint Programming Approach for Solving Patient Transportation Problems |journal=Principles and Practice of Constraint Programming |date=2018 |volume=11008 |pages=490–506 |doi=10.1007/978-3-319-98334-9_32}}</ref> The standard objective of the VRP is to minimise the total route cost.<ref name="toth" />{{rp|5}} Other objectives, such as minimising the number of
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>{{rp|5}}
| |||