Multi-period bin packing model and effective constructive heuristics for corridor-based logistics capacity planning

The bin packing problem is one of the most studied combinatorial optimization problem. This paper proposes two novel bin packing problem settings with many practical applications, in particular in logistics capacity planning. Both problems explicitly consider, besides the classical bin-selection costs, the item and bin-specific item-to-bin assignment costs. These assignment costs depend not only on the physical, e.g., item and bin size, and economic, e.g., bin selection fixed cost and the cost of item "transport" by the bin, but also on the temporal attributes of items and bins, e.g., availability of regular bins for selection and utilization and of items to be assigned to such a regular bin. Special, item-specific in terms of size, spot-market bins may be used at higher cost for the items one cannot fit into the selected bins. Single and a multi-period formulations are proposed, both aiming to minimize the total cost of the system computed as the sum of the fixed costs of the selected bins and the total item-to-bin assignment cost using regular and spot-market bins. The multi-period formulation optimizes the cost over all the time periods considered. Several constructive heuristics are proposed, three for the single-period model, and four for the multi-period formulation. The heuristics are evaluated and compared through an extensive computational experimentation. The numerical results show the high level of performance of the proposed heuristics in terms of solution quality and computational efficiency, as well as the potential benefits of using the new models in practical applications.

装箱问题是研究最多的组合优化问题之一。本文提出了两种具有许多实际应用的新型装箱问题设定，特别是在物流能力规划方面。这两个问题除了经典的箱子选择成本外，还明确考虑了物品以及特定箱子与物品到箱子的分配成本。这些分配成本不仅取决于物理属性，例如物品和箱子的大小，以及经济属性，例如箱子选择的固定成本和箱子运输物品的成本，还取决于物品和箱子的时间属性，例如可供选择和使用的常规箱子的可用性以及要分配到此类常规箱子的物品的可用性。对于无法装入所选箱子的物品，可以使用特殊的、在尺寸方面特定于物品的现货市场箱子，但成本较高。提出了单周期和多周期的公式，两者都旨在最小化系统的总成本，该总成本计算为所选箱子的固定成本之和以及使用常规箱子和现货市场箱子的物品到箱子的总分配成本。多周期公式在考虑的所有时间段内优化成本。提出了几种构造性启发式算法，单周期模型有三种，多周期公式有四种。通过广泛的计算实验对启发式算法进行了评估和比较。数值结果表明，所提出的启发式算法在解的质量和计算效率方面具有较高的性能，以及在实际应用中使用新模型的潜在益处。