pyCombinatorial

Introduction

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; Or-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; Randomized Spectral Seriation; RL Q-Learning; RL Double Q-Learning; RL S.A.R.S.A (State Action Reward State Action); Ruin & Recreate; Scatter Search; Simulated Annealing; SOM (Self Organizing Maps); Space Filling Curve (Hilbert); Space Filling Curve (Morton); Space Filling Curve (Sierpinski); Spectral Seriation Initializer; Stochastic Hill Climbing; Sweep; Tabu Search; Truncated Branch & Bound; Twice-Around the Tree Algorithm (Double Tree Algorithm); Variable Neighborhood Search; Zero Suffix Method.

Usage

1. Install

pip install pycombinatorial

2. 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))

3. 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 )
• Or-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 ](htt