基于多元优化算法的三维装箱问题的研究

用多元优化算法（Multi-variant optimization algorithm,MOA）实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中;局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化;通过递推的随机放置和局部调整优化,目标函数值逐步逼近最优值,从而获得一个较为理想的三维装箱方案.算法通过对BR1~BR10共1000组三维装箱问题测试实例的测试仿真,得到理想的装箱效果,说明用多元优化算法实现三维装箱问题的有效性和可行性.     

一种求解集装箱装载问题的启发式算法

所谓集装箱装载问题,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器,其目标是最大化容器的积裁率.对这一问题,国内外学者利用不同的哲学思想,提出了诸如遗传算法、模拟退火算法等求解算法.本文提出一种求解此问题的基于最大穴度优先原则的启发式算法.算法中使用了两个重要的策略:最大穴度原则和最小边度原则.用一些公开的算例对算法性能进行了实算测试,测试结果表明:算法所得结果的容器积载率高,是求解集装箱装载问题的有效算法.     

求解三维装箱问题的混合模拟退火算法

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.     

VCS: A new heuristic function for selecting boxes in the single container loading problem

The single container loading problem consists of a container that has to be filled with a set of boxes. The objective of the problem is to maximize the total volume of the loaded boxes. For solving the problem, constructive approaches are the most successful. A key element of these approaches is related to the selection of the box to load next. In this work, we propose a new evaluation function for ranking boxes. Our function rewards boxes that fit well in the container, taking into account the previously placed ones. To construct a more robust function, we consider some other well-known evaluation criteria such as the volume of the block and the estimated wasted volume in the free space of the container. Our approach shows promising results when compared with other state-of-the-art algorithms on a set of 1600 well-known benchmark instances.     

A novel hybrid tabu search approach to container loading

The container loading problem, which is significant for a number of industrial sectors, aims to obtain a high space utilisation in the container while satisfying practical constraints. This paper presents a novel hybrid tabu search approach to the container loading problem. A loading heuristic is devised to incorporate heuristic strategies with a handling method for remaining spaces to generate optimal loading arrangements of boxes with stability considered. The tabu search technique, which covers the encoding, evaluation criteria and configuration of neighbourhood and candidate solutions, is used to improve the performance of the loading heuristic. Experimental results with benchmark data show that the hybrid approach provides a better space utilisation than the published approaches under the condition of all loaded boxes with one hundred percent support from below. Moreover, it is shown that the hybrid tabu search can solve problems with the constraints of weight limit and weight distribution with real world data.     

Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem

The container loading problem (CLP) has important industrial and commercial application for global logistics and supply chain. Many algorithms have been proposed for solving the 2D/3D container loading problem, yet most of them consider single objective optimization. In practice, container loading involves optimizing a number of objectives. This study aims to develop a multi-objective multi-population biased random-key genetic algorithm for the three-dimensional single container loading problem. In particular, the proposed genetic algorithm applied multi-population strategy and fuzzy logic controller (FLC) to improve efficiency and effectiveness. Indeed, the proposed approach maximizes the container space utilization and the value of total loaded boxes by employing Pareto approach and adaptive weights approach. Numerical experiments are designed to compare the results between the proposed approach and existing approaches in hard and weak heterogeneous cases to estimate the validity of this approach. The results have shown practical viability of this approach. This study concludes with discussions of contributions and future research directions.     

A heuristic block-loading algorithm based on multi-layer search for the container loading problem

This paper presents an efficient heuristic block-loading algorithm based on multi-layer search for the three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing phase, according to a fixed strategy, until no blocks are available. Second, the concept of composite block is introduced, the difference between traditional block and composite block being that composite block can contain multiple types of boxes in one block under some restrictions. Third, based on the depth-first search algorithm, a multi-layer search algorithm is developed for determining the selected block in each packing phase, and making this result closer to the optimal solution. Computational results on a classic data set show that the proposed algorithm outperforms the best known algorithm in almost all the test data.     

A tree search algorithm for the container loading problem

