یک پست تصادفی الگوریتم ژنتیک کلیدی مغرضانه برای مسئله بسته بندی صندوق دو بعدی و سه بعدی

In this paper we present a novel biased random-key genetic algorithm (BRKGA) for 2D and 3D bin packing problems. The approach uses a maximal-space representation to manage the free spaces in the bins. The proposed algorithm hybridizes a novel placement procedure with a genetic algorithm based on random keys. The BRKGA is used to evolve the order in which the boxes are packed into the bins and the parameters used by the placement procedure. Two new placement heuristics are used to determine the bin and the free maximal space where each box is placed. A novel fitness function that improves significantly the solution quality is also developed. The new approach is extensively tested on 858 problem instances and compared with other approaches published in the literature. The computational experiment results demonstrate that the new approach consistently equals or outperforms the other approaches and the statistical analysis confirms that the approach is significantly better than all the other approaches.

The three-dimensional bin packing problem (3D-BPP) consists in packing, with no overlapping, a set of three-dimensional rectangular shaped boxes (items) into the minimum number of three-dimensional rectangular shaped bins (containers). All the bins have identical known dimensions (D,W,H)(D,W,H) and each box i has dimensions (di,wi,hi)(di,wi,hi) for i=1,…,ni=1,…,n. Without loss of generality one can assume that all input data are positive integers and that di≤Ddi≤D, wi≤Wwi≤W, and hi≤Hhi≤H for i=1,…,ni=1,…,n. It is assumed that the boxes can be rotated. Fig. 1 shows an example of a bin packing problem with two bins and more than two hundred boxes. The two-dimensional bin packing problem (2B-BPP) addresses the problem for two-dimensional bins (W,H) and boxes (wi,hi)(wi,hi) and can be treated as a special case of 3D-BPP when di=Ddi=D for i=1,…,ni=1,…,n. According to the typology for cutting and packing problems proposed by Wäscher et al. (2007) bin packing problems can be classified as Single Stock-Size Cutting Stock Problem (SSSCSP) for weakly heterogeneous item sets or as 3D-SBSBPP (3D-Single Bin-Size Bin Packing Problems) for strongly heterogeneous item sets. The bin packing problem addressed in this paper is classified as 3D-SBSBPP (3D-Single Bin-Size Bin Packing Problems). The 2D-BPP and 3D-BPP are strongly NP-hard as they generalize the strongly NP-hard one-dimensional bin packing problem (Martello et al., 2000).Three-dimensional packing problems have numerous relevant industrial applications such as loading cargo into vehicles, containers or pallets, or in packaging design. The 3D-BPP can also arise as a sub-problem of other complex problems not only in packing and cutting but also in some scheduling problems (Park et al., 1996 and Hartmann, 2000). An exact method for the 3D-SBSBPP that uses a two-level Branch & Bound method was proposed by Martello et al. (2000). Initially their proposal only solved robot-packable problems (den Boef et al., 2005), but later it was modified for solving the general problem (Martello et al., 2007). Fekete and Schepers, 1997 and Fekete and Schepers, 2004 define an implicit representation of the packing by means of Interval Graphs (IGs), the Packing Class (PC) representation. The authors consider the relative position of the boxes in a feasible packing and, from the projection of the items on each orthogonal axis, they define a graph describing the overlappings of the items in the container. A new class of lower bounds was introduced by Fekete and Schepers (1997). The authors extend the use of dual feasible functions, first introduced by Johnson (1973), to two- and three-dimensional packing problems, including 3D-SBSBPP. Boschetti (2004) proposed the most recent lower bound, which introduces new dual feasible functions. This new bound dominates previous ones. Boschetti and Mingozzi, 2003a and Boschetti and Mingozzi, 2003b propose new lower bounds for the two-dimensional case. Several constructive and meta-heuristic algorithms have been designed for solving large bin packing problems. Faroe et al. (2003) proposed a Guided Local Search heuristic for 3D-SBSBPP and 2D-SBSBPP, based on the iterative solution of constraint satisfaction problems. Starting with an upper bound on the number of bins obtained by a greedy heuristic, the algorithm iteratively decreases the number of bins, each time searching for a feasible packing of the boxes using the GLS method. Lodi et al., 1999 and Lodi et al., 2002 have developed tabu search algorithms based on new constructive procedures for two-dimensional and three-dimensional cases and in Lodi et al. (2004) propose a unified tabu search code for general multi-dimensional bin packing problems. More recently, Crainic et al. (2009) developed a two-level tabu search algorithm, using the representation proposed for nD-SBSBPP by Fekete and Schepers (2004) and Fekete et al. (2007), in which the first level aims to reduce the number of bins and the second optimizes the packing of the bins. For the two-dimensional bin packing problem (2D-SBSBPP), Boschetti and Mingozzi (2003b) developed an effective constructive heuristic that assigns a score to each box, considers the boxes according to decreasing values of the corresponding scores, updates the scores using a specified criterion, and iterates until either an optimal solution is found or a maximum number of iterations is reached. Monaci and Toth (2006) designed a set-covering-based heuristic approach in which in a first phase a large number of columns are generated by heuristic procedures and by the execution of the exact algorithm by Martello and Vigo (1998) with a time-limit. In the second phase these columns are used for solving a set-covering problem which gives the solution to the original bin packing problem. Parreño et al. (2010) propose a new hybrid GRASP/VND algorithm for solving the 3D-SBSBPP bin packing problem which can also be directly applied to the two-dimensional case (2D-SBSBPP). 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. Mack and Bortfeldt (2012) present a straightforward heuristic for the 3D-SSSCSP where all items may be rotated and the guillotine cut constraint has to be respected. The heuristic is based on a method for the container loading problem following a wall-building approach and on a method for the one-dimensional BPP. 3D-SBSBPP is NP-hard in the strong sense. Therefore, when large instances are considered, heuristics are the methods of choice. In this paper we present a novel biased random-key genetic algorithm (BRKGA) for the 2D-SBSBPP and 3D-SBSBPP. The approach uses a maximal-space representation to manage the free spaces in the bins. The proposed algorithm hybridizes a novel placement procedure with a genetic algorithm based on random keys. The BRKGA is used to evolve the order in which the boxes are packed into the bins and the parameters used by the placement procedure. The remainder of the paper is organized as follows. In Section 2 we introduce the new approach, describing in detail the BRKGA, the novel placement strategy, the novel fitness function, and the parallel implementation. Finally, in Section 3, we report on computational experiments, and in Section 4 make concluding remarks. 2. Biased random-key genetic algorithm We begin this section with an overview of the proposed solution process. This is followed by a discussion of the biased random-key genetic algorithm, including detailed descriptions of the solution encoding and decoding, evolutionary process, fitness function, and parallel implementation

In this paper we addressed the three-dimensional bin packing problem which consists in packing, with no overlapping, a set of three-dimensional rectangular shaped boxes into the minimum number of three-dimensional rectangular shaped bins. All the bins have identical known dimensions and each box i is has dimensions (di,wi,hi)(di,wi,hi) for i=1,…,ni=1,…,n. It is assumed that the boxes can be rotated. A novel biased random-key genetic algorithm (BRKGA) for the 2D-SBSBPP and 3D-SBSBPP was developed. The approach uses a maximal-space representation to manage the free spaces in the bins (Lai and Chan, 1997). The proposed algorithm hybridizes a novel placement procedure with a genetic algorithm based on random keys. The BRKGA is used to evolve the order in which the boxes are packed into the bins and the parameters used by the placement procedure. Two heuristic procedures, DTFTRC-1 and DTFTRC-2, are used to determine the bin and the free maximal space where each box is placed. A novel fitness function that improves significantly the solutions quality is also developed. The new approach is extensively tested on 858 problem instances and compared with other approaches published in the literature. The computational experiments results demonstrate that the new approach consistently equals or outperforms the other approaches and the statistical analysis confirms that the approach is significantly better than all the other approaches.