Skip to content

TSP is a classic optimization problem in computer science and operations research. In this essay, we playfully apply TSP to the case where Elon Musk, the visionary entrepreneur of SpaceX, wishes to visit all the planets of our solar system with minimum cost.

License

Notifications You must be signed in to change notification settings

tkachenko0/Traveling-Salesman-Problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

42 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Traveling Salesman Problem

This is a project created for the final project of the Decision Science subject of the Master's Degree in Computer science of the University of Cagliari.

About

TSP is a classic optimization problem in computer science and operations research. The problem is defined as follows:

Given a set of cities and the distances between each pair of cities, the objective is to find the shortest possible route that allows a salesperson to visit each city exactly once and return to the starting city.

The TSP is classified as an NP-hard problem, which means that it is computationally difficult to find an optimal solution for large instances of the problem. As the number of cities increases, the number of possible routes grows exponentially, making it infeasible to brute-force all possibilities.

In this essay, we playfully apply TSP to the case where Elon Musk, the visionary entrepreneur of SpaceX, wishes to visit all the planets of our solar system. Each path between planets has an associated cost. The goal is to find the overall route that allows Elon Musk to visit all planets while reducing the cost as much as possible.

Planets

Elon Musk

Getting Started

Move to the source folder

cd src

Create a virtual environment and activate it

python3.7 -m venv venv
source venv/bin/activate

Install the requirements

pip install -r requirements.txt

Run the main.py file

python3 main.py

Remember to free the virtual environment in case of dependency additions

pip freeze > requirements.txt

Resources

About

TSP is a classic optimization problem in computer science and operations research. In this essay, we playfully apply TSP to the case where Elon Musk, the visionary entrepreneur of SpaceX, wishes to visit all the planets of our solar system with minimum cost.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages