Skip to main content

Travelling Salesman Problem Using Simulated Annealing

Project description

Travelling Salesman Problem Using Simulated Annealing

This package solves the Travelling Salesman Problem (TSP) using Simulated Annealing (SA).

Required Libraries

  • Numpy
  • Pandas
  • Matplotlib
  • Math

Installation

The satsp package can be installed using pip:

pip install satsp

Usage

Basic usage:

from satsp import solver

cities = [[1, 6.0, 7.0],
          [2, 4.0, 9.0],
	  [3, 7.0, 1.0]]

solver.Solve(cities)
solver.PrintSolution()

The three columns in cities represent id, x coordinate and y coordinate.

Advanced Usage:

solver.Solve(city_list = None, dist_matrix = None, start_temp = None, \
          stop_temp = None, alpha = None, epochs = None, epoch_length = None, \
          epoch_length_factor = 1.00, stopping_count = 100, screen_output = True)

Arguments of solver.Solve() function:

city_list: a N*3 matrix containing three columns representing id, x coordinate and y coordinate of the N cities. Can be None.

dist_matrix: a N*N matrix containing the distances between the N cities. If None is passed and a None city_list is passed, the program will calculate the Eclidean distances between the cities. If both city_list and dist_matrix are None, a test instance with 48 cities will be solved.

start_temp: initial temperature for SA. If None is passed, the program will estimate the initial temperature using a small sample from the data.

stop_temp: stopping temperature for SA. Can be None.

alpha: cooling rate for SA. If None is passed, the program will calculate alpha if stop_temp and epochs are given. Otherwise alpha is set at 0.99.

epochs: number of epochs for SA. A decisive factor for the running time of the algorithm. The program will terminate after this number of epochs. If None is passed, and stop_temp and alpha are given, the program will calculate number of epochs. Otherwise, the stopping condition will be switched to no improvement after a certain number of epochs, where the number is decided by stopping_count.

epoch_length: number of iterations in each epoch. The default is min(100, N*(N-1) / 2).

epoch_length_factor: the rate at which epoch length increases at each epoch. Should be greater than or equal to 1. Default is 1.00. A small value is recommended for large instances.

stopping_count: the number of epochs after which the program will stop if no improvement is made. This stopping condition is only activated if the number of total epochs is neither specified by the user nor can be calculated by the program. Default is 100. screen_output: Parameters of SA, progress of the algorithm and the results will be displayed if set to True. Default is True.

Other functions provided by solver: solver.GetBestDist(): return the total distance of the best TSP tour solver.GetBestTour(): return a list of cities of the best TSP tour solver.PrintBestTour(): Output a picture drawing the best TSP tour solver.PrintConvergence(): Plot the convergence of the distances at the end of each epoch

Algorithm

This package implements the simulated annealing (SA) metaheuristic to solve TSP. A sketch of the algorithm is as follows:

  1. Generate a random initial tour, and set an initial temperature.
  2. Set a number for the iterations to be performed, determined by epoch length.
  3. Randomly pick two cities in the tour and perform a "2-opt" operation, i.e., reverse the tour between the two cities.
  4. If a tour with shorter distance is obtained, accept the new tour. Otherwise, accept the new tour with a certain probability determined by the difference between old and new distances and the current temperature.
  5. Repeat 3-4 for the number of iterations determined in 2.
  6. If a stopping condition is met, terminate. Otherwise go to 7.
  7. Decrease the temperature and repeat 2-5.

References

Kirkpatrick, Scott, C. Daniel Gelatt, and Mario P. Vecchi. "Optimization by simulated annealing." Science 220.4598 (1983): 671-680.

Park, Moon-Won, and Yeong-Dae Kim. "A systematic procedure for setting parameters in simulated annealing algorithms." Computers & Operations Research 25.3 (1998): 207-217.

Project details


Download files

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

Source Distribution

satsp-0.9.tar.gz (7.0 kB view details)

Uploaded Source

Built Distribution

satsp-0.9-py3-none-any.whl (7.8 kB view details)

Uploaded Python 3

File details

Details for the file satsp-0.9.tar.gz.

File metadata

  • Download URL: satsp-0.9.tar.gz
  • Upload date:
  • Size: 7.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/1.11.0 pkginfo/1.4.2 requests/2.18.4 setuptools/40.3.0 requests-toolbelt/0.8.0 tqdm/4.26.0 CPython/3.6.5

File hashes

Hashes for satsp-0.9.tar.gz
Algorithm Hash digest
SHA256 8e5af08399dca87468ac74ed515703233ae288115ce9272eabdfde34e2c05ab8
MD5 9128df52d477b47220860a8aeefb5aa7
BLAKE2b-256 be71200301bfae7f3b4a4203659a48170601d1162868b58438904721f41e19fe

See more details on using hashes here.

File details

Details for the file satsp-0.9-py3-none-any.whl.

File metadata

  • Download URL: satsp-0.9-py3-none-any.whl
  • Upload date:
  • Size: 7.8 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/1.11.0 pkginfo/1.4.2 requests/2.18.4 setuptools/40.3.0 requests-toolbelt/0.8.0 tqdm/4.26.0 CPython/3.6.5

File hashes

Hashes for satsp-0.9-py3-none-any.whl
Algorithm Hash digest
SHA256 a5fd67b0996f3b6e2088776ec2bb45da301648dfb27e2b15f7feb5bf8c56a4ab
MD5 3e4be6c344cdca836abc7f13e869212e
BLAKE2b-256 6a49670f30c39ba811c58a5d427565238e085133c630f864a477c75f77dea1b0

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page