Solution Techniques for VRP
Here, the most commonly used techniques for solving Vehicle
Routing Problems are listed. Near all of them are heuristics and metaheuristics
because no exact algorithm can be guaranteed to find optimal tours within reasonable
computing time when the number of cities is large. This is due to the NP-Hardness
of the problem. Next we can find a classification of the solution techniques
we have considered:
- Exact Approaches:
As the name suggests, this approach proposes to compute every
possible solution until one of the bests is reached.
Heuristic methods perform a relatively limited
exploration of the search space and typically produce good quality solutions
within modest computing times.
- Constructive Methods:
Gradually build a feasible solution while keeping an eye on solution cost,
but do not contain an improvement phase per se.
- 2-Phase Algorithm:
The problem is decomposed into its two natural components:
- Clustering of vertices into feasible routes
- Actual route construction
metaheuristics, the emphasis is on performing a deep exploration of the most
promising regions of the solution space. The quality of solutions produced
by these methods is much higher than that obtained by classical heuristics.
with possible feedback loops between the two stages.