A comprehensive implementation of Traveling Salesman Problem algorithms with interactive visualization and real-world Pakistan city routing.
This project implements and compares multiple algorithms to solve the Traveling Salesman Problem (TSP) using real-world data of 50 major cities in Pakistan. It includes interactive visualizations and performance analysis of different algorithmic approaches.
The project demonstrates practical applications of algorithms in route optimization, including nearest neighbor heuristic, brute force exact solutions, and advanced dynamic programming techniques.
-
Nearest Neighbor (NN) - Greedy heuristic approach
- Fast O(n²) execution time
- Good approximation for large datasets
- Starting point dependent
-
Brute Force - Exhaustive search
- Guarantees optimal solution
- O(n!) time complexity
- Limited to small datasets (n < 13)
-
Held-Karp (HK) - Dynamic programming
- O(n²2^n) time complexity
- Optimal solution with better scalability
- Moderate practical range (n < 20)
-
All Algorithms - Comparative analysis
- Run all three methods simultaneously
- Compare execution times
- Analyze solution quality
- Interactive route maps with matplotlib
- Distance calculation visualization
- Algorithm performance comparison
- City coordinate plotting with GPS data
- Distance heatmaps
- Execution time benchmarking
- Total Cities: 50 major cities in Pakistan
- Data Format: CSV with City name, Latitude, Longitude
- Geographic Coverage: Complete Pakistan including:
- Major metropolitan areas (Karachi, Lahore, Islamabad)
- Regional cities and towns
- Northern and southern regions
City,Latitude,Longitude
Karachi,24.8607,67.0011
Lahore,31.5204,74.3587
Islamabad,33.6844,73.0479
Peshawar,34.0151,71.5787
Multan,30.1575,71.4289
- Python 3.8 or higher
- pip package manager
- 2GB RAM minimum
-
Clone the repository
git clone https://github.com/Viblla/CS-378_Sem_Project.git cd CS-378_Sem_Project -
Install dependencies
pip install -r requirements.txt
-
Run the program
python daa_project_2022064.py
-
Interactive prompts
- Select starting city (0-based index)
- Enter number of cities to analyze
- Choose algorithm (nn, bf, hk, or all)
CS-378_Sem_Project/
├── daa_project_2022064.py # Main algorithm implementation
├── DAA_Project_2022064.ipynb # Jupyter notebook with analysis
├── pakistan_cities_coordinates.csv # Dataset with city coordinates
├── requirements.txt # Python dependencies
├── README.md # This file
├── LICENSE # MIT License
└── index.html # GitHub Pages landing page
python daa_project_2022064.py
# Enter: 0 for start city
# Enter: 15 for number of cities
# Enter: nn for Nearest Neighborpython daa_project_2022064.py
# Enter: 0 for start city
# Enter: 10 for number of cities (keep small!)
# Enter: bf for Brute Forcepython daa_project_2022064.py
# Enter: 0 for start city
# Enter: 16 for number of cities
# Enter: hk for Held-Karppython daa_project_2022064.py
# Enter: 0 for start city
# Enter: 12 for number of cities
# Enter: all for comparison| Algorithm | Best Case | Average | Worst Case |
|---|---|---|---|
| Nearest Neighbor | O(n²) | O(n²) | O(n²) |
| Brute Force | O(n!) | O(n!) | O(n!) |
| Held-Karp | O(n²2^n) | O(n²2^n) | O(n²2^n) |
| Algorithm | Space |
|---|---|
| Nearest Neighbor | O(n) |
| Brute Force | O(n!) |
| Held-Karp | O(n2^n) |
- NN (10 cities): ~0.5ms
- BF (10 cities): ~150ms
- HK (15 cities): ~200ms
- NN (50 cities): ~2ms
- NN: 110-130% of optimal
- BF: 100% (optimal)
- HK: 100% (optimal)
- Use Nearest Neighbor when: Speed is critical, problem size > 20
- Use Brute Force when: Problem size < 13, accuracy is mandatory
- Use Held-Karp when: Balance needed between size (< 25) and optimality
- Use Comparison mode when: Learning or benchmarking
- Shortest complete tour covers ~5,000 km across all 50 cities
- Optimal routes cluster geographically adjacent cities
- Nearest Neighbor achieves 85-95% of optimal solution
- Metropolitan hubs (Karachi, Lahore, Islamabad) serve as natural route centers
- Pandas - Data manipulation and CSV processing
- Matplotlib - Data visualization and mapping
- NumPy - Numerical computations
- Python itertools - Combination generation for brute force
- Jupyter Notebook - Interactive analysis
- Python 3.8+ - Language and runtime
Program crashes with "File not found"
- Ensure
pakistan_cities_coordinates.csvis in the same directory - Check file permissions
Out of Memory with Brute Force
- Reduce number of cities (keep below 13)
- Brute force factorial time requires exponential memory
Slow execution with Held-Karp
- Normal for cities > 18
- Try smaller subset first
- Use Nearest Neighbor for quick estimates
Visualization not appearing
- Ensure matplotlib is installed:
pip install matplotlib - Check display settings in Jupyter notebook
- Use interactive mode:
%matplotlib notebook
- Web-based interactive interface
- Real-time GPS data integration
- Ant Colony Optimization algorithm
- Genetic Algorithm implementation
- Multi-threading for parallel execution
- Export routes to KML/GPX format
- Mobile app version
- Machine learning prediction models
- Real vehicle routing constraints
- Cost optimization with fuel prices
- Held, M., & Karp, R. M. (1962). A Dynamic Programming Approach to Sequencing Problems
- Christofides, N. (1976). Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem
- Lin, S., & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for the TSP
Desktop only - Recommended:
- Chrome 90+
- Firefox 88+
- Safari 14+
- Edge 90+
For bugs or questions:
- Check the troubleshooting section
- Review algorithm selection guide
- Verify dataset integrity
- Check Python version compatibility (3.8+)
This project is licensed under the MIT License - see the LICENSE file for details.
- Course: Design and Analysis of Algorithms (CS-378)
- Semester: 6th Semester
- University: GIKI (Ghulam Ishaq Khan Institute)
- Registration Number: 2022064
- Status: Complete
- Last Updated: January 2026
- Department of Computer Science at GIKI
- TSP research community and academic publications
- Open source libraries (Pandas, Matplotlib, NumPy)
- Pakistan geographic data providers
Solving the Traveling Salesman Problem with algorithms and precision