A heuristic for the three-dimensional strip packing problem

The contribution presents a heuristic for the three-dimensional strip packing problem (3D-SPP) with rectangular pieces (boxes). The considered 3D-SPP can be formulated as follows: for a given set of boxes and a given longitudinal open container, determine an arrangement of all boxes within the container so that the required container length is minimized.     

A branch-and-price algorithm for the two-dimensional level strip packing problem

The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items.     

Three-stage heuristic algorithm for three-dimensional irregular packing problem

This paper studies a new practical problem which can be decomposed into three three-dimensional packing problems: three-dimensional irregular packing with variable-size cartons problem, three-dimensional variable-size bin packing problem, and the single container loading problem. Since the three sub-problems are NP-hard, searching a good solution becomes more difficult. In this paper, mathematical models of each sub-problem are developed and three-stage heuristic algorithms are proposed to solve this new problem. Experiments are conducted with random instances generated by real-life case. Computational results indicate that the proposed algorithm is efficient and can yield satisfactory results.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.     

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.     

A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

Given a set of rectangular pieces and a container of fixed width and variable length, the two-dimensional strip packing problem (2D-SPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the layout is minimised. Until now mainly heuristics, for example genetic algorithms (GA), were proposed for the 2D-SPP which use encoded solutions that are manipulated by standard operators. In this paper a GA for the 2D-SPP is suggested that works without any encoding of solutions. Rather fully defined layouts are manipulated as such by means of specific genetic operators. Two additional constraints, namely the orientation constraint and the guillotine constraint, can be taken into account. The GA is subjected to a comprehensive test using benchmark instances with up to 5000 pieces. Compared to eleven competing methods from the literature the GA performs best.     

A skyline heuristic for the 2D rectangular packing and strip packing problems

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an “iterative doubling” binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP.     

Bidirectional best-fit heuristic for orthogonal rectangular strip packing

In a non-guillotinable rectangular strip packing problem (RF-SPP), the best orthogonal placement of given rectangular pieces on a strip of stock sheet having fixed width and infinite height are searched. The aim is to minimize the height of the strip while including all the pieces in appropriate orientations. In this study, a novel bidirectional best-fit heuristic (BBF) is introduced for solving RF-SPPs. The proposed heuristic as a new feature considers the gaps in both horizontal and vertical directions during the placement process. The performance of BBF is compared to some previous approaches, including one of the best heuristics from the literature. BBF achieves better results than the existing heuristics and delivers a better or matching performance as compared to the most of the previously proposed meta-heuristics for solving RF-SPPs.     

A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint

The article presents a tree search algorithm (TRSA) for the strip packing problem in two and three dimensions with guillotine cutting constraint. In the 3D-SPP a set of rectangular items (boxes) and a container with fixed width and height but variable length are given. An arrangement of all boxes within the container has to be determined so that the required length is minimised. The 2D-SPP is analogously defined. The proposed TRSA is based on a tree search algorithm for the container loading problem by Fanslau and Bortfeldt (INFORMS J. Comput. 22:222?C235, 2010). The TRSA generates guillotine packing patterns throughout. In a comparison with all recently proposed 3D-SPP methods the TRSA performs very competitive. Fine results are also achieved for the 2D-SPP.     

4-Block heuristic for the rectangle packing problem

In this paper the rectangle packing problem (RPP) is considered. The RPP consists in finding a packing pattern of small rectangles within a larger rectangle such that the area utilization is maximized. We develop new heuristics for the RPP which are based on the G4-heuristic for the pallet loading problem. In addition to the general RPP we take also into account further restrictions which are of practical interest.     

A hybrid placement strategy for the three-dimensional strip packing problem

This paper presents a hybrid placement strategy for the three-dimensional strip packing problem which involves packing a set of cuboids (‘boxes’) into a three-dimensional bin (parallelepiped) of fixed width and height but unconstrained length (the ‘container’). The goal is to pack all of the boxes into the container, minimising its resulting length. This problem has potential industry application in stock cutting (wood, polystyrene, etc. – minimising wastage) and also cargo loading, as well as other applications in areas such as multi-dimensional resource scheduling. In addition to the proposed strategy a number of test results on available literature benchmark problems are presented and analysed. The results of empirical testing of the algorithm show that it out-performs other methods from the literature, consistently in terms of speed and solution quality-producing 28 best known results from 35 test cases.     

The variable-width strip packing problem

Here, we focus on a generalized version of the strip packing problem; namely we have several open-end strips with different widths, and we wish to pack rectangular items into these strips without overlapping such that we have to minimize either the makespan (i.e. the top of the topmost item), or the total area used. We investigate the online variant of the problem, where the items are arriving one-by-one, and we have to make irrevocable decisions on their packing. A similar framework was proposed by Ye and Mei (On-line scheduling of parallel jobs in heterogeneous multiple clusters. Frontiers in algorithmics and algorithmic aspects in information and management, Springer, Berlin, pp 139–148, 2012. https://doi.org/10.1007/978-3-642-29700-7_13) for scheduling models, and they studied the absolute competitive ratio of their algorithm. Our contribution is to define a new objective function and several algorithms by combining so-called shelf algorithms with techniques taken from the areas of the variable-sized bin packing problem and scheduling. We analyzed the asymptotic competitive ratio of our algorithms.

     

A reference length approach for the 3D strip packing problem

In the three-dimensional strip packing problem (3DSP), we are given a container with an open dimension and a set of rectangular cuboids (boxes) and the task is to orthogonally pack all the boxes into the container such that the magnitude of the open dimension is minimized. We propose a block building heuristic based on extreme points for this problem that uses a reference length to guide its solution. Our 3DSP approach employs this heuristic in a one-step lookahead tree search algorithm using an iterative construction strategy. We tested our approach on standard 3DSP benchmark test data; the results show that our approach produces better solutions on average than all other approaches in literature for the majority of these data sets using comparable computation time.     

A heuristic algorithm for the truckload and less-than-truckload problem

The delivery of goods from a warehouse to local customers is an important and practical problem of a logistics manager. In reality, we are facing the fluctuation of demand. When the total demand is greater than the whole capacity of owned trucks, the logistics managers may consider using an outsider carrier.Logistics managers can make a selection between a truckload (a private truck) and a less-than-truckload carrier (an outsider carrier). Selecting the right mode to transport a shipment may bring significant cost savings to the company.In this paper, we address the problem of routing a fixed number of trucks with limited capacity from a central warehouse to customers with known demand. The objective of this paper is developing a heuristic algorithm to route the private trucks and to make a selection of less-than-truckload carriers by minimizing a total cost function. Both the mathematical model and the heuristic algorithm are developed. Finally, some computational results and suggestions for future research are presented.     

A heuristic algorithm for the multidimensional zero-one knapsack problem

Computational and theoretical aspects of a new heuristic for the multidimensional zero-one knapsack problem are studied. Its computational efficiency is compared with two other well-known heuristics.     

A heuristic for the circle packing problem with a variety of containers

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two-dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right-angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems.Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature.     

A heuristic algorithm for the free newspaper delivery problem

This paper addresses the problem of finding an effective distribution plan to deliver free newspapers from a production plant to subway, bus, or tram stations. The overall goal is to combine two factors: first, the free newspaper producing company wants to minimize the number of vehicle trips needed to distribute all newspapers produced at the production plant. Second, the company is interested in minimizing the time needed to consume all newspapers, i.e., the time needed to get all the newspapers taken by the final readers. The resulting routing problem combines aspects of the vehicle routing problem with time windows, the inventory routing problem, and additional constraints related to the production schedule. We propose a formulation and different heuristic approaches, as well as a hybrid method. Computational tests with real world data show that the hybrid method is the best in various problem settings.     

An effective heuristic for the two-dimensional irregular bin packing problem

This paper proposes an adaptation, to the two-dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD), originally designed for the one-dimensional bin packing problem. In the two-dimensional case, not only is it the case that the piece’s size is important but its shape also has a significant influence. Therefore, DJD as a selection heuristic has to be paired with a placement heuristic to completely construct a solution to the underlying packing problem. A successful adaptation of the DJD requires a routine to reduce computational costs, which is also proposed and successfully tested in this paper. Results, on a wide variety of instance types with convex polygons, are found to be significantly better than those produced by more conventional selection heuristics.     

A hybrid evolutionary algorithm for the two-dimensional packing problem

This paper presents a hybrid evolutionary algorithm for the two-dimensional non-guillotine packing problem. The problem consists of packing many rectangular pieces into a single rectangular sheet in order to maximize the total area of the pieces packed. Moreover, there is a constraint on the maximum number of times that a piece may be used in a packing pattern. The set of packing patterns is processed by an evolutionary algorithm. Three mutation operators and two types of quality functions are used in the algorithm. The best solution obtained by the evolutionary algorithm is used as the initial solution in a tree search improvement procedure. This approach is tested on a set of benchmark problems taken from the literature and compared with the results published by other authors.