=================
Python TSP Solver
=================
``python-tsp`` is a library written in pure Python for solving typical Traveling
Salesperson Problems (TSP). It can work with symmetric and asymmetric versions.
Installation
============
.. code:: bash
pip install python-tsp
Examples
========
Given a distance matrix as a numpy array, it is easy to compute a Hamiltonian
path with least cost. For instance, to use a Dynamic Programming method:
.. code:: python
import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming
distance_matrix = np.array([
[0, 5, 4, 10],
[5, 0, 8, 5],
[4, 8, 0, 3],
[10, 5, 3, 0]
])
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)
The solution will be ``[0, 1, 3, 2]``, with total distance 17. Notice it is
always a closed path, so after node 2 we go back to 0.
To solve the same problem with a metaheuristic method:
.. code:: python
from python_tsp.heuristics import solve_tsp_simulated_annealing
permutation, distance = solve_tsp_simulated_annealing(distance_matrix)
Keep in mind that, being a metaheuristic, the solution may vary from execution
to execution, and there is no guarantee of optimality. However, it may be a
way faster alternative in larger instances.
If you with for an open TSP version (it is not required to go back to the
origin), just set all elements of the first column of the distance matrix to
zero:
.. code:: python
distance_matrix[:, 0] = 0
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)
and in this case we obtain ``[0, 2, 3, 1]``, with distance 12. Notice that in
this case the distance matrix is actually asymmetric, and the methods here are
applicable as well.
The previous examples assumed you already had a distance matrix. If that is not
the case, the ``distances`` module has prepared some functions to compute an
Euclidean distance matrix or a
`Great Circle Distance <https://en.wikipedia.org/wiki/Great-circle_distance>`_.
For example, if you have an array where each row has the latitude and longitude
of a point,
.. code:: python
import numpy as np
from python_tsp.distances import great_circle_distance_matrix
sources = np.array([
[ 40.73024833, -73.79440675],
[ 41.47362495, -73.92783272],
[ 41.26591 , -73.21026228],
[ 41.3249908 , -73.507788 ]
])
distance_matrix = great_circle_distance_matrix(sources)
See the `project's repository <https://github.com/fillipe-gsm/python-tsp>`_
for more examples and a list of available methods.
Raw data
{
"_id": null,
"home_page": "https://github.com/fillipe-gsm/python-tsp",
"name": "python-tsp",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.8.1,<4.0.0",
"maintainer_email": "",
"keywords": "",
"author": "Fillipe Goulart",
"author_email": "fillipe.gsm@tutanota.com",
"download_url": "https://files.pythonhosted.org/packages/b5/17/4156bf2a82d15cf66c7b8ed7fac867b153332b28c8b0a768ee9fa0f87301/python_tsp-0.4.0.tar.gz",
"platform": null,
"description": "=================\nPython TSP Solver\n=================\n\n``python-tsp`` is a library written in pure Python for solving typical Traveling\nSalesperson Problems (TSP). It can work with symmetric and asymmetric versions.\n\n\nInstallation\n============\n.. code:: bash\n\n pip install python-tsp\n\n\nExamples\n========\n\nGiven a distance matrix as a numpy array, it is easy to compute a Hamiltonian\npath with least cost. For instance, to use a Dynamic Programming method:\n\n.. code:: python\n\n import numpy as np\n from python_tsp.exact import solve_tsp_dynamic_programming\n\n distance_matrix = np.array([\n [0, 5, 4, 10],\n [5, 0, 8, 5],\n [4, 8, 0, 3],\n [10, 5, 3, 0]\n ])\n permutation, distance = solve_tsp_dynamic_programming(distance_matrix)\n\nThe solution will be ``[0, 1, 3, 2]``, with total distance 17. Notice it is\nalways a closed path, so after node 2 we go back to 0.\n\nTo solve the same problem with a metaheuristic method:\n\n.. code:: python\n\n from python_tsp.heuristics import solve_tsp_simulated_annealing\n\n permutation, distance = solve_tsp_simulated_annealing(distance_matrix) \n\nKeep in mind that, being a metaheuristic, the solution may vary from execution\nto execution, and there is no guarantee of optimality. However, it may be a\nway faster alternative in larger instances.\n\nIf you with for an open TSP version (it is not required to go back to the\norigin), just set all elements of the first column of the distance matrix to\nzero:\n\n.. code:: python\n\n distance_matrix[:, 0] = 0\n permutation, distance = solve_tsp_dynamic_programming(distance_matrix)\n\nand in this case we obtain ``[0, 2, 3, 1]``, with distance 12. Notice that in\nthis case the distance matrix is actually asymmetric, and the methods here are\napplicable as well.\n\nThe previous examples assumed you already had a distance matrix. If that is not\nthe case, the ``distances`` module has prepared some functions to compute an \nEuclidean distance matrix or a\n`Great Circle Distance <https://en.wikipedia.org/wiki/Great-circle_distance>`_.\n\nFor example, if you have an array where each row has the latitude and longitude\nof a point,\n\n.. code:: python\n\n import numpy as np\n from python_tsp.distances import great_circle_distance_matrix\n\n sources = np.array([\n [ 40.73024833, -73.79440675],\n [ 41.47362495, -73.92783272],\n [ 41.26591 , -73.21026228],\n [ 41.3249908 , -73.507788 ]\n ])\n distance_matrix = great_circle_distance_matrix(sources)\n\nSee the `project's repository <https://github.com/fillipe-gsm/python-tsp>`_ \nfor more examples and a list of available methods.\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Library to solve the Traveling Salesperson Problem in pure Python.",
"version": "0.4.0",
"project_urls": {
"Homepage": "https://github.com/fillipe-gsm/python-tsp",
"Repository": "https://github.com/fillipe-gsm/python-tsp"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "6b48865289cba47b9f519e8fe4bcc1888aa687ad6bec6d674809d3e9cac6663c",
"md5": "3e239666b6475430750e8c77d110540e",
"sha256": "261e755102464154964320f9bd48494490278e010da35d01c29fe1fbc04a9827"
},
"downloads": -1,
"filename": "python_tsp-0.4.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "3e239666b6475430750e8c77d110540e",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8.1,<4.0.0",
"size": 22881,
"upload_time": "2023-08-24T15:59:02",
"upload_time_iso_8601": "2023-08-24T15:59:02.046136Z",
"url": "https://files.pythonhosted.org/packages/6b/48/865289cba47b9f519e8fe4bcc1888aa687ad6bec6d674809d3e9cac6663c/python_tsp-0.4.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "b5174156bf2a82d15cf66c7b8ed7fac867b153332b28c8b0a768ee9fa0f87301",
"md5": "591a5e6b36ad8700bc668e1d43344846",
"sha256": "3e99a8f817d582fb4883d9a10d05f6f458b387c8f921b2e2fb63021777a1656a"
},
"downloads": -1,
"filename": "python_tsp-0.4.0.tar.gz",
"has_sig": false,
"md5_digest": "591a5e6b36ad8700bc668e1d43344846",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8.1,<4.0.0",
"size": 15711,
"upload_time": "2023-08-24T15:59:03",
"upload_time_iso_8601": "2023-08-24T15:59:03.886866Z",
"url": "https://files.pythonhosted.org/packages/b5/17/4156bf2a82d15cf66c7b8ed7fac867b153332b28c8b0a768ee9fa0f87301/python_tsp-0.4.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-08-24 15:59:03",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "fillipe-gsm",
"github_project": "python-tsp",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "python-tsp"
}
JSON
