Content deleted Content added
Improved thumbnail |
Brief introduction to approximate solutions for the VRP |
||
Line 99:
There are many methods to solve vehicle routing problems manually. For example, optimum routing is a big efficiency issue for forklifts in large warehouses. Some of the manual methods to decide upon the most efficient route are: Largest gap, S-shape, Aisle-by-aisle, Combined and Combined +. While Combined + method is the most complex, thus the hardest to be used by lift truck operators, it is the most efficient routing method. Still the percentage difference between the manual optimum routing method and the real optimum route was on average 13%.<ref>{{cite web|url=http://locatible.com/blog/logistics/why-is-manual-warehouse-optimum-routing-so-unefficient/ |title=Why Is Manual Warehouse Optimum Routing So Inefficient? |website=Locatible.com |date=2016-09-26 |access-date=2016-09-26}}</ref><ref>{{cite web|last=Roodbergen |first=Kees Jan |url=http://roodbergen.com/publications/IJPR2001.pdf |title=Routing methods for warehouses with multiple cross aisles |website=roodbergen.com |date=2001 |access-date=2016-09-26}}</ref>
==Approximate solutions==
==Metaheuristic==▼
Many real-world applications use computational methods that produce approximate solutions, due to the computational complexity of the VRP. These methods are typically [[Heuristic_(computer_science)|heuristic]]-based and belong to one of two classes:<ref name="toth"/>{{rp|109}}
* '''Classical heuristics'''–perform a set of relatively simple operations to quickly construct a relatively good solution.
* '''Metaheuristics'''–classify and explore the most promising parts of the solution space.
▲===Metaheuristic===
Due to the difficulty of solving to optimality large-scale instances of vehicle routing problems, a significant research effort has been dedicated to [[metaheuristic]]s such as [[Genetic algorithms]], [[Tabu search]], [[Simulated annealing]] and Adaptive Large Neighborhood Search (ALNS). Some of the most recent and efficient metaheuristics for vehicle routing problems reach solutions within 0.5% or 1% of the optimum for problem instances counting hundreds or thousands of delivery points.<ref>{{cite journal|vauthors=Vidal T, Crainic TG, Gendreau M, Prins C|year=2014|title=A unified solution framework for multi-attribute vehicle routing problems
| |||