The rack-loading problem consists in placing three-dimensional items in non-stacking, height-adjustable racks under a global height limit while preserving similarity to historical configurations used by operators. We model this setting as a three-dimensional bin-packing variant with fixed rack footprint, variable bin heights, and explicit non-overlap and non-stacking constraints, and solve it with the CP-SAT engine of OR-Tools. Our main contribution is a systematic study of how to select and construct effective hints from historical templates to initialize the solver. We develop a heuristic geometric assignment strategy that chooses the closest template and transfers placements, and a MIP-based assignment framework with Full, Partial, and Critical Assignment policies that trade off guidance and flexibility. A Wasserstein-based similarity measure quantifies how closely solutions mimic historical layouts. Experiments on instances derived from the Hoare and Beasley dataset show that carefully selected hints substantially improve feasibility and runtime on difficult cases, while the geometric strategy yields configurations closest to historical templates.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

From Historical Templates to Hints: Selecting Effective Initializations for the Rack-Loading Problem

  • Thaïs Souyri,
  • Nadia Lahrichi,
  • Louis-Martin Rousseau

摘要

The rack-loading problem consists in placing three-dimensional items in non-stacking, height-adjustable racks under a global height limit while preserving similarity to historical configurations used by operators. We model this setting as a three-dimensional bin-packing variant with fixed rack footprint, variable bin heights, and explicit non-overlap and non-stacking constraints, and solve it with the CP-SAT engine of OR-Tools. Our main contribution is a systematic study of how to select and construct effective hints from historical templates to initialize the solver. We develop a heuristic geometric assignment strategy that chooses the closest template and transfers placements, and a MIP-based assignment framework with Full, Partial, and Critical Assignment policies that trade off guidance and flexibility. A Wasserstein-based similarity measure quantifies how closely solutions mimic historical layouts. Experiments on instances derived from the Hoare and Beasley dataset show that carefully selected hints substantially improve feasibility and runtime on difficult cases, while the geometric strategy yields configurations closest to historical templates.