An Island-Based Parallel Biased Random-Key Genetic Algorithm for the Three-Dimensional Trailer Loading Problem

arXiv:2609.39272v1, submitted on September 30, 2026, by A. del Río, L. Díaz, L. C. de Vicente, J. Cameselle, and B. Fernández, introduces a novel Island-Based Parallel Biased Random-Key Genetic Algorithm (BRKGA) framework named PANGEA to solve the Three-Dimensional Trailer Loading Problem (3D-TLP).

• Problem Context: The 3D-TLP is an NP-hard optimization challenge involving the placement and orientation of heterogeneous items in trailers to maximize volume utilization while satisfying complex logistical and safety constraints.
• Methodology: The approach combines a modified BRKGA with an island-based parallelization strategy where multiple subpopulations evolve independently to promote diversity and reduce premature convergence. It utilizes a nested parallelism architecture: an outer island model for population diversity and an inner master-slave model for distributing the computationally expensive decoding and fitness evaluation across multi-core processors.
• Key Innovations: The chromosome representation was expanded to include genes for Empty Maximal Space (EMS) selection and specific package positioning, allowing the algorithm to explore a broader solution space than previous heuristics.
• Validation Results: Tested on 50 real-world trailer transportation instances (687 packages), the algorithm achieved a 100% feasibility rate for 74% of instances within 200 seconds. Parallel configurations significantly reduced computational time (e.g., <21 seconds for parallel vs. ~44 seconds for the non-parallel baseline) while maintaining high solution quality and robustness across varying migration topologies and island counts.

This material addresses the Three-Dimensional Trailer Loading Problem (3D-TLP), a combinatorial optimization problem in which heterogeneous items must be placed and oriented inside a trailer to maximize volume utilization while satisfying logistical, physical, and safety constraints. Because the problem is NP-hard, exact optimization methods generally become impractical for realistic instance sizes, especially when many items, orientations, stacking rules, and stability or accessibility constraints are present. The paper therefore targets the need for scalable heuristic or metaheuristic methods that can produce high-quality loading plans in computationally meaningful time.

The proposed approach is an island-based parallel biased random-key genetic algorithm. In this framework, each candidate solution is encoded as a set of random keys rather than as an explicit placement plan; a constraint-aware decoding procedure then maps those keys into a concrete trailer layout. This representation allows the genetic algorithm to operate on a simpler continuous or discrete search space while still generating feasible or near-feasible loadings. The “biased” component suggests that the search is guided toward promising regions of the solution space, for example by favoring placements that improve utilization or reduce constraint violations. The island-based parallel structure further improves performance by maintaining multiple subpopulations that explore different regions of the search space, with migration or communication between islands to balance exploration and exploitation.

The work matters because efficient trailer loading has direct operational value in logistics, freight transport, and supply-chain planning, where even modest improvements in volume utilization can reduce transportation costs and increase throughput. More broadly, the paper contributes a practical metaheuristic design for a difficult three-dimensional packing problem: it combines random-key encoding, biasing mechanisms, and parallel island evolution to make the search more tractable for large, constraint-rich instances. For technically oriented readers, the key insight is that decomposing the loading problem into a genotype-to-phenotype decoding step and a distributed evolutionary search can be an effective way to handle the combinatorial complexity and feasibility constraints of real-world 3D trailer loading.