多约束三维装箱问题的混合遗传算法

三维装箱问题提出至今已有很多研究成果,各种启发式算法配合遗传算法、蚁群算法和模拟退火算法的设计层出不穷。而针对于三维装箱问题的各种约束,虽然各自有相应的处理方法,但却没有一种方法可以整合各种约束条件,这是因为启发式算法往往容易满足部分约束却很难满足所有约束的特点。在前人研究的基础上,针对各种遗传算法的约束条件,设计可以相互组合的解决各种约束条件的算法,通过对这些算法规则组合,可以解决各种约束条件下的三维装箱问题。     

解决约束三维装箱问题的混合粒子群算法

针对约束条件下三维装箱问题复杂性,为提高装箱利用率,本文提出了混合粒子群算法,该算法采用BF启发式算法配合改进的自适应权重粒子群算法实现。通过仿真试验,结果表明该混合粒子群算法对解决部分约束条件下装箱问题较之传统研究遗传算法利用率和准确率更高,具有不同程度的可行性。     

多约束三维装箱问题的研究综述

至今三维装箱已经诞生出了很多优秀的研究结果,这其中包含有启发式算法,遗传算法,蚁群算法,以及模拟退火算法等解决方法。近几年来随着物流行业的飞速发展,成本控制在物流行业中显得尤为重要,因此,针对三维装箱这一类典型NP-complete问题有了更高的要求。在此,对三位装箱近几年来几种典型的研究算法进行了相应的详细介绍,并通过对各种算法进行比对分析,总结了多约束三维装箱过程现阶段所存在的一些问题,最后展望了该问题的发展方向。     

一种求解三维集装箱装箱问题的混合遗传算法

在遗传算法的基础上结合传统启发式装箱算法,设计了一个混合遗传算法,该算法既继承了遗传算法的全局搜索好的优点,也克服了遗传算法局部搜索能力差的缺点,能够较好地解决集装箱这类多目标多约束的空间三维分布的问题。     

面向梯形箱子的三维装箱问题算法研究

针对梯形箱子的三维装箱问题,提出了一种基于空间分割的构造性启发式算法,根据梯形箱子三维装箱问题的特点,设计了相应的空间分割策略、空间合并策略与空间重组策略,在此基础上加入遗传算法,提高算法局部与全局搜索能力。实验结果表明,该算法能有效处理梯形箱子三维装箱问题。     

三维装箱问题的偏随机密钥混合遗传算法

考虑实践约束的三维装箱问题属于复杂的组合优化问题,具有典型NP难问题的特点。针对一般遗传算法求解装箱问题易陷入局部最优的缺点,提出使用偏随机密钥遗传算法进行装载序列搜索,结合基于极点的启发式方法实现货物的优化布置,进而通过部分装载物品的位移来改善整体重心分布。经过实例运算和分析,证明提出的方法能快速制定货物优化布置方案,达到装载工具高效利用及货物安全运输的要求。     

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

集装箱装载问题的一种DNA遗传算法

三维集装箱装载是一个复杂的组合优化问题,约束条件多,属于NP完全问题,求解难度大.在考虑方向性约束和稳定性约束的情况下,提出了一种DNA遗传算法（DNA-GA）,给出了有效的编码和解码方法。实例计算结果表明,利用DNA-GA解决装箱问题是行之有效的一种方法,对推广DNA计算在求解NP难解问题中的应用具有一定的意义。     

三阶段优化算法求解带三维装载约束的MDVRP北大核心CSCD

对带三维装载约束的多车场车辆路径问题,以最小化车辆行驶总里程为优化目标,建立问题模型,并提出一种三阶段优化算法进行求解。第一阶段设计带循环平衡的K-medoids聚类算法,将原问题分解成多个带三维装载约束限制的车辆路径子问题。第二阶段提出一种双层结构的超启发式蚁群算法用于求解各子问题,以确定各车辆的配送路径。在该算法中,低层设计9种启发式操作,并将其所构成的排列作为高层个体;同时,高层采用蚁群算法更新高层个体,以引导算法搜索方向。第三阶段以第二阶段所得阶段解作为初始解,设计组合启发式装箱算法对带容积约束的装箱过程进行优化,进而将第二、三阶段确定的解合并为原问题的解。最后,仿真实验和算法比较验证了所提算法的有效性。     

求解入库堆垛问题的改进约束满足算法

入库堆垛问题普遍存在于堆场作业管理中,是在货物数目和出库顺序已知的前提下,要求较长（重）的货物置于较短（轻）的货物下方,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的A形装箱问题,并建立了约束满足模型,设计了嵌入经典装箱启发式的约束满足求解算法。实验表明,该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。     

Automating the packing heuristic design process with genetic programming

