A library to solve TSP (Travelling Salesman Problem) using Exact Algorithms, Heuristics and Metaheuristics
Project description
pyCombinatorial
Introduction
A library to solve the TSP (Travelling Salesman Problem) using Exact Algorithms, Heuristics and Metaheuristics : 2-opt; 2.5-opt; 3-opt; 4-opt; 5-opt; 2-opt Stochastic; 2.5-opt Stochastic; 3-opt Stochastic; 4-opt Stochastic; 5-opt Stochastic; Ant Colony Optimization; Adaptive Large Neighborhood Search; Bellman-Held-Karp Exact Algorithm; Branch & Bound; BRKGA (Biased Random Key Genetic Algorithm); Brute Force; Cheapest Insertion; Christofides Algorithm; Clarke & Wright (Savings Heuristic); Concave Hull Algorithm; Convex Hull Algorithm; Elastic Net; Extremal Optimization; Farthest Insertion; Genetic Algorithm; GRASP (Greedy Randomized Adaptive Search Procedure); Greedy Karp-Steele Patching; Guided Search; Hopfield Network; Iterated Search; Karp-Steele Patching; Large Neighborhood Search; Multifragment Heuristic; Nearest Insertion; Nearest Neighbour; Random Insertion; Random Tour; Scatter Search; Simulated Annealing; SOM (Self Organizing Maps); Space Filling Curve (Hilbert); Space Filling Curve (Morton); Space Filling Curve (Sierpinski); Stochastic Hill Climbing; Sweep; Tabu Search; Truncated Branch & Bound; Twice-Around the Tree Algorithm (Double Tree Algorithm); Variable Neighborhood Search.
Usage
- Install
pip install pyCombinatorial
- Import
# Required Libraries
import pandas as pd
# GA
from pyCombinatorial.algorithm import genetic_algorithm
from pyCombinatorial.utils import graphs, util
# Loading Coordinates # Berlin 52 (Minimum Distance = 7544.3659)
coordinates = pd.read_csv('https://bit.ly/3Oyn3hN', sep = '\t')
coordinates = coordinates.values
# Obtaining the Distance Matrix
distance_matrix = util.build_distance_matrix(coordinates)
# GA - Parameters
parameters = {
'population_size': 15,
'elite': 1,
'mutation_rate': 0.1,
'mutation_search': 8,
'generations': 1000,
'verbose': True
}
# GA - Algorithm
route, distance = genetic_algorithm(distance_matrix, **parameters)
# Plot Locations and Tour
graphs.plot_tour(coordinates, city_tour = route, view = 'browser', size = 10)
print('Total Distance: ', round(distance, 2))
- Try it in Colab
- 2-opt ( Colab Demo ) ( Paper )
- 2.5-opt ( Colab Demo ) ( Paper )
- 3-opt ( Colab Demo ) ( Paper )
- 4-opt ( Colab Demo ) ( Paper )
- 5-opt ( Colab Demo ) ( Paper )
- 2-opt Stochastic ( Colab Demo ) ( Paper )
- 2.5-opt Stochastic ( Colab Demo ) ( Paper )
- 3-opt Stochastic ( Colab Demo ) ( Paper )
- 4-opt Stochastic ( Colab Demo ) ( Paper )
- 5-opt Stochastic ( Colab Demo ) ( Paper )
- Ant Colony Optimization ( Colab Demo ) ( Paper )
- Adaptive Large Neighborhood Search ( Colab Demo ) ( Paper )
- Bellman-Held-Karp Exact Algorithm ( Colab Demo ) ( Paper )
- Branch & Bound ( Colab Demo ) ( Paper )
- BRKGA (Biased Random Key Genetic Algorithm) ( Colab Demo ) ( Paper )
- Brute Force ( Colab Demo ) ( Paper )
- Cheapest Insertion ( Colab Demo ) ( Paper )
- Christofides Algorithm ( Colab Demo ) ( Paper )
- Clarke & Wright (Savings Heuristic) ( Colab Demo ) ( Paper )
- Concave Hull Algorithm ( Colab Demo ) ( Paper )
- Convex Hull Algorithm ( Colab Demo ) ( Paper )
- Elastic Net ( Colab Demo ) ( Paper )
- Extremal Optimization ( Colab Demo ) ( Paper )
- Farthest Insertion ( Colab Demo ) ( Paper )
- Genetic Algorithm ( Colab Demo ) ( Paper )
- GRASP (Greedy Randomized Adaptive Search Procedure) ( Colab Demo ) ( Paper )
- Greedy Karp-Steele Patching ( Colab Demo ) ( Paper )
- Guided Search ( Colab Demo ) ( Paper )
- Hopfield Network ( Colab Demo ) ( Paper )
- Iterated Search ( Colab Demo ) ( Paper )
- Karp-Steele Patching ( Colab Demo ) ( Paper )
- Large Neighborhood Search ( Colab Demo ) ( Paper )
- Multifragment Heuristic ( Colab Demo ) ( Paper )
- Nearest Insertion ( Colab Demo ) ( Paper )
- Nearest Neighbour ( Colab Demo ) ( Paper )
- Random Insertion ( Colab Demo ) ( Paper )
- Random Tour ( Colab Demo ) ( Paper )
- Scatter Search ( Colab Demo ) ( Paper )
- Simulated Annealing ( Colab Demo ) ( Paper )
- SOM (Self Organizing Maps) ( Colab Demo ) ( Paper )
- Space Filling Curve (Hilbert) ( Colab Demo ) ( Paper )
- Space Filling Curve (Morton) ( Colab Demo ) ( Paper )
- Space Filling Curve (Sierpinski) ( Colab Demo ) ( Paper )
- Stochastic Hill Climbing ( Colab Demo ) ( Paper )
- Sweep ( Colab Demo ) ( Paper )
- Tabu Search ( Colab Demo ) ( Paper )
- Truncated Branch & Bound ( Colab Demo ) ( Paper )
- Twice-Around the Tree Algorithm ( Colab Demo ) ( Paper )
- Variable Neighborhood Search ( Colab Demo ) ( Paper )
Single Objective Optimization
For Single Objective Optimization try pyMetaheuristic
Multiobjective Optimization or Many Objectives Optimization
For Multiobjective Optimization or Many Objectives Optimization try pyMultiobjective
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for pyCombinatorial-1.8.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 884daf05e718317005940492e9be4953f7b36c473fff0ffdcf6d024530e6bd0d |
|
MD5 | b14cca4c852bc95f175421831b44213d |
|
BLAKE2b-256 | 3c5438ae8bbd79eb45acfd7ad1de40944574a375c8593afe53005b2de450cc8c |