Optimized Route Planner Using Travelling Salesman Problem (TSP) / DAA Project by Abhinav

An advanced route optimization system that calculates the shortest possible route for visiting multiple destinations and returning to the starting point. This project implements several algorithms to solve the Travelling Salesman Problem (TSP) and provides performance comparisons between them.

Features

Multiple TSP Algorithms:
- Brute Force (for small instances)
- Dynamic Programming (Held-Karp)
- Nearest Neighbor Approximation
- Minimum Spanning Tree (MST) 2-Approximation
- Christofides Algorithm (3/2-Approximation)
- Simulated Annealing (Metaheuristic)
- Genetic Algorithm (Metaheuristic)
Graph Visualization: Visual representation of routes and algorithm performance
Algorithm Comparison: Analyze execution time and solution quality across algorithms
Distance Metrics: Support for Euclidean and Manhattan distances
Google Maps Integration: Convert addresses to coordinates and get detailed directions
Performance Optimization: Scalable to handle larger numbers of locations

Project Structure

/
├── backend/                    # Python backend
│   ├── algorithms/             # TSP algorithm implementations
│   │   ├── brute_force.py      # Exhaustive search (O(n!))
│   │   ├── dynamic_programming.py # Held-Karp algorithm (O(n²2ⁿ))
│   │   ├── approximation.py    # Approximation algorithms
│   │   └── metaheuristic.py    # Simulated annealing & genetic algorithms
│   ├── utils/                  # Utility modules
│   │   ├── graph.py            # Graph representation
│   │   └── visualization.py    # Route visualization tools
│   ├── main.py                 # Flask API endpoints
│   └── requirements.txt        # Python dependencies
│
└── frontend/                   # React frontend
    ├── src/
    │   ├── components/         # React components
    │   │   ├── RouteMap.js     # Route visualization component
    │   │   ├── RouteMap.css
    │   │   ├── ControlPanel.js # User control interface 
    │   │   └── ControlPanel.css
    │   ├── App.js              # Main app component
    │   └── App.css             # Global styles
    └── public/                 # Static assets

Getting Started

Prerequisites

Python 3.8+ with pip
Node.js and npm

Installation

Clone the repository

git clone https://github.com/iabhinavtiwari247/optimized-route-planner.git
cd optimized-route-planner

Set up the backend

cd backend
pip install -r requirements.txt

Set up the frontend
```
cd frontend
npm install
```
Create a .env file in the backend directory with your Google Maps API key:
```
GOOGLE_MAPS_API_KEY=your-api-key-here
```

Running the Application

Start the backend server
```
cd backend
python main.py
```
Start the frontend development server
```
cd frontend
npm start
```
Open your browser and navigate to http://localhost:3000

API Endpoints

GET /health - Health check endpoint
POST /api/solve - Solve TSP with a specific algorithm
POST /api/compare - Compare multiple TSP algorithms
POST /api/geocode - Convert an address to coordinates
POST /api/directions - Get detailed directions between locations

Algorithm Performance

Algorithm	Time Complexity	Space Complexity	Optimality	Best For
Brute Force	O(n!)	O(n)	Optimal	< 10 locations
Dynamic Programming	O(n²2ⁿ)	O(n2ⁿ)	Optimal	< 20 locations
Nearest Neighbor	O(n²)	O(n)	Approximate	Any size, quick solutions
MST 2-Approximation	O(n² log n)	O(n)	≤ 2 * optimal	Medium-sized problems
Christofides	O(n³)	O(n²)	≤ 1.5 * optimal	Metric TSPs
Simulated Annealing	O(n² * iterations)	O(n)	Near-optimal	Large problems
Genetic Algorithm	O(population * generations * n)	O(population * n)	Near-optimal	Large problems

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

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

Acknowledgments

Special thanks to all contributors
Inspired by the traveling salesman problem in combinatorial optimization

Optimized Route Planner Using Travelling Salesman Problem (TSP)

An advanced route optimization system that calculates the shortest possible route for visiting multiple destinations and returning to the starting point. This project implements several algorithms to solve the Travelling Salesman Problem (TSP) and provides performance comparisons between them.

Features

