Traveling Salesman Problem (TSP) Solver

A Python project that solves the Traveling Salesman Problem using and comparing three different heuristic/metaheuristic optimization algorithms: Hill Climbing, Simulated Annealing, and a Genetic Algorithm.

Given a set of randomly generated 2D city coordinates, the program finds a short route that visits every city exactly once and returns to the start, then benchmarks the three algorithms against each other on distance and runtime.

Table of Contents

• Features
• Prerequisites
• Installation
• Usage
• Algorithms Implemented
  • Hill Climbing
  • Simulated Annealing
  • Genetic Algorithm
• Program Workflow
• Fair Comparison
• Performance Metrics
• Technologies Used
• Project Structure
• Customization
• Contributing
• License

Features

• Hill Climbing — iterative local search using random swap neighbors, keeping only improving moves
• Simulated Annealing — probabilistic local search that accepts some worse moves early on (controlled by a cooling temperature) to escape local optima
• Genetic Algorithm — population-based search using ranked selection, order-preserving crossover, and swap mutation
• Fair, timed comparison of all three algorithms on the same random problem instance
• Visualization of the generated cities and the resulting tours using matplotlib

Prerequisites

• Python 3.7+
• matplotlib

Installation

Clone or download the project, then install the dependency:

pip install matplotlib

Usage

Run the script directly:

python "TSP Project.py"

This will:

1. Generate 20 random cities on a 20×20 grid and plot them
2. Run Hill Climbing, Simulated Annealing, and the Genetic Algorithm on the same initial tour
3. Print each algorithm's total tour distance and runtime to the console
4. Display a side-by-side plot comparing the three resulting tours

Example Output

cities = [(3, 14), (7, 2), (19, 8), ...]
Running TSP algorithms fairly...

Hill Climbing: Distance = 142.3821, Time = 0.0123 sec
Simulated Annealing: Distance = 118.5732, Time = 0.4501 sec
Genetic Algorithm: Distance = 105.9104, Time = 1.2044 sec

Sample Output

Side-by-side comparison of the tours found by Hill Climbing, Simulated Annealing, and the Genetic Algorithm, including their final distance and runtime.

Algorithms Implemented

Hill Climbing

Hill Climbing is a local search algorithm that repeatedly swaps two cities and accepts the new solution only if it improves the total distance.

Characteristics

• Greedy optimization
• Fast execution
• Can become trapped in local optima

---

Simulated Annealing

Simulated Annealing improves upon Hill Climbing by occasionally accepting worse solutions with a probability controlled by temperature, allowing it to escape local optima.

Characteristics

• Escapes local minima
• Temperature-based exploration
• Better search diversity

---

Genetic Algorithm

The Genetic Algorithm evolves a population of candidate solutions using:

• Selection
• Crossover
• Mutation
• Elitism

The population gradually improves over generations to produce high-quality solutions.

Characteristics

• Population-based optimization
• Good global search capability
• Usually provides the best solution among the three

---

Program Workflow

1. Generate random cities.
2. Display the generated city locations.
3. Create a random initial tour.
4. Run the Hill Climbing algorithm.
5. Run the Simulated Annealing algorithm.
6. Run the Genetic Algorithm.
7. Measure the execution time of each algorithm.
8. Calculate the best route distance.
9. Display the resulting routes for comparison.

Fair Comparison

To ensure a fair evaluation:

• All algorithms start from the same randomly shuffled initial tour.
• They optimize the identical set of randomly generated cities.
• Execution time is measured independently.
• Final route distance is used for comparison.

Performance Metrics

Each algorithm is evaluated using:

• Total travel distance
• Execution time
• Route quality
• Visual comparison of the generated tours

Technologies Used

• Python
• Math
• Random
• Time
• Matplotlib

Project Structure

.
├── Images/
│   └── output.png     # Sample output comparing the three algorithms
└── TSP Project.py      # Contains distance calculations, all three algorithms,
                          # timing utilities, plotting functions, and the main script

Customization

You can tweak the following directly in the script:

• cord — number and range of randomly generated cities (default: 20 cities on a 0–20 grid)
• Algorithm parameters listed in the table above (iterations, cooling rate, population size, mutation rate, etc.)

Contributing

Contributions are welcome! If you'd like to improve the algorithms, add new heuristics, or enhance the visualizations: you can also reach out via email at rseyednozadi@gmail.com.

1. Fork the repository
2. Create a new branch (git checkout -b feature/your-feature-name)
3. Make your changes and commit them (git commit -m "Add some feature")
4. Push to your branch (git push origin feature/your-feature-name)
5. Open a Pull Request describing your changes

Feel free to open an issue first to discuss what you'd like to change.

License

This project is licensed under the MIT License. See the LICENSE file for details.