详情

原文传递圆柱形物体装载问题的启发式递归算法

论文题名：	圆柱形物体装载问题的启发式递归算法
关键词：	圆柱形物体;装载问题;启发式递归算法;背包问题;集装箱装载系统;托盘装载
摘要：	装载问题通常指将若干小物体以最佳方式组合并装入一个大的空间从而使得空间的利用率最大，是经典的三维装箱问题和背包问题的组合形式。装载问题涉及多学科、多领域的知识，属于复杂的组合优化问题，生产实践中广泛地出现在铁路货车车厢装载、汽车车厢装载、轮船装载、集装箱装载等场合。提高散集装箱装载的质量、效率和可靠性，对集装箱安全、高效运输具有重大意义。当前有关集装箱装载系统的研究和设计主要集中在用计算机解决装载计算问题。三维填充问题分为单元装箱问题、集装箱装载问题和托盘装载问题等。在实际中通常需要考虑：方向、承载能力、稳定性等限制。由于三维箱体布局为NP 完全问题，随着布局箱体增多，解空间爆增，计算效率较低。将小箱装到大箱中的文献虽然较多，但将小箱尺寸的设计和装载到大箱联系起来的文献就很少见了。在托盘装载中，物体通常为长方体，其边平行于托盘的边，物体之间互相不重叠，而且物体装入的高度不能超过托盘限定高度，使得装载利用率最大。对于生产商托盘装载，大多数文献都是将所有待排放物体沿着同一朝向放置，这样可以实现按层放置，每一层相当于二维排样中的放置算法，实际上将问题转换为二维平面矩形排放问题，而且都是同一尺寸的物体，约束条件比较简单，所达到的优化程度比较高。批发商托盘装载所装入物体的尺寸不相等，实现起来比较难。本文根据当前物流行业对解决复杂集装箱装载问题的需求，在充分了解各类装箱问题的基础上，研究了圆柱形物体的托盘装载问题：第一阶段，先将同尺寸圆柱型物品竖直装入长方体小箱子内；第二阶段，将小箱子分层放入托盘。本文提出一种简易有效且便于装载的递归启发式算法。第一阶段为圆柱形物体的排放问题。同尺寸圆形的排放存在多种方式，多采用递归剪切方式，适合于冲裁下料问题，由于装载问题不同于工业生产中的圆形片下料切割，所以传统的剪切割方法虽然在某些问题上能够取得较好的效果，但是不适用于装载问题。基于对本文研究问题的分析，采用圆形的启发式规范排放，即排放时使相邻行圆筒的夹角为常数，无论是人工还是自动排放都容易得到。对于各种可能的小箱尺寸，用规范排放确定物品在小箱内的布局，使所装物品尽可能多。第二阶段将矩形小箱子装入托盘中。将圆筒规范排放到箱子之后，要考虑的是：将箱子排放到托盘或分层排放到集装箱中，使装载利用率最大。这个问题可以看成是相同尺寸矩形的最优排放。即在一块板材中排入若干尺寸相同的矩形毛坯。同尺寸矩形排放问题通常采用规范多级方式，可以看作是将已排好的部分矩形区域的上边界水平摆放一行，或者沿着右边界竖直摆放一行。本文采用动态规划算法实现同尺寸矩形的规范方式，通过设置成本控制参数，找到级数最少的最优规范方式，使得装卸过程简单易操作。然后，研究和开发了一个实用的圆柱形物体装载排样系统。在完成算法设计的基础上，规划和设计了排样系统的基本功能模块，开发了一个基于启发式递归算法的优化排样系统。通过大量实验测试，从装载利用率和排样时间两方面验证了该系统的算法的可行性。通过对级数最大和最小情况的对比，说明本算法在实际应用中能简化装载过程，降低装载成本。计算结果显示，运用本文算法可综合考虑装载利用率和装载方案的复杂程度，取得较好的效果。最后，论文在对己完成的工作进行了总结，提出了需要进一步改进的工作。
作者：	杨莹
专业：	计算机应用技术
导师：	崔耀东
授予学位：	硕士
授予学位单位：	广西师范大学
学位年度：	2008
正文语种：	中文