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:
As the name suggests, this approach proposes to compute every possible solution until one of the bests is reached.
- Branch and bound
- Branch and cut
Heuristic methods perform a relatively limited exploration of the search space and typically produce good quality solutions within modest computing times.
Gradually build a feasible solution while keeping an eye on solution cost, but do not contain an improvement phase per se.
- Savings: Clark and Wright
- Matching Based
- Multi-route Improvement Heuristics
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.
- Cluster-First, Route-Second Algorithms
- Route-First, Cluster-Second Algorithms