2026-08-27 ノースカロライナ州立大学（NC State）
＜関連情報＞
- https://news.ncsu.edu/2026/08/cracking-the-packing-code-new-models-incorporate-item-priority-location-and-weight-distribution/
- https://www.sciencedirect.com/science/article/pii/S0305048326001271
- https://onlinelibrary.wiley.com/doi/full/10.1002/nav.70087
軍事輸送計画の強化：優先順位付けされた2次元直交パッキングアプローチ Enhancing military load planning: A prioritized 2-D orthogonal packing approach
William K. Kirschenman, H. Sebastian Heese, Michael G. Kay, Russell E. King, Brandon M. McConnell
Omega Available online: 14 August 2026
DOI:https://doi.org/10.1016/j.omega.2026.103638
Abstract
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.
複数の優先順位付けレベルを持つ2次元直交パッキング問題：空間最適化の観点から The 2-D Orthogonal Packing Problem With Multiple Levels of Prioritization: A Spatial Optimization Perspective
William K. Kirschenman, H. Sebastian Heese, Michael G. Kay, Russell E. King, Brandon M. McConnell
Naval Research Logistics Published: 26 July 2026
DOI:https://doi.org/10.1002/nav.70087
ABSTRACT
This paper addresses two-dimensional orthogonal packing within a confined space, integrating bin packing principles with facility layout concepts to address scenarios in which items must not only fit but also be arranged according to spatial priorities. We embed a prioritization matrix into the bin packing framework, enabling items to be clustered with one another or pulled toward certain bin access points based on assigned priority weights. Unlike traditional bin packing, which often minimizes bin count or unused space, our approach balances proximity to bin access points and adjacency among functionally related items already assigned to a given bin, extending the utility of bin packing to applications requiring more nuanced layout preferences. We introduce a single mixed-integer linear programming (MILP) model and a complementary sliding-window matheuristic that scales effectively to larger problem instances. Numerical experiments illustrate that this matheuristic approach consistently outperforms a direct MILP solve with a commercial solver in both runtime and solution quality, and also performs best among the adapted heuristic and metaheuristic alternatives considered in our study. This computational study underscores the flexibility and effectiveness of embedding multilevel priorities into orthogonal packing.
