🗺️ Traveling Salesman Problem (TSP) Solver

A comprehensive web application that solves the Traveling Salesman Problem using three different algorithms and visualizes the results on an interactive map.

🚀 Features

• Three TSP Algorithms: Compare Brute Force, Dynamic Programming, and Greedy approaches
• Interactive Map Visualization: View optimal paths on OpenStreetMap using Leaflet.js
• Real-world Distance Calculations: Uses OpenStreetMap Nominatim API for geocoding and OSRM for routing
• Performance Analysis: Compare execution times and solution quality
• Responsive Design: Works on desktop and mobile devices
• Multiple Path Visualization: See all algorithm results simultaneously with different colors

🏗️ Project Structure

TSP-Solver/
├── backend/                 # Python FastAPI backend
│   ├── main.py             # FastAPI application entry point
│   ├── routes.py           # API endpoints
│   ├── services.py         # Location services (Nominatim + OSRM)
│   ├── algorithms/         # TSP algorithm implementations
│   │   ├── __init__.py
│   │   ├── brute_force.py  # O(n!) brute force solution
│   │   ├── dp.py           # O(n²×2ⁿ) dynamic programming (Held-Karp)
│   │   └── greedy.py       # O(n²) nearest neighbor heuristic
│   ├── requirements.txt    # Python dependencies
│   └── .env               # Environment configuration
├── frontend/              # React frontend
│   ├── public/
│   │   └── index.html
│   ├── src/
│   │   ├── components/
│   │   │   ├── CityForm.jsx      # City input form
│   │   │   ├── MapView.jsx       # Leaflet map visualization
│   │   │   └── ResultsSection.jsx # Algorithm results display
│   │   ├── App.jsx        # Main application component
│   │   ├── index.js       # React entry point
│   │   └── index.css      # Tailwind CSS styles
│   ├── package.json       # Node.js dependencies
│   ├── tailwind.config.js # Tailwind CSS configuration
│   └── postcss.config.js  # PostCSS configuration
└── README.md             # This file

🔧 Setup Instructions

Prerequisites

• Python 3.8+
• Node.js 16+
• npm or yarn

Backend Setup

1. Navigate to backend directory:

   cd backend

2. Create virtual environment (recommended):

   python -m venv venv
   source venv/bin/activate  # On Windows: venv\Scripts\activate

3. Install dependencies:

   pip install -r requirements.txt

4. Start the backend server:

   uvicorn main:app --reload

   The API will be available at http://localhost:8000

5. Verify backend is running: Visit http://localhost:8000 - you should see {"message": "TSP Solver API is running!"}

Frontend Setup

1. Navigate to frontend directory:

   cd frontend

2. Install dependencies:

   npm install

3. Start the development server:

   npm start

   The application will open at http://localhost:3000

📝 Usage Guide

1. Enter Cities: Use the input form to add cities you want to visit

   • Type city names like "Mumbai", "New York", "London"
   • Use the sample city sets for quick testing
   • Minimum 2 cities required, maximum 15 recommended

2. Solve TSP: Click "Solve TSP" to run all algorithms

   • ≤8 cities: All three algorithms will run
   • 9-15 cities: Brute force is skipped (too slow)
   • >15 cities: Only greedy algorithm runs

3. View Results:

   • Map View: Interactive map showing all paths in different colors
   • Results Section: Detailed algorithm comparison with execution times
   • Performance Analysis: Compare solution quality and speed

🧮 Algorithm Details

1. Brute Force

• Time Complexity: O(n!)
• Space Complexity: O(1)
• Description: Tests all possible permutations to guarantee optimal solution
• Best For: Small instances (≤8 cities)

2. Dynamic Programming (Held-Karp)

• Time Complexity: O(n²×2ⁿ)
• Space Complexity: O(n×2ⁿ)
• Description: Uses bitmask DP to find optimal solution efficiently
• Best For: Medium instances (≤15 cities)

3. Greedy (Nearest Neighbor)

• Time Complexity: O(n²)
• Space Complexity: O(n)
• Description: Fast heuristic that may not find optimal solution
• Best For: Large instances or quick approximations

🌐 API Endpoints

POST /tsp

Solve TSP for given cities.

Request:

{
  "cities": ["Mumbai", "Delhi", "Bangalore", "Chennai"]
}

Response:

{
  "cities": [
    {
      "name": "Mumbai",
      "lat": 19.0760,
      "lon": 72.8777,
      "display_name": "Mumbai, Maharashtra, India"
    }
  ],
  "distance_matrix": [[0.0, 1153.8], [1153.8, 0.0]],
  "results": {
    "brute_force": {
      "algorithm": "Brute Force",
      "path": [0, 1, 2, 3],
      "distance": 2847.5,
      "execution_time": 0.001
    }
  }
}

GET /health

Health check endpoint.

🔧 Configuration

Environment Variables (.env)

NOMINATIM_BASE_URL=https://nominatim.openstreetmap.org
OSRM_BASE_URL=http://router.project-osrm.org
API_HOST=0.0.0.0
API_PORT=8000
FRONTEND_URL=http://localhost:3000

🎨 Technologies Used

Backend

• FastAPI: Modern Python web framework
• aiohttp: Async HTTP client for API calls
• Pydantic: Data validation and serialization
• Uvicorn: ASGI server

Frontend

• React 18: Modern frontend framework
• Tailwind CSS: Utility-first CSS framework
• Leaflet: Interactive maps library
• React-Leaflet: React bindings for Leaflet

External APIs

• OpenStreetMap Nominatim: Geocoding service
• OSRM: Routing service for distance calculations

🚧 Troubleshooting

Common Issues

1. Backend won't start:

   • Check Python version (3.8+)
   • Ensure all dependencies are installed: pip install -r requirements.txt
   • Verify port 8000 is available

2. Frontend won't start:

   • Check Node.js version (16+)
   • Clear npm cache: npm cache clean --force
   • Delete node_modules and reinstall: rm -rf node_modules && npm install

3. CORS errors:

   • Ensure backend is running on port 8000
   • Check CORS configuration in main.py

4. Map not loading:

   • Check internet connection
   • Verify Leaflet CSS is loading correctly
   • Check browser console for errors

5. Cities not found:

   • Try more specific city names (e.g., "Mumbai, India")
   • Check Nominatim API is accessible
   • Some city names might not be in OpenStreetMap database

📊 Performance Notes

• Brute Force: Exponential growth - 10! = 3.6M permutations
• Dynamic Programming: Better scaling but still exponential in space
• Greedy: Scales well but solution quality varies
• API Rate Limits: Nominatim and OSRM have usage limits for free tier

🛠️ Development

Adding New Algorithms

1. Create new file in backend/algorithms/
2. Implement function with signature: solve_tsp_algorithm(distance_matrix) -> Dict
3. Add import and call in routes.py
4. Update frontend colors and labels

Extending Frontend

• Components are in frontend/src/components/
• Styling uses Tailwind CSS utility classes
• Map customization in MapView.jsx

📄 License

This project is open source and available under the MIT License.

🤝 Contributing

1. Fork the repository
2. Create feature branch: git checkout -b feature/new-feature
3. Commit changes: git commit -am 'Add new feature'
4. Push to branch: git push origin feature/new-feature
5. Submit pull request

📧 Support

For issues and questions:

• Check the troubleshooting section
• Open an issue on GitHub
• Review the API documentation at http://localhost:8000/docs when backend is running