Nature inspired genetic algorithms for hard packing problems

This paper presents two novel genetic algorithms (GAs) for hard industrially relevant packing problems. The design of both algorithms is inspired by aspects of molecular genetics, in particular, the modular exon-intron structure of eukaryotic genes. Two representative packing problems are used to test the utility of the proposed approach: the bin packing problem (BPP) and the multiple knapsack problem (MKP). The algorithm for the BPP, the exon shuffling GA (ESGA), is a steady-state GA with a sophisticated crossover operator that makes maximum use of the principle of natural selection to evolve feasible solutions with no explicit verification of constraint violations. The second algorithm, the Exonic GA (ExGA), implements an RNA inspired adaptive repair function necessary for the highly constrained MKP. Three different variants of this algorithm are presented and compared, which evolve a partial ordering of items using a segmented encoding that is utilised in the repair of infeasible solutions. All algorithms are tested on a range of benchmark problems, and the results indicate a very high degree of accuracy and reliability compared to other approaches in the literature.     

基于支配强度的NSGA Ⅱ改进算法在研究生招生面试分组中的应用

针对研究生招生面试分组这一NP难问题,提出了一种以分组遗传算法(GGA)和基于支配强度的改进NSGA Ⅱ算法为基础的混合多目标分组遗传算法。通过基于矩阵编码的多交叉/多变异算子、次精英化的初始化种群策略以及改进的帕累托支配关系,解决了经典NSGA Ⅱ算法在该问题中的收敛速度慢、易陷入局部最优的问题。仿真实验结果表明,该方法只需进行较少代数(不超过100代)的进化,即可获得最优解集,满足了快速分组的用户偏好。     

A heuristic for solving large bin packing problems in two and three dimensions

The more-dimensional bin packing problem (BPP) considered here requires packing a set of rectangular-shaped items into a minimum number of identical rectangular-shaped bins. All items may be rotated and the guillotine cut constraint has to be respected. A straightforward heuristic is presented that is based on a method for the container loading problem following a wall-building approach and on a method for the one-dimensional BPP. 1,800 new benchmark instances are introduced for the two-dimensional and three-dimensional BPP. The instances include more than 1,500 items on average. Applied to these very large instances, the heuristic generates solutions of acceptable quality in short computation times. Moreover, the influence of different instance parameters on the solution quality is investigated by an extended computational study.     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

In this paper we consider a variation of the bin packing problem in which bins of different types have different costs and capacities. Furthermore, each bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size bin packing problem.     

A note on the minimum bounded edge-partition of a tree

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of ‘balanced trees’ common for the stochastic programming application which motivated investigation of this problem.Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used.     

On solving multiobjective bin packing problems using evolutionary particle swarm optimization

The bin packing problem is widely found in applications such as loading of tractor trailer trucks, cargo airplanes and ships, where a balanced load provides better fuel efficiency and safer ride. In these applications, there are often conflicting criteria to be satisfied, i.e., to minimize the bins used and to balance the load of each bin, subject to a number of practical constraints. Unlike existing studies that only consider the issue of minimum bins, a multiobjective two-dimensional mathematical model for bin packing problems with multiple constraints (MOBPP-2D) is formulated in this paper. To solve MOBPP-2D problems, a multiobjective evolutionary particle swarm optimization algorithm (MOEPSO) is proposed. Without the need of combining both objectives into a composite scalar weighting function, MOEPSO incorporates the concept of Pareto’s optimality to evolve a family of solutions along the trade-off surface. Extensive numerical investigations are performed on various test instances, and their performances are compared both quantitatively and statistically with other optimization methods to illustrate the effectiveness and efficiency of MOEPSO in solving multiobjective bin packing problems.     

A hybrid heuristic algorithm for the 2D variable-sized bin packing problem

In this paper, we consider the two-dimensional variable-sized bin packing problem (2DVSBPP) with guillotine constraint. 2DVSBPP is a well-known NP-hard optimization problem which has several real applications. A mixed bin packing algorithm (MixPacking) which combines a heuristic packing algorithm with the Best Fit algorithm is proposed to solve the single bin problem, and then a backtracking algorithm which embeds MixPacking is developed to solve the 2DVSBPP. A hybrid heuristic algorithm based on iterative simulated annealing and binary search (named HHA) is then developed to further improve the results of our Backtracking algorithm. Computational experiments on the benchmark instances for 2DVSBPP show that HHA has achieved good results and outperforms existing algorithms.     

Hybrid algorithm for the two-dimensional rectangular layer-packing problem

In this paper, a rectangular layer-packing algorithm (RLPA) combined with modified genetic algorithm (GA) or particle swarm optimization (PSO) algorithm is developed to solve the problem with emerging restraints, which is raised from the two-dimensional rectangular packing problem with some small rectangles that need to be packed into a fixed rectangular object. RLPA is designed from the BL algorithm and lowest horizontal line algorithm. GA and PSO are also modified to satisfy the constraint conditions. Best GA or PSO parameters are obtained by conducting experiments on some typical instances. The results are also compared, which validate the quality of the solutions and show the effectiveness of the modified algorithm.     

