求解复杂集装箱装载问题的新方法

提出了一种求解复杂集装箱装载问题的新方法，该方法将求解复杂装箱问题分成两步：首先，根据一定的启发式规则将集装箱进行体积最大化装载，并在深度方向根据货物将空间分层；然后，用遗传算法将各层进行重心位置最优化调整，使装载方案更加符合实际运输需要。实际应用结果表明，该方法在空间利用率、重心位置以及计算效率等方面都优于其他同类方法。     

求解集装箱装载问题的混合蚁群模拟退火算法

目的 针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题,提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法 首先,采用塔装载启发式算法将三维待装箱装载成塔集,即将三维装箱问题降为二维装箱问题,有效降低集装箱的装载规模;其次,蚁群算法通过融入信息素选择更新策略,并利用自适应信息素挥发系数来提升算法整体的收敛速度,同时结合模拟退火算法对每代优秀路径集进行局部搜索,避免算法因收敛过快而陷入局部最优;最后,将蚁群模拟退火算法与二维装载点启发式算法相结合,优化每座塔的装载顺序和放置姿态,寻找最优的装载方案。结果 实验证明,在250组算例中,采用混合算法后,集装箱的平均空间利用率为90.92%,优于其他3种对比算法。结论 设计的混合蚁群模拟退火算法适用于解决大规模集装箱装载问题。     

一刀切约束下的二维装箱问题高效求解算法

目的 为实现大规模物料的快速剪裁切割,对考虑一刀切约束的二维装箱问题进行研究,并构建相应的改进优先度算法IPH(Improved Priority Algorithm,IPH).方法 IPH能够在不需要任何迭代搜索下,直接进行剩余空间分割与填充.为此,发展PH算法中的优先度放置规则,并以最大化生成大空间面积和最小化生成小空间面积为基础,设计改进砌砖式空间分割策略.结果 针对标准数据集的对比实验表明,IPH能够在较短时间内完成大规模算例的高效求解,并首次获得了多个算例的最优填装效果.结论 基于概率较优的启发式求解方法,能够实现无迭代优选下的一刀切二维装箱问题直接求解,且运算效果令人满意.     

基于层间垫平的囊匣三维装箱优化设计

目的 为提高囊匣的装载率及装箱效率,研究层间垫平的强异构类的三维装箱问题,实现快速计算囊匣装箱方案和衬垫方案并指示装箱。方法 基于囊匣实际装箱需求,以衬垫体积最小为目标,设计基于贪心策略与改进的装箱顺序策略的两步优化启发式算法,对装箱与衬垫方案进行优化;并根据不同放置方向,设计不同的输出效果以指示装箱。结果 与装箱优化前数据进行对比实验证明,该算法推荐的装箱方案与衬垫方案可以减少木箱的使用数量与体积,减少垫平用衬垫体积7.21%,装箱时间缩短了约一半。结论 文中设计的混合启发式算法能为囊匣装箱问题找到合适的装箱与衬垫方案,减少衬垫的使用,提高装载率以及装箱效率。     

Heuristic Programming in Spatial System Design

A link is needed to transform and to demonstrate the methodology of heuristic programming to the environment of spatial systems design. A class of problems is proposed which appears to be particularly suitable for this purpose. These problems relate to complex decisions in which the allocation and use of space is a critical dimension. This paper describes a game which may be viewed as an abstraction of real systems involving the packing of smaller items into a larger space; i.e., problems somewhat similar to the knapsack problem. The game has been invented as a means of focusing the attention of student designers on “real” games as opposed to parlor games. A computer implementation of a space game is described which provides for the addition and testing of subroutines incorporating heuristics for making decisions in design problems related to space.     

Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem

This paper studies a real-life multi-objective two-dimensional single-bin-size bin-packing problem arising in industry. A packing pattern is defined by one bin, a set of items packed into the bin and the packing positions of these items. A number of bins can be placed with the same packing pattern. The objective is not only to minimise the number of bins used, as in traditional bin-packing problems, but also to minimise the number of packing patterns. Based on our previous study of a heuristic stemming from dynamic programming by aggregating states to avoid the exponential increase in the number of states, we further develop this heuristic by decomposing a pattern with a number of bins at each step. Computational results show that this heuristic provides satisfactory results with a gap generally less than 20% with respect to the optimum.     

考虑装载顺序约束的航空货物装箱问题研究

