| Name | tsp-ip JSON |
| Version |
0.1.3
JSON |
| download |
| home_page | https://github.com/rebui1der/tsp-ip |
| Summary | TSP-IP (Travelling Salesman Problem integer programing) |
| upload_time | 2024-09-02 07:40:12 |
| maintainer | None |
| docs_url | None |
| author | rebui1der |
| requires_python | >=3.11 |
| license | None |
| keywords |
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# tsp-ip
TSP-IP (Travelling Salesman Problem integer programing)
Installing the package
pip install tsp-ip
Example 1
```python
import numpy as np
import networkx as nx
from tsp_ip import tsp_ip
n = 20
print('Graph size = ', n)
matrix = np.random.randint(1, 99, (n, n))
print(matrix)
# Find the solution init as matrix numpy
path_len, graph_result = tsp_ip(matrix)
if path_len:
# Get the list of edges of the optimal path
print('Min path =', nx.find_cycle(graph_result))
print('Length =', path_len)
else:
print('Solution impossible!')
```
Example 2
```python
from tsp_ip import tsp_ip
from math import hypot
import random as rnd
import networkx as nx
import matplotlib.pyplot as plt
def distance(point1, point2):
return hypot(point2[0] - point1[0], point2[1] - point1[1])
n = 50
print('Graph size = ', n)
points = [(rnd.uniform(0, 1000), rnd.uniform(0, 1000)) for _ in range(n)]
init_graph = nx.DiGraph()
for i in range(n):
for j in range(n):
if j < i:
length = round(distance(points[i], points[j]))
init_graph.add_edge(i, j, weight=length)
init_graph.add_edge(j, i, weight=length)
# Find the solution init as graph
path_len, graph_result = tsp_ip(init_graph, msg=True)
if path_len:
# Get the list of edges of the optimal path
print('Min path =', nx.find_cycle(graph_result))
print('Length =', path_len)
else:
print('Solution impossible!')
# Draw the graph
plt.figure(figsize=(10, 8))
plt.axis("equal")
nx.draw(graph_result, points, width=0, with_labels=True, node_size=0, font_size=9, font_color="blue", arrowsize=0.1)
nx.draw(graph_result, points, width=1, edge_color="red", style="-", with_labels=False, node_size=0, arrowsize=10)
plt.show()
```
For performance comparison, the implementation of the model in the Miller–Tucker–Zemlin formulation
```python
from tsp_ip import tsp_mtz
```
Feel the difference.
Raw data
{
"_id": null,
"home_page": "https://github.com/rebui1der/tsp-ip",
"name": "tsp-ip",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.11",
"maintainer_email": null,
"keywords": null,
"author": "rebui1der",
"author_email": "vlad_wizard@mail.ru",
"download_url": "https://files.pythonhosted.org/packages/68/48/bac665718a04494d8d5e1da7d8ca96a4c00b8cf8ea4fee455252c42eee46/tsp_ip-0.1.3.tar.gz",
"platform": null,
"description": "# tsp-ip\r\nTSP-IP (Travelling Salesman Problem integer programing)\r\n\r\nInstalling the package\r\n\r\n\tpip install tsp-ip\r\n\r\nExample 1\r\n\r\n```python\r\nimport numpy as np\r\nimport networkx as nx\r\nfrom tsp_ip import tsp_ip\r\n\r\nn = 20\r\nprint('Graph size = ', n)\r\nmatrix = np.random.randint(1, 99, (n, n))\r\nprint(matrix)\r\n\r\n# Find the solution init as matrix numpy\r\npath_len, graph_result = tsp_ip(matrix)\r\n\r\nif path_len:\r\n # Get the list of edges of the optimal path\r\n print('Min path =', nx.find_cycle(graph_result))\r\n print('Length =', path_len)\r\nelse:\r\n print('Solution impossible!')\r\n```\r\n\r\n\r\nExample 2\r\n\r\n```python\r\nfrom tsp_ip import tsp_ip\r\nfrom math import hypot\r\nimport random as rnd\r\nimport networkx as nx\r\nimport matplotlib.pyplot as plt\r\n\r\ndef distance(point1, point2):\r\n return hypot(point2[0] - point1[0], point2[1] - point1[1])\r\n\r\nn = 50\r\nprint('Graph size = ', n)\r\npoints = [(rnd.uniform(0, 1000), rnd.uniform(0, 1000)) for _ in range(n)]\r\n\r\ninit_graph = nx.DiGraph()\r\nfor i in range(n):\r\n for j in range(n):\r\n if j < i:\r\n length = round(distance(points[i], points[j]))\r\n init_graph.add_edge(i, j, weight=length)\r\n init_graph.add_edge(j, i, weight=length)\r\n\r\n# Find the solution init as graph\r\npath_len, graph_result = tsp_ip(init_graph, msg=True)\r\n\r\nif path_len:\r\n # Get the list of edges of the optimal path\r\n print('Min path =', nx.find_cycle(graph_result))\r\n print('Length =', path_len)\r\nelse:\r\n print('Solution impossible!')\r\n\r\n# Draw the graph\r\nplt.figure(figsize=(10, 8))\r\nplt.axis(\"equal\")\r\nnx.draw(graph_result, points, width=0, with_labels=True, node_size=0, font_size=9, font_color=\"blue\", arrowsize=0.1)\r\nnx.draw(graph_result, points, width=1, edge_color=\"red\", style=\"-\", with_labels=False, node_size=0, arrowsize=10)\r\nplt.show()\r\n```\r\n\r\nFor performance comparison, the implementation of the model in the Miller\u0432\u0402\u201cTucker\u0432\u0402\u201cZemlin formulation\r\n\r\n```python\r\nfrom tsp_ip import tsp_mtz\r\n```\r\n\r\nFeel the difference.\r\n",
"bugtrack_url": null,
"license": null,
"summary": "TSP-IP (Travelling Salesman Problem integer programing)",
"version": "0.1.3",
"project_urls": {
"Homepage": "https://github.com/rebui1der/tsp-ip"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "6848bac665718a04494d8d5e1da7d8ca96a4c00b8cf8ea4fee455252c42eee46",
"md5": "89f1546d546f8036a78eb15ddb15ddd9",
"sha256": "9baaf6c498eaf30e10298efbe77cca07e9b1d25c78c30e16da1f60d661572a26"
},
"downloads": -1,
"filename": "tsp_ip-0.1.3.tar.gz",
"has_sig": false,
"md5_digest": "89f1546d546f8036a78eb15ddb15ddd9",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.11",
"size": 16025,
"upload_time": "2024-09-02T07:40:12",
"upload_time_iso_8601": "2024-09-02T07:40:12.449011Z",
"url": "https://files.pythonhosted.org/packages/68/48/bac665718a04494d8d5e1da7d8ca96a4c00b8cf8ea4fee455252c42eee46/tsp_ip-0.1.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-09-02 07:40:12",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "rebui1der",
"github_project": "tsp-ip",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "tsp-ip"
}
