Enhancing Military Load Planning: A Prioritized 2-D Orthogonal Packing Approach

Military combat loading requires arranging equipment on maritime transport vessels to enable rapid, prioritized off-loading while maintaining unit cohesion and vessel stability. Related maritime deck-loading settings can involve similar access, grouping, and balance requirements. This paper extends a prioritized two-dimensional orthogonal packing framework to incorporate global load balancing requirements alongside existing prioritization objectives. We study three solution approaches for this globally constrained problem: a monolithic mixed-integer linear programming (MILP) approach, a sliding-window matheuristic, and a sliding-window matheuristic with in-stride load balancing penalties. For any sliding-window solution that fails to achieve both feasible packing and load balancing in the initial stage, we develop a universal post-processing strategy that selectively relaxes and re-optimizes item positions to achieve balance with minimal disruption to the prioritized layout. Computational experiments demonstrate that the matheuristic approaches fundamentally outperform the monolithic MILP approach in load balance reliability, solution quality, and computational efficiency, providing practical guidance for integrating automated optimization into military load planning systems. Among these, the simpler sliding-window matheuristic followed by post-processing repair emerges as the recommended practical configuration, offering the strongest overall combination of balance success, solution quality, and runtime, while the in-stride variant remains a narrower alternative when direct first-stage balance attainment is paramount. The matheuristic pipelines generate high-quality, load-balanced solutions for single-vessel scenarios within a few minutes on average, enabling rapid evaluation of multiple loading configurations during time-critical deployment planning.