目的 以航空货运背景下流水线上货物的装箱问题为研究对象,旨在最大化地利用集装箱装载空间.方法 在考虑货物装载顺序、质量、体积、不重叠、稳定性等一系列现实约束的条件下,建立集装箱堆码模型,设计一种拟人启发式与遗传相结合的组合启发式算法.首先通过设定规则并赋予权重,得到有序可放置点集合,采用拟人启发式算法构建货物装载策略,得到初始装箱方案;然后通过遗传算法中的交叉、变异操作对方案进行寻优,在可行方案中选出集装箱空间利用率最大的装箱方案;最后采用某机场物流公司的实际货物数据进行实验,并实现装载方案的可视化.结果 相较于混合模拟退火算法,组合启发式算法收敛性好,搜索速度快,能够在较短的时间内得到空间利用率较高的装载方案,货物垛形规划更为紧凑,稳定性更高.结论 所提算法对于不同种类的货物有着更好的适应性,能够实现强异构货物的合理布局,保证了货物装载过程中垛形的稳定性,可为航空货物装箱问题的工程应用提供参考.     

Packing solar cells on a roof

We consider the problem of finding a suitable placement of solar cells on the roof of a building. Since roofs may be of nonrectangular shape and may have obstacles like chimneys, dormers or windows on them, finding an optimal layout is not a trivial task. Mathematically, this setting belongs to the class of cutting and packing problems, with an additional difficulty in the shape of the disposable roof area: existing approaches do not cover our situation where we deal with nonconvex roofs. We develop a mixed integer linear model for this problem and present an enhanced version of the classical bottom-left heuristic. Examples demonstrate that this new approach considerably improves traditional strategies.     

基于启发式算法的单航空集装器的装箱优化设计

目的 为了解决当前航空业因航空集装器上货物的组装编排均由人工完成,尚无任何软件系统可以实现自动计算,造成航空货运经济效益和时效性低下的问题,开展航空集装器（ULD）装箱算法研究。方法 应用先进的贪心算法与遗传算法相结合的启发式算法研究单个航空集装器的装箱最优问题。结果 对单个航空集装器（ULD）装箱进行了装箱模型构建和算法优化,使得节省的航空集装器空间得到全部利用,实现最优装箱。结论 文中算法计算出的装载方案较人工计算更精确、更具稳定性,且经济效益更高。后续还有望把这种算法转化为高度智能化的软件系统,对航空货运自动化和工作流程标准化具有一定的推动意义。     

一种基于蜜蜂进化选择算子的布局遗传算法

三维矩形布局问题属于NP难问题,对于三维矩形布局问题的求解大多依赖于各种启发式算法.该文以布局物体体积递减为定序规则,结合布局物体在布局空间中的几何可行域,以吸引子法为定位规则,利用蜜蜂进化型遗传算法优化吸引子函数中的参数来求解三维矩形布局问题（BEGA）,得到新型布局遗传算法.最后对不同的算例进行了计算,并与以标准比例选择作为选择算子的传统布局遗传算法（SPGA）等对比证明了该算法的有效性.     

求解矩形布局问题的自适应算法

矩形布局问题属于NP-Hard问题,其求解算法多为启发式算法。该文侧重于构造布局求解算法中定位函数(规则)的优化,将模拟退火算法的思想融入到遗传算法中,提出了求解矩形布局问题的自适应算法,其利用自适应交叉、变异及接收劣质解的概率等方法对定位函数中各参数进行优化。算法通过两种方式确定初始种群的数目,具有较强的适应性。在算法搜索的后期,利用差异性较大的个体进行交叉操作,从而保持种群的多样性。最后通过实例证明了该算法能够很好的应用于矩形布局问题的求解。     

A semi-discrete geometric representation for nesting problems

This paper deals with the resolution of nesting algorithm, known as the irregular packing problem. It focuses on the geometric layer of the nesting algorithm, namely on the implementation of a semi-discrete representation of irregular geometric shapes and on the use of this representation in a nesting algorithm, proposed in previous publications. The proposed geometric scheme combines the features of discrete representation scheme and analytical concepts to quickly represent the geometry of part/sheet in digital form. The uniqueness of the proposed representation scheme lies in representing a part/sheet, of simple to complex geometry, with a series of equidistant vertical lines. These vertical lines not only aid in detecting collision among the parts easily but also assist in effective placement of parts on the sheet with bottom-left placement heuristic. With a view to enhance the speed of nesting, a scheme called Quick Void Skip is proposed to quickly identify the vacant regions on the sheet. For faster and effective nesting of a variety of parts on any geometry of sheet, the distance between the vertical lines, representing the part/sheet geometry, is adaptively chosen. Finally, the effectiveness of the proposed scheme is demonstrated by comparing its performance with that achieved by a semi-discrete approach, proposed in a previous study.     

Efficient heuristics for robot acquisition planning for a CIM system

