Traveler Salesman Problem Optimization

A list of Heuristics, Metaheuristics and Matheuristic algorithms for solve the TSP.
Read the paper »

View Results • Report Bug • Request Feature

---

📔 Introduction

This project encompasses a comprehensive suite of algorithms designed to tackle the classic TSP, providing solutions via various heuristics, matheuristics, and exact optimization models. Leveraging the power of IBM’s CPLEX solver, our exact models deliver high-quality solutions with mathematical rigor and efficiency.

Overview

The TSP Solver offers a versatile and powerful framework to approach the Traveling Salesman Problem, which seeks the shortest possible route that visits each city once and returns to the origin city. Our solver is equipped with:

• Heuristics: Fast, efficient algorithms that provide good solutions within a reasonable time frame. These include methods such as Nearest Neighbor and 2-Opt.
• Matheuristics: Advanced hybrid techniques that combine heuristics with mathematical programming to enhance solution quality.
• Exact Models: Robust formulations that guarantee optimal solutions using the CPLEX solver from IBM, ensuring precision and thoroughness in solving TSP instances.

Neirest Neighbor	Neirest Neighbor + 2-Opt
Benders' Loop	Local Branching

The program also includes a version of Performance profiler developed in python by Professor Salvagnin to analyze the performance of the implemented algorithms. This tool allows you to compare the performance of different algorithms and evaluate the quality of the solutions obtained. These are some examples of the results:

Important

1. To run this program you need to have a valid CPLEX license. You can download the CPLEX solver from the IBM website.

🛠 Built in

The entire program is developed using the following major frameworks and libraries. Leave any add-ons / plug-ins for the thanks section.

C Programming Language • CMake • IBM CPLEX Optimization Studio • GNUPlot

⇧

📚 Documentation

• Random: A simple algorithm that generates random solutions to the TSP, providing a baseline for comparison with more sophisticated methods.
• Heuristics
  • Nearest Neighbor (NN): This algorithm starts from an initial node and selects the nearest node to move to next. The process is repeated until all nodes have been visited. It is a simple and effective method to quickly obtain an acceptable solution for problems like the Traveling Salesman Problem (TSP).
  • 2-Opt: The 2-Opt algorithm is used to iteratively improve a solution by exchanging pairs of edges. The idea is to reduce the overall path length by finding and removing "crosses" between the edges, replacing them with non-intersecting edges.
• Metaheuristics
  • Variable Neighborhood Search (VNS): This metaheuristic explores different neighborhood structures to avoid getting stuck in local minima. By changing the neighborhood structure, the algorithm can explore a larger part of the solution space, increasing the chances of finding the optimal solution.
  • Tabu Search (TS): Tabu Search employs a tabu list to keep track of already visited solutions, preventing the algorithm from revisiting them. This mechanism helps avoid cycles and overcome local minima, promoting a more thorough search of the solution space.
• Exact Methods
  • Benders' Loop: This algorithm solves complex problems by dividing them into a main problem and various subproblems. The iterative process alternates between solving the main problem and the subproblems, progressively refining the overall solution.
  • Glued Benders' Loop: Similar to Benders' Loop, this method addresses the main problem and subproblems iteratively but with the integration of techniques that improve convergence and process efficiency.
  • Mipstart: Custom function applied to the relaxed solution of the problem
  • Callback Base: It's a callback function that can be used when CPLEX finds an integer solution so we can check the number of components and add the SECs if needed.
  • Callback Relax: It's a callback function that can be used when CPLEX finds a relaxed (not integer) solution so we can check the number of components and add the SECs if there is more than one, or a min cut otherwise.
  • Posting Base: It's a method implemented in the Callback Base that performs the gluing operation on the candidate solution and posts it on the CPLEX environment.
  • Posting Relax: It's a method implemented in the Callback Relax that use an heuristic method on the relaxed solution to get a feasible solution and posts it on the CPLEX environment.
• Matheuristics
  • Local Branching: This approach introduces local constraints to rapidly explore portions of the solution space, improving the effectiveness in searching for optimal solutions.
  • Hard Fixing (Diving): This technique temporarily fixes some variables to reduce the problem size, allowing a deeper search in the remaining variables. It is particularly useful for tackling large-scale problems, improving the speed of convergence towards an optimal solution.

For a more complete explanation of how the algorithms work, please refer to the Paper »

There are different parameters and different ways to start the program. More details are available at the following link: Documentation »

⇧

🧰 Prerequisites

To use the actual algorithms, a CPLEX license is required. If you have a license, you can download the software from IBM's official website. An installation guide for MacOS is available at the following link: CPLEX installation on MacOS ». Currently, there is no installation guide available for Windows or Linux.

NOTE: You also need to install cmake and gnuplot to compile the code.