Multiple TSP Algorithms:
- Brute Force (for small instances)
- Dynamic Programming (Held-Karp)
- Nearest Neighbor Approximation
- Minimum Spanning Tree (MST) 2-Approximation
- Christofides Algorithm (3/2-Approximation)
- Simulated Annealing (Metaheuristic)
- Genetic Algorithm (Metaheuristic)
Graph Visualization: Visual representation of routes and algorithm performance
Algorithm Comparison: Analyze execution time and solution quality across algorithms
Distance Metrics: Support for Euclidean and Manhattan distances
Google Maps Integration: Convert addresses to coordinates and get detailed directions
Performance Optimization: Scalable to handle larger numbers of locations

Project Structure

/
├── backend/                    # Python backend
│   ├── algorithms/             # TSP algorithm implementations
│   │   ├── brute_force.py      # Exhaustive search (O(n!))
│   │   ├── dynamic_programming.py # Held-Karp algorithm (O(n²2ⁿ))
│   │   ├── approximation.py    # Approximation algorithms
│   │   └── metaheuristic.py    # Simulated annealing & genetic algorithms
│   ├── utils/                  # Utility modules
│   │   ├── graph.py            # Graph representation
│   │   └── visualization.py    # Route visualization tools
│   ├── main.py                 # Flask API endpoints
│   └── requirements.txt        # Python dependencies
│
└── frontend/                   # React frontend
    ├── src/
    │   ├── components/         # React components
    │   │   ├── RouteMap.js     # Route visualization component
    │   │   ├── RouteMap.css
    │   │   ├── ControlPanel.js # User control interface 
    │   │   └── ControlPanel.css
    │   ├── App.js              # Main app component
    │   └── App.css             # Global styles
    └── public/                 # Static assets

Getting Started

Prerequisites

Python 3.8+ with pip
Node.js and npm

Installation

Clone the repository

git clone https://github.com/iabhinavtiwari247/optimized-route-planner.git
cd optimized-route-planner

Set up the backend

cd backend
pip install -r requirements.txt

Set up the frontend
```
cd frontend
npm install
```
Create a .env file in the backend directory with your Google Maps API key:
```
GOOGLE_MAPS_API_KEY=your-api-key-here
```

Running the Application

Start the backend server
```
cd backend
python main.py
```
Start the frontend development server
```
cd frontend
npm start
```
Open your browser and navigate to http://localhost:3000

API Endpoints

GET /health - Health check endpoint
POST /api/solve - Solve TSP with a specific algorithm
POST /api/compare - Compare multiple TSP algorithms
POST /api/geocode - Convert an address to coordinates
POST /api/directions - Get detailed directions between locations

Algorithm Performance

Algorithm	Time Complexity	Space Complexity	Optimality	Best For
Brute Force	O(n!)	O(n)	Optimal	< 10 locations
Dynamic Programming	O(n²2ⁿ)	O(n2ⁿ)	Optimal	< 20 locations
Nearest Neighbor	O(n²)	O(n)	Approximate	Any size, quick solutions
MST 2-Approximation	O(n² log n)	O(n)	≤ 2 * optimal	Medium-sized problems
Christofides	O(n³)	O(n²)	≤ 1.5 * optimal	Metric TSPs
Simulated Annealing	O(n² * iterations)	O(n)	Near-optimal	Large problems
Genetic Algorithm	O(population * generations * n)	O(population * n)	Near-optimal	Large problems

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Deployment

Docker Deployment (Recommended)

This project includes Docker and Docker Compose configurations for easy deployment.

Make sure you have Docker and Docker Compose installed on your system
```
docker --version
docker-compose --version
```
Copy the example environment file and configure your environment variables
```
cp .env.example .env
```
Then edit the .env file to add your Google Maps API key and any other configuration
Build and start the containers
```
docker-compose up -d --build
```
Access the application at http://localhost
Monitor the container logs
```
docker-compose logs -f
```
To stop the containers
```
docker-compose down
```

Deployment on Cloud Platforms

Heroku Deployment

This project includes configuration for deploying to Heroku with Docker support.

Option 1: Using the Deployment Script (Recommended)

Make sure you have the Heroku CLI installed
Run the deployment script:
```
scripts\deploy-heroku.bat
```
Follow the prompts to enter your app name and Google Maps API key

Option 2: Manual Deployment with Docker

Login to Heroku and the Container Registry:
```
heroku login
heroku container:login
```
Create a new Heroku app:
```
heroku create your-app-name
```

Set your Google Maps API key:

heroku config:set GOOGLE_MAPS_API_KEY=your_api_key_here --app your-app-name

Build and push the container:

heroku container:push web --app your-app-name

Release the container:

heroku container:release web --app your-app-name

Open your app:
```
heroku open --app your-app-name
```

