ALNS
ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic - Published in JOSS (2023)
Science Score: 98.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 9 DOI reference(s) in README and JOSS metadata -
✓Academic publication links
Links to: joss.theoj.org -
○Committers with academic emails
-
○Institutional organization owner
-
✓JOSS paper metadata
Published in Journal of Open Source Software
Keywords
Keywords from Contributors
Scientific Fields
Repository
Adaptive large neighbourhood search (and more!) in Python.
Basic Info
- Host: GitHub
- Owner: N-Wouda
- License: mit
- Language: Python
- Default Branch: master
- Homepage: https://alns.readthedocs.io/en/latest/
- Size: 4.26 MB
Statistics
- Stars: 546
- Watchers: 8
- Forks: 138
- Open Issues: 3
- Releases: 40
Topics
Metadata Files
README.md
alns is a general, well-documented and tested implementation of the adaptive
large neighbourhood search (ALNS) metaheuristic in Python. ALNS is an algorithm
that can be used to solve difficult combinatorial optimisation problems. The
algorithm begins with an initial solution. Then the algorithm iterates until a
stopping criterion is met. In each iteration, a destroy and repair operator are
selected, which transform the current solution into a candidate solution. This
candidate solution is then evaluated by an acceptance criterion, and the
operator selection scheme is updated based on the evaluation outcome.
Installing alns
The alns package depends on numpy and matplotlib. It may be installed in the
usual way as
pip install alns
Additionally, to enable more advanced operator selection schemes using
multi-armed bandit algorithms, alns may be installed with the optional
MABWiser dependency:
pip install alns[mabwiser]
Getting started
The documentation is available here. If you are new to metaheuristics or ALNS, you might benefit from reading the introduction to ALNS page.
The alns library provides the ALNS algorithm and various acceptance criteria,
operator selection schemes, and stopping criteria. To solve your own problem,
you should provide the following:
- A solution state for your problem that implements an
objective()function. - An initial solution.
- One or more destroy and repair operators tailored to your problem.
A "quickstart" code template is available here.
Examples
We provide several 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 using very simple destroy and repair heuristics.
- The capacitated vehicle routing problem (CVRP), here. We solve an instance with 241 customers 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 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 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. 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.
Contributing
We are very grateful for any contributions you are willing to make. Please have a look here to get started. If you aim to make a large change, it is helpful to discuss the change first in a new GitHub issue. Feel free to open one!
Getting help
Feel free to open an issue or a new discussion thread here on GitHub. Please do not e-mail us with questions, modelling issues, or code examples. Those are much easier to discuss via GitHub than over e-mail. When writing your issue or discussion, please follow the instructions here.
How to cite alns
If you use alns in your research, please consider citing the following paper:
Wouda, N.A., and L. Lan (2023). ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic. Journal of Open Source Software, 8(81): 5028. https://doi.org/10.21105/joss.05028
Or, using the following BibTeX entry:
bibtex
@article{Wouda_Lan_ALNS_2023,
doi = {10.21105/joss.05028},
url = {https://doi.org/10.21105/joss.05028},
year = {2023},
publisher = {The Open Journal},
volume = {8},
number = {81},
pages = {5028},
author = {Niels A. Wouda and Leon Lan},
title = {{ALNS}: a {P}ython implementation of the adaptive large neighbourhood search metaheuristic},
journal = {Journal of Open Source Software}
}
Owner
- Name: Niels Wouda
- Login: N-Wouda
- Kind: user
- Location: Groningen
- Website: https://nielswouda.com
- Repositories: 20
- Profile: https://github.com/N-Wouda
Building @PyVRP. I like optimisation problems and writing code to solve them!
JOSS Publication
ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic
Authors
Department of Operations, University of Groningen, Groningen, The Netherlands \newline
Department of Mathematics, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands \newline
Editor
Hugo Ledoux
Tags
operations research metaheuristics adaptive large neighbourhood searchCitation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software, please cite it using the following metadata."
authors:
- family-names: "Wouda"
given-names: "Niels A."
orcid: "https://orcid.org/0000-0003-2463-0309"
- family-names: "Lan"
given-names: "Leon"
orcid: "https://orcid.org/0000-0001-7479-0218"
title: "ALNS"
version: "v5.0.4"
date-released: "2023-01-19"
doi: "10.5281/zenodo.7551649"
url: "https://github.com/N-Wouda/ALNS"
preferred-citation:
type: article
authors:
- family-names: "Wouda"
given-names: "Niels A."
orcid: "https://orcid.org/0000-0003-2463-0309"
- family-names: "Lan"
given-names: "Leon"
orcid: "https://orcid.org/0000-0001-7479-0218"
title: "ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic"
journal: "Journal of Open Source Software"
volume: 8
issue: 81
year: 2023
doi: "10.21105/joss.05028"
start: 5028
Papers & Mentions
Total mentions: 1
Informational Gene Phylogenies Do Not Support a Fourth Domain of Life for Nucleocytoplasmic Large DNA Viruses
- DOI: 10.1371/journal.pone.0021080
- OpenAlex ID: https://openalex.org/W2026029387
- Published: June 2011
GitHub Events
Total
- Create event: 5
- Release event: 1
- Issues event: 8
- Watch event: 96
- Delete event: 5
- Issue comment event: 15
- Push event: 22
- Pull request review comment event: 5
- Pull request review event: 6
- Pull request event: 8
- Fork event: 13
Last Year
- Create event: 5
- Release event: 1
- Issues event: 8
- Watch event: 96
- Delete event: 5
- Issue comment event: 15
- Push event: 22
- Pull request review comment event: 5
- Pull request review event: 6
- Pull request event: 8
- Fork event: 13
Committers
Last synced: 5 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Niels Wouda | n****a@g****m | 154 |
| Leon | 3****n | 20 |
| dependabot[bot] | 4****] | 2 |
| Xue Qianming | 3****g | 1 |
| Xiangyu | a****u@g****m | 1 |
| Theodoros Skondras Mexis | 9****s | 1 |
| Paul Biberstein | 4****s | 1 |
| Ashish Peruri | a****7@g****m | 1 |
Issues and Pull Requests
Last synced: 4 months ago
All Time
- Total issues: 69
- Total pull requests: 58
- Average time to close issues: 4 months
- Average time to close pull requests: 3 days
- Total issue authors: 18
- Total pull request authors: 8
- Average comments per issue: 4.09
- Average comments per pull request: 3.21
- Merged pull requests: 54
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 3
- Pull requests: 5
- Average time to close issues: 2 days
- Average time to close pull requests: 8 days
- Issue authors: 3
- Pull request authors: 2
- Average comments per issue: 4.0
- Average comments per pull request: 1.0
- Merged pull requests: 5
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- N-Wouda (34)
- leonlan (14)
- rlacjfjin (4)
- biyewansui (2)
- atharvanachankar (1)
- TNQINGYUN (1)
- Leetungkwan (1)
- zwh66s (1)
- mostpalonen (1)
- suleman-81 (1)
- Guo-Shi (1)
- ricohageman (1)
- carol007 (1)
- maryam2171 (1)
- Tiara-cmd (1)
Pull Request Authors
- N-Wouda (31)
- leonlan (25)
- afshinshafaei7 (2)
- P-bibs (1)
- SleepyBag (1)
- TeoSkondras (1)
- AshishPvjs (1)
- danielskatz (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- pypi 6,096 last-month
- Total dependent packages: 1
- Total dependent repositories: 2
- Total versions: 40
- Total maintainers: 1
pypi.org: alns
A flexible implementation of the adaptive large neighbourhood search (ALNS) algorithm.
- Homepage: https://github.com/N-Wouda/ALNS
- Documentation: https://alns.readthedocs.io/
- License: MIT
-
Latest release: 7.0.0
published about 1 year ago
Rankings
Maintainers (1)
Dependencies
- black ^22.3.0 develop
- codecov * develop
- flake8 ^4.0.1 develop
- mypy >=0.670 develop
- networkx >=2.4.0 develop
- pytest >=6.0.0 develop
- pytest-cov >=2.6.1 develop
- tsplib95 >=0.7.0 develop
- matplotlib >=2.2.0
- numpy >=1.15.2
- python ^3.7
- actions/cache v3 composite
- actions/checkout v3 composite
- actions/setup-python v4 composite
- codecov/codecov-action v3 composite
- josStorer/get-current-time v2.0.2 composite