How felicze/3l-cvrp works
1. The core C++ implementation that contains the branch‐and‐cut algorithm and its numerous submodules.
Main components
• Core Algorithm (C++ Source)
• This component is implemented in the “cpp/3L-VehicleRouting” directory. It includes several submodules:
• 3L-VehicleRoutingApplication: Entry point/application (contains the main algorithm logic, reading parameters, executing solver, etc.).
• CommonBasics: Contains fundamental helper functions and algorithmic building blocks (e.g., base models, helper functions for CP and MIP services).
• ContainerLoading: Implements the three-dimensional container loading subproblem; includes the exact CP model for checking route feasibility and different packing algorithms.
• VehicleRouting: Handles the vehicle routing aspects (e.g., separation of cuts, branch and cut solvers, heuristics, and modeling of instances and solutions).
• External integration: This part makes use of third-party libraries and code packages that are provided in “external” (e.g., CLI11 for command line parsing, cvrpsep for separation of cuts, nlohmann for JSON).
• Build and configuration: The CMake-based build system (with related CMakeLists.txt files) configures the overall structure and dependency builds.
• Data Management
• Input Data: Under “data/input/3l-cvrp”, this folder holds instance files (JSON format) and parameter files.
• Output Data: Under “data/output/3l-cvrp”, a variety of result variants are stored (e.g., “all-constraints”, “no-fragility”, “no-support”, etc.). These include solution files, logs, statistics, and validator files.
• Visualization and Analysis (Python)
• The “python” folder hosts the visualization application. Key files such as “SolutionVisualizer.py”, “RouteVisualizer.py”, and several analysis modules (like StatisticAnalyzer.py) built using Streamlit support solution and statistic display.
• Configuration files (pyproject.toml and requirements.txt) indicate the dependency management for this component.
Relationships and interactions
• The input data (instances and parameters) feed into the C++ algorithm via command-line arguments.
• The branch-and-cut algorithm solves a 3L-CVRP instance, using external libraries (Gurobi for MIP, OR-Tools for CP) in its submodules.
• The algorithm writes its outputs, including detailed solution files and solver logs/statistics to the output directories.
• The Python visualizer reads these outputs (JSON files, logs) and renders interactive solution visualizations and performance statistics.
• External libraries act as supporting services for both the algorithm (e.g., boosting optimization and parsing) and for JSON output management.
Important architectural patterns/design principles
• Modularity: Different functional parts of the algorithm (loading, routing, helper routines) are separated into distinct subdirectories (“CommonBasics”, “ContainerLoading”, “VehicleRouting”) clearly mapping to layered responsibilities.
• Separation of concerns: The core solver is isolated from the data operations (inputs/outputs) and from visualization, enabling independent testing and development.
• Use of external libraries to abstract command-line interfaces (CLI11), JSON serialization (nlohmann), and mathematical optimization (Gurobi, OR-Tools) promotes reusability.
Relevant technologies and frameworks
• C++ along with CMake as the primary build tool.
• Gurobi (as the MIP solver) and Google OR-Tools (for CP-based loading feasibility).
• Boost and TBB libraries.
• External domain-specific code such as A-MDVRP and CVRPSEP modules.
• For the visualization part: Python, Streamlit, and associated libraries (e.g., requirements.txt dependencies).