TSP Heuristics Visualizer

This project provides interactive visualizations for two common heuristics for the Traveling Salesman Problem (TSP):

1. Nearest Neighbor Heuristic
2. Insertion Heuristic

The visualizations are built with Pygame and use real-world city data from Argentina.

Features

• Interactive City Selection: Choose your starting city or initial set of cities.
• Step-by-Step Visualization: Watch the algorithms progress one step at a time.
• Detailed Information: See candidate cities, distances, and insertion costs.
• Real Distance Calculation: Uses the Haversine formula for accurate geographic distances.
• Complete Tour Visualization: Shows the final tour connecting all cities.

How to Use

1. Installation

Make sure you have Python and pip installed. Then, install the required dependencies:

pip install -r requirements.txt

2. Run the Program

You can run either of the two heuristic visualizations:

To run the Nearest Neighbor Heuristic:

python heuristic.py

To run the Insertion Heuristic:

python heuristic2.py

3. Controls

Nearest Neighbor (heuristic.py)

• City Selection Phase:
  • LEFT/RIGHT Arrow Keys: Navigate through the list of cities.
  • SPACE: Start the algorithm with the selected city.
• Algorithm Phase:
  • SPACE: Execute the next step of the algorithm.
  • R: Run the algorithm automatically until completion.
  • ESC: Reset and return to city selection.

Insertion Heuristic (heuristic2.py)

• Initial Tour Selection Phase:
  • LEFT/RIGHT Arrow Keys: Navigate through the list of cities.
  • SPACE: Select a city (you will select 3 to form the initial tour).
• Algorithm Phase:
  • SPACE: Execute the next step (find best insertion and perform it).
  • R: Run the algorithm automatically until completion.
  • ESC: Reset and return to city selection.

Heuristics Implemented

Nearest Neighbor Heuristic

This is a greedy algorithm that works as follows:

1. Start at a selected city.
2. From the current city, find the nearest unvisited city.
3. Move to that city and mark it as visited.
4. Repeat until all cities are visited.
5. Return to the starting city to complete the tour.

Insertion Heuristic

This heuristic builds the tour incrementally:

1. Start with a small tour of 3 cities.
2. Select a city not yet in the tour.
3. Find the edge in the current tour where inserting the new city causes the minimum increase in total tour length.
4. Insert the city into that position.
5. Repeat until all cities are included in the tour.

Data Source

The program reads city data from cities.csv which contains Argentine cities with their coordinates:

• name: City name
• lat: Latitude
• long: Longitude

Limitations

Heuristics provide approximate solutions to the TSP. They are fast but do not guarantee finding the absolute best (optimal) tour. The quality of the solution can depend on the starting city or the initial tour.

Visual Legend

• Blue Circles: Unvisited cities
• Yellow Circle: Currently selected starting city (during selection)
• Red Circle: Current city being processed
• Green Circles: Already visited cities
• Orange Circles: Candidate cities (possible next destinations)
• Red Lines: Current path taken
• Orange Lines: Lines to candidate cities
• Candidates Table: Right-side table showing all unvisited cities sorted by distance
  • Yellow highlight: Next city to be selected (nearest neighbor)
  • Distance shown in kilometers using Haversine formula

Example Usage

1. Run the program
2. Use arrow keys to select "Buenos Aires" as starting city
3. Press SPACE to begin
4. Press SPACE repeatedly to see each step, or press R for automatic execution
5. Observe how the algorithm chooses the nearest city at each step
6. See the final tour and total distance
7. Press ESC to try a different starting city