This project addresses the optimization problem of an assembly line for a factory (based on a FORD case study), seeking the optimal distribution of departments to minimize the cost of material flow. Developed by Carlos Requena Doña and Yessin Mohamed as part of Practice 1 of the Metaheuristics course.
Various optimization techniques are implemented and compared, ranging from constructive heuristics to advanced local search metaheuristics.
🏭 Problem Definition (QAP)
The objective is to assign departments to locations to minimize the quadratic cost function:
Where the goal is to minimize the product of flow () of materials between departments by the distance () between assigned locations.
🧠 Implemented Algorithms
1. Greedy Algorithm
A constructive heuristic that generates a quick initial solution.
- Uses priority queues (Heaps) to sort flows (highest to lowest) and distances (lowest to highest).
- Iteratively assigns departments with the highest flow to the closest available locations.
2. Local Search First-Improvement
Improves the initial solution by exploring the neighborhood through permutations (swap) of two departments.
- Strategy: Accepts the first neighboring solution that improves the current cost.
- DLB (Don’t Look Better): Implementation of a bit vector to optimize the search, marking those departments that have not generated improvements recently to avoid useless re-evaluations.
3. Tabu Search
An advanced metaheuristic that allows escaping local optima by accepting movements that worsen the solution, guided by short and long-term memories.
- Short-Term Memory: Tabu List prohibiting reversing recent moves or repeating visited solutions during a “tabu tenure”.
- Long-Term Memory: Frequency of department assignment to locations to guide diversification/intensification.
- Strategic Oscillation: Alternates between intensification (exploiting promising zones) and diversification (exploring new zones) phases based on frequency memory.
4. Multistart (GRASP)
Combines randomized construction with local search to explore multiple regions of the solution space.
- Constructive Phase: A Randomized Greedy (GRASP) that does not always choose the best option, but one of the best ‘n’ options randomly (RCL - Restricted Candidate List).
- Improvement Phase: Applies Tabu Search to each generated solution, keeping the best global solution found after multiple executions.
🛠️ Architecture and Design
- FileLoader (Singleton): Loading flow and distance matrices from files, allowing problem instances to be changed without recompiling.
- Representation: Integer vector
vwherev[i]is the location of departmenti. - Logging: Detailed logging system to analyze the convergence and behavior of algorithms in each iteration.
Combinatorial optimization project implemented in C++.