Package description
A wrapper for c++ to solve the Traveling Salesman Problem
Installation
pip install tsp-c
Available methods
- Greedy
- Simulated Annealing (SA)
- Particle Swarm Optimization (PSO)
- Ant Colony Optimization (ACO)
- Two-opt Heuristic
Available functions
solve_greedy(distance_matrix)
solve_SA(distance_matrix)
set_param_SA(C0, Cmin, L0, alpha)
solve_PSO(distance_matrix)
set_param_ACO(hconst, alpha, beta, evprate, intsty, nAnt, nItr)
solve_ACO(distance_matrix)
solve_two_opt(distance_matrix)
set_param_PSO(w, c1, c2, maxV, muProb, nPar, nItr)
Examples
To solve the problem with the Greedy method:
import tsp_c as tsp
distance_matrix = [
[0.0, 290.7, 254.9, 172.9],
[263.6, 0.0, 508.3, 185.0],
[258.2, 497.1, 0.0, 405.6],
[136.8, 190.7, 394.8, 0.0]
]
sol, distance = tsp.solve_greedy(distance_matrix)
print("\nSolution from Greedy:")
print(distance, " ", sol)
The solution will be (1, 3, 0, 2) with total distance 1073.8000000000002.
To solve the problem with the Simulated Annealing method, change the code to:
sol, distance = tsp.solve_SA(distance_matrix)
To set the parameters of the Simulated Annealing method, use:
tsp.set_param_SA(C0, Cmin, L0, alpha)
where
- C0 = Initial temperature (default = 20.0)
- Cmin = Final temperature (default = 0.1)
- L0 = Number of iterations in each temperature (default = 10000)
- alpha = cooling rate (default = 0.9)
For example:
tsp.set_param_SA(10.0, 0.01, 10000, 0.95)
To set the parameters of the ACO method, use:
tsp.set_param_ACO(hconst, alpha, beta, evprate, intsty, nAnt, nItr)
where
- hconst = Heuristic Constant (default = 50.0)
- alpha = Pheromone influence (default = 3, min = 0.0001, max = 10.0)
- beta = Heuristic influence (default = 5, min = 0.0001, max = 10.0)
- evprate = Evaporation Rate (default = 0.05)
- intsty = Pheromone intensity (default = 0.1)
- nAnt = Number of ants (default = 50)
- nItr = Number of iterations (default = 100)
For example:
tsp.set_param_ACO(100.0, 5, 4, 0.1, 0.15, 200, 200)
To set the parameters of the PSO method, use:
tsp.set_param_PSO(w, c1, c2, maxV, muProb, nPar, nItr)
where
- w = Inertia weight of the particle (default = 1.0)
- c1 = acceleration coefficient for the local best position (default = 2.0)
- c2 = acceleration coefficient for the global best position (default = 2.0)
- maxV = Maximum velocity of the particles (default = 2.0)
- muProb = mutation probability that change the position of a particle (default = 0.05)
- nPar = Number of particles (default = 100)
- nItr = Number of iterations (default = 5000)
For example:
tsp.set_param_PSO(0.8, 1.5, 1.5, 5, 0.1, 200, 1000)
Requirement
python >=3.6
Operating System
Linux
References
- Janjarassuk, Udom. (2011). A comparison of heuristic approaches to the travelling salesman problem. ICIC Express Letters. 5. 279-283.
1 maintainer
Metadata
1 maintainer
Release files for tsp-c 0.0.30
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| tsp-c-0.0.30.tar.gz | 118.5 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| tsp_c-0.0.30-py3-none-any.whl | Python 3 | none | any | Details |
Total release size: 235.7 kB
Release files / tsp-c-0.0.30.tar.gz
| Download URL | tsp-c-0.0.30.tar.gz |
|---|---|
| Size | 118.5 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
ffc55d51b0d4f8b91fc2dd18cf6c6c1d46111a28224ae9ce777b697e72c85c4a
|
|
BLAKE2b-256 checksum How to use checksums |
d3c4eb904287d6bfa865cb30026b731b65b97788db665528c00f63143ddba3be
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.7.5
|
Release files / tsp_c-0.0.30-py3-none-any.whl
| Download URL | tsp_c-0.0.30-py3-none-any.whl |
|---|---|
| Size | 117.3 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
b53bf831ab7a411cc619d03bcd838f8ecf9f55f03b9b72691ff10e6811e390e5
|
|
BLAKE2b-256 checksum How to use checksums |
0fe12158122ad4cd2615b684311563b865fddfd737d4b56f93d6d194af56fae7
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.7.5
|
