🧭 Traveling Salesman Problem – Genetic Algorithm Solver

A Python project for solving the Traveling Salesman Problem using a Genetic Algorithm, with theoretical comparison through the 1-tree lower bound.

📑 Table of Contents

• Problem Description
• Why a Genetic Algorithm?
• 1-Tree Lower Bound with Prim's Algorithm
• Project Features
• Configuration
• Usage
  • Running Benchmark Mode
  • Running Single Solution Mode
• Results
• Dependencies
• License

🧩 Problem Description

The Traveling Salesman Problem (TSP) is one of the most famous combinatorial optimization challenges:

Given a set of cities and the distances between them, find the shortest possible tour that visits each city exactly once and returns to the starting point.

Since TSP is NP-hard, solving it exactly for large instances is computationally expensive. Heuristic and metaheuristic approaches such as evolutionary algorithms provide practical ways to obtain high-quality solutions in reasonable time.

🧬 Why a Genetic Algorithm?

The Genetic Algorithm (GA) belongs to the family of evolutionary algorithms and is inspired by natural selection.

• Representation → Each individual (chromosome) is a permutation of cities (a candidate route).
• Initialization → Start with a random population of tours.
• Selection → Favor shorter tours when picking parents.
• Crossover → Combine routes to produce offspring with traits from both parents.
• Mutation → Introduce small random changes to maintain diversity.
• Elitism → Preserve the best individuals for the next generation.
• Termination → Stop after a fixed number of generations or convergence.

This process allows the GA to balance exploration (searching new solutions) and exploitation (refining good ones).

🌳 1-Tree Lower Bound with Prim's Algorithm

In addition to implementing GA, this project computes a 1-tree lower bound to benchmark solution quality:

1. Build a Minimum Spanning Tree (MST) of all cities except one, using Prim's algorithm.
2. Connect the excluded city to the MST using its two shortest edges.
3. The resulting structure is a 1-tree, which provides a theoretical lower bound for the TSP.

✅ Why it matters:

• The lower bound lets us compare GA results against the "best possible" cost estimate.
• It quantifies how close our heuristic solution is to optimal.
• It's a standard technique in branch-and-bound and advanced TSP solvers.

✨ Project Features

• Two execution modes:
  • Benchmark Mode → multiple runs, statistical evaluation, and performance plots.
  • Single Solution Mode → one GA run with detailed output of the best route.
• Parameter tuning in the config/ folder (population size, mutation rate, crossover rate, elite size, etc.).
• Performance graphs and convergence plots.
• Integration of 1-tree lower bound results.
• Modular, extensible design.

⚙️ Configuration

Configurable parameters include:

• population_size
• mutation_rate
• crossover_rate
• elite_size
• max_generations
• mating_pool_size_factor

➡️ All stored in config/ for easy tweaking.

🚀 Usage

Clone the repository:

git clone https://github.com/re-pixel/TravelingSalesman.git
cd TravelingSalesman

Install dependencies:

pip install -r requirements.txt

Running Benchmark Mode

python main.py --mode benchmark

Runs multiple GA executions and generates performance plots.

Running Single Solution Mode

python main.py --mode single

Runs GA once and prints the best route with its total distance.

📊 Results

• Benchmark Mode: Produces performance graphs comparing parameter settings.
• Single Solution Mode: Outputs the best route and cost.
• Lower Bound: The 1-tree lower bound is displayed for comparison with GA results.

📦 Dependencies

pip install -r requirements.txt

📜 License

This project is open-source under the MIT License.