Welcome to tsp-grasp! A Python package with Heuristics for solving the Traveling Salesman Problem (TSP).
The package tspgrasp is available on PyPI, so you can install it via pip by running the following command line:
pip install tspgrasp
To install the package in development versions, clone it from github using:
git clone https://github.com/bruscalia/tsp-grasp.git
And run one of the two following commands:
pip install .
python setup.py install
Make sure Cython and numpy are also available in your python environment.
Alternatively, you can directly run:
pip install git+https://github.com/bruscalia/tsp-grasp.git
Here is a minimum working example in which a symmetric distance matrix is produced from 2-dimensional coordinates.
# Imports
import numpy as np
from scipy.spatial.distance import pdist, squareform
from tspgrasp import Grasp# Create distance matrix
X = np.random.random((100, 2))
D = squareform(pdist(X))
# Instantiate algorithm and solve problem
grasp = Grasp(seed=12)
sol = grasp(D, time_limit=10, max_iter=100)
# Display cost and tour
print(f"Cost: {sol.cost}")
print(f"Tour: {sol.tour}")Greedy Randomized Adaptive Search Procedures (GRASP) are metaheuristics constituted by a hybridization of a semi-greedy procedure with a local search method. For more details please refer to Resende & Ribeiro (2016).
Local search moves implemented were based on the work of Vidal (2022).
You can reach out to me at bruscalia12@gmail.com
Resende, M. G., & Ribeiro, C. C. (2016). Optimization by GRASP. Springer Science+ Business Media New York. https://doi.org/10.1007/978-1-4939-6530-4
Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, 105643. https://doi.org/10.1016/j.cor.2021.105643