| Name | alns JSON |
| Version |
5.3.2
JSON |
| download |
| home_page | https://github.com/N-Wouda/ALNS |
| Summary | A flexible implementation of the adaptive large neighbourhood search (ALNS) algorithm. |
| upload_time | 2023-08-06 10:25:22 |
| maintainer | |
| docs_url | None |
| author | Niels Wouda |
| requires_python | >=3.8,<4.0 |
| license | MIT |
| keywords |
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
[](https://badge.fury.io/py/alns)
[](https://github.com/N-Wouda/ALNS/actions/workflows/alns.yaml)
[](https://alns.readthedocs.io/en/latest/?badge=latest)
[](https://codecov.io/gh/N-Wouda/ALNS)
[](https://doi.org/10.21105/joss.05028)
``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][12] dependency:
```
pip install alns[mabwiser]
```
### Getting started
The documentation is available [here][1]. If you are new to metaheuristics or
ALNS, you might benefit from reading the [introduction to ALNS][11] 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][10].
### Examples
We provide several example notebooks showing how the ALNS library may be used.
These include:
- The travelling salesman problem (TSP), [here][2]. We solve an instance of 131
cities using very simple destroy and repair heuristics.
- The capacitated vehicle routing problem (CVRP), [here][8]. 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][4]. 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][6]. 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][9]. 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][5].
### Contributing
We are very grateful for any contributions you are willing to make. Please have
a look [here][3] 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
If you are looking for help, please follow the instructions [here][7].
### 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}
}
```
[1]: https://alns.readthedocs.io/en/latest/
[2]: https://alns.readthedocs.io/en/latest/examples/travelling_salesman_problem.html
[3]: https://alns.readthedocs.io/en/latest/setup/contributing.html
[4]: https://alns.readthedocs.io/en/latest/examples/cutting_stock_problem.html
[5]: https://alns.readthedocs.io/en/latest/examples/alns_features.html
[6]: https://alns.readthedocs.io/en/latest/examples/resource_constrained_project_scheduling_problem.html
[7]: https://alns.readthedocs.io/en/latest/setup/getting_help.html
[8]: https://alns.readthedocs.io/en/latest/examples/capacitated_vehicle_routing_problem.html
[9]: https://alns.readthedocs.io/en/latest/examples/permutation_flow_shop_problem.html
[10]: https://alns.readthedocs.io/en/latest/setup/template.html
[11]: https://alns.readthedocs.io/en/latest/setup/introduction_to_alns.html
[12]: https://github.com/fidelity/mabwiser
Raw data
{
"_id": null,
"home_page": "https://github.com/N-Wouda/ALNS",
"name": "alns",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.8,<4.0",
"maintainer_email": "",
"keywords": "",
"author": "Niels Wouda",
"author_email": "nielswouda@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/a8/05/7e8ed9ac901434c560525e286acb289698b2548184703e31f89035710f49/alns-5.3.2.tar.gz",
"platform": null,
"description": "[](https://badge.fury.io/py/alns)\n[](https://github.com/N-Wouda/ALNS/actions/workflows/alns.yaml)\n[](https://alns.readthedocs.io/en/latest/?badge=latest)\n[](https://codecov.io/gh/N-Wouda/ALNS)\n[](https://doi.org/10.21105/joss.05028)\n\n``alns`` is a general, well-documented and tested implementation of the adaptive\nlarge neighbourhood search (ALNS) metaheuristic in Python. ALNS is an algorithm\nthat can be used to solve difficult combinatorial optimisation problems. The\nalgorithm begins with an initial solution. Then the algorithm iterates until a\nstopping criterion is met. In each iteration, a destroy and repair operator are\nselected, which transform the current solution into a candidate solution. This\ncandidate solution is then evaluated by an acceptance criterion, and the\noperator selection scheme is updated based on the evaluation outcome.\n\n### Installing `alns`\n\nThe `alns` package depends on `numpy` and `matplotlib`. It may be installed in the\nusual way as\n```\npip install alns\n```\nAdditionally, to enable more advanced operator selection schemes using \nmulti-armed bandit algorithms, `alns` may be installed with the optional \n[MABWiser][12] dependency:\n```\npip install alns[mabwiser]\n```\n\n### Getting started\n\nThe documentation is available [here][1]. If you are new to metaheuristics or \nALNS, you might benefit from reading the [introduction to ALNS][11] page.\n\nThe `alns` library provides the ALNS algorithm and various acceptance criteria,\noperator selection schemes, and stopping criteria. To solve your own problem,\nyou should provide the following:\n\n- A solution state for your problem that implements an `objective()` function.\n- An initial solution.\n- One or more destroy and repair operators tailored to your problem.\n\nA \"quickstart\" code template is available [here][10].\n\n### Examples\n\nWe provide several example notebooks showing how the ALNS library may be used.\nThese include:\n\n- The travelling salesman problem (TSP), [here][2]. We solve an instance of 131\n cities using very simple destroy and repair heuristics.\n- The capacitated vehicle routing problem (CVRP), [here][8]. We solve an\n instance with 241 customers using a combination of a greedy repair operator,\n and a _slack-induced substring removal_ destroy operator.\n- The cutting-stock problem (CSP), [here][4]. We solve an instance with 180\n beams over 165 distinct sizes in only a very limited number of iterations.\n- The resource-constrained project scheduling problem (RCPSP), [here][6]. We\n solve an instance with 90 jobs and 4 resources using a number of different\n operators and enhancement techniques from the literature.\n- The permutation flow shop problem (PFSP), [here][9]. We solve an instance with\n 50 jobs and 20 machines. Moreover, we demonstrate multiple advanced features\n of ALNS, including auto-fitting the acceptance criterion and adding local\n search to repair operators. We also demonstrate how one could tune ALNS\n parameters.\n\nFinally, the features notebook gives an overview of various options available in\nthe `alns` package. In the notebook we use these different options to solve a\ntoy 0/1-knapsack problem. The notebook is a good starting point for when you\nwant to use different schemes, acceptance or stopping criteria yourself. It is\navailable [here][5].\n\n### Contributing\n\nWe are very grateful for any contributions you are willing to make. Please have\na look [here][3] to get started. If you aim to make a large change, it is\nhelpful to discuss the change first in a new GitHub issue. Feel free to open\none!\n\n### Getting help\n\nIf you are looking for help, please follow the instructions [here][7].\n\n### How to cite `alns`\n\nIf you use `alns` in your research, please consider citing the following paper:\n\n> Wouda, N.A., and L. Lan (2023). \n> ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic. \n> _Journal of Open Source Software_, 8(81): 5028. \n> https://doi.org/10.21105/joss.05028\n\nOr, using the following BibTeX entry:\n\n```bibtex\n@article{Wouda_Lan_ALNS_2023, \n doi = {10.21105/joss.05028}, \n url = {https://doi.org/10.21105/joss.05028}, \n year = {2023}, \n publisher = {The Open Journal}, \n volume = {8}, \n number = {81}, \n pages = {5028}, \n author = {Niels A. Wouda and Leon Lan}, \n title = {{ALNS}: a {P}ython implementation of the adaptive large neighbourhood search metaheuristic}, \n journal = {Journal of Open Source Software} \n}\n```\n\n[1]: https://alns.readthedocs.io/en/latest/\n\n[2]: https://alns.readthedocs.io/en/latest/examples/travelling_salesman_problem.html\n\n[3]: https://alns.readthedocs.io/en/latest/setup/contributing.html\n\n[4]: https://alns.readthedocs.io/en/latest/examples/cutting_stock_problem.html\n\n[5]: https://alns.readthedocs.io/en/latest/examples/alns_features.html\n\n[6]: https://alns.readthedocs.io/en/latest/examples/resource_constrained_project_scheduling_problem.html\n\n[7]: https://alns.readthedocs.io/en/latest/setup/getting_help.html\n\n[8]: https://alns.readthedocs.io/en/latest/examples/capacitated_vehicle_routing_problem.html\n\n[9]: https://alns.readthedocs.io/en/latest/examples/permutation_flow_shop_problem.html\n\n[10]: https://alns.readthedocs.io/en/latest/setup/template.html\n\n[11]: https://alns.readthedocs.io/en/latest/setup/introduction_to_alns.html\n\n[12]: https://github.com/fidelity/mabwiser\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "A flexible implementation of the adaptive large neighbourhood search (ALNS) algorithm.",
"version": "5.3.2",
"project_urls": {
"Homepage": "https://github.com/N-Wouda/ALNS",
"Repository": "https://github.com/N-Wouda/ALNS",
"Tracker": "https://github.com/N-Wouda/ALNS/issues"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "743ee0424fc413e4ac59a4f1d460814baa9c33d118bd8fcb8882402b66c024c6",
"md5": "6d974276bcff4ea0b026a8ffa2811a59",
"sha256": "bcacc1f39573dbcad1dc20d3b0b5415d42744f05d82c4eb7d2a52e6fdebe694b"
},
"downloads": -1,
"filename": "alns-5.3.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "6d974276bcff4ea0b026a8ffa2811a59",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8,<4.0",
"size": 63746,
"upload_time": "2023-08-06T10:25:21",
"upload_time_iso_8601": "2023-08-06T10:25:21.306063Z",
"url": "https://files.pythonhosted.org/packages/74/3e/e0424fc413e4ac59a4f1d460814baa9c33d118bd8fcb8882402b66c024c6/alns-5.3.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a8057e8ed9ac901434c560525e286acb289698b2548184703e31f89035710f49",
"md5": "77d64bbac541b1e1624db10596462ec3",
"sha256": "a65215c6e3094089e677dc8df6222dc13521a2aa10c75df7e5349f15ce90ee55"
},
"downloads": -1,
"filename": "alns-5.3.2.tar.gz",
"has_sig": false,
"md5_digest": "77d64bbac541b1e1624db10596462ec3",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8,<4.0",
"size": 41443,
"upload_time": "2023-08-06T10:25:22",
"upload_time_iso_8601": "2023-08-06T10:25:22.984965Z",
"url": "https://files.pythonhosted.org/packages/a8/05/7e8ed9ac901434c560525e286acb289698b2548184703e31f89035710f49/alns-5.3.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-08-06 10:25:22",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "N-Wouda",
"github_project": "ALNS",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "alns"
}
