Vehicle Routing Problem - Release Notes

Version: 1.0.0
Release Date: September 2024
Developed by: Antônio Amaral Egydio Martins
Course: Supercomputação - Insper 2024.1

This project explores various algorithmic approaches to solve the Vehicle Routing Problem (VRP) using both serial and parallel computing techniques. It employs C++, OpenMP, and MPI for efficient computation on different scales, from small to large problem instances. Below are the key features, enhancements, and known issues in this release.

Key Features

1. Directory Structure

Well-organized project directories separating code, executables, documentation, and outputs.
Jupyter notebook for explanations and testing.
Python script for graph visualization.

2. Algorithms

Global Search (Serial and Parallel): Implements a complete search of all possible paths using both serial and parallel processing methods (OpenMP and MPI).
Heuristic Search (Serial and Parallel): A faster, approximate solution using the Nearest Neighbor algorithm, available in serial and parallel versions.
Parallel Optimization: Utilizes optimized permutation generation and path exploration, including parallelization strategies with OpenMP and MPI.
Path Generation: Serial and parallel generation of valid routes based on vehicle capacity and graph connectivity.

3. Parallel Computing

Integration of OpenMP for multi-threaded processing.
Full MPI support for distributed processing across cluster nodes.
Custom SLURM script provided for running MPI on cluster environments.

4. Performance Analysis

Comparative analysis of serial vs. parallel implementations.
Performance improvements achieved with parallel algorithms on large graph instances:
Up to 78.45% reduction in execution time using MPI for N=11.
Significant improvements for global path search in parallel executions.

5. Extra Features

Added extra parallelized versions of path generation and nearest neighbor search.
Enhanced heuristic search for faster approximate solutions.

Enhancements
Parallel Permutation Generation: Optimized to reduce overhead from synchronization and copying, leading to a faster performance in larger problem sets.
Global Parallelization: Full integration of MPI and OpenMP for massive performance gains in the search for the optimal vehicle routing path.
Heuristic Search Tuning: Improved heuristic algorithms for faster execution, ideal for larger graphs where global search becomes computationally expensive.

Known Issues
Heuristic Search Precision: In some cases, the heuristic approach may not reach the global minimum, with an error margin of up to 30.30% in edge cases (N=6).
Overhead in Small Graphs: For smaller graph sizes (N<7), parallelization overhead reduces the benefits of parallel processing, making serial versions perform equally well or better.

Performance Results Summary
Serial algorithms perform adequately for small datasets but scale poorly with the problem size.
Parallel algorithms (OpenMP and MPI) show significant performance improvements, especially for large problem instances (N=9, N=11).
The global search algorithm always produces the most accurate results but requires more computational resources.
Heuristic search provides a faster alternative but at the cost of reduced precision.

Future Work
Further optimize heuristic methods to reduce the error margin in large datasets.
Explore additional parallelization techniques, including hybrid models using both OpenMP and MPI.
Extend performance testing to even larger graph sizes for real-world scalability.