Multi-Lingual Supply Chain Algorithm Performance Benchmark

Optimizing for Real-World Scenarios

1. Project Overview

This project is a comprehensive performance benchmark comparing the execution speed and solution quality of various programming languages— Python, C++, Rust, and Julia **—when applied to a critical **Supply Chain Management (SCM) problem: the Capacitated Vehicle Routing Problem (CVRP) .

**At its core, it's a deep dive into how different programming paradigms and compiler optimizations impact the efficiency of solving complex, real-world logistical challenges. We implemented and benchmarked two widely used CVRP heuristics: the **Nearest Neighbor Heuristic and the Clarke & Wright Savings Heuristic , across carefully constructed datasets of varying scales (small, medium, and large).

2. What Does This Project Do?

The project systematically:

• Generates Realistic Data: Creates synthetic CVRP instances (customer locations, demands, vehicle capacities, depot location) in a standardized text format, ensuring fair and reproducible comparisons across languages.
• Implements Core Algorithms: Provides robust implementations of the Nearest Neighbor and Savings heuristics in Python, C++, Rust, and Julia. Each implementation adheres to the specific language's best practices for performance.
• Automates Benchmarking: Includes dedicated runner scripts for each language to automate the execution of the algorithms across all data scales, capturing precise execution times (in milliseconds) and the resulting route costs.
• Collects Structured Results: Stores all performance data (language, heuristic, problem scale, instance details, execution time, and total cost) in standardized CSV files for easy aggregation and analysis.
• Compares Performance: Allows for direct, side-by-side comparison of how each language and heuristic performs under different computational loads, highlighting their strengths and weaknesses.

Why is This Project Relevance to Supply Chain Management

This project is highly relevant to modern supply chain and logistics operations due to several key factors:

• Optimizing Real-World Logistics: The Vehicle Routing Problem is a cornerstone of transportation and distribution. Efficiently solving it directly translates to reduced fuel costs, optimized delivery times, improved customer satisfaction, and lower operational expenses for businesses.
• Addressing Computational Complexity: Many SCM optimization problems are NP-hard, meaning they become exponentially harder to solve as problem size increases. This project demonstrates how different languages handle this inherent computational intensity.
• Informing Technology Decisions: In enterprise-level SCM systems, choosing the right technology stack for performance-critical components is vital. This benchmark provides empirical evidence to guide decisions on when to use a high-productivity language like Python for prototyping vs. a high-performance language like C++, Rust, or Julia for production-grade algorithms.
• Resource Management: Understanding memory usage and CPU efficiency is crucial for deploying scalable SCM solutions, whether on cloud infrastructure or embedded systems.
• Algorithm Validation: By implementing the same algorithms across multiple languages, the project implicitly validates the correctness and consistency of the heuristic logic.

4. Algorithms Explained

Capacitated Vehicle Routing Problem (CVRP)

The CVRP is a classic optimization problem where a fleet of vehicles with limited capacity must serve a set of customers with known demands, starting and ending at a central depot. The objective is typically to minimize the total travel distance of all vehicles while ensuring all customer demands are met and vehicle capacities are not exceeded.

Nearest Neighbor Heuristic

• Concept: A greedy approach where a vehicle always travels to the closest unvisited customer it can serve (within capacity). It's simple and fast.

