pyCombinatorial is a Python-based library designed to tackle the classic Travelling Salesman Problem (TSP) through a diverse set of Exact Algorithms, Heuristics, Metaheuristics and Reinforcement Learning. It brings together both well-established and cutting-edge methodologies, offering end-users a flexible toolkit to generate high-quality solutions for TSP instances of various sizes and complexities.
Techniques: 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; Bitonic Tour; 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; FRNN (Fixed Radius Near Neighbor); 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; RL Q-Learning; RL Double Q-Learning; RL S.A.R.S.A (State Action Reward State Action); 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; Zero Suffix Method.
- 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
3.1 Lat Long Datasets
- Lat Long ( Colab Demo )
3.2 Algorithms
- 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 )
- Bitonic Tour( 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 )
- FRNN (Fixed Radius Near Neighbor) ( 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 )
- RL Q-Learning ( Colab Demo ) ( Paper )
- RL Double Q-Learning ( Colab Demo ) ( Paper )
- RL S.A.R.S.A ( 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 )
- Zero Suffix Method ( Colab Demo ) ( Paper )
For Single Objective Optimization try pyMetaheuristic
For Multiobjective Optimization or Many Objectives Optimization try pyMultiobjective