# Lin-Kernighan Heuristic in Python
This package contains the implementation of *Lin-Kernighan Heuristic* as the main solver for Travelling Salesman Problem (**TSP**) instances. Installation can be made via the pip command:
```
pip install lk_heuristic
```
## Implementation Remarks
### LK and LKH
LK Heuristic was first reported in an [1973 article][lk_article], where the core basis of the algorithm is well explained and detailed. A few decades later, in an [1998 article][lkh_article], Keld Helsgaun reported some enhancements to the original LK Heuristic (the famous [LKH heuristic][lkh]) with additional technical details for implementing the LK heuristic.
Both of these articles were the foundation for the implementation of the algorithm included in this package, with additional inspiration from [Arthur Mahéo post][arthur] / python implementation (which I strongly recommend the reading!).
### Node Structure
Nodes are implemented as Doubly-Linked Lists, one of the structures mentioned by Helsgaun to speed up edge swap operations. More advanced structures can be implemented for faster swaps, but are not included in this package.
### Refinements
There are 4 refinements proposed in the 1973 article aiming to improve the algorithm performance, which were implemented in this packages:
1. Avoid checkout time (by skipping repeated 'bad' tours)
2. Lookahead (by selecting 'good' edges for swaps)
3. Reduction (by keeping 'good' edges from being broken)
4. Non-Sequential exchanges (by executing the double-bridge 4-Opt move)
### Tour Types
Classical TSP instances are closed loops, also called Hamiltonian cycles, where last and first nodes are connected together. Another type of tours, called Hamiltonian paths, have no connection between starting and ending nodes, but requires a specific solving strategy. This package can solve both problems by setting the 'tour_type' parameter at main solve() function. The same parameter is used to export the solution file and can be used to plot instances based on their tour types.
## How-to-use
### TSPLIB
The use of this package is based on [.tsp files][tsplib] as the input to the improve procedure and also as the output (with the difference that nodes will be sorted at output file). Currently the .tsp files supported are *"TYPE: TSP"* (i.e, symmetric problem) and *"EDGE_WEIGHT_TYPE: EUC_2D / EUC_3D"* (euclidean distance in 2D or 3D), with no "special" sections in .tsp file.
### Solvers
The package contains 4 possible solvers for the TSP problem, which can be selected during interactive mode or silent mode:
1. **Brute-Force**: test all tour possibilities (this should be used for very small problems)
2. **Nearest-Neighbor**: collect nearest nodes starting from a random node (fast, but non-optimal)
3. **Lin-Kernighan 1**: LK algorithm inspired by the original LK Paper
4. **Lin-Kernighan 2**: LK algorithm inspired by Helsgaum LK-simplification and Arthur Mahéo python implementation
Methods 1 and 2 were implemented mostly for testing reasons and some performance comparisons, so the recommended solver is Lin-Kernighan.
### Interactive Mode
Interactive mode will ask users to select the input file and a solver function, when no args are supplied to the solve function, like shown in the sample code below:
```
from lk_heuristic.utils.solver_funcs import solve
solve()
```
### Silent Mode
In silent mode all args are passed to the solve function so that no interaction is required through the shell, like shown in the sample code below:
```
from lk_heuristic.utils.solver_funcs import solve
solve(tsp_file="C:/temp/test.tsp", solution_method="lk1_improve", runs=50, backtracking=(5, 5), reduction_level=4, reduction_cycle=4, tour_type="cycle", file_name="C:/temp/test_solution.tsp", logging_level=20)
```
### Example of an interactive run
```
from lk_heuristic.utils.solver_funcs import solve
solve()
# Step 1 - TSP Instance Selection #
*TSP instances avaliable in 'samples' directory:
[0] - a280.tsp
[1] - att48.tsp
[2] - hexagon_2d.tsp
[3] - hexagon_3d.tsp
--> Select one of the instances: 2
# Step 2 - TSP Solution Methods #
*TSP solution methods avaliable in tsp.py:
[0] - bf_improve
[1] - nn_improve
[2] - lk1_improve
[3] - lk2_improve
--> Select one of the solution methods: 2
2022-04-26 19:32:02,850 [INFO] lk_heuristic.utils.solver_funcs: Importing .tsp file 'hexagon_2d.tsp'
2022-04-26 19:32:02,853 [INFO] lk_heuristic.utils.solver_funcs: Using 'euc_2d' for edge type 'EUC_2D'
2022-04-26 19:32:02,854 [INFO] lk_heuristic.utils.solver_funcs: Creating TSP instance
2022-04-26 19:32:02,859 [INFO] lk_heuristic.utils.solver_funcs: Starting improve loop
2022-04-26 19:32:02,861 [DEBUG] lk_heuristic.models.tsp: Starting tour cost: 214.996
2022-04-26 19:32:02,862 [DEBUG] lk_heuristic.models.tsp: Current tour '1' cost: 167.055 / gain: 47.942 / swaps: 1 / feasible swaps: 1 / unfeasible swaps: 0
2022-04-26 19:32:02,864 [DEBUG] lk_heuristic.models.tsp: Current tour '2' cost: 152.913 / gain: 14.142 / swaps: 2 / feasible swaps: 0 / unfeasible swaps: 2
2022-04-26 19:32:02,866 [DEBUG] lk_heuristic.models.tsp: Current tour '3' cost: 123.071 / gain: 29.841 / swaps: 2 / feasible swaps: 2 / unfeasible swaps: 0
2022-04-26 19:32:02,870 [DEBUG] lk_heuristic.models.tsp: Current tour '4' cost: 100.711 / gain: 22.361 / swaps: 2 / feasible swaps: 2 / unfeasible swaps: 0
2022-04-26 19:32:02,874 [DEBUG] lk_heuristic.models.tsp: Current tour '5' cost: 100.711 / gain: 0.000 / swaps: 0 / feasible swaps: 0 / unfeasible swaps: 0
2022-04-26 19:32:02,875 [INFO] lk_heuristic.utils.solver_funcs: [Run:1] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.014s)
2022-04-26 19:32:02,876 [INFO] lk_heuristic.utils.solver_funcs: Exporting 'hexagon_2d_100.711.tsp' file to solutions
folder
```
### Example of a silent run
```
from lk_heuristic.utils.solver_funcs import solve
solve(tsp_file="C:/temp/test.tsp", solution_method="lk1_improve", runs=50, backtracking=(5, 5), reduction_level=4, reduction_cycle=4, tour_type="cycle", file_name="C:/temp/test_solution.tsp", logging_level=20)
2022-04-26 19:35:41,423 [INFO] lk_heuristic.utils.solver_funcs: Importing .tsp file 'test.tsp'
2022-04-26 19:35:41,424 [INFO] lk_heuristic.utils.solver_funcs: Using 'euc_2d' for edge type 'EUC_2D'
2022-04-26 19:35:41,425 [INFO] lk_heuristic.utils.solver_funcs: Creating TSP instance
2022-04-26 19:35:41,426 [INFO] lk_heuristic.utils.solver_funcs: Starting improve loop
2022-04-26 19:35:41,431 [INFO] lk_heuristic.utils.solver_funcs: [Run:1] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.005s)
2022-04-26 19:35:41,441 [INFO] lk_heuristic.utils.solver_funcs: [Run:2] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.009s)
2022-04-26 19:35:41,445 [INFO] lk_heuristic.utils.solver_funcs: [Run:3] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.003s)
2022-04-26 19:35:41,450 [INFO] lk_heuristic.utils.solver_funcs: [Run:4] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.004s)
2022-04-26 19:35:41,455 [INFO] lk_heuristic.utils.solver_funcs: [Run:5] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.004s)
2022-04-26 19:35:41,456 [INFO] lk_heuristic.utils.solver_funcs: Exporting 'test_100.711.tsp' file to solutions folder
```
## Plotting
The main output from the improvement process is the .tsp file with nodes sorted as in the optimal tour found at improvement procedure. User can use this file and parse it to his preferred visualization tool. Although, a simple tool was designed to display 2D and 3D plots using [Plotly][plotly].
In plot_funcs.py, there are two functions to plot either 2D or 3D graphs using as input the .tsp file. After running those functions, a html file is exported at 'plots' folder, which can be viewed using the browser.
The 'tour_type' parameter is used to plot either Hamiltonian 'cycle' or 'path'. The 'path' type will not connect first and last tsp file nodes, which are correctly sorted when solving tsp instances with the 'tour_type' == 'path'
```
from lk_heuristic.utils.plot_funcs import plot_tsp_2d
plot_tsp_2d("src/lk_heuristic/solutions/a280_2593.558.tsp", tour_type="cycle")
```
Example of the plot result using a280.tsp instance
## Packages and Versions
- OS: Windows 10 / Linux (tested on WSL2)
- Python: 3.7.0 64bit
- Additional Packages: plotly==5.5.0
## Future Work
For those who are interested in LK heuristic and want to help implementing and improving this library, here are some ideas of future work:
- Implement the checkout refinement as done in LKH (using a hashtable)
- Implement a better node structure than Doubly Linked Lists
- Implement a better cost matrix data structure
- Implement all default cost functions and patterns from TSPLIB
- Implement CLK (Chained Lin Kernighan) algorithm
- Rework unit tests with shorter tests and use more edge cases
[lk_article]: https://doi.org/10.1287%2Fopre.21.2.498
[lkh_article]: https://doi.org/10.1016%2FS0377-2217%2899%2900284-2
[lkh]: http://webhotel4.ruc.dk/~keld/research/LKH/
[arthur]: https://arthur.maheo.net/implementing-lin-kernighan-in-python/
[tsplib]: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[plotly]: https://plotly.com/python/
Raw data
{
"_id": null,
"home_page": "https://github.com/kikocastroneto/lk_heuristic",
"name": "lk-heuristic",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "tsp,lk,lkh",
"author": "Frederico de Castro Neto",
"author_email": "fred.cneto@hotmail.com",
"download_url": "https://files.pythonhosted.org/packages/83/84/3ed42a8530561526aa93ee7ba2299cc2df5111169e6a3be7206117c9ca2f/lk_heuristic-0.0.4.tar.gz",
"platform": null,
"description": "# Lin-Kernighan Heuristic in Python\r\n\r\nThis package contains the implementation of *Lin-Kernighan Heuristic* as the main solver for Travelling Salesman Problem (**TSP**) instances. Installation can be made via the pip command:\r\n\r\n```\r\npip install lk_heuristic\r\n```\r\n\r\n## Implementation Remarks\r\n\r\n### LK and LKH\r\n\r\nLK Heuristic was first reported in an [1973 article][lk_article], where the core basis of the algorithm is well explained and detailed. A few decades later, in an [1998 article][lkh_article], Keld Helsgaun reported some enhancements to the original LK Heuristic (the famous [LKH heuristic][lkh]) with additional technical details for implementing the LK heuristic.\r\n\r\nBoth of these articles were the foundation for the implementation of the algorithm included in this package, with additional inspiration from [Arthur Mah\u00e9o post][arthur] / python implementation (which I strongly recommend the reading!).\r\n\r\n### Node Structure\r\n\r\nNodes are implemented as Doubly-Linked Lists, one of the structures mentioned by Helsgaun to speed up edge swap operations. More advanced structures can be implemented for faster swaps, but are not included in this package.\r\n\r\n### Refinements\r\n\r\nThere are 4 refinements proposed in the 1973 article aiming to improve the algorithm performance, which were implemented in this packages:\r\n\r\n 1. Avoid checkout time (by skipping repeated 'bad' tours)\r\n 2. Lookahead (by selecting 'good' edges for swaps)\r\n 3. Reduction (by keeping 'good' edges from being broken)\r\n 4. Non-Sequential exchanges (by executing the double-bridge 4-Opt move)\r\n\r\n### Tour Types\r\n\r\nClassical TSP instances are closed loops, also called Hamiltonian cycles, where last and first nodes are connected together. Another type of tours, called Hamiltonian paths, have no connection between starting and ending nodes, but requires a specific solving strategy. This package can solve both problems by setting the 'tour_type' parameter at main solve() function. The same parameter is used to export the solution file and can be used to plot instances based on their tour types. \r\n\r\n## How-to-use\r\n\r\n### TSPLIB\r\n\r\nThe use of this package is based on [.tsp files][tsplib] as the input to the improve procedure and also as the output (with the difference that nodes will be sorted at output file). Currently the .tsp files supported are *\"TYPE: TSP\"* (i.e, symmetric problem) and *\"EDGE_WEIGHT_TYPE: EUC_2D / EUC_3D\"* (euclidean distance in 2D or 3D), with no \"special\" sections in .tsp file. \r\n\r\n### Solvers\r\n\r\nThe package contains 4 possible solvers for the TSP problem, which can be selected during interactive mode or silent mode:\r\n\r\n 1. **Brute-Force**: test all tour possibilities (this should be used for very small problems)\r\n 2. **Nearest-Neighbor**: collect nearest nodes starting from a random node (fast, but non-optimal)\r\n 3. **Lin-Kernighan 1**: LK algorithm inspired by the original LK Paper\r\n 4. **Lin-Kernighan 2**: LK algorithm inspired by Helsgaum LK-simplification and Arthur Mah\u00e9o python implementation \r\n\r\nMethods 1 and 2 were implemented mostly for testing reasons and some performance comparisons, so the recommended solver is Lin-Kernighan.\r\n\r\n### Interactive Mode\r\n\r\nInteractive mode will ask users to select the input file and a solver function, when no args are supplied to the solve function, like shown in the sample code below:\r\n\r\n``` \r\nfrom lk_heuristic.utils.solver_funcs import solve\r\nsolve()\r\n```\r\n\r\n### Silent Mode\r\n\r\nIn silent mode all args are passed to the solve function so that no interaction is required through the shell, like shown in the sample code below:\r\n\r\n```\r\nfrom lk_heuristic.utils.solver_funcs import solve\r\nsolve(tsp_file=\"C:/temp/test.tsp\", solution_method=\"lk1_improve\", runs=50, backtracking=(5, 5), reduction_level=4, reduction_cycle=4, tour_type=\"cycle\", file_name=\"C:/temp/test_solution.tsp\", logging_level=20)\r\n```\r\n\r\n### Example of an interactive run \r\n\r\n```\r\nfrom lk_heuristic.utils.solver_funcs import solve\r\nsolve()\r\n# Step 1 - TSP Instance Selection #\r\n*TSP instances avaliable in 'samples' directory:\r\n[0] - a280.tsp\r\n[1] - att48.tsp\r\n[2] - hexagon_2d.tsp\r\n[3] - hexagon_3d.tsp\r\n--> Select one of the instances: 2\r\n\r\n# Step 2 - TSP Solution Methods #\r\n*TSP solution methods avaliable in tsp.py:\r\n[0] - bf_improve\r\n[1] - nn_improve\r\n[2] - lk1_improve\r\n[3] - lk2_improve\r\n--> Select one of the solution methods: 2\r\n\r\n2022-04-26 19:32:02,850 [INFO] lk_heuristic.utils.solver_funcs: Importing .tsp file 'hexagon_2d.tsp'\r\n2022-04-26 19:32:02,853 [INFO] lk_heuristic.utils.solver_funcs: Using 'euc_2d' for edge type 'EUC_2D'\r\n2022-04-26 19:32:02,854 [INFO] lk_heuristic.utils.solver_funcs: Creating TSP instance\r\n2022-04-26 19:32:02,859 [INFO] lk_heuristic.utils.solver_funcs: Starting improve loop\r\n2022-04-26 19:32:02,861 [DEBUG] lk_heuristic.models.tsp: Starting tour cost: 214.996\r\n2022-04-26 19:32:02,862 [DEBUG] lk_heuristic.models.tsp: Current tour '1' cost: 167.055 / gain: 47.942 / swaps: 1 / feasible swaps: 1 / unfeasible swaps: 0\r\n2022-04-26 19:32:02,864 [DEBUG] lk_heuristic.models.tsp: Current tour '2' cost: 152.913 / gain: 14.142 / swaps: 2 / feasible swaps: 0 / unfeasible swaps: 2\r\n2022-04-26 19:32:02,866 [DEBUG] lk_heuristic.models.tsp: Current tour '3' cost: 123.071 / gain: 29.841 / swaps: 2 / feasible swaps: 2 / unfeasible swaps: 0\r\n2022-04-26 19:32:02,870 [DEBUG] lk_heuristic.models.tsp: Current tour '4' cost: 100.711 / gain: 22.361 / swaps: 2 / feasible swaps: 2 / unfeasible swaps: 0\r\n2022-04-26 19:32:02,874 [DEBUG] lk_heuristic.models.tsp: Current tour '5' cost: 100.711 / gain: 0.000 / swaps: 0 / feasible swaps: 0 / unfeasible swaps: 0\r\n2022-04-26 19:32:02,875 [INFO] lk_heuristic.utils.solver_funcs: [Run:1] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.014s)\r\n2022-04-26 19:32:02,876 [INFO] lk_heuristic.utils.solver_funcs: Exporting 'hexagon_2d_100.711.tsp' file to solutions \r\nfolder\r\n```\r\n\r\n### Example of a silent run \r\n\r\n```\r\nfrom lk_heuristic.utils.solver_funcs import solve\r\nsolve(tsp_file=\"C:/temp/test.tsp\", solution_method=\"lk1_improve\", runs=50, backtracking=(5, 5), reduction_level=4, reduction_cycle=4, tour_type=\"cycle\", file_name=\"C:/temp/test_solution.tsp\", logging_level=20)\r\n2022-04-26 19:35:41,423 [INFO] lk_heuristic.utils.solver_funcs: Importing .tsp file 'test.tsp'\r\n2022-04-26 19:35:41,424 [INFO] lk_heuristic.utils.solver_funcs: Using 'euc_2d' for edge type 'EUC_2D'\r\n2022-04-26 19:35:41,425 [INFO] lk_heuristic.utils.solver_funcs: Creating TSP instance\r\n2022-04-26 19:35:41,426 [INFO] lk_heuristic.utils.solver_funcs: Starting improve loop\r\n2022-04-26 19:35:41,431 [INFO] lk_heuristic.utils.solver_funcs: [Run:1] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.005s)\r\n2022-04-26 19:35:41,441 [INFO] lk_heuristic.utils.solver_funcs: [Run:2] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.009s)\r\n2022-04-26 19:35:41,445 [INFO] lk_heuristic.utils.solver_funcs: [Run:3] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.003s)\r\n2022-04-26 19:35:41,450 [INFO] lk_heuristic.utils.solver_funcs: [Run:4] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.004s)\r\n2022-04-26 19:35:41,455 [INFO] lk_heuristic.utils.solver_funcs: [Run:5] --> Cost: 100.711 / Best: 100.711 / Mean: 100.711 (0.004s)\r\n2022-04-26 19:35:41,456 [INFO] lk_heuristic.utils.solver_funcs: Exporting 'test_100.711.tsp' file to solutions folder\r\n```\r\n\r\n## Plotting\r\n\r\nThe main output from the improvement process is the .tsp file with nodes sorted as in the optimal tour found at improvement procedure. User can use this file and parse it to his preferred visualization tool. Although, a simple tool was designed to display 2D and 3D plots using [Plotly][plotly].\r\n\r\nIn plot_funcs.py, there are two functions to plot either 2D or 3D graphs using as input the .tsp file. After running those functions, a html file is exported at 'plots' folder, which can be viewed using the browser.\r\n\r\nThe 'tour_type' parameter is used to plot either Hamiltonian 'cycle' or 'path'. The 'path' type will not connect first and last tsp file nodes, which are correctly sorted when solving tsp instances with the 'tour_type' == 'path'\r\n\r\n```\r\nfrom lk_heuristic.utils.plot_funcs import plot_tsp_2d\r\nplot_tsp_2d(\"src/lk_heuristic/solutions/a280_2593.558.tsp\", tour_type=\"cycle\")\r\n```\r\n\r\nExample of the plot result using a280.tsp instance\r\n\r\n\r\n## Packages and Versions\r\n\r\n- OS: Windows 10 / Linux (tested on WSL2)\r\n- Python: 3.7.0 64bit\r\n- Additional Packages: plotly==5.5.0 \r\n\r\n## Future Work\r\n\r\nFor those who are interested in LK heuristic and want to help implementing and improving this library, here are some ideas of future work:\r\n\r\n- Implement the checkout refinement as done in LKH (using a hashtable)\r\n- Implement a better node structure than Doubly Linked Lists\r\n- Implement a better cost matrix data structure\r\n- Implement all default cost functions and patterns from TSPLIB\r\n- Implement CLK (Chained Lin Kernighan) algorithm\r\n- Rework unit tests with shorter tests and use more edge cases\r\n\r\n[lk_article]: https://doi.org/10.1287%2Fopre.21.2.498\r\n[lkh_article]: https://doi.org/10.1016%2FS0377-2217%2899%2900284-2\r\n[lkh]: http://webhotel4.ruc.dk/~keld/research/LKH/\r\n[arthur]: https://arthur.maheo.net/implementing-lin-kernighan-in-python/\r\n[tsplib]: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/\r\n[plotly]: https://plotly.com/python/\r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Lin-Kernighan Heuristic in Python",
"version": "0.0.4",
"project_urls": {
"Homepage": "https://github.com/kikocastroneto/lk_heuristic"
},
"split_keywords": [
"tsp",
"lk",
"lkh"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "401fa98c7c056702c57fac04c9857fb9142dcb9e11e7cc6573f661b7168721cc",
"md5": "e7944780e4621511ae9d433122b40c12",
"sha256": "2f4c6c48a0f3e411e6953ac77a2cdf55e0492c86f578411ede2038ee16fa84a9"
},
"downloads": -1,
"filename": "lk_heuristic-0.0.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "e7944780e4621511ae9d433122b40c12",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 34688,
"upload_time": "2024-01-07T13:39:13",
"upload_time_iso_8601": "2024-01-07T13:39:13.961675Z",
"url": "https://files.pythonhosted.org/packages/40/1f/a98c7c056702c57fac04c9857fb9142dcb9e11e7cc6573f661b7168721cc/lk_heuristic-0.0.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "83843ed42a8530561526aa93ee7ba2299cc2df5111169e6a3be7206117c9ca2f",
"md5": "5e8ba477dce24cb95fe60e7a5c308618",
"sha256": "5894228e96a83daa63847f5fcf53c2de7b023273ffe0faba5218c2f785227a56"
},
"downloads": -1,
"filename": "lk_heuristic-0.0.4.tar.gz",
"has_sig": false,
"md5_digest": "5e8ba477dce24cb95fe60e7a5c308618",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 36739,
"upload_time": "2024-01-07T13:39:15",
"upload_time_iso_8601": "2024-01-07T13:39:15.769577Z",
"url": "https://files.pythonhosted.org/packages/83/84/3ed42a8530561526aa93ee7ba2299cc2df5111169e6a3be7206117c9ca2f/lk_heuristic-0.0.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-07 13:39:15",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "kikocastroneto",
"github_project": "lk_heuristic",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "lk-heuristic"
}
JSON
