求解集装箱装载问题的拟人算法

本文对长方体Pacing问题（即集装箱装载问题），提出了一种拟人型的启发式算法。不同于求解该问题的传统方法，本文利用最大穴度优先原则，使长方体的排列尽可能紧凑，从而使容器中装入画可能多的长方体。实验表明即使用于强异构型的困难算例，该算法也具有高效的求解结果。     

求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计，裁缝裁剪布料，玻璃切割等工作中提出了矩形和圆形装填问题，即把不同大小的矩形块和圆饼装入一个矩形容器中，以最大化容器的面积利用率为优化目标。对这一问题，可采用模拟退火，遗传算法等国际流行算法进行求解，但这些方法计算时间较长，计算结果的优度也不甚理想。利用人类的智慧和经验，提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％，平均计算时阊为8．38s。测试结果表明，算法对求解矩形和圆形装填问题是行之有效的。     

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

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

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

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

有卸货顺序约束的集装箱装载问题及算法研究

对有卸货顺序约束的三维集装箱问题进行了描述.基于禁忌规则,采用了求解该问题的模拟退火算法,设计了货物的摆放规则和序列生成方式.采用3种邻域,根据邻域的不同,构造了2种禁忌表.根据问题的特点,在模拟退火算法抽样过程中加入了禁忌规则.介绍了算法的原理,给出了具有代表性算例试验结果并且进行了分析.试验结果表明,提出的混合算法对有卸货顺序约束的集装箱三维装载问题的有效性.     

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

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

求解长方体Packing问题的高效算法

对典型的NP难度问题--著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语"金角银边草肚皮"的启发,并将它发展提高到"价值最高钻石穴",提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录.     

一种求解多维0-1背包问题的拟人算法

在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法,蚁群算法及其它一些启发式算法等求解算法。该文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法,对55个测试算例进行了实算测试,得到了其中54个算例的最优解。测试结果表明,用该文提出的拟人算法求解多维0-1背包问题,计算结果的优度高,计算时间短,是求解此问题的有效算法。     

遗传算法求解复杂集装箱装载问题方法研究

现场集装箱装载问题多为多目标、多约束优化的复杂问题.遗传算法本身的鲁棒性、并行搜索性以及在NP完全问题求解中的广泛应用,表明遗传算法是解决复杂集装箱装载问题的有效途径.探讨了遗传算法在求解这一复杂问题过程中的应用,给出了有效的编码形式和解码运算.算例求解结果显示出很好的效果.     

蚁群算法求解复杂集装箱装载问题

针对复杂集装箱装载问题(CLP),应用启发式信息与蚁群算法求解了最优装载方案。首先,建立了复杂集装箱装载问题的数学模型,利用蚁群算法对解空间的强搜索能力、潜在并行性及可扩充性,结合三空间分解策略将布局空间依次分割;然后,装入满足约束条件的最优货物块,完成不同大小三维矩形货物的装载布局。在此基础上,设计了基于空间划分策略的蚁群算法。最后以700件货物装入40尺(12.025m)高柜箱进行计算,结果表明该方法能提高集装箱的空间利用率,同时兼顾了多个装载约束条件,可应用性好。     

The optimum route problem by genetic algorithm for loading/unloading of yard crane

In recent years, the scale of container transportation and the size of vessels are becoming larger and larger; development of automatic container cranes becomes a necessity. As a key function of automatic control of unmanned cranes, the optimum route can minimize the cycle time by calculating the most efficient combination of horizontal and vertical motions of container loading/unloading. In this study, we have comprehensively studied various issues in the route planning in different fields. Later, the mathematical model based on the problem analysis of loading/unloading process was presented. Particularly, to solve the problem, an optimum route method based on genetic algorithm, which satisfies the criteria such as length, smooth degree and safety distance, was developed. Finally, the computational experiments testified the effectiveness of the algorithm and explored a new way to increase the efficiency of container loading/unloading process.     

A Genetic Algorithm for Solving the Container Loading Problem

The paper presents a genetic algorithm (GA) for the container loading problem. The main ideas of the approach are first to generate a set of disjunctive box towers and second to arrange the box towers on the floor of the container according to a given optimization criterion. The loading problem may include different practical constraints. The performance of the GA is demonstrated by a numerical test comparing the GA and several other procedures for the container loading problem.     

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.     

基于遗传算法的Unity3D装箱系统设计

针对物流配送的装箱问题,本文设计一款新型的基于遗传算法和Unity3D物理引擎软件系统。与传统的遗传算法相比。该系统可以方便快捷地计算出基于多条件的合理装箱方案,即如何摆放货物才能最大限度地利用集装箱空间。该系统应用Unity3D添加的手动装载功能和装箱方案导出功能,通过JS脚本设计物体的运动及基本操作过程。仿真结果表明,该系统既能高效地计算出一套完整的装箱方案,又能通过人为的经验加以调整,从而实现更好的装箱方案。     

Dynamic rolling strategy for multi-vessel quay crane scheduling

This paper focuses on the container loading and unloading problem with dynamic ship arrival times. Using a determined berth plan, in combination with the reality of a container terminal production scheduling environment, this paper proposes a scheduling method for quay cranes that can be used for multiple vessels in a container terminal, based on a dynamic rolling-horizon strategy. The goal of this method is to minimize the operation time of all ships at port and obtain operation equilibrium of quay cranes by establishing a mathematical model and using a genetic algorithm to solve the model. Numerical simulations are applied to calculate the optimal loading and unloading order and the completion time of container tasks on a ship. By comparing this result with the traditional method of quay crane loading and unloading, the paper verifies that the quay crane scheduling method for multiple vessels based on a dynamic rolling-horizon strategy can provide a positive contribution to improve the efficiency of container terminal quay crane loading and unloading and reduce resource wastage.     

集装箱轻重货物混合平衡装载模型与算法

负载平衡是集装箱装运过程中的基本约束,轻重货物混合装载时较难满足,如何精确量化负载平衡、实现轻重货物混合平衡装载亟待研究。以集装箱轻重货物混合平衡装载问题为研究对象,构造负载平衡函数,综合考虑负载平衡、位置、重量和旋转等约束,建立轻重货物混合平衡装载模型;根据对负载平衡的影响程度,将待装货物分类组成轻重货物单元,在采用评估函数和中心骨架等启发式方法分类处理的基础上,设计轻重货物混合平衡装载算法。3 000个算例表明：所提出的模型和算法能够在保证集装箱容积利用率不低于90%的同时使负载平衡约束满足率达96.07%以上。     

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

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

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.