Vehicle Routing Task
A Vehicle Routing Task is an multi-agent routing task that involves vehicles in transportation networks.
- AKA: VRP.
- …
- Counter-Example(s):
- See: Combinatorial Optimization, Integer Programming, Travelling Salesman Problem, NP-Hard.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/vehicle_routing_problem Retrieved:2015-12-13.
- 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 well-known Travelling Salesman Problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which 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 approach called the savings algorithm.
Determining the optimal solution is an NP-hard problem in combinatorial optimization, so the size of problems that can be solved optimally is limited . The commercial solvers therefore tend to use heuristics due to the size of real world VRPs and the frequency that they may have to be solved.
The VRP has many obvious applications in industry. In fact the use of computer optimisation programs can give savings of 5% to a company as transportation is usually a significant component of the cost of a product (10%) - indeed the transportation sector makes up 10% of the EU's GDP. Consequently, any savings created by the VRP, even less than 5%, are significant.
- 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 well-known Travelling Salesman Problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which 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 approach called the savings algorithm.