面向梯形箱子的三维装箱问题算法研究

针对梯形箱子的三维装箱问题,提出了一种基于空间分割的构造性启发式算法,根据梯形箱子三维装箱问题的特点,设计了相应的空间分割策略、空间合并策略与空间重组策略,在此基础上加入遗传算法,提高算法局部与全局搜索能力。实验结果表明,该算法能有效处理梯形箱子三维装箱问题。     

A greedy search for the three-dimensional bin packing problem: the packing static stability case

We suggest a greedy search heuristic for solving the three-dimensional bin packing problem (3D-BPP) where in addition to the usual requirement of minimum amount of bins being used, the resulting packing of items into the bins must be physically stable. The problem is NP-hard in the strong sense and imposes severe computational strain for solving it in practice. Computational experiments are also presented and the results are compared with those obtained by the Martello, Pisinger and Vigo (2000) heuristic.     

A new variable-sized bin packing problem

The problem of BLASTing a genome against a database of DNA sequences to identify potential relationships with other genomes can be divided into subproblems quite naturally. We consider a setting where the problem is distributed to PCs having idle time. This results in a new variant of bin packing, where a rectangle is divided into smaller rectangles that are to be packed in variable-sized bins which arrive on-line. A rectangle fits in a bin, if the sum of its height and width is no more than the size of the bin. The goal is to minimize the total size of the bins used for packing the entire rectangle.     

Approximation algorithms for a hierarchically structured bin packing problem

In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size.     

Comments on the hierarchically structured bin packing problem

We study the hierarchically structured bin packing problem. In this problem, the items to be packed into bins are at the leaves of a tree. The objective of the packing is to minimize the total number of bins into which the descendants of an internal node are packed, summed over all internal nodes. We investigate an existing algorithm and make a correction to the analysis of its approximation ratio. Further results regarding the structure of an optimal solution and a strengthened inapproximability result are given.     

Solving the one-dimensional bin packing problem with a weight annealing heuristic

In this paper, we develop a new procedure that uses the concept of weight annealing to solve the one-dimensional bin packing problem. Our procedure is straightforward and easy to follow. We apply it to 1587 instances taken from benchmark problem sets and compare our results to those found in the literature. We find that our procedure produces very high-quality solutions very quickly and generates several new optimal solutions.     

Two-dimensional on-line bin packing problem with rotatable items

In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is “rotatable” by $\text{90°}$. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.     

Solving the variable size bin packing problem with discretized formulations

In this paper we study the use of a discretized formulation for solving the variable size bin packing problem (VSBPP). The VSBPP is a generalization of the bin packing problem where bins of different capacities (and different costs) are available for packing a set of items. The objective is to pack all the items minimizing the total cost associated with the bins. We start by presenting a straightforward integer programming formulation to the problem and later on, propose a less straightforward formulation obtained by using a so-called discretized model reformulation technique proposed for other problems (see [Gouveia L. A 2n constraint formulation for the capacitated minimal spanning tree problem. Operations Research 1995; 43:130–141; Gouveia L, Saldanha-da-Gama F. On the capacitated concentrator location problem: a reformulation by discretization. Computers and Operations Research 2006; 33:1242–1258]). New valid inequalities suggested by the variables of the discretized model are also proposed to strengthen the original linear relaxation bounds. Computational results (see Section 4) with up to 1000 items show that these valid inequalities not only enhance the linear programming relaxation bound but may also be extremely helpful when using a commercial package for solving optimally VSBPP.     

Using genetic algorithms to solve quality-related bin packing problem

The Bin Packing Problem is an industrial problem which involves grouping items into appropriate bin to minimize the cost and number of used bins. It provides a solution for assigning parts to optimize some predefined measures of productivity. In this study, Ion Plating (IP) industry requires similar approach on allocating production jobs into batches for producing better quality products and enabling to meet customer deadlines. The aim of this paper is to (i) develop a Bin Packing Genetic Algorithms (BPGA) with different weighting combinations, taking into account the quality of product and service; (ii) improve the production efficiency by reducing the production unit cost in IP. Genetic Algorithm was chosen because it is one of the best heuristics algorithms on solving optimization problems. In the case studies, industrial data of a precious metal finishing company was used to simulate the proposed BPGA model, and the computational results were compared with these industrial data. The results from three different weighting combinations demonstrated that fewer resources would be required by applying the proposed model in solving BP problem in the Ion Plating Cell.     

Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts

This paper deals with the two-dimensional bin packing problem with conflicts (BPC-2D). Given a finite set of rectangular items, an unlimited number of rectangular bins and a conflict graph, the goal is to find a conflict-free packing of the items minimizing the number of bins used. In this paper, we propose a new framework based on a tree-decomposition for solving this problem. It proceeds by decomposing a BPC-2D instance into subproblems to be solved independently. Applying this decomposition method is not straightforward, since merging partial solutions is hard. Several heuristic strategies are proposed to make an effective use of the decomposition. Computational experiments show the practical effectiveness of our approach.     

Optimal multi-dimensional vector bin packing using simulated evolution

The use of the evolutionary heuristic simulated evolution for the optimization of the multi-dimensional vector bin packing problem, which is encountered in several industrial applications, is described. These applications range from production planning and steel fabrication to assignment of virtual machines (VMs) onto physical hosts at cloud-based data centers. The dimensions of VMs can include demands of CPU, memory, bandwidth, disk space etc. The generalized goodness functions that aid traversing the search space in an intelligent manner are designed to cater to the multidimensional nature of items (VMs). The efficiency of heuristics is tested by considering phase transition in the generation of difficult test cases. The quality of the heuristics is judged by determining how close the solution is to the estimated lower bound. A new implementation of a tighter lower bound is proposed. Experiments show that superior quality results are obtained by employing the proposed strategy.     

Efficient algorithms for real-life instances of the variable size bin packing problem

In this paper we present a local search heuristic for real-life instances of the variable size bin packing problem, and an exact algorithm for small instances. One important issue our heuristic is able to satisfy is that solutions must be delivered within (milli)seconds and that the solution methods should be robust to last minute changes in the data. Furthermore we show that we are able to incorporate the concept of usable leftovers on a single bin, and the implementation of many additional constraints should be supported by the straightforward solution representation. The heuristic is compared to others from the literature, and comes out ahead on a large subset of the instances.     

受位置约束的有色装箱问题

作为对有色装箱问题的推广,提出了一种受位置约束的有色装箱问题（longest item at the bottom coloring bin packing problem,LIBCBPP）,即在有色物品的装箱过程中,要求重（长）的物品置于轻（短）的物品下方.该问题在任务调度和日常生活中的运输等问题中有着广泛的应用背景.给出了一个求解该问题的近似KC-LIBFF算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.     

A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts

A new heuristic algorithm for solving the two-dimensional bin-packing problem with guillotine cuts (2DBP|?|G)$(2\mathrm{DBP}|?|\mathrm{G})$ is presented. The heuristic constructs a solution by packing a bin at a time. Central to the adopted solution scheme is the principle of average-area sufficiency proposed by the authors for guiding selection of items to fill a bin. The algorithm is tested on a set of standard benchmark problem instances and compared with existing heuristics producing the best-known results. The results presented attest to the efficacy of the proposed scheme.     

有卸货顺序约束的集装箱装载问题及算法研究

对有卸货顺序约束的三维集装箱问题进行了描述.基于禁忌规则,采用了求解该问题的模拟退火算法,设计了货物的摆放规则和序列生成方式.采用3种邻域,根据邻域的不同,构造了2种禁忌表.根据问题的特点,在模拟退火算法抽样过程中加入了禁忌规则.介绍了算法的原理,给出了具有代表性算例试验结果并且进行了分析.试验结果表明,提出的混合算法对有卸货顺序约束的集装箱三维装载问题的有效性.     

Efficient lower bounds and heuristics for the variable cost and size bin packing problem

We consider the variable cost and size bin packing problem, a generalization of the well-known bin packing problem, where a set of items must be packed into a set of heterogeneous bins characterized by possibly different volumes and fixed selection costs. The objective of the problem is to select bins to pack all items at minimum total bin-selection cost. The paper introduces lower bounds and heuristics for the problem, the latter integrating lower and upper bound techniques. Extensive numerical tests conducted on instances with up to 1000 items show the effectiveness of these methods in terms of computational effort and solution quality. We also provide a systematic numerical analysis of the impact on solution quality of the bin selection costs and the correlations between these and the bin volumes. The results show that these correlations matter and that solution methods that are un-biased toward particular correlation values perform better.