• Process:

  1. Start a vehicle at the depot.
  2. From the current location, find the closest unvisited customer whose demand fits the vehicle's remaining capacity.
  3. Travel to that customer, update load, and mark as visited.
  4. Repeat from the new customer's location.
  5. If no more customers can be served, the vehicle returns to the depot.
  6. Dispatch a new vehicle if unvisited customers remain.

  Savings Heuristic (Clarke & Wright)

  • Concept: A more sophisticated heuristic that focuses on "saving" distance by merging routes. It starts with individual routes for each customer and iteratively combines them.

  • Process:

    1. **Initialize: Each customer is served by its own route: **<span class="selected">Depot -> Customer i -> Depot</span>.
    2. Calculate Savings: For every pair of customers (i, j), calculate the distance saved by connecting them directly (<span class="selected">d(Depot, i) + d(j, Depot) - d(i, j)</span>).
    3. Sort Savings: Sort all potential savings in descending order.
    4. **Merge Routes: Iterate through sorted savings. If two routes can be merged (customer **<span class="selected">i</span> is at the end of its route, <span class="selected">j</span> is at the start of its route, and capacity isn't exceeded), combine them.
    5. Repeat until no more valid merges can be made.

    Why Benchmarking These Algorithms Matters

    • Practicality for NP-Hard Problems: CVRP is NP-hard. Heuristics offer "good enough" solutions in reasonable time, a crucial trade-off for real-world operations.
    • Operational Impact: Faster and better routes reduce costs (fuel, labor) and improve efficiency and responsiveness in logistics.
    • Scalability Assessment: Benchmarking across various data sizes reveals how execution time grows, informing system scalability.

    How Execution Time is Measured

    Execution time (in milliseconds) is captured using high-resolution timers native to each language (<span class="selected">time.perf_counter()</span> in Python, <span class="selected">std::chrono</span> in C++, <span class="selected">std::time::Instant</span> in Rust, <span class="selected">Dates.now()</span> in Julia). Timing starts just before the algorithm's core logic and ends immediately after, excluding file I/O or result formatting. This ensures a pure comparison of algorithmic computation speed.

  5. Supported Languages

  This project includes implementations and benchmarks for:

  • Python: For rapid prototyping, data generation, and a high-level scripting baseline.
  • C++: For low-level control, maximum performance, and a strong comparison point for system-level efficiency.
  • Rust: For high performance, memory safety, and modern systems programming practices.
  • Julia: For high-performance scientific and numerical computing, and its "two-language problem" solution potential.

  6. Installation & Setup

  To run this project, you will need the respective language runtimes and compilers installed on your system.

  General Setup

  1. Clone the Repository:

     git clone https://github.com/MD-Zayed-Al-Sajed/Multi-lingual-performance-benchmark-for-Supply-Chain-CVRP-algorithms.git
     cd Multi-lingual-performance-benchmark-for-Supply-Chain-CVRP-algorithms
     
     

  2. Generate Data: All language benchmarks use common data generated by Python.

     python scripts/generate_cvrp_data.py
     
     

     **This will create **<span class="selected">*.txt</span> files in the <span class="selected">data/small</span>, <span class="selected">data/medium</span>, and <span class="selected">data/large</span> subdirectories.

  Language-Specific Setup

  Python

  • Installation:Python 3.x
  • Dependencies:

    pip install pandas
    
    

  C++

  • Compiler: A C++17 compatible compiler (e.g., GCC/G++ via MinGW-w64 on Windows or MSYS2, Clang on macOS/Linux). Ensure <span class="selected">g++</span> is in your system's PATH.

  Rust

  • Installation: Follow instructions on Rustup.rs. Install the <span class="selected">x86_64-pc-windows-gnu</span> toolchain if on Windows with MinGW/MSYS2:

    curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
    # During installation, choose option 2 (customize), then select `x86_64-pc-windows-gnu` for the default host triple.
    
    

  • Dependencies: Managed by <span class="selected">Cargo.toml</span>. Run <span class="selected">cargo build</span> within <span class="selected">rust_impl</span> to download.

  Julia

  • Installation: Download installer from JuliaLang.org. Ensure <span class="selected">julia</span> executable is in your system's PATH.
  • Dependencies: Managed by <span class="selected">Project.toml</span> and <span class="selected">Manifest.toml</span>.
    1. **Navigate to **<span class="selected">julia_impl</span> directory.
    2. Open Julia REPL (<span class="selected">julia</span>).
    3. In Pkg mode (<span class="selected">]</span>):

       (v1.x) pkg> activate .
       (cvrp_benchmark) pkg> add CSV DataFrames LinearAlgebra Statistics Dates Printf
       (cvrp_benchmark) pkg> precompile
       
       

  7. How to Run the Benchmarks

  **All benchmark results will be saved as CSV files in the **<span class="selected">results/</span> directory (created automatically).

  Python Benchmark

  From the project root:

  python python_impl/run_python_benchmark.py
  
  

  C++ Benchmark

  From the project root:

  1. Compile: Navigate to the <span class="selected">cpp_impl</span> directory in your terminal.

     cd cpp_impl
     g++ -c cvrp_structs.h # Might not be needed directly depending on includes
     g++ -c cvrp_utils.cpp -o cvrp_utils.o -std=c++17 -Wall
     g++ -c cvrp_heuristics.cpp -o cvrp_heuristics.o -std=c++17 -Wall
     g++ -c main.cpp -o main.o -std=c++17 -Wall
     g++ main.o cvrp_utils.o cvrp_heuristics.o -o cvrp_benchmark_cpp.exe -std=c++17
     
     

  2. Run:

     ./cvrp_benchmark_cpp.exe
     
     

     **(Or **<span class="selected">.\cvrp_benchmark_cpp.exe</span> on Windows PowerShell/CMD)

  Rust Benchmark

  **From the **<span class="selected">rust_impl</span> directory:

  cd rust_impl
  cargo run --release
  
  

  Julia Benchmark

  **From the **<span class="selected">julia_impl</span> directory:

  1. Open Julia REPL (<span class="selected">julia</span>).
  2. In the REPL:

     julia> include("run_julia_benchmark.jl")
     julia> run_benchmark()
     
     

  8. Project Structure

  cvrp_benchmark/
  ├── data/                       # Stores generated CVRP instance files (small, medium, large)
  ├── python_impl/                # Python implementations
  │   ├── cvrp_solver.py          # Data structures, parsing, and heuristic logic
  │   └── run_python_benchmark.py # Script to run benchmarks and collect results
  ├── cpp_impl/                   # C++ implementations
  │   ├── cvrp_structs.h          # C++ data structures
  │   ├── cvrp_utils.h/.cpp       # C++ utility functions (distance, parsing)
  │   ├── cvrp_heuristics.h/.cpp  # C++ heuristic implementations (Nearest Neighbor, Savings)
  │   └── main.cpp                # C++ benchmark runner and main executable
  ├── rust_impl/                  # Rust implementations
  │   ├── Cargo.toml              # Rust project manifest
  │   ├── src/                    # Rust source files
  │   │   ├── lib.rs              # Data structures, parsing, and heuristic logic (library)
  │   │   └── main.rs             # Benchmark runner (binary)
  │   └── (target/, Cargo.lock)   # Generated by Cargo
  ├── julia_impl/                 # Julia implementations
  │   ├── Project.toml            # Julia project manifest
  │   ├── Manifest.toml           # Julia package versions (generated)
  │   ├── run_julia_benchmark.jl  # Script to run benchmarks
  │   └── src/                    # Julia source files
  │       └── CVRPBenchmarks.jl   # Julia module with data structures, parsing, and heuristics
  ├── results/                    # Directory to store all benchmark CSV results
  ├── scripts/                    # General utility scripts
  │   └── generate_cvrp_data.py   # Script to generate CVRP instance data
  └── README.md                   # This file
  
  

  9. Results & Analysis

  **After running all benchmarks, the **<span class="selected">results/</span> directory will contain:

  • <span class="selected">python_benchmark_results.csv</span>
  • <span class="selected">cpp_benchmark_results.csv</span>
  • <span class="selected">rust_benchmark_results.csv</span>
  • <span class="selected">julia_benchmark_results.csv</span>

  (Future Update: This section will include detailed plots and interpretations of the performance data, comparing execution times and solution quality across languages and heuristics.)

