A flexible implementation of the adaptive large neighbourhood search (ALNS) algorithm.
Project description
This package offers a general, well-documented and tested implementation of the adaptive large neighbourhood search (ALNS) meta-heuristic, based on the description given in Pisinger and Ropke (2010). It may be installed in the usual way as
pip install alns
Examples
If you wish to dive right in, the documentation contains example notebooks showing how the ALNS library may be used. These include:
- The travelling salesman problem (TSP), here. We solve an instance of 131 cities in one minute to a 2% optimality gap, using very simple destroy and repair heuristics.
- The capacitated vehicle routing problem (CVRP), here. We solve an instance with 241 customers to within 3% of optimality using a combination of a greedy repair operator, and a slack-induced substring removal destroy operator.
- The cutting-stock problem (CSP), here. We solve an instance with 180 beams over 165 distinct sizes to within 1.35% of optimality in only a very limited number of iterations.
- The resource-constrained project scheduling problem (RCPSP), here. We solve an instance with 90 jobs and 4 resources to within 4% of the best known solution, using a number of different operators and enhancement techniques from the literature.
- The permutation flow shop problem (PFSP), here. We solve an instance with 50 jobs and 20 machines to within 1.5% of the best known solution. Moreover, we demonstrate multiple advanced features of ALNS, including auto-fitting the acceptance criterion and adding local search to repair operators. We also demonstrate how one could tune ALNS parameters.
Finally, the features notebook gives an overview of various options available
in the alns package. In the notebook we use these different options to solve
a toy 0/1-knapsack problem. The notebook is a good starting point for when you
want to use different schemes, acceptance or stopping criteria yourself. It is
available here.
How to use
Our documentation provides a complete overview of the alns package. In
short: the alns package exposes two classes, ALNS and State. The first
may be used to run the ALNS algorithm, the second may be subclassed to
store a solution state - all it requires is to define an objective
member function, returning an objective value.
The ALNS algorithm must be supplied with an operator selection scheme, an acceptance criterion, and a stopping criterion. These are explained further in the documentation.
References
- Pisinger, D., and Ropke, S. (2010). Large Neighborhood Search. In M. Gendreau (Ed.), Handbook of Metaheuristics (2 ed., pp. 399-420). Springer.
- Santini, A., Ropke, S. & Hvattum, L.M. (2018). A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics 24 (5): 783-815.
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