The literature shows that one-, two-, and three-dimensional bin packing and knapsack packing are difficult problems in operational research. Many techniques, including exact, heuristic, and metaheuristic approaches, have been investigated to solve these problems and it is often not clear which method to use when presented with a new instance. This paper presents an approach which is motivated by the goal of building computer systems which can design heuristic methods. The overall aim is to explore the possibilities for automating the heuristic design process. We present a genetic programming system to automatically generate a good quality heuristic for each instance. It is not necessary to change the methodology depending on the problem type (one-, two-, or three-dimensional knapsack and bin packing problems), and it therefore has a level of generality unmatched by other systems in the literature. We carry out an extensive suite of experiments and compare with the best human designed heuristics in the literature. Note that our heuristic design methodology uses the same parameters for all the experiments. The contribution of this paper is to present a more general packing methodology than those currently available, and to show that, by using this methodology, it is possible for a computer system to design heuristics which are competitive with the human designed heuristics from the literature. This represents the first packing algorithm in the literature able to claim human competitive results in such a wide variety of packing domains.     

A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems

The three-dimensional multiple bin-size bin packing problem, MBSBPP, is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considered for each phase of the algorithm and the good performance of our algorithm compared with previously reported results.     

Multi-dimensional bin packing problems with guillotine constraints

The problem addressed in this paper is the decision problem of determining if a set of multi-dimensional rectangular boxes can be orthogonally packed into a rectangular bin while satisfying the requirement that the packing should be guillotine cuttable. That is, there should exist a series of face parallel straight cuts that can recursively cut the bin into pieces so that each piece contains a box and no box has been intersected by a cut. The unrestricted problem is known to be NP-hard. In this paper we present a generalization of a constructive algorithm for the multi-dimensional bin packing problem, with and without the guillotine constraint, based on constraint programming.     

A global search framework for practical three-dimensional packing with variable carton orientations

This article aims to tackle a practical three-dimensional packing problem, where a number of cartons of diverse sizes are to be packed into a bin with fixed length and width but open height. Each carton is allowed to be packed in any one of the six orientations, and the carton edges are parallel to the bin edges. The allowance of variable carton orientations exponentially increases the solution space and makes the problem very challenging to solve. This study first elaborately devises the packing procedure, which converts an arbitrary sequence of cartons into a compact packing solution and subsequently develops an improved genetic algorithm (IGA) to evolve a set of solutions. Moreover, a novel global search framework (GSF), utilizing the concept of evolutionary gradient, is proposed to further improve the solution quality. Numerical experiments indicate that IGA provides faster and better results and GSF demonstrates its superior performance, especially in solving relative large-size and heterogeneous instances. Applying the proposed algorithms to some benchmarking cases of the three-dimensional strip packing problem also indicates that the algorithms are robust and effective compared to existing methods in the literature.     

Improved integer programming models for simple assembly line balancing and related problems

We propose a stronger formulation of the precedence constraints and the station limits for the simple assembly line balancing problem. The linear relaxation of the improved integer program theoretically dominates all previous formulations using impulse variables, and produces solutions of significantly better quality in practice. The improved formulation can be used to strengthen related problems with similar restrictions. We demonstrate their effectiveness on the U‐shaped assembly line balancing problem and on the bin packing problem with precedence constraints.     

Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms

In this paper we discuss lower bounds for the asymptotic worst case ratio of on-line algorithms for different kind of bin packing problems. Recently, Galambos and Frenk gave a simple proof of the 1.536 ... lower bound for the 1-dimensional bin packing problem. Following their ideas, we present a general technique that can be used to derive lower bounds for other bin packing problems as well. We apply this technique to prove new lower bounds for the 2-dimensional (1.802...) and 3-dimensional (1.974...) bin packing problem.     

Genetic algorithm for robot selection and work station assignment problem

In this paper, we introduce Genetic Algorithm (GA) for optimal Robot Selection and Work station Assignment (RS/WA) problem for a CIM system. In particular, the RS/WA problem can be considered as a generalized two-dimensional multi-type bin packing problem that has been shown to be NP-hard. A multichromosome GA combined with heuristic bin packing algorithm is implemented for solving the problem and the effeciency of proposed method is shown by numerical example. Our approach may be applicable to other this kind of bin packing problems.     

Efficient lower bounds and heuristics for the variable cost and size bin packing problem

We consider the variable cost and size bin packing problem, a generalization of the well-known bin packing problem, where a set of items must be packed into a set of heterogeneous bins characterized by possibly different volumes and fixed selection costs. The objective of the problem is to select bins to pack all items at minimum total bin-selection cost. The paper introduces lower bounds and heuristics for the problem, the latter integrating lower and upper bound techniques. Extensive numerical tests conducted on instances with up to 1000 items show the effectiveness of these methods in terms of computational effort and solution quality. We also provide a systematic numerical analysis of the impact on solution quality of the bin selection costs and the correlations between these and the bin volumes. The results show that these correlations matter and that solution methods that are un-biased toward particular correlation values perform better.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.