This paper presents a binary tree search algorithm for the three dimensional container loading problem (3D-CLP). The 3D-CLP is about how to load a subset of a given set of rectangular boxes into a rectangular container, such that the packing volume is maximized. In this algorithm, all the boxes are grouped into strips and layers while three constraints, i.e., full support constraint, orientation constraint and guillotine cutting constraint are satisfied. A binary tree is created where each tree node denotes a container loading plan. For a non-root each node, the layer set of its left (or right) child is obtained by inserting a directed layer into its layer set. A directed layer is parallel (or perpendicular) to the left side of the container. Each leaf node denotes a complete container loading plan. The solution is the layer set whose total volume of the boxes is the greatest among all tree nodes. The proposed algorithm achieves good results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff with reasonable computing time.     

Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier

In this paper, we present heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem arising in a real-world situation. In this problem, customers make requests of goods, which are packed in a sortment of boxes. The objective is to find minimum cost delivery routes for a set of identical vehicles that, departing from a depot, visit all customers only once and return to the depot. Apart of the usual 3D container loading constraints which ensure that the boxes are packed completely inside the vehicles and that the boxes do not overlap each other in each vehicle, the problem also takes into account constraints related to the vertical stability of the cargo and multi-drop situations. The algorithms are based on the combination of classical heuristics from both vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include other practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. The approaches are also sufficiently generic to be embedded with algorithms other than those considered in this study, as well as they can be easily adapted to consider other practical constraints, such as the load bearing strength of the boxes, time windows and pickups and deliveries. Computational tests were performed with these methods considering instances based on the vehicle routing literature and actual customers’ orders, as well as instances based on a real-world situation of a Brazilian carrier. The results show that the heuristics are able to produce relatively good solutions for real instances with hundreds of customers and thousands of boxes.     

A parallel multi-population biased random-key genetic algorithm for a container loading problem

This paper presents a multi-population biased random-key genetic algorithm (BRKGA) for the single container loading problem (3D-CLP) where several rectangular boxes of different sizes are loaded into a single rectangular container. The approach uses a maximal-space representation to manage the free spaces in the container. The proposed algorithm hybridizes a novel placement procedure with a multi-population genetic algorithm based on random keys. The BRKGA is used to evolve the order in which the box types are loaded into the container and the corresponding type of layer used in the placement procedure. A heuristic is used to determine the maximal space where each box is placed. A novel procedure is developed for joining free spaces in the case where full support from below is required. The approach is extensively tested on the complete set of test problem instances of Bischoff and Ratcliff [1] and Davies and Bischoff [2] and is compared with 13 other approaches. The test set consists of 1500 instances from weakly to strongly heterogeneous cargo. The computational experiments demonstrate that not only the approach performs very well in all types of instance classes but also it obtains the best overall results when compared with other approaches published in the literature.     

A hybrid differential evolution algorithm for multiple container loading problem with heterogeneous containers

We consider a multiple container loading problem, commonly known as the three-dimensional bin packing problem (3D-BPP), which deals with maximizing container space utilization while the containers available for packing are heterogeneous, i.e., varying in size. The problem has wide applications in cargo transportation, warehouse management, medical packaging, and so on. We develop a differential evolution (DE) algorithm hybridized with a novel packing heuristic strategy, best-match-first (BMF), which generates a compact packing solution based on a given box packing sequence and a container loading sequence. The effectiveness of the proposed algorithm is evaluated on a set of industrial instances and randomly generated instances. The results show that the proposed algorithm outperforms existing solution approaches in terms of solution quality.     

A heuristic for packing boxes into a container

Given a container of known dimensions and a collection of rectangular boxes with known dimensions and number of boxes of each type, the problem is to find suitable positions for placing the boxes in the container in such a way that all the boxes can be fitted in. A heuristic for computer or manual operation is described.     

一种高效的同尺寸长方体的装箱算法

针对应用广泛的同尺寸长方体货品的装箱问题,本文运用分层装载方案,根据货品的长宽高采用三种不同的层高,利用动态规划算法分别计算三种层的最大装载量,再通过背包算法对层进行组合,得出装箱的最优方案。该算法复杂度低,装载方案简单。     

Three-dimensional container loading models with cargo stability and load bearing constraints

Mathematical models for the problem of loading rectangular boxes into containers, trucks or railway cars have been proposed in the literature, however, there is a lack of studies which consider realistic constraints that often arise in practice. In this paper, we present mixed integer linear programming models for the container loading problem that consider the vertical and horizontal stability of the cargo and the load bearing strength of the cargo (including fragility). The models can also be used for loading rectangular boxes on pallets where the boxes do not need to be arranged in horizontal layers on the pallet. A comprehensive performance analysis using optimization software with 100s of randomly generated instances is presented. The computational results validate the models and show that they are able to handle only problems of a moderate size. However, these models might be useful to motivate future research exploring other solution approaches to solve this problem, such as decomposition methods, relaxation methods, heuristics, among others.     

