Solution Methods 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.

Heuristics

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: (1) clustering of vertices into feasible routes and (2) actual route construction, with possible feedback loops between the two stages.

Metaheuristics