Option 3: Manual Deployment with Git

Login to Heroku:
```
heroku login
```
Create a new Heroku app:
```
heroku create your-app-name
```

Set your Google Maps API key:

heroku config:set GOOGLE_MAPS_API_KEY=your_api_key_here --app your-app-name

Deploy your app:

git add .
git commit -m "Heroku deployment"
git push heroku master

Open your app:
```
heroku open --app your-app-name
```

AWS Deployment

Create an ECR repository for your Docker images
Build and push your images to ECR
Deploy using ECS or Kubernetes (EKS)
Configure an Application Load Balancer

Google Cloud Platform

Push images to Google Container Registry
Deploy using Google Kubernetes Engine (GKE)
Configure external load balancing

Microsoft Azure

Push images to Azure Container Registry
Deploy using Azure Kubernetes Service (AKS)
Configure Azure Load Balancer

Render Deployment

This project includes configuration for deploying to Render.com, a modern cloud platform.

Option 1: Using the Deployment Script (Recommended)

Make sure you have a Render account and Git installed

Run the deployment script:

# On Windows
scripts\deploy-render.bat

# On Unix/Linux/Mac
bash scripts/deploy-render.sh

Follow the prompts to initialize Git if needed and open the Render dashboard
Connect your repository and deploy the blueprint

Option 2: Manual Deployment

Push your code to GitHub or GitLab
Log in to Render Dashboard
Click "New" and select "Blueprint"
Connect your repository with the code
Configure your services based on the render.yaml file
Set your Google Maps API key as an environment variable
Apply the changes and wait for deployment to complete

Your application will be available at:

Frontend: https://tsp-frontend.onrender.com
Backend API: https://tsp-backend.onrender.com

License

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

Acknowledgments

Special thanks to all contributors
Inspired by the traveling salesman problem in combinatorial optimization

Docker Deployment Steps

Build the Docker images:

# Build backend image
docker build -t tsp-backend ./backend

# Build frontend image
docker build -t tsp-frontend ./frontend

Create a Docker network:
```
docker network create tsp-network
```

Run the containers:

# Run backend container
docker run -d --name tsp-backend \
  --network tsp-network \
  -p 5000:5000 \
  -e GOOGLE_MAPS_API_KEY=your_api_key_here \
  tsp-backend

# Run frontend container
docker run -d --name tsp-frontend \
  --network tsp-network \
  -p 80:80 \
  tsp-frontend

Alternatively, use Docker Compose (recommended):

# Set your Google Maps API key in .env file first
docker-compose up -d

Access the application:
- Frontend: http://localhost
- Backend API: http://localhost:5000/health

Monitor the containers:

# View logs
docker-compose logs -f

# Check status
docker-compose ps

Stop the application:
```
docker-compose down
```

To Download the app : If you want to download the entire Dockerized app to your pc then :

Steps:

Export the Docker image:

docker save -o my_app_image.tar my-app-image-name

Transfer the .tar file to another PC:

Use USB, FTP, SCP, or any file-sharing method.

On the PC: Install Docker if not already:

Download Docker and install.

Load the Docker image:

docker load -i my_app_image.tar

Run the Docker container:

docker run -d -p 8080:80 my-app-image-name

Access the application on the new PC:

In the browser: http://localhost:8080

Name		Name	Last commit message	Last commit date
backend		backend
frontend/src		frontend/src
.env		.env
README.md		README.md

Latest commit

History

Folders and files

Repository files navigation

Optimized Route Planner Using Travelling Salesman Problem (TSP) / DAA Project by Abhinav

Features

Project Structure

Getting Started

Prerequisites

Installation

Running the Application

API Endpoints

Algorithm Performance

Contributing

License

Acknowledgments

Optimized Route Planner Using Travelling Salesman Problem (TSP)

Features

Project Structure

Getting Started

Prerequisites

Installation

Running the Application

API Endpoints

Algorithm Performance

Contributing

Deployment

Docker Deployment (Recommended)

Deployment on Cloud Platforms

Heroku Deployment

Option 1: Using the Deployment Script (Recommended)

Option 2: Manual Deployment with Docker

Option 3: Manual Deployment with Git

AWS Deployment

Google Cloud Platform

Microsoft Azure

Render Deployment

Option 1: Using the Deployment Script (Recommended)

Option 2: Manual Deployment

License

Acknowledgments

Docker Deployment Steps

About

Resources

Stars

Watchers

Forks

Releases

Packages

Used by

Contributors

Languages