求解三维装箱问题的混合遗传模拟退火算法

集装箱装载是货物运输过程中重要的一步,其属于NP-hard问题。为了提高效率,降低成本,提出了以集装箱体积利用率最大化为目标建立三维装载模型,同时考虑体积约束、重量约束、重心约束、方向约束。利用混合遗传、模拟退火与三空间分割启发式装载算法求解模型,算法中融入局部最优解保存策略来避免局部较好解在后续的算法过程中出现适应度降低的情况。通过强异类算例与弱异类算例对算法进行性能测试,并结合具体的货物装载数据,得出三维装载图与目标函数值。结果表明,该算法应用于集装箱装载有着较好的效果。     

An optimization model for the container pre-marshalling problem

In most container yards around the world, containers are stacked high to utilize yard space more efficiently. In these yards, one major factor that affects their operational efficiency is the need to re-shuffle containers when accessing a container that is buried beneath other containers. One way to achieve higher loading efficiency is to pre-marshal the containers in such a way that it fits the loading sequence. In this research, we present a mathematical model for the container pre-marshalling problem. With respect to a given yard layout and a given sequence that containers are loaded onto a ship, the model yields a plan to re-position the export containers within the yard, so that no extra re-handles will be needed during the loading operation. The optimization goal is to minimize the number of container movements during pre-marshalling. The resulting model is an integer programming model composed of a multi-commodity flow problem and a set of side constraints. Several possible variations of the model as well as a solution heuristic are also discussed. Computation results are provided.     

A domain-specific knowledge-based heuristic for the Blocks Relocation Problem

The Blocks Relocation Problem consists in minimizing the number of movements performed by a gantry crane in order to retrieve a subset of containers placed into a bay of a container yard according to a predefined order. A study on the mathematical formulations proposed in the related literature reveals that they are not suitable for its solution due to their high computational burden. Moreover, in this paper we show that, in some cases, they do not guarantee the optimality of the obtained solutions. In this regard, several optimization methods based on the well-known A¹ search framework are introduced to tackle the problem from an exact point of view. Using our A¹ algorithm we have corrected the optimal objective function value of 17 solutions out of 45 instances considered by Caserta et al. (2012) [4]. In addition, this work presents a domain-specific knowledge-based heuristic algorithm to find high-quality solutions by means of short computational times. It is based on finding the most promising positions into the bay where to relocate those containers that are currently located on the next one to be retrieved, in such a way that, they do not require any additional relocation operation in the future. The computational tests indicate the higher effectiveness and efficiency of the suggested heuristic when solving real-world scenarios in comparison with the most competitive approaches from the literature.     

求解三维装箱问题的多层树搜索算法

提出了一种求解三维装箱问题的多层树搜索算法, 该算法采用箱子–片–条–层–实体的顺序生成装载方案, 装载方案由实体表示. 该算法由3层搜索树构成. 第1层为三叉树, 每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层; 第2层为二叉树, 每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条; 第3层为四叉树, 用于将同种的多个箱子生成片. 在同时满足摆放方向约束和完全支撑约束的前提下, 该算法求解BR12~BR15得到的填充率高于现有装箱算法.     

同类货物集装箱装载问题的启发式算法

提出了求解同类货物集装箱装载问题的一种启发式算法.算法中采用了层的思想,集装箱的每个面都可用来构建层.通过对二维布局、层高组合和用来构建层的集装箱面的选择等三个方面的优化求解,得到了具有较高装载率的集装箱装载方案.实例结果表明,该算法是求解同类货物集装箱装载问题的一种行之有效的方法.     

A heuristic partitioning algorithm for a packaging problem

A heuristic algorithm for solving a problem of a minimum-cost packaging ofN items of the magnitudea _j intoM boxes of the capacityb _i with a costc _ij being assigned to the itemj packing into the boxi is presented. The principal idea of the algorithm consists in the preliminary partitioning of the problem into smaller subproblems and getting an approximate solution by solving these subproblems. A motivation of the heuristic and an application of the algorithm are given.