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

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

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.     

On the generalized bin packing problem

The generalized bin packing problem (GBPP) is a novel packing problem arising in many transportation and logistic settings, characterized by multiple items and bins attributes and the presence of both compulsory and non‐compulsory items. In this paper, we study the computational complexity and the approximability of the GBPP. We prove that the GBPP cannot be approximated by any constant, unless . We also study the particular case of a single bin type and show that when an unlimited number of bins is available, the GBPP can be reduced to the bin packing with rejection (BPR) problem, which is approximable. We also prove that the GBPP satisfies Bellman's optimality principle and, exploiting this result, we develop a dynamic programming solution approach. Finally, we study the behavior of standard and widespread heuristics such as the first fit, best fit, first fit decreasing, and best fit decreasing. We show that while they successfully approximate previous versions of bin packing problems, they fail to approximate the GBPP.     

一种新的多约束尺寸可变的装箱问题

多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数,还引入了物品类型、箱子类型等参数,建立了数学模型,将经典的FFD（First Fit Decreasing）算法进行了推广,提出了新的算法MFFD,并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,MFFD算法效果较好。     

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.     

An analysis of lower bound procedures for the bin packing problem

In this paper, we review LB2 and LB3, two lower bounds for the bin packing problem that were respectively introduced by Martello and Toth and by Labbé, Laporte and Mercure. We prove that LB3⩾LB2. We also prove that the worst-case asymptotic performance ratio of LB3 is $\text{3}\text{4}$ and that this ratio cannot be improved. We study LB2, LB3 and three of their variants both analytically and computationally. In particular, we clarify the relationships between LB2″, the bound implemented by Martello and Toth in their well-known bin packing code, and both LB2 and LB3.     

二维离线非旋转装箱问题的一个混合算法

针对二维离线非旋转装箱问题,在凹角和适应值的思想的基础上,提出了一个改进型的Best-Fit启发式算法,并结合基于自然数编码的遗传算法构建了混合算法。同时在遗传迭代过程中,引入二维装箱问题的下界思想作为迭代的终止条件之一,减少了遗传算法无效迭代次数,另外根据问题自身特点,有效地降低了染色体长度,提高了整体的计算速度。在36个标准测试案例的测试基础上与一些经典的算法进行了比较,实验结果表明该算法在工业生产可接受的时间内与其他经典的算法相比能够获得更为满意的结果。     

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.     

A grouping genetic algorithm with controlled gene transmission for the bin packing problem

In this study, the one-dimensional Bin Packing Problem (BPP) is approached. The BPP is a classical optimization problem that is known for its applicability and complexity. We propose a method that is referred to as the Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) for Bin Packing. The proposed algorithm promotes the transmission of the best genes in the chromosomes without losing the balance between the selective pressure and population diversity. The transmission of the best genes is accomplished by means of a new set of grouping genetic operators, while the evolution is balanced with a new reproduction technique that controls the exploration of the search space and prevents premature convergence of the algorithm. The results obtained from an extensive computational study confirm that (1) promoting the transmission of the best genes improves the performance of each grouping genetic operator; (2) adding intelligence to the packing and rearrangement heuristics enhances the performance of a GGA; (3) controlling selective pressure and population diversity tends to lead to higher effectiveness; and (4) GGA-CGT is comparable to the best state-of-the-art algorithms, outperforming the published results for the class of instances Hard28, which appears to have the greatest degree of difficulty for BPP algorithms.