Explore the vast range of titles available.

We tackle the online 3D bin packing problem (3D-BPP), a challenging yet practically useful variant of the classical bin packing problem. In this problem, the items are delivered to the agent without informing the full sequence information. The agent must directly pack these items into the target bin stably without changing their arrival order, and no further adjustment is permitted. Online 3D-BPP can be naturally formulated as a Markov decision process (MDP). We adopt deep reinforcement learning, in particular, the on-policy actor-critic framework, to solve this MDP with constrained action space. To learn a practically feasible packing policy, we propose three critical designs. First, we propose an online analysis of packing stability based on a novel stacking tree. It attains a high analysis accuracy while reducing the computational complexity from O ( N 2 ) to O ( N log N ), making it especially suited for reinforcement learning training. Second, we propose a decoupled packing policy learning for different dimensions of placement which enables high-resolution spatial discretization and hence high packing precision. Third, we introduce a reward function that dictates the robot to place items in a far-to-near order and therefore simplifies the collision avoidance in movement planning of the robotic arm. Furthermore, we provide a comprehensive discussion on several key implemental issues. The extensive evaluation demonstrates that our learned policy outperforms the state-of-the-art methods significantly and is practically usable for real-world applications.

The one-dimensional bin packing problem (1DBPP) is a well-known NP-hard problem in computer science and operations research that involves many real-world applications. Its primary objective is to allocate items into bins while minimizing the number of bins used. Due to the complexity of the problem, exact algorithms are often impractical for large instances, which has led to a reliance on tailored heuristics that may perform well on some instances but poorly on others. In this study, we propose a method to automatically generate selection hyper-heuristics (HHs), which are then applied to solve 1DBPP instances by leveraging the strengths of simple heuristics while avoiding their drawbacks. Specifically, we introduce a steady-state μ Genetic Algorithm (SSμGA) to generate selection HHs, benefiting from the gradual population updates of steady-state GAs and the efficiency of μGAs with smaller populations for faster iterations. Our experimental results showcase the effectiveness of the SSμGA across multiple training and testing datasets for the 1DBPP. Compared to other evolutionary methodologies, also used as generative HH methods (i.e., generational GA, steady-state GA, and generational μGA), the SSμGA consistently achieves higher fitness values within the same number of evaluations, on the training set. Additionally, on both generated and literature 1DBPP instances for the testing set, the selection HHs generated by the SSμGA were highly competitive, often outperforming those produced by other methods. Furthermore, the SSμGA-generated HHs displayed both specialization for specific instance types and generalization across varied instances.

We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality. In this paper we propose a new exact method that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders' decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is reiterated. We show that both the master and the slave are strongly -hard problems and solve them with tailored preprocessing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders' cuts, using the so-called combinatorial Benders' cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms.

The consolidation of virtual machine (VM) is the strategy of efficient and intelligent use of cloud datacenters resources. One of the important subproblems of VM consolidation is VM placement problem. The main objective of VM placement problem is to minimize the number of running physical machines or hosts in cloud datacenters. This paper focuses on solving VM placement problem with respect to the available bandwidth which is formulated as variable sized bin packing problem. Moreover, a new bandwidth allocation policy is developed and hybridized with an improved variant of whale optimization algorithm (WOA) called improved Lévy based whale optimization algorithm. Cloudsim toolkit is used in order to test the validity of the proposed algorithm on 25 different data sets that generated randomly and compared with many optimization algorithms including: WOA, first fit, best fit, particle swarm optimization, genetic algorithm, and intelligent tuned harmony search. The obtained results are analyzed by Friedman test which indicates the prosperity of the proposed algorithm for minimizing the number of running physical machine.

Modern logistics operations require real-time adaptive solutions for three-dimensional bin packing that maintain spatial symmetry and load balance. This paper introduces a time-series-based online 3D packing problem with dual unknown sequences, where containers and items arrive dynamically. The challenge lies in achieving symmetric distribution for stability and optimal space utilization. We propose the Second-Order Dual Pointer Adversarial Network (So-DPAN), a deep reinforcement learning architecture that leverages symmetry principles to decompose spatiotemporal optimization into sequence matching and spatial arrangement sub-problems. The dual pointer mechanism enables efficient item-container pairing, while the second-order structure captures temporal dependencies by maintaining symmetric packing patterns. Our approach considers geometric symmetry for spatial arrangement and temporal symmetry for sequence matching. The Actor-Critic framework uses symmetry-based reward functions to guide learning toward balanced configurations. Experiments demonstrate that So-DPAN outperforms DQN, DDPG, and traditional heuristics in solution quality and efficiency while maintaining superior symmetry metrics in center-of-gravity positioning and load distribution. The algorithm exploits inherent symmetries in packing structure, advancing theoretical understanding through symmetry-aware optimization while providing a deployable framework for Industry 4.0 smart logistics.

