The traveling salesman problem (TSP) consists of finding the minimum route to connect N cities, which are all visited only once and which returns to its departure city. This classic optimization problem is very simple to state but very difficult to solve. Indeed, the most naive algorithm consisting of comparing all possible paths requires a calculation time which is proportional to N!. Slightly more efficient exact algorithms have been created, but they do not allow us to go much further than 200,000 cities.
This solution provides a desktop application built in Python using Tkinter and a genetic algorithm to solve the TSP.
tsp_problem_algorithm_genitic.py: Main Python script implementing the TSP solver with Tkinter GUI and genetic algorithm.images/: Directory containing icons used in the GUI.logo.ico: Icon file used for the application.
- Interactive Graph: Users can draw nodes on the canvas by clicking, representing cities for the TSP.
- Conversion to Distance Matrix: Converts the drawn graph into a distance matrix by specifying distances between nodes.
- TSP Solving: Solves the TSP using a genetic algorithm and displays the best route found.
- Dark/Light Mode: Supports both dark and light modes for user preference.
- Graph Clearing: Option to clear the graph and start fresh.
To run the application, follow these steps:
- Clone the repository or download the source files.
- Ensure you have Python installed on your system.
- Install the required libraries by running:
pip install numpy deap customtkinter - Convert the Python script to an executable file using PyInstaller:
pyinstaller --onefile -w --icon="images/logo.ico" "tsp_problem_algorithm_genitic.py" - Run the generated executable file.
- Launch the application.
- Draw nodes on the canvas by clicking to represent cities.
- Connect nodes and convert to a distance matrix.
- Solve the TSP using the genetic algorithm.
- View the best route found and its fitness score.
- Optionally, switch between dark and light mode.
- Clear the graph to start fresh.