In this paper, a planning model and three efficient heuristics are developed for equipment acquisition planning for a CIM system using multiple-type robots. Our planning model considers selection of a proper mix of multiple-type robots such that operational requirements (i.e., time and space) from a given number of work stations are satisfied at minimal system cost. In specific, each robot is characterized by its fixed charge and subject to two capacity constraints on machine time and work space; and each work station has known demands for both machine time and work space, and is to be served by only one robot. The model is formulated as a pure 0–1 mathematical program and is shown to be harder than two-dimensional bin packing, a well-known NP-hard problem. The three heuristics developed are: a greedy heuristic, tabu thresholding, and simulated annealing. All heuristics are tested by solving 450 randomly generated problems. Computational results indicate that all three heuristics are effective and efficient in solving problems of a practical size (i.e., 50 work stations and a maximum of 20 robots). However, none of the heuristics are overwhelmingly better than the others in terms of both solution time and quality. Future research issues are also discussed.     

A heuristic approach to the three-dimensional cargo-loading problem

Since no exact analytical method for solving the three-dimensional cargo-loading problem has been developed, the heuristic approaches with practical assumptions are still useful. A dynamic programming approach to this problem is proposed in this paper. Loading a three-dimensional cargo space is done layer by layer, a special property which is taken advantage of in the proposed algorithm. The computational performance of this heuristic is demonstrated by comparing its results with suggested values published by the General Services Administration, Washington, DC.     

An experimental comparison of systematic placement procedures for facility layout design

A comparison of alternative procedures for automatic placement of facilities in a layout is presented. Various placement procedures are reviewed, incorporated in an existing ‘construction’ type heuristic and evaluated in terms of placement computation time, satisfaction of goals expressed using linguistic patterns, fulfilment of desired adjacency of facilities and regularity of shapes of facilities in resulting layouts. An experiment illustrates the application of various placement procedures fora set of randomly generated and known layout problems to compare the performance of alternative placement procedures.     

Sequence based heuristics for two-dimensional bin packing problems

This article addresses several variants of the two-dimensional bin packing problem. In the most basic version of the problem it is intended to pack a given number of rectangular items with given sizes in rectangular bins in such a way that the number of bins used is minimized. Different heuristic approaches (greedy, local search, and variable neighbourhood descent) are proposed for solving four guillotine two-dimensional bin packing problems. The heuristics are based on the definition of a packing sequence for items and in a set of criteria for packing one item in a current partial solution. Several extensions are introduced to deal with issues pointed out by two furniture companies. Extensive computational results on instances from the literature and from the two furniture companies are reported and compared with optimal solutions, solutions from other five (meta)heuristics and, for a small set of instances, with the ones used in the companies.     

基于非线性规划的包装箱组托优化设计

目的以相同规格包装箱为研究对象,求解包装箱组托码放规则的最优化方案。方法以H2DPP模型为基础,采用块启发式算法,建立非线性规划模型,利用Lingo软件求解最优码放数量及各决策变量值。结果在托盘规格一定的情况下,包装箱规格越大,目标函数值越小;托盘长宽与包装箱长宽分别成整数比时,迭代的次数要远小于其他情况。结论利用Lingo软件求解非线性规划组托模型,用时不超过0.05 s,该方案更高效、准确地解决了流通过程中包装箱的组托问题,实现了组托方法的最优化。     

A flexible labour division approach to the polygon packing problem based on space allocation

This paper deals with the two-dimensional satellite module polygon packing problem. Based on the duality of material and space, it regards the polygon packing problem as a space allocation problem, which involves allocating the container space to the given polygons reasonably and efficiently. Ant colony’s labour division is essentially a kind of task allocation. Using this task allocation to achieve the space allocation in polygon packing problems, a flexible labour division approach (FLD) is proposed based on the response threshold model. According to the characteristics of space allocation in polygon packing problems, FLD designs three actions for polygons to occupy the container space. With the interaction between environmental stimulus and response threshold, each polygon takes an appropriate action to complete the space allocation and a layout that meets the requirements of satellite module layout is obtained. The results of standard test instances demonstrate the effectiveness of FLD when compared with self-organisation emergence algorithm. Moreover, experiments on the general polygon packing problem also show that FLD is competitive with other existing algorithms.     

抗氧化包装之无氧包装设计研究

目的为保护抗氧化要求比较苛刻的产品,研究一种更加可靠的抗氧化包装工艺。方法通过对现存抗氧化包装工艺的研究,对目前常用的空间除氧技术原理及效果进行分析,设计研究出一种新型抗氧化包装工艺——无氧包装工艺。结果首次定义了无氧包装的相关概念,划分了无氧包装的除氧级别,设计出了无氧包装的工艺流程以及无氧包装的实现方法。无氧包装工艺主要有密闭空间系统和除氧系统等,并且设计了密闭空间的结构和除氧系统的工艺原理。结论利用无氧包装工艺可克服传统抗氧化包装工艺中存在的问题,满足更加苛刻的抗氧化保护的要求,可使最终残氧量(体积分数)低于0.0001%,且残氧量可控。