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?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, 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.
- Comment
- enThe 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, 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.
- Depiction
- Has abstract
- enThe 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, 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, so the size of problems that can be optimally solved using mathematical programming or combinatorial optimization may 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%.
- Has close match
- 15518-0
- Hypernym
- Optimization
- Is Part Of
- target
- Is primary topic of
- Vehicle routing problem
- Label
- enVehicle routing problem
- Link from a Wikipage to an external page
- www.martrans.org/documents/2008/rst/dvrp%20psaraftis%2088.pdf
- Link from a Wikipage to another Wikipage
- Arc routing
- Binary data
- Category:Combinatorial optimization
- Category:NP-complete problems
- Chinese postman problem
- Combinatorial optimization
- Complete graph
- Directed edge
- File:Figure illustrating the vehicle routing problem.png
- File:Map of vrp subproblems.jpg
- Genetic algorithms
- George Dantzig
- Graph (discrete mathematics)
- Greedy algorithm
- Integer programming
- Job Shop Scheduling
- LIFO (computing)
- List of graph theory topics
- Mathematical programming
- Metaheuristic
- NP-hard
- Shortest path problems
- Simulated annealing
- Tabu search
- Travelling salesman problem
- Vehicle rescheduling problem
- SameAs
- 55az3
- Araç rotalama problemi
- Jármű útvonaltervezési probléma
- m.026dfdm
- Problema de enrutamiento de vehículos
- Problema de roteamento de veículos
- Problema rutării vehiculelor
- Problème de tournées de véhicules
- Problem marszrutyzacji
- Q944041
- Tourenplanung
- Vehicle routing problem
- Vehicle routing problem
- Проблем рутирања возила
- 车辆路径问题
- Subject
- Category:Combinatorial optimization
- Category:NP-complete problems
- Thumbnail
- WasDerivedFrom
- Vehicle routing problem?oldid=1116600484&ns=0
- WikiPageLength
- 20180
- Wikipage page ID
- 7799668
- Wikipage revision ID
- 1116600484
- WikiPageUsesTemplate
- Template:Cite arXiv
- Template:Cite conference
- Template:Cite journal
- Template:EquationNote
- Template:EquationRef
- Template:Like essay
- Template:NumBlk
- Template:Reflist
- Template:Tmath
