A collection of algotihms, links and paper and (naive) implementation

VRP Algorithms

A collection of VRP algorithms. Refer to this page for (all?) references used in this repo.

The following is the overview algorithms based on NEO. Note that the follwing image is just a simplified version of the overview of VRP family. The actual variants and algorithms are actually more than the following.

Variants

• CVRP
• VRPTW
• SVRP
• VRPPPD
• VRPB
• SDVRP
• MDVRP

Exact Algorithms

• Branch and bound
• Branch and cut

Heuristic Algorithms

Note that the following hyperlinks in sub-sections may not work

• Constructive heuristic

  • Clarke and Wright savings algorithm
  • Matching Based
  • Multi-route Improvement Heuristic
    • Thompson and Psaraftis
    • Van Breedam
    • Kinderwater and Savelsbergh

• 2-Phase heuristic

  • Cluster-First, Route-Second Algorithms
    • Fisher and Jakimar
    • The Petal Algorithm
    • The Sweep Algorithm
  • Route-First, Cluster-Second Algorithms
    • Beasley's Algorithm

Meta Heuristic Algorithms

• Ant Algorithms
• Constraint Programming
• Deterministic Annealing
• Genetic Algorithms
• Simulated Annealing
• Tabu Search
  • Granular Tabu
  • The Adaptive Memory Procedure
  • Kelly and Xu
  • Taburoute