⇧

⚙️ How to Start

As mentioned earlier, there are different options:

• Single Command: Launch a single execution with command line parameters
• Menu: Launch a single execution with parameters chosen from a menu
• Launcher: Launch one or more executions with parameters present in a text file

Single Command

Once you have chosen the parameters and positioned yourself on the folder containing the code, you can launch the program with the following commands:

MacOS

    mkdir build && cmake -S . -DCPLEXDIR="/Applications/CPLEX_Studio2211/cplex" -B build
    make -C build && ./TSP_Optimization -g 100 -model 2 -opt 1

Windows

    cmake . -B build --fresh && cmake --build build --clean-first
    .\TSP_Optimization -f Resource/a280.tsp -model 2 -v 60

Linux

    mkdir build && cmake -S . -DCPLEXDIR="C:/Program Files/IBM/ILOG/CPLEX_Studio_Community2211/cplex/" -B build
    make -C build && ./TSP_Optimization -g 300 -model 3 -opt 12 -s 1 -v 60 -tl 120

Menu

If you want to use the menu after compiling the code as previously with cmake, you can launch the program with the following command:

MacOS/Linux

    make -C build && ./TSP_Optimization

Windows

    .\TSP_Optimization -g 300 -model 2 -v 10 -tl 60

Launcher

If you want to use the Launcher after compiling the code as previously with cmake, you can launch the program with the following command:

MacOS/Linux

    make -C build && clear && ./TSP_Optimization -launcher Resource/Launcher/launcher.txt

Windows

    .\TSP_Optimization -launcher Resource/Launcher/launcher.txt

An example of the launcher file can be found at the following link: Laucher Example »

We remind you that a list of available parameters is present at the following link: Available Parameters »

Once launched, the program will execute the chosen algorithm, displaying the results on the screen with GNUPlot (if selected as a parameter). Additionally, the files generated through the -g command with the coordinates of the points will be saved. An .svg and .png image of the optimal path found will also be saved as output.

Note: If the launcher is used, a .csv file with the obtained results will be generated in the output, so that you can use the performance profiler. To use it automatically, it is also necessary to install python3 and matplotlib by following these steps:

    python3 -m venv env
    pip3 install matplotlib
    . env/bin/activate

You can also launch it manually on .csv file with the following command:

    python3 src/Comparator/perfprof.py -D , -T 3600 -S 2 -M 20 CSV_PATH OUTPUT_PATH/OUTPUT_FILE_NAME.pdf -P 'Performance Profile'

Di seguto è possibile vedere un esempio dell'output ottenuto a termminale. Dove la prima parte contine i parametri utilizzati, la seconda parte i risultati ottenuti come il costo ed i tempi. NOTE: Per visionare gli output dei risultati e necessario settare il verbose ad un valore maggiore di 0 come riportato nell'immagine.

    make -C build && clear && ./TSP_Optimization -g 100 -model 2 -opt 1 -s 1 -tl 120 -v 1

⇧

---

📮 Responsible Disclosure

We assume no responsibility for an improper use of this code and everything related to it. We do not assume any responsibility for damage caused to people and / or objects in the use of the code.

By using this code even in a small part, the developers are declined from any responsibility.

It is possible to have more information by viewing the following links: Code of conduct • License

⇧

🐛 Bug and Feature

To report a bug or to request the implementation of new features, it is strongly recommended to use the ISSUES tool from Github »

Here you may already find the answer to the problem you have encountered, in case it has already happened to other people. Otherwise you can report the bugs found.

ATTENTION: To speed up the resolution of problems, it is recommended to answer all the questions present in the request phase in an exhaustive manner.

(Even in the phase of requests for the implementation of new functions, we ask you to better specify the reasons for the request and what final result you want to obtain).

⇧

---

🔍 License

APACHE LICENSE
Version 2.0, Jan 2004

"License" shall mean the terms and conditions for use, reproduction, and distribution as defined by Sections 1 through 9 of this document.

"Licensor" shall mean the copyright owner or entity authorized by the copyright owner that is granting the License...
License Documentation »

✏️ Authors and Copyright

👨🏽‍💻	Andrea Pietrobon	Andrea Felline
🌐	pietrobonandrea.com	andreafelline.altervista.org
	@PietrobonAndrea
🗄 Traveler Salesman Problem Optimization

⇧

📌 Third Party Licenses

Software	License owner	License type	Link	Note
IBM CPLEX Optimization Studio	IBM	-	Link
Perfprof	Proessor D. Salvagnin	Not Specified	link
GNUPlot	Thomas Williams, Colin Kelley	Copyright	link

⇧

---

Copyrright (C) by Pietrobon Andrea
Released date: 24-07-2024