Various algorithms to solve the traveler salesman problem!
📄Paper
·
🕹️Live Demo
·
🐞Report Bug
·
⚙️Request Feature
This is a project for the course Operations Research 2 taken by prof. Matteo Fischetti in the a.y. 2020/2021
This project focuses on solving TSPs with different algorithms
You can download the latest release from here
Here we describe how the project folder is organized:
- build is a generated folder by cmake which contains all the files needed for building the project and its executable
- data folder contains the .tsp files
- docs contains the documentation of the data formatting taken from TSLIB
- include contains the .h files of the project
- libs contains the third pary libraries utilized in this project.If it's not present, create it
- logs is a generated folder when a method which uses CPLEX is utilized. It contains the CPLEX's log files
- results contains the performance profile experiments saved in .csv files and some comparison charts saved in .pdf files
- model is a generated folder which contains .lp files generated by CPLEX
- other_codes contains some python scripts which are useful for performance profiles etc
- plot contains the solved plots of the problems
- src contains the source files of the project
- test not used
- tour is a generated folder which saves the .tour files in TSPLIB format. Those files contain the information of the problem's solution
- webapp contains the backend and the frontend
To compile this repository, Cplex and Concorde are required. To install Cplex you can follow IBM's guide.
To install Concorde, follow the following steps:
- Download Concorde's zipped tar file from here
- Extract it in the libs folder. You should now have libs/concorde. Note if the libs folder is not present, create it
- Now using terminal type
cd libs/concorde - Now type
./configure. If you're MacOS user, type./configure --host=darwin - When the latest comand finishes, type
maketo conclude the installation
If you want details on how to install concorde, check this guide
When all the requirements are satisfied, you can finally compile the project.
Once you have configured the the project with CMake based on your IDE and environment, to compile the project you have to go in build folder typing cd build and type make.
The input data is given TSPLIB The format is described in tsp95.pdf
To run the program, inside the build folder, type ./tsp.
To see all the command line options, use ./tsp --help.
To see the list of the methods available, use ./tsp --methods.
An example of usage is: ./tsp -f ../data/att48.tsp -method GG -t 300 -verbose 4
To plot the TSP solution in a png file, gnuplot must be installed. You can install it from your OS repository such as apt install gnuplot on ubuntu or brew install gnuplot on MacOS.
If you're on windows, use Windows Subsistem for Linux (WSL). The native compatibility on windows is not supported
Using docker (easiest way):
docker build -t tsp-webapp .docker run -p 80:80 -d tsp-webapp
Install pip:
sudo apt updatesudo apt install python3-pippip3 --version
Install Flask:
sudo apt install python3-venv- Go to the folder that contains
backed.py: python3 -m venv venv- To start using this virtual environment:
source venv/bin/activate (venv) $ pip install Flask(venv) $ python -m flask --version(venv) $ pip install -U flask-cors
Start the application locally:
(venv) $ export FLASK_APP=backend.py(venv) $ flask run- Open http://127.0.0.1:5000 in your web browser and you will see the website
Start the applicaton on production server:
(venv) $ export FLASK_APP=backend.py(venv) $ nohup flask run --host=0.0.0.0 --port=80- OR in the project root folder execute
nohup ./runBacked.sh
To stop the development server type CTRL-C in your terminal.
To deactivate the Virtual Environment: (venv) $ deactivate
Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.
Copyright (c) 2021 Denis Deronjic & Stefano Ivancich