-
terminal log
About the Project
Inspiration
The optimization of assembly yard logistics in modern shipbuilding is a critical operational bottleneck. Handling massive hull blocks under spatial, temporal, and crane availability constraints is mathematically equivalent to a highly constrained 3D Packing Problem (2D Space + 1D Time). Our inspiration came from treating time as a physical dimension, mapping the puzzle into a spatial-temporal coordinate system where block scheduling and placement are solved concurrently.
How We Built It
We chose Rust for the core solver to guarantee memory safety, zero-cost abstractions, and maximum execution speed. The optimization pipeline is structured in four sophisticated phases:
- Multi-Start Greedy First-Fit Decreasing (FFD): Starts by sorting blocks based on five physical metrics: Volume \( (W \times D) \), Area, Slack \( (Due - Start - Assembly) \), Weight, and Longest Side.
- Parallel Genetic Algorithm (GA): Evolves block placement permutations using Order Crossover (OX) and mutation operators, running multi-threaded fitness evaluations using
rayon. - Simulated Annealing (SA) with Systematic Fallback: Refines local neighborhoods. Rather than relying entirely on random coordinate selection, which fails in crowded yards, we designed a Systematic First-Fit Fallback search. If random attempts miss a spot, the solver scans the grid step-by-step to guarantee finding a slot.
- Large Neighbourhood Search (LNS): An adaptive destroy-and-repair phase that removes a set of \( k \) blocks and rebuilds the yard layout.
Challenges We Faced
The most significant challenge was the density threshold bottleneck. In tightly packed yards (over 50% capacity), simulated annealing (SA) would get stuck because the probability of finding a valid free slot by pure random coordinate selection was close to zero. If there were 1,000 blocks, it would fail completely.
We overcame this by introducing two key mechanisms:
- A systematic First-Fit fallback grid scan in the SA relocation operators.
- An LNS phase that destroys and re-repairs complex layout configurations.
This hybrid approach pushed our placed block count on the hardest instances from 152 to 178 blocks within a short 30-second budget.
What We Learned
We learned that combining stochastic metaheuristics (SA) with systematic, constructive search (FFD/LNS) is the key to solving NP-hard packing-scheduling problems in highly crowded physical environments.
