TSP Solver: Dynamic Programming and GVNS Approaches 🌍

Introduction

Welcome to the Traveling Salesman Problem (TSP) Solver, an interactive web application designed to find optimal solutions for the classic TSP using both Dynamic Programming and GVNS (General Variable Neighborhood Search) algorithms. The TSP is a fundamental combinatorial optimization problem that involves finding the shortest possible route that visits a given set of cities and returns to the origin city.

This project provides a user-friendly interface for solving TSP instances, visualizing solutions, and understanding the concepts behind these two powerful algorithms.

Features

• Dynamic Programming: Utilizes dynamic programming to calculate the exact solution to small-to-medium-sized TSP instances.
• GVNS Algorithm: Implements the GVNS metaheuristic, a versatile local search method, to tackle larger TSP instances.
• Interactive Visualization: Visualizes the optimal TSP route on a map, making it easy to understand and interpret the results.
• Upload Custom Data: Allows users to upload their own datasets in CSV or Excel format for TSP problem-solving.
• Performance Metrics: Measures and displays performance metrics such as solution quality and computation time.
• Download Solutions: Provides the option to download the TSP solution as a CSV file for further analysis or integration into other applications.

Demo

Explore the application and see it in action by clicking the link below:

Application Interfaces

📈 Dynamic Programming Interface

Description: This interface showcases the Dynamic Programming approach for solving TSP instances. It provides exact solutions for small-to-medium-sized TSP problems.

🔎 GVNS Algorithm Interface

Description: Explore the power of the GVNS (General Variable Neighborhood Search) algorithm in solving larger TSP instances. This metaheuristic approach is designed for scalability and efficiency.

🌐 Interactive Visualization Interface

Description: Visualize the optimal TSP route on an interactive map. This interface provides a graphical representation of the solution, making it easy to understand and analyze.

Getting Started

Follow these simple steps to run the TSP Solver locally:

Prerequisites

Make sure you have Python and the following Python packages installed:

• streamlit
• pandas
• matplotlib
• numpy
• streamlit-lottie

You can install them using pip:

pip install streamlit pandas matplotlib numpy streamlit-lottie 

Usage

1- Clone this repository to your local machine.

2- Navigate to the project directory in your terminal.

3- Run the Streamlit app using the following command:

streamlit run App.py

The app will open in your default web browser. You can now start solving TSP instances and visualizing the results.

Contact 👥

Feel free to reach out to us if you have any questions or suggestions:

Chaimae BOUYARMANE

Happy traveling salesman problem solving! 🚗💨