Algorithm Analysis and Design project
This repository comprises the second part of the Algorithm Analysis and Design course unit project. The goal was to create a solution for a specific problem applying the object-oriented paradigm in C++ and algorithm design.
Project description
The theme approached in the problem is a particularization of the Travelling Salesman Problem, the Vehicle Routing Problem with Pick-up and Delivery. This repository contains the algorithm solution for that problem as well as an application related to the problem.
Project article
A more theoretical study of the problem can accessed here. The study contains all the information related to the algorithm development process as well as the conceptual business model.
Compiling
Dependencies
GraphViewer
GraphViewer is a tool for graph visualization based on the JUNG framework, in the context of the Algorithm Design and Analysis course, at FEUP. It has been developed and mantained over the years by the course's Teaching Assistant students.
Google Test
Google Test is a unit testing library for the C++ programming language, based on the xUnit architecture.
Requirements
- CMake 3.10.2 or higher
- Java 8 or higher (used in GraphViewer)
Linux
To compile a linux executable file run the build.sh script in the root directory. The output files are going to be stored in the build directory.
Windows
To compile a linux executable file run the winbuild.sh script in the root directory. The output files are going to be stored in the winbuild directory.
Running
Resources and libraries
The maps must be placed in the resources directory. The GraphViewer jar file must be placed in the lib directory. Both directories have to be in the same directory as the executable file.
Program arguments
Map name
The name of the map to run the application. There are currently two maps in the resources. A small map around FEUP, resources/Porto. And a highly connected graph with the city of Porto, resources/Porto_strong.
Values: Porto and Porto_strong.
Company garage id
The location ID of the company's garage. The location ID of a node is defined in the nodes.txt file of a map.
Values: any ID in the nodes.txt file of a map.
Demonstration mode
When defined true the application bootstraps a default company client with a set of predefined pick-up points. This argument is optional.
Values: true of false.
Running in Linux
./application <map name> <company garage id> [<demonstration mode>]Running in Windows
.\application.exe <map name> <company garage id> [<demonstration mode>]Documentation
The code documentation is generated with doxygen. Doxygen is a third-party documentation tool, thus, it is necessary a previous installation in order to be able to get the documentation. A standard project doxygen configuration file is located in the 'docs' directory under the name doxyfile. Currently, the documentation is only exported in HTML. After exporting the files are stored in the docs directory.
Here is an example of how to export the documentation with the standard project doxygen configuration file:
cd doc
doxygen DoxyfileTesting
The unit tests are perfomed by Google Test, the Google's C++ test framework. Currently, the version used is the latest.
The code coverage can be consulted by clicking the coverage badge in the header.
Examples
1. Company with 4 available vehicles and 10 pick-up points
2. Company with 3 available vehicles and 6 pick-up points
Disclaimer
This repository contains the C++ solution for the problem. Note that it might contain errors and should not be used as a solution for anyone besides the authors.