Repository contains implementation of ALNS metaheuristic for Capacitated Vehicle Routing Problem (CVRP) solution. Adaptive Large Neighbourhood Search is a metaheuristic that combines ideas of Local Search (LS) heuristics and searches optimal solutions in much larger neighbourhoods by sequentially destroying part of current solution and trying to repair it. For that purpose, ALNS may utilize one of several preconfigured destroy and repair operators, i.e. heuristics that either unassign customers from their respective routes or try to fit them into a (presumably) better positions in possibly different routes.
To faciliate divergence in produced solutions and adapt solver to a concrete problem, on each iteration both types of operators are picked at random (customarily, using a roulette wheel). Essentially, that is where adaptive in ALNS stems from. In this implementation, however, as of now, relative operator weights are not fitted during optimization.
One can get more details about the algorithm in the literature:
- Large Neighbourhood Method proposal by P.Shaw
- LNS paper by S.Ropke
- Comparison of acceptance criteria for ALNS metaheuristic
- ALNS applied to GVRPTW
Related repositories that strongly influenced the implementation:
- Related Python package with great docs
- Decomposition Strategies for VRP
- C++ implementation, loosely based on original implementation by S.Ropke
pip install -r requirements.txt
mkdir -p data
cd notebooks
# will evaluate ALNS solver on problems from cvrplib
# and produce benchmark.csv file in data/ directory
# with results and metadata
python3 benchmark.pyNotebooks under notebooks directory serve for visualization of results.