This project demonstrates a diverse and highly valuable skill set that is directly applicable to roles in software development, data science, operations research, and supply chain technology.

project showcases:

• Full-Stack Development Mindset (Conceptual): Covers data generation (input), core logic implementation (processing), and results analysis (output).
• Multi-Language Proficiency: Hands-on experience and adaptability in Python, C++, Rust, and Julia. A rare and highly sought-after combination.
• Performance Engineering: Explicitly focuses on benchmarking and optimizing code for speed and efficiency, a critical skill for high-throughput systems.
• Algorithmic Understanding: Proves a solid grasp of complex optimization algorithms (CVRP heuristics) and the ability to translate theoretical concepts into practical code.
• Problem-Solving & Debugging: The iterative process of building and debugging across multiple languages (especially with subtle parsing issues) highlights strong analytical and troubleshooting capabilities.
• Software Development Best Practices: Adherence to modular design, clear code organization, and systematic testing.
• Data Analysis & Visualization: Ability to collect raw data, process it (using tools like Pandas in Python), and present insights through structured results (CSV) and implied visualizations.
• Attention to Detail: The need for precise parsing across different language environments demonstrates meticulousness.
• Domain Knowledge: Directly applicable experience in supply chain optimization, a rapidly growing field.

This project goes far beyond simple algorithm implementation, showcasing capable of tackling complex, interdisciplinary technical challenges in performance-critical domains.

License

**This project is open-sourced under the **MIT License.

Contributions are welcome! If you find issues or have improvements, feel free to open a pull request.