| Name | lkh JSON |
| Version |
2.0.0
JSON |
| download |
| home_page | |
| Summary | Super simple Python wrapper for LKH-3 |
| upload_time | 2023-09-26 20:54:33 |
| maintainer | |
| docs_url | None |
| author | Ben Hudson |
| requires_python | >=3.3,<4.0 |
| license | DBAD |
| keywords |
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# PyLKH
This is a super simple Python wrapper for the constrained traveling salesman and vehicle routing problem solver called [LKH-3](http://akira.ruc.dk/~keld/research/LKH-3/).
If you want to use this wrapper, you need to install LKH-3 first. For example, on Ubuntu:
```
wget http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.6.tgz
tar xvfz LKH-3.0.6.tgz
cd LKH-3.0.6
make
sudo cp LKH /usr/local/bin
```
LKH-3 expects problems in the [TSPLIB](https://github.com/ben-hudson/pylkh/blob/master/docs/tsplib.pdf) format.
It extends the format [to support VRPs](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh-3.pdf).
Using PyLKH you can solve problems represented as Python objects or files.
> __CAUTION:__ distances are represented by integer values in the TSPLIB format. This can produce unexpected behaviour for some problems, like those with all nodes within the unit square. You can use the `EXACT_2D` distance to avoid rounding issues.
## Install
```
pip install lkh
```
## Example
```
import requests
import lkh
problem_str = requests.get('http://vrp.atd-lab.inf.puc-rio.br/media/com_vrp/instances/A/A-n32-k5.vrp').text
problem = lkh.LKHProblem.parse(problem_str)
solver_path = '../LKH-3.0.6/LKH'
lkh.solve(solver_path, problem=problem, max_trials=10000, runs=10)
```
Output (values correspond to nodes, which are 1-indexed, _not_ node indicies, which are 0-indexed):
```
[[27, 8, 14, 18, 20, 32, 22],
[25, 28],
[15, 29, 12, 5, 24, 4, 3, 7],
[30, 19, 9, 10, 23, 16, 11, 26, 6, 21],
[13, 2, 17, 31]]
```
## API
### ```lkh.solve(solver='LKH', problem=None, problem_file=None, **kwargs)```
Solve a problem instance.
#### Parameters
* __solver__ (optional): Path to LKH-3 executable. Defaults to `LKH`.
* __problem__ (optional): Problem object. [LKHProblem](https://github.com/ben-hudson/pylkh/blob/master/lkh/problems.py#L28) is preferred but [tsplib95.models.StandardProblem](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.StandardProblem) also works. `problem` or `problem_file` is required.
* __problem_file__ (optional): Path to TSPLIB-formatted problem. `problem` or `problem_file` is required.
* __kwargs__ (optional): Any LKH-3 parameter described [here](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh.pdf) (pg. 5-7) or [here](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh-3.pdf) (pg. 6-8). Lowercase works. For example: `runs=10`.
#### Returns
__routes__: List of lists of nodes (nodes, *not* node indicies).
### _class_ ```lkh.LKHProblem```
A problem that can be solved by LKH-3. Fields are (partially) described [here](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh-3.pdf) (pg. 4-6). Inherits from [tsplib95.models.StandardProblem](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.StandardProblem).
The available specification fields are:
* `CAPACITY`
* `COMMENT`
* `DEMAND_DIMENSION`
* `DIMENSION`
* `DISPLAY_DATA_TYPE`
* `DISTANCE`
* `EDGE_DATA_FORMAT`
* `EDGE_WEIGHT_FORMAT`
* `EDGE_WEIGHT_TYPE`
* `NAME`
* `NODE_COORD_TYPE`
* `RISK_THRESHOLD`
* `SALESMEN`
* `SCALE`
* `SERVICE_TIME`
* `TYPE`
* `VEHICLES`
The available data fields are:
* `BACKHAUL_SECTION`
* `CTSP_SET_SECTION`
* `DEMAND_SECTION`
* `DEPOT_SECTION`
* `DISPLAY_DATA_SECTION`
* `DRAFT_LIMIT_SECTION`
* `EDGE_DATA_SECTION`
* `EDGE_WEIGHT_SECTION`
* `FIXED_EDGES_SECTION`
* `NODE_COORD_SECTION`
* `PICKUP_AND_DELIVERY_SECTION`
* `REQUIRED_NODES_SECTION`
* `SERVICE_TIME_SECTION`
* `TIME_WINDOW_SECTION`
You probably want to initialize a problem instance using one of the following class methods:
#### _classmethod_ ```load(filepath, **options)```
Load a problem instance from a text file.
Inherited from [tsplib95.problems.Problem.load](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.Problem.load).
#### _classmethod_ ```parse(text, **options)```
Parse text into a problem instance.
Inherited from [tsplib95.problems.Problem.parse](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.Problem.parse).
#### _classmethod_ ```read(fp, **options)```
Read a problem instance from a file-like object.
Inherited from [tsplib95.problems.Problem.read](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.Problem.read).
Raw data
{
"_id": null,
"home_page": "",
"name": "lkh",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.3,<4.0",
"maintainer_email": "",
"keywords": "",
"author": "Ben Hudson",
"author_email": "benhudson@fastmail.com",
"download_url": "",
"platform": null,
"description": "# PyLKH\nThis is a super simple Python wrapper for the constrained traveling salesman and vehicle routing problem solver called [LKH-3](http://akira.ruc.dk/~keld/research/LKH-3/).\n\nIf you want to use this wrapper, you need to install LKH-3 first. For example, on Ubuntu:\n```\nwget http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.6.tgz\ntar xvfz LKH-3.0.6.tgz\ncd LKH-3.0.6\nmake\nsudo cp LKH /usr/local/bin\n```\n\nLKH-3 expects problems in the [TSPLIB](https://github.com/ben-hudson/pylkh/blob/master/docs/tsplib.pdf) format.\nIt extends the format [to support VRPs](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh-3.pdf).\n\nUsing PyLKH you can solve problems represented as Python objects or files.\n\n> __CAUTION:__ distances are represented by integer values in the TSPLIB format. This can produce unexpected behaviour for some problems, like those with all nodes within the unit square. You can use the `EXACT_2D` distance to avoid rounding issues.\n\n## Install\n```\npip install lkh\n```\n\n## Example\n```\nimport requests\nimport lkh\n\nproblem_str = requests.get('http://vrp.atd-lab.inf.puc-rio.br/media/com_vrp/instances/A/A-n32-k5.vrp').text\nproblem = lkh.LKHProblem.parse(problem_str)\n\nsolver_path = '../LKH-3.0.6/LKH'\nlkh.solve(solver_path, problem=problem, max_trials=10000, runs=10)\n```\nOutput (values correspond to nodes, which are 1-indexed, _not_ node indicies, which are 0-indexed):\n```\n[[27, 8, 14, 18, 20, 32, 22],\n [25, 28],\n [15, 29, 12, 5, 24, 4, 3, 7],\n [30, 19, 9, 10, 23, 16, 11, 26, 6, 21],\n [13, 2, 17, 31]]\n```\n\n## API\n### ```lkh.solve(solver='LKH', problem=None, problem_file=None, **kwargs)```\n\nSolve a problem instance.\n\n#### Parameters\n* __solver__ (optional): Path to LKH-3 executable. Defaults to `LKH`.\n\n* __problem__ (optional): Problem object. [LKHProblem](https://github.com/ben-hudson/pylkh/blob/master/lkh/problems.py#L28) is preferred but [tsplib95.models.StandardProblem](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.StandardProblem) also works. `problem` or `problem_file` is required.\n\n* __problem_file__ (optional): Path to TSPLIB-formatted problem. `problem` or `problem_file` is required.\n\n* __kwargs__ (optional): Any LKH-3 parameter described [here](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh.pdf) (pg. 5-7) or [here](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh-3.pdf) (pg. 6-8). Lowercase works. For example: `runs=10`.\n\n#### Returns\n__routes__: List of lists of nodes (nodes, *not* node indicies).\n\n### _class_ ```lkh.LKHProblem```\n\nA problem that can be solved by LKH-3. Fields are (partially) described [here](https://github.com/ben-hudson/pylkh/blob/master/docs/lkh-3.pdf) (pg. 4-6). Inherits from [tsplib95.models.StandardProblem](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.StandardProblem).\n\nThe available specification fields are:\n* `CAPACITY`\n* `COMMENT`\n* `DEMAND_DIMENSION`\n* `DIMENSION`\n* `DISPLAY_DATA_TYPE`\n* `DISTANCE`\n* `EDGE_DATA_FORMAT`\n* `EDGE_WEIGHT_FORMAT`\n* `EDGE_WEIGHT_TYPE`\n* `NAME`\n* `NODE_COORD_TYPE`\n* `RISK_THRESHOLD`\n* `SALESMEN`\n* `SCALE`\n* `SERVICE_TIME`\n* `TYPE`\n* `VEHICLES`\n\nThe available data fields are:\n* `BACKHAUL_SECTION`\n* `CTSP_SET_SECTION`\n* `DEMAND_SECTION`\n* `DEPOT_SECTION`\n* `DISPLAY_DATA_SECTION`\n* `DRAFT_LIMIT_SECTION`\n* `EDGE_DATA_SECTION`\n* `EDGE_WEIGHT_SECTION`\n* `FIXED_EDGES_SECTION`\n* `NODE_COORD_SECTION`\n* `PICKUP_AND_DELIVERY_SECTION`\n* `REQUIRED_NODES_SECTION`\n* `SERVICE_TIME_SECTION`\n* `TIME_WINDOW_SECTION`\n\n\nYou probably want to initialize a problem instance using one of the following class methods:\n\n #### _classmethod_ ```load(filepath, **options)```\n\n Load a problem instance from a text file.\n\n Inherited from [tsplib95.problems.Problem.load](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.Problem.load).\n\n #### _classmethod_ ```parse(text, **options)```\n\n Parse text into a problem instance.\n\n Inherited from [tsplib95.problems.Problem.parse](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.Problem.parse).\n\n #### _classmethod_ ```read(fp, **options)```\n\n Read a problem instance from a file-like object.\n\n Inherited from [tsplib95.problems.Problem.read](https://tsplib95.readthedocs.io/en/stable/pages/modules.html#tsplib95.models.Problem.read).\n\n",
"bugtrack_url": null,
"license": "DBAD",
"summary": "Super simple Python wrapper for LKH-3",
"version": "2.0.0",
"project_urls": null,
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c673bc14b1c26703919425035a6c024d7014fd0a8a2b581f61b83bf2136bcae8",
"md5": "0e56b7a87aa43f83a3c142f9d3eb9dfb",
"sha256": "4f0086b18f616afe46c67cf1acfbfbae5c3dc57c54fe49fab482a034782efb9b"
},
"downloads": -1,
"filename": "lkh-2.0.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "0e56b7a87aa43f83a3c142f9d3eb9dfb",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.3,<4.0",
"size": 24200,
"upload_time": "2023-09-26T20:54:33",
"upload_time_iso_8601": "2023-09-26T20:54:33.376620Z",
"url": "https://files.pythonhosted.org/packages/c6/73/bc14b1c26703919425035a6c024d7014fd0a8a2b581f61b83bf2136bcae8/lkh-2.0.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-09-26 20:54:33",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "lkh"
}