This paper discusses the two-dimensional loading capacitated vehicle routing problem (2L-CVRP) with heterogeneous fleet (2L-HFVRP). The 2L-CVRP can be found in many real-life situations related to the transportation of voluminous items where two-dimensional packing restrictions have to be considered, e.g.: transportation of heavy machinery, forklifts, professional cleaning equipment, etc. Here, we also consider a heterogeneous fleet of vehicles, comprising units of different capacities, sizes and fixed/variable costs. Despite the fact that heterogeneous fleets are quite ubiquitous in real-life scenarios, there is a lack of publications in the literature discussing the 2L-HFVRP. In particular, to the best of our knowledge no previous work discusses the non-oriented 2L-HFVRP, in which items are allowed to be rotated during the truck-loading process. After describing and motivating the problem, a literature review on related work is performed. Then, a multi-start algorithm based on biased randomization of routing and packing heuristics is proposed. A set of computational experiments contribute to illustrate the scope of our approach, as well as to show its efficiency.

Manufacturing systems need to be resilient and self-organizing to adapt to unexpected disruptions, such as product changes or rapid order, in supply chain changes while increasing the automation level of robotized logistics processes to cope with the lack of human experts. Deep Reinforcement Learning is a potential solution to solve more complex problems by introducing artificial neural networks in Reinforcement Learning. In this paper, a game engine was used for Deep Reinforcement Learning training, which allows visualization of view learning and result processes more intuitively than other tools, as well as a physical engine for a more realistic problem-solving environment. The present research demonstrates that a Deep Reinforcement Learning model can effectively address the real-time sequential 3D bin packing problem by utilizing a game engine to visualize the environment. The results indicate that this approach holds promise for tackling complex logistical challenges in dynamic settings.

We consider the one-dimensional skiving stock problem, also known as the dual bin packing problem, with the aim of maximizing the best known dual and proper dual gaps. We apply the methods of computational search of large gaps initially developed for the one-dimensional cutting stock problem, which is related to the bin packing problem. The best known dual gap is raised from 1.0476 to 1.1795. The proper dual gap is improved to 1.1319. We also apply a number of new heuristics developed for the skiving stock problem back to the cutting stock problem, raising the largest known proper gap from 1.0625 to 1.1.

This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packing problem. The width-filled skyline is used to represent the interior packing state, and a constructive rectangular packing algorithm with the commonly adopted fitness evaluation for placement is designed. Then, the consecutive item packing is simulated as Markov Decision Process, where the state is defined as the set of already packed items, and the action is defined as the rectangle selected to be packed along with its orientation. We propose the reverse updating of Q -value in the paradigm of Q-learning and use the algorithm to optimize the sequence and orientation of the rectangles. The decreasing-size-choice mechanism in Q-learning is studied on randomly generated problems to optimize the setting of ε -greedy policy. We also test the Q-learning-based algorithm on the benchmark instances of C21, N13, N -series from NT, Cgcut and Beng. Compared with a few state-of-the-art algorithms, the computational results show that the proposed algorithm can produce good packing quality when adequate execution time allowed.

The two-dimensional strip-packing problem (2D-SPP) emerges as a notable variant of the cutting and packing (C&P) problem, aiming to optimize the arrangement of small rectangular items within unique strips with a fixed width and infinite height to minimize the usage of height. Despite extensive academic exploration, applying 2D-SPP solutions in industrial settings remains challenging. Two significant issues, often overlooked in academia yet frequently encountered in industrial contexts, are the uncertain demand for items, exacerbated by the bullwhip effect, and the need for diverse types of strips to cater to varying customer needs. Our paper addresses this academia–industry gap by proposing a robust optimization model for the uncertain 2D-SPP with variable-sized bins, aiming to manage the demand fluctuations within a box uncertainty set framework. Additionally, we employ the contiguous one-dimensional relaxation technique in conjunction with column generation to tighten the lower bound of the problem, thereby augmenting solution accuracy. Furthermore, we leverage the Karush–Kuhn–Tucker (KKT) condition to transform the model into a more tractable form, subsequently leading to an exact solution. Based on datasets from a real-life plastic-cutting company, comprehensive experiments validate the effectiveness and efficiency of our proposed relaxation method and algorithm, showcasing the potential for an improved industrial application of 2D-SPP solutions.