Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

An optimization package for the traveling salesman problem

Project description

tspy: An optimization package for the traveling salesman problem.

The tspy package gives a Python framework in which to study the famous Traveling Salesman Problem (TSP). In this package, one can work on specific instances of the TSP. Approximation methods and lower bounds are included by default. The structure of the package makes it easy to create and include your own methods.

Installation

The tspy package can be installed using pip:

pip install tspy

How to use tspy

Creating an instance

To create an instance of the TSP, use:

from tspy import TSP
tsp = TSP()

Currently, data can be given to the instance in two ways: by giving it the NxN distance matrix D or, in the case of an Euclidian TSP, a NxP data matrix X and a distance function.

# Using the distance matrix
tsp.read_mat(D)

# Using the data matrix and a distance function
tsp.read_data(X, dist)

Computing approximate solutions

The module tsp.solvers contains several algorithms providing approximate solutions of TSP instances. For example, the 2-opt algorithm gives good solutions rather quickly. Here is how it can be used in the tspy package:

from tspy.solvers import TwoOpt_solver
two_opt = TwoOpt_solver(initial_tour='NN', iter_num=100)
two_opt_tour = tsp.get_approx_solution(two_opt)

Other solvers are used similarly.

Current solutions are stored in the dictionary tsp.tours. If a data matrix has been provided to the instance, a plot of the solution can be shown:

tsp.plot_solution('TwoOpt_solver')

alt text

At any point, the best solution that has been computed can be retrieved:

best_tour = tsp.get_best_solution()

Computing lower bounds

The TSP being NP-hard, it is difficult to get exact solutions for large instances. However, by computing lower bounds we can know how good our approximations are. The tspy package provides several lower bounds methods. One example is given by the Simple_LP_bound which gives the optimal solution of the LP relaxation of the TSP:

from tspy.lower_bounds import Simple_LP_bound
lower_bound = tsp.get_lower_bound(Simple_LP_bound())

At any point, the best lower bound that has been computed can be retrieved:

best_lower_bound = tsp.get_best_lower_bound()

Future

The following features will be added soon:

  • Genetic programming
  • Ant colony optimization
  • Lin–Kernighan heuristic
  • Better LP lower bounds

Feel free to contact me if you would like to contribute.

Author

tspy was written by William Borgeaud (williamborgeaud[at]gmail.com).

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for tspy, version 0.1.1.1
Filename, size File type Python version Upload date Hashes
Filename, size tspy-0.1.1.1-py3-none-any.whl (9.0 kB) File type Wheel Python version py3 Upload date Hashes View hashes
Filename, size tspy-0.1.1.1.tar.gz (7.6 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page