Project developed for DA 23/24, by Nuno Machado, Rafael Magalhães, Ricardo Oliveira.

Understand the limitations of solving intractable problems like TSP. Implement basic exhaustive approaches and refine critical thinking skills by designing and analyzing approximate solutions using heuristics.

Design efficient algorithms to find optimal routes for vehicles in shipping and delivery scenarios. Backtracking techniques for small graphs and approximation algorithms for larger graphs are emphasized.

Real datasets describe urban delivery points and harbors. Implement a menu-driven interface, functionality to load and parse datasets, and document code using Doxygen.

Develop a backtracking algorithm for TSP.
Implement a triangular approximation heuristic.
Design another heuristic for TSP.
Develop an algorithm for TSP in real-world graphs.

Includes small toy examples, real-world graphs, and extra medium-sized graphs for experimentation.