/pyCombinatorial

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; Bellman-Held-Karp Exact Algorithm; Branch & Bound; BRKGA (Biased Random Key Genetic

Primary LanguagePythonOtherNOASSERTION

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; 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; 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

  1. Install
pip install pyCombinatorial
  1. 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))
  1. Try it in Colab

Single Objective Optimization

For Single Objective Optimization try pyMetaheuristic

Multiobjective Optimization or Many Objectives Optimization

For Multiobjective Optimization or Many Objectives Optimization try pyMultiobjective