🚛 Transportation Problem Solver (C)

This repository contains a complete implementation in C of Operations Research algorithms to solve the Transportation Problem.

The project minimizes transportation costs between multiple sources (factories) and destinations (stores) using both heuristic and exact methods. It includes an interactive solver and a benchmarking module for complexity analysis.

---

🚀 Features

Implemented Algorithms

Initial Solutions

• 📐 North-West Corner Method: Basic and fast initial solution.
• 🔨 Balas-Hammer (Vogel's Approximation Method): Penalty-based (regret-based) method providing a better starting solution.

Optimization

• 👣 Stepping Stone Method: Exact algorithm using potentials (uᵢ, vⱼ) and reduced costs to reach the global optimum.

---

🛠️ Technical Characteristics

• Degeneracy Handling: Automatic detection and correction using artificial basic variables (ε).
• Graph Theory: Connectivity verification of the basic feasible solution using Breadth-First Search (BFS).
• Cycle Detection: Recursive Depth-First Search (DFS) algorithm to identify improvement cycles during pivot operations.
• Detailed Logs: Generation of trace files (trace_t_X.txt) containing all computation steps (matrices, pivots, costs).

---

📂 Project Structure

• projet_transports.c : Main Program
  Interactive solver allowing users to load files, choose the algorithm, and visualize steps one by one.

• comple.c : Benchmark Module
  Generates random N × N transportation problems to compare CPU performance between North-West and Balas-Hammer methods.

• recherche_ope.txt : Example file containing multiple problem instances.

• trace_*.txt : Log files generated during execution.

---

🛠️ Installation and Compilation

The project requires no external libraries beyond the standard C library.

1️⃣ Compile the Interactive Solver

gcc projet_transports.c -o solver

2️⃣ Compile the Benchmark Module

gcc comple.c -o benchmark

---

▶️ Usage

Run the Solver

./solver

Run the Benchmark

./benchmark

---

📊 Purpose

This project is designed for educational purposes in Operations Research and algorithm analysis.
It demonstrates:

• Construction of initial feasible solutions
• Optimality testing using potentials
• Cycle detection and pivot improvement
• Algorithmic complexity comparison
• Practical implementation of graph traversal techniques

---

📜 License

This project is provided for academic and educational use.