RoutingManager

A C++ implementation of algorithms for the Traveling Salesman Problem (TSP) on weighted graphs, offering an exact Backtracking Search and a fast Triangular‑Approximation heuristic.

Developed as the Programming Project II assignment for the Algorithm Design course at FEUP. This repository is a reorganized fork of liac1983/FEUP-DA-Project2 with improved code logic, project structure, build convenience, and documentation to aid readability.

📘 Overview

The RoutingManager project aims to solve the Traveling Salesman Problem (TSP) on graph inputs representing cities and pairwise distances. It provides two TSP approaches:

• Backtracking Search

  • Explores all feasible permutations to find an optimal tour.
  • Guarantees optimality but has exponential runtime for larger instances.

• Triangular Approximation Heuristic

  • Builds a fast, near-optimal tour using a triangle-inequality based heuristic.
  • Suitable for larger graphs where exact search is infeasible.

📁 Project Structure

The project is structured as follows:

.
├── build/                         # Compiled binaries (created after building)
├── data/                          # Input datasets for testing
├── docs/
│    ├── Doxygen/
│    │    ├── Doxyfile             # Doxygen configuration file
│    │    ├── logo.jpg             # Project logo
│    │    └── output/              # Doxygen output directory
│    ├── ProjectDescription.pdf    # Project description
│    └── ProjectPresentation.pdf   # Project presentation slides
├── src/
│    ├── Graph.cpp                 # Graph class implementation
│    ├── Graph.h
│    ├── Menu.cpp                  # Menu class implementation
│    ├── Menu.h
│    ├── Parsing.cpp               # Parsing class implementation
│    └── TSP.cpp                   # TSP algorithms implementation
├── .gitignore
├── LICENSE                        # Project license (MIT)
├── main.cpp                       # Entry point for the application
├── Makefile                       # Build instructions
├── README.md                      # Project overview and usage guide
└── RoutingManager                 # Compiled executable (after building)

🚀 Running the Project

To run the RoutingManager project, follow these steps:

0. Prerequisites:

   Ensure you have a C++ compiler (like g++) and make installed on your system.

1. Clone the Repository:

   git clone https://github.com/AFNeves/RoutingManager.git

2. Navigate to the Project Directory:

   cd RoutingManager

3. Build and Run the Project:

   make run

4. (Optional) Clean Build Files:

   make clean

📄 Documentation

The project description and presentation slides can be found in the docs directory:

• ProjectDescription.pdf — detailed project requirements, modeling decisions, and algorithm descriptions.
• ProjectPresentation.pdf — slides used for the project presentation.

Doxygen API reference has already been generated under docs/Doxygen/output/html/index.html. Open that file in your browser to explore the full API documentation (classes, public methods, data members, call graphs and cross‑references).

👥 Authors

This project was developed by:

• Afonso Neves (up202108884@up.pt)
• Lara Cunha (up202108876@up.pt)

📎 License

This project is licensed under the terms of the MIT License.