Multiple-type,two-dimensional bin packing problems: Applications and algorithms

In this paper we consider a class of bin selection and packing problems (BPP) in which potential bins are of various types, have two resource constraints, and the resource requirement for each object differs for each bin type. The problem is to select bins and assign the objects to bins so as to minimize the sum of bin costs while meeting the two resource constraints. This problem represents an extension of the classical two-dimensional BPP in which bins are homogeneous. Typical applications of this research include computer storage device selection with file assignment, robot selection with work station assignment, and computer processor selection with task assignment. Three solution algorithms have been developed and tested: a simple greedy heuristic, a method based onsimulated annealing (SA) and an exact algorithm based onColumn Generation with Branch and Bound (CG). An LP-based method for generating tight lower bounds was also developed (LB). Several hundred test problems based on computer storage device selection and file assignment were generated and solved. The heuristic solved problems up to 100 objects in less than a second; average solution value was within about 3% of the optimum. SA improved solutions to an average gap of less than 1% but a significant increase in computing time. LB produced average lower bounds within 3% of optimum within a few seconds. CG is practical for small to moderately-sized problems — possibly as many as 50 objects.     

Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios. The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its deterministic counterpart. Furthermore, we show that common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be adapted to obtain these results.     

约束装箱问题的混合遗传算法求解

本将最佳适应法和遗传算法相结合，提出了一种新的启发式混合遗传算法对具有时间约束的装箱问题进行求解，给出了具体的算法步骤，试算结果表明基于启发式算法的混合遗传算法适合于求解各种约束条件下的大规模装箱问题。     

A hybrid genetic algorithmic approach to the maximally diverse grouping problem

The maximally diverse grouping problem (MDGP) is a NP-complete problem. For such NP-complete problems, heuristics play a major role in searching for solutions. Most of the heuristics for MDGP focus on the equal group-size situation. In this paper, we develop a genetic algorithm (GA)-based hybrid heuristic to solve this problem considering not only the equal group-size situation but also the different group-size situation. The performance of the algorithm is compared with the established Lotfi–Cerveny–Weitz algorithm and the non-hybrid GA. Computational experience indicates that the proposed GA-based hybrid algorithm is a good tool for solving MDGP. Moreover, it can be easily modified to solve other equivalent problems.     

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing

The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.     

Three-dimensional bin packing problem with variable bin height

This paper studies a variant of the three-dimensional bin packing problem (3D-BPP), where the bin height can be adjusted to the cartons it packs. The bins and cartons to be packed are assumed rectangular in shape. The cartons are allowed to be rotated into any one of the six positions that keep the carton edges parallel to the bin edges. This greatly increases the difficulty of finding a good solution since the search space expands significantly comparing to the 3D-BPP where the cartons have fixed orientations. A mathematical (mixed integer programming) approach is modified based on [Chen, C. S., Lee, S. M., Shen, Q. S., 1995. An analytical model for the container loading problem. European Journal of Operational Research 80 (1), 68–76] and numerical experiments indicate that the mathematical approach is not suitable for the variable bin height 3D-BPP. A special bin packing algorithm based on packing index is designed to utilize the special problem feature and is used as a building block for a genetic algorithm designed for the 3D-BPP. The paper also investigates the situation where more than one type of bin are used and provides a heuristic for packing a batch of cartons using the genetic algorithm. Numerical experiments show that our proposed method yields quick and satisfactory results when benchmarked against the actual packing practice and the MIP model with the latest version of CPLEX.     

Fuzzy bin packing problem

This paper deals with the fuzzy bin packing problem that is a packing problem of non-rigid rectangles into an open rectangular bin. This problem is different from the conventional bin packing problem, which considers only rigid rectangles. The goal of the fuzzy bin packing problem is to minimize both the height of a packing and the extra cost due to the reduction of each piece. The total cost of the problem is represented as the sum of the height cost and the extra cost due to reductions of the pieces, which is called reduction cost. Because the conventional bin packing problem itself is an NP-hard problem, the presented optimization method assumes that an initial packing for non-reduced pieces has already been found. A closed form solution is presented for fuzzy bin packing problems, in which fuzzy numbers are triangular and the reduction cost is given by a quadratic function.     

基于粒子群算法的非线性二层规划问题的求解算法

粒子群算法（Particle Swarm Optimization，PSO）是一种新兴的优化技术，其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现，可调参数少，已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点，对非线性二层规划的上下层问题求解，并根据二层规划的特点，给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。     

Fast algorithms for fragmentable items bin packing

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92 % of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99 % of all 4500 runs. No run lasted longer than 220 ms.     

Local Search Algorithms for the Bin Packing Problem and Their Relationships to Various Construction Heuristics

The tradeoff between the speed and quality of the solutions obtained by various construction and local search algorithms for the elementary bin packing problem (BPP) are analyzed to obtain useful information for designing algorithms for real-world problems that can be modeled as BPPs. On the basis of intensive computational experiments, we observe that the framework of a solution (i.e., a part of a solution consisting of large items or items with tight constraints) should be constructed in the early stages of a local search. New local search algorithms are proposed as empirical